Homework 3: Penny Matching

Homework 3: Penny Matching

Bart Massey 2013-02-12

The game of Penny Matching was one of the first games programmed for computer play. Penny Matching is kind of a cut-down version (!) of Rock-Scissors-Paper. The rules for Penny Matching in this assignment are as follows:

  • The game lasts 10 rounds.

  • In each round:

    • The human player selects either heads or tails, but does not tell the computer player.

    • The computer player guesses whether the human selected heads or tails.

    • The human player tells the computer player what they (the human) picked.

    • If the computer was right, it wins a penny. Otherwise the human wins a penny.

A transcript of my Penny Matching program playing a game is below. Your game should look as much like mine as reasonably possible.

I wish your assignment could be to try to build a computer player that will beat you. This seems too hard, so instead let's build a computer player that might beat a three-year-old.

The plan for the computer player is simple. The computer can't always play the same thing, and it should play depending on what the human has done up until now. What we will do is make the computer more likely to play heads when the human has been playing heads more, and more likely to play tails more when the human has been playing tails more.

In fact, what we will do is this: On the first and second turn, have the computer play randomly (equal probability of predicting heads or tails). On the rest of the turns, have the computer predict heads with probability equal to

number of times the human has chosen heads / total number of turns

For example, if the human has so far chosen TTHHTTT, the probability of the computer choosing H should be 2 / 7. One can get this probability easily using randrange() as described in the book:

 k = randrange(7) if k < 2: # pick heads else: # pick tails

(Note the use of less-than here. This is because randrange(n) returns a number between 0 and n-1 inclusive. It takes some thought to see that this code is right.)

There are some readings about computer Penny Matching linked on the course Moodle page, if you're curious. Have fun!

Assignment Summary: Write a program called penny.py that is our Penny Matching game and computer player. Turn it in on the Moodle.

Bonus Version (not required): Another predictor that is useful is whether the human player often changes their answer from turn to turn. (Humans tend to do this too much.) Make a new version of your program that predicts that the human will give a different answer than last time with probability equal to the fraction of times that they have given different answers in the past.

Extra Bonus Version (not required): Combining predictors can give better prediction. Make a new version of your program that keeps track of both the "frequency of heads" and "frequency of changes" predictors, and uses whichever one seems to be "doing better" right now to make its current pick. Here, "doing better" means something like "would have predicted the answer correctly in the past with higher probability."

 Round 1 Secretly choose H or T. Hit <enter> to continue. asdjfk; I predict you picked 'H'. What did you pick (enter 'H' or 'T')? q I need you to enter 'H' or 'T'. Please try again. What did you pick (enter 'H' or 'T')? h One penny for me! Round 2 Secretly choose H or T. Hit <enter> to continue. I predict you picked 'H'. What did you pick (enter 'H' or 'T')? T One penny for you. Round 3 Secretly choose H or T. Hit <enter> to continue. I predict you picked 'T'. What did you pick (enter 'H' or 'T')? T One penny for me! Round 4 Secretly choose H or T. Hit <enter> to continue. I predict you picked 'T'. What did you pick (enter 'H' or 'T')? H One penny for you. Round 5 Secretly choose H or T. Hit <enter> to continue. I predict you picked 'T'. What did you pick (enter 'H' or 'T')? H One penny for you. Round 6 Secretly choose H or T. Hit <enter> to continue. I predict you picked 'H'. What did you pick (enter 'H' or 'T')? H One penny for me! Round 7 Secretly choose H or T. Hit <enter> to continue. I predict you picked 'T'. What did you pick (enter 'H' or 'T')? H One penny for you. Round 8 Secretly choose H or T. Hit <enter> to continue. I predict you picked 'T'. What did you pick (enter 'H' or 'T')? H One penny for you. Round 9 Secretly choose H or T. Hit <enter> to continue. I predict you picked 'H'. What did you pick (enter 'H' or 'T')? H One penny for me! Round 10 Secretly choose H or T. Hit <enter> to continue. I predict you picked 'H'. What did you pick (enter 'H' or 'T')? H One penny for me! Final score: me: 5 you: 5 We tie. Thanks for playing!