Ubuntu moon over water
I made a wallpaper for my Ubuntu 12.04 installation today.
Pybrain
Note to self: Learn more about Pybrain and how you can use it to make a computer opponent for your Go Fish game.
Thinking about Go Fish with Python
Today I’m thinking about the Go Fish program I want to write in Python. Writing code that follows the rules of the game seems fairly straightforward. But there are a few advances I’d like to make with this program from my last program that made the computer play War against itself.
First, I want to make it where a human player is playing against the computer. Sure, watching a computer play against itself is neat for a few seconds, but it gets boring if there is no interaction. Achieving this shouldn’t be too hard. I should be able to make it print a menu of all the cards in your hand, then you just choose the corresponding menu item for the card you want to ask your opponent for.
Second, I will have to make the computer adhere to a strategy. Instead of just playing the top card from its hand, like it does in War, the computer also will have to choose what to ask for from you. Maybe I could write it so it just goes through its list of cards and asks for each consecutive card in its hand. I also want to make it so if the computer draws something you have recently asked for, it will know to ask you for that card. Perhaps I could create a difficulty setting so the harder the opponent, the longer it remembers what cards you’ve asked for.
It seems kind of daunting, but I know that all I have to do is break it down into smaller pieces, and only work on them one at a time.
Introduction to writing card games in Python
I want to make card games with Python, so I think about how to simulate a deck of cards. Some of the properties of a deck are such: It has 52 unique cards. Each card consists of a rank: 2 through 10 and Jack, Queen, King, Ace; and a suit: Clubs, Diamonds, Hearts or Spades. Cards move around from the deck to a player’s hand, to being “in play” on the table, or to the discard pile, or perhaps any number of places, depending on the rules of the game you are playing with them. For the sake of sanity, a card cannot be in more than one place at one time.
So creating a shuffled deck of cards is very simple. If you think of the values of Jack, Queen, King and Ace as 11, 12, 13, and 14, you can implement a deck with just a few lines of code in a function:
import random
def shuffled_deck():
deck = []
for suit in ['Clubs', 'Diamonds', 'Hearts', 'Spades']:
for num in xrange(2, 15):
deck.append([num, suit])
random.shuffle(deck)
return deckNow you can do all kinds of operations on this list of cards you’ve created, and that’s where you start getting into the rules of whatever game you’re playing. I decided to start out with the simplest game I could think of: War. But before I get into that, I want to make the cards a little more user friendly. Right now the cards have a number and a suit. But say you get the 12 of Clubs. That’s not really a card. It should be called the Queen of Clubs. I wrote another little function that will return the proper name for a card when passed the value of its rank:
def card_name(card):
if card == 11:
return 'Jack'
elif card == 12:
return 'Queen'
elif card == 13:
return 'King'
elif card == 14:
return 'Ace'
else:
return str(card)Now I want to make the computer play War against itself. You might play War differently than this, but here are the rules I made it play by:
- The deck is shuffled and each player is dealt a hand of 26 cards.
- Each player plays the first card from their hand. Whichever card has a higher rank wins, and the player takes both cards and places them in his or her “won” pile.
- If the two cards in play are of the same rank, those remain on the table and each player reveals another card. Once a player wins a round, the tying cards from the previous round (or rounds) are all won by the winner of the most recent round.
- When all cards are depleted from a player’s hand, the cards in that player’s “won” pile are shuffled and then become the player’s new hand, and play continues.
- The game is won when one player has taken all the cards. If the final round is a tie, no one wins that round and the winner of the game is determined by who has the most cards.
So with that, here is the full code for War:
import random
def shuffled_deck():
deck = []
for suit in ['Clubs', 'Diamonds', 'Hearts', 'Spades']:
for num in xrange(2, 15):
deck.append([num, suit])
random.shuffle(deck)
return deck
def card_name(card):
if card == 11:
return 'Jack'
elif card == 12:
return 'Queen'
elif card == 13:
return 'King'
elif card == 14:
return 'Ace'
else:
return str(card)
def deal_cards(deck):
return deck[::2], deck[1::2]
def check_cards(player1, player2):
if player1 > player2:
return 'player1'
elif player1 < player2:
return 'player2'
else:
return 'tied'
def replenish(wonpile):
random.shuffle(wonpile)
return wonpile
deck = shuffled_deck()
hand1, hand2 = deal_cards(deck)
ontable = []
round = 0
hand1won = []
hand2won = []
while len(hand1) > 0 and len(hand2) > 0:
round += 1
print "Round %d" % round
card1 = hand1.pop(0)
card2 = hand2.pop(0)
ontable.extend([card1, card2])
print "Player One plays the %s of %s." % (card_name(card1[0]), card1[1])
print "Player Two plays the %s of %s." % (card_name(card2[0]), card2[1])
play_winner = check_cards(card1[0], card2[0])
if play_winner == 'player1':
print "Player One wins the round."
hand1won.extend(ontable)
ontable = []
elif play_winner == 'player2':
print "Player Two wins the round."
hand2won.extend(ontable)
ontable = []
elif play_winner == 'tied':
print "The players tie for this round and the cards remain on the table."
print "The score is now Player One: %s, Player Two: %s" % (len(hand1won)+len(hand1), len(hand2won)+len(hand2))
if len(hand1) == 0 and len(hand1won) > 0:
print "Player One replenishes."
hand1 = replenish(hand1won)
hand1won = []
if len(hand2) == 0 and len(hand2won) > 0:
print "Player Two replenishes."
hand2 = replenish(hand2won)
hand2won = []
if len(hand1) > len(hand2):
print "Player One wins the game!"
elif len(hand1) < len(hand2):
print "Player Two wins the game!"I think I will try a game of Go Fish next.
A PyPy experiment
I really have no idea what PyPy is. All I know is that it is an implementation of Python written in Python (?) and that it runs faster than Python. For example, I tested the Monty Hall Problem that I wrote recently, and timed them. Here is the result:
[daniel@TimeMachine Python]$ time python2 monty_hall_switch.py All choices were switched. Wins: 66679 Losses: 33321 real 0m1.265s user 0m1.243s sys 0m0.023s [daniel@TimeMachine Python]$ time pypy monty_hall_switch.py All choices were switched. Wins: 66853 Losses: 33147 real 0m0.594s user 0m0.477s sys 0m0.070s
So PyPy ran the program more than twice as fast as Python. Pretty neat, huh?
Calculating and testing probability with Python
“Please do not be alarmed by anything you see or hear around you … We are now cruising at a level of two to the power of two hundred and seventy-six thousand to one against and falling, and we will be restoring normality just as soon as we are sure what is normal anyway. Thank you …”
Inside a bag are 9 coins. 4 of these coins are fair, in that they have a 50% chance of coming up heads. The other 5 coins in the bag are unfair coins. When they are flipped, they have a 65% chance of coming up heads. What are the chances, expressed as a percentage, that when drawing a random coin from the bag and flipping it 3 times, it will come up heads all 3 times?
Finding the answer is slightly tedious, but not difficult. First you have to consider what would happen if you randomly chose a fair coin from the bag, then you have to consider what would happen if you randomly chose an unfair coin. Add those two possibilities together, and there’s your answer.
Fair coin
First, let’s look at what happens when you draw a fair coin from the bag and flip it three times. The chances of one flip coming up heads are 50%. Twice would be 50% squared, and three times would be 50% cubed. You can express this as .5^3, or .125, or 12.5%. Since only 4 of the 9 coins in the bag are fair, you need to multiply .125 by 4/9. That puts the chances of pulling a fair coin and having it come up heads on all three flips at about 5.56%.
Unfair coin
The way to find the chances of pulling an unfair coin and getting three heads is the same. .65^3 = about 27.46%, and since there are 5 unfair coins from 9 total, .2746 * 5/9 = about .1526, or 15.26%.
Add them up
All that’s left now is to add the chances of the two possibilities together to get the total chances of pulling any coin from the bag and getting three heads. 5.56% + 15.26% = 20.82%. The equation should look like this:
probability = (.50 ^ 3 * 4 / 9) + (.65 ^ 3 * 5 / 9)
And when you do it that way, you end up with about 20.81% instead of 20.82%, because you’re only rounding the final answer instead of rounding the answers to intermediate steps.
The proof
So I wanted to test this out and see what Python would do when simulating such a scenario 100,000 times. Here is the code I came up with:
# coinflips.py
# a program to test the concept presented at
# http://www.khanacademy.org/math/probability/v/dependent-probability-example-1
# by Daniel Veazey <danielveazey@gmail.com>
import random
# what happens when you flip a coin a number of times, depending on
# whether the coin is fair or unfair (weighted)
# a pseudo-random number is genereated from 1 to 100
# and compared to what its odds of landing on heads are
# return True for heads if result is below odds
# or return False for tails if the result is above the odds
def flipping(how_many_flips, odds):
no_of_heads = 0
for flip in range(0, how_many_flips):
flip_result = random.randint(1, 100)
if flip_result <= odds:
no_of_heads += 1
return no_of_heads == how_many_flips
# choosing a coin pseudo-randomly
# pseudo-random integer is generated from the number of coins available
# and compared to the number of fair coins available
# True = unfair coin; False = fair coin
def choosing_coin(how_many_fair, how_many_unfair):
total_coins = how_many_fair + how_many_unfair
chosen_coin = random.randint(1, total_coins)
return chosen_coin > how_many_fair
# ask user for parameters of test
print "Testing probability of fair and unfair coin flips when a random coin is pulled from a bag.\n"
fair_coins = float(raw_input("How many fair coins do you wish to put in the bag? "))
unfair_coins = float(raw_input("How many unfair coins do you wish to put in the bag? "))
unfair_odds = float(raw_input("For the unfair coins, what percent chance does one flip have that it will come up heads? "))
number_of_flips = float(raw_input("How many times do you want to flip the coin chosen from the bag? "))
# tell the user what the probability is
print "\nThe chances of getting", int(number_of_flips), "heads in a row are about", float("%.4f" % ((((unfair_odds / 100.00) ** number_of_flips) * unfair_coins / (fair_coins + unfair_coins)) + ((.50 ** number_of_flips) * fair_coins / (fair_coins + unfair_coins))))*100.00, "percent."
print "I am now running the simulation 100,000 times. This may take a few seconds.\n"
# the simulation: success is the number of times the flips came up all heads
success = 0
for x in range(100000):
# choose a coin
if choosing_coin(fair_coins, unfair_coins) == True:
# flipping an unfair coin
if flipping(int(number_of_flips), (unfair_odds)) == True:
success += 1
# flipping a fair coin
else:
if flipping(int(number_of_flips), 50) == True:
success += 1
print "Simulation complete. All heads came up", success, "out of 100,000 times."And here is what Python told me:
Testing probability of fair and unfair coin flips when a random coin is pulled from a bag. How many fair coins do you wish to put in the bag? 4 How many unfair coins do you wish to put in the bag? 5 For the unfair coins, what percent chance does one flip have that it will come up heads? 65 How many times do you want to flip the coin chosen from the bag? 3 The chances of getting 3 heads in a row are about 20.81 percent. I am now running the simulation 100,000 times. This may take a few seconds. Simulation complete. All heads came up 20621 out of 100,000 times.
How it works
After importing the random module, the first function I defined is flipping(how_many_flips, odds). It generates a pseudo-random number and compares it to the odds that are passed to the function. If the number comes in under the odds, then it adds one to the variable no_of_heads. It does this again as many times as necessary to meet the value of how_many_flips were passed to it. Once it has done that, it returns True if no_of_heads is equal to how_many_flips. Otherwise it returns False.
The second function defined is choosing_coin(how_many_fair, how_many_unfair). Another pseudo-random number is generated, between 1 and the total number of coins that are available. If the random number is greater than how_many_fair, the function returns True to tell that an unfair coin was chosen. Otherwise it returns False.
Now Python asks for some data from the user. It wants to know how many fair_coins and unfair_coins there are, how unfair the unfair coins are (unfair_odds), and number_of_flips that the user wants it to do on the chosen coin.
All these variables are assigned as floating point variables, but there is room for improvement here. It would be better if I had made them decimals, but it seems that whenever I try to use decimals in Python, instead of getting what I’m expecting, I get stuff like this:
>>> decimal.getcontext().prec = 2
>>> decimal.Decimal(4.56)
Decimal('4.55999999999999960920149533194489777088165283203125')
>>> x = decimal.Decimal(4.56)
>>> x
Decimal('4.55999999999999960920149533194489777088165283203125')
>>> y = decimal.Decimal(2.3)
>>> y
Decimal('2.29999999999999982236431605997495353221893310546875')
>>> x + y
Decimal('6.9')
>>>
So I’m leaving it as floating point variables right now. I need to read more about decimals in Python, and once I figure out how to use them correctly, I might change those variables to decimals if I haven’t moved on to bigger and better things. Now back to the program.
After getting the values from the user, Python calculates the probability using the previously mentioned equation. Then it runs a simulation using those numbers 100,000 times. It calls the choosing_coin() function, and if it is returned True for an unfair coin, it calls the flipping() function and passes the unfair_odds to it. If choosing_coin() returns False, the program calls flipping() with 50 as the odds. When it passes number_of_flips to the flipping() function, it passes it as an integer because a for loop requires the values in the range to be integers, and it would encounter an error if it tried to use a floating point variable as one of the range’s values.
So if flipping() returns True for either using the unfair_odds or 50 for fair odds, Python keeps track of it by adding 1 to the value of the variable named success. Finally, it tells the results of its tests. It’s usually very close to its corresponding probability.
Recommended reading
The Monty Hall Problem
Have you ever heard of the Monty Hall Problem? My friend Korgan, who runs the blog Better Than Granite, told me about it. It goes like this:
You are on the show Let’s Make a Deal, and you are presented with three doors. Behind one door is a car. Behind the other two doors are goats. You are asked to choose a door, but at this point, it remains closed. Monty Hall (the host of the show) knows what is behind each door, and opens up one of the other two doors to reveal a goat. Now you are given the option of switching to the other unopened door or staying with your original choice. What should you do?
Think about it for a minute.
When you first look at the problem, it seems like it doesn’t matter if you switch or not, because behind one of the remaining doors is the car and the other door, a goat. So you have a 50/50 chance of winning. But that’s wrong. Let’s look at the probabilities of the two strategies, not switching and switching:
Not switching
When you first choose a door, you have about a 33.3% chance of choosing the car, and about a 66.7% chance of choosing a goat. Now if you decide not to switch to the other door, it doesn’t matter which door Monty Hall opens, and your chances of winning the car remain at about 33.3%, and the chance that you’ve chosen a goat remain at about 66.7%.
Switching
Now let’s look at what happens when you decide to switch doors. If you chose the correct door the first time (about a 33.3% chance), and Monty Hall opens one of the other doors to reveal a goat, then you decide to switch, you’ll obviously get the other goat. So however many times you play this game, roughly 33.3% of the time you will end up with a goat if you always switch doors. But say you chose a door with a goat behind it first (about a 66.7% chance), once Monty reveals the other goat, and you always switch, you will end up with the car. So about 66.7% of the times you play this game and choose to switch, you will win the car.
The proof
It took me a little while to wrap my head around it, and since it was not very intuitive to me, I decided to write a Python program to test it. I wrote it so it would run through the game 100,000 times and report the results. It pseudo-randomly places a car behind one of the three doors and then chooses a door. One of the remaining doors with a goat is revealed and then the program checks to see if switching is favorable. It does all this without any visual output, but rather just tallies up the wins and losses and reports those. I was very pleased that it only took 22 lines of code. Here it is:
import random
def populate_doors(): # put a car behind one door
door=['goat', 'goat', 'goat']
door[random.randint(0,2)]='car'
return door
wins = 0
losses = 0
# playing the game 100,000 times:
for x in range(100000):
doors=populate_doors()
first_choice=random.randint(0,2) # choose a random door
for y in range(3): # reveal first losing, unchosen door
if doors[y] != 'car' and y != first_choice:
doors[y] = 'out'
break
if doors[first_choice] == 'car':
losses = losses + 1 # contestant switched to losing door
else:
wins = wins + 1 # contestant switched to winning door
print "All choices were switched."
print "Wins:", wins
print "Losses:", lossesFeel free to test it out. You’ll find that roughly 66.7% of the time, the computer wins using this strategy. Korgan wrote a similar program in C. Here is his code:
//evidence of the monty hall solution.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define GAMES 3000000
int main(void){
unsigned i, j, k, choice, winsbyswitch=0, door[3];
srand(time(NULL)); //initialize random seed.
for(i=0; i<GAMES; i++){
door[0] = (!(rand()%2)) ? 1: 0; //give door 1 either a car or a goat randomly.
if(door[0]) door[1]=door[2]=0; //if 1st door has car, give other doors goats.
else{ door[1] = (!(rand()%2)) ? 1: 0; door[2] = (!door[1]) ? 1: 0; } //else, give 2nd door car or goat, give 3rd door what's left.
choice = rand()%3; //choose a random door.
//if the next door has a goat, and the following door has a car, or vice versa, you'd win if you switch.
if(((!(door[((choice+1)%3)])) && (door[((choice+2)%3)])) || (!(door[((choice+2)%3)]) && (door[((choice+1)%3)]))) winsbyswitch++;
}
printf("\nAfter %u games, I won %u by switching. That is %f%%. ", GAMES, winsbyswitch, (float)winsbyswitch*100.0/(float)i);
}Changing stuff in Geany
I use Geany for my IDE. It’s pretty good for what I do. I’m no hardcore coder. I just use Python for experimenting and learning.
It had been a little while since I did anything with Python. In fact, the last time I used it was before I installed Arch. I got a little bit of coding fever and wanted to refresh my memory. I was thinking about rewriting my Sudoku solver program, using functions instead of the hot mess that I left it in a few months ago.
But I was running into a little problem. When I would press F5 to run my program, the terminal that popped up gave me this error message:
./geany_run_script.sh: line 5: python: command not found ------------------ (program exited with code: 127) Press return to continue
“Well that’s no good,” I thought. It turns out that Geany was trying to run Python with the command “python,” which would be fine if “python” were the command it needed to run. But since I am using Arch, “python” is for the bleeding edge Python 3, whereas the more commonly used Python 2.7 is called with “python2.” Since I didn’t want to use Python 3 and didn’t have it installed, I needed to change the command to “python2″ so Geany wouldn’t give me these error messages anymore. Sure, I could just save the program and then open a terminal and type “python2 filename.py,” but that wouldn’t be a good solution because it would be a hassle.
I checked every preference menu I could find in Geany, but I couldn’t find a setting to change what it pointed to for running Python (or any other) programs. Then I looked all over the place for geany_run_script.sh, but I couldn’t find it anywhere, either. I did, however find some configuration files in /usr/share/geany. Particularly, I found /usr/share/geany/filetypes.python. That directory also had filetypes for all the languages that Geany supports. At the very end of filetypes.python were these lines:
[build_settings] # %f will be replaced by the complete filename # %e will be replaced by the filename without extension # (use only one of it at one time) compiler=python -m py_compile "%f" run_cmd=python "%f"
Changing that last line took care of the problem:
run_cmd=python2 "%f"
So Geany stopped giving me error messages when I tried to run my Python programs and I was happy.
I still have a long way to go on rewriting my Sudoku solver, but I will post it here when it is updated. Keep an eye out.