The Matching Pennies Game

Matching pennies is a simple two-player prediction game.

It is a simplified version of Rock, Scissors, Paper - with only two symbols, HEADS and TAILS.

One player is the MATCHER, the other player is the MISMATCHER.

The MATCHER aims to see matching pennies. The MISMATCHER wants the pennies not to match.

Players both simultaneously select either HEADS or TAILS. They then share their plays to see who won. The rules are as follows:

Pennies match: MATCHER wins

Pennies don't match: MISMATCHER wins
Pennies don't match: MISMATCHER wins

Pennies match: MATCHER wins

The players play the game repeatedly in an extended sequence, try to identify patterns in the opponent's moves, and then play to exploit them.

The game has some significance as a simple model of sequence prediction in an environment where there are other intelligent agents.

Next, a video of me explaining the game, and its significance.

Matching pennies


Hi. I'm Tim Tyler - and this is a video about the matching pennies problem - and its significance as a model of sequence prediction.

In some of my previous videos, I have described the significance of sequence prediction.

In a nutsell, predicting the future is important for agents who want to understand the consequences of their actions - in order to enable them to choose between them. Intelligent agents typically devote much of their brainpower to this kind of task.

Sequence prediction is a general, abstract model of prediction. The problem is equivalent to stream compression - which is a classical computer science problem akin to searching or sorting.

Sequence prediction is a good problem to use for measuring the forecasting abilities of intelligent agents.

One approach to constructing a prediction component is to to automatically breed prediction programs. In this approach, a a tournament is held - where many programs compete with each other and attempt to predict each other's actions - and then the winners are used to construct the next generation of programs.

The classical approach to sequence prediction takes the form of the rock-paper-scissors game.

Players simultaneously choose one of rock, paper or scissors - and then win or lose according to this table of payoffs.

The game is then iterated repeatedly.

Though there is a chance element, this is essentially a game of skill. It is often possible to systematically win by identifying patterns in your opponent's responses.

There are annual championships of rock-paper-scissors - which look like this:

Adversarial sequence prediction

There have also been numerous computer tournaments - oriented around playing rock-paper-scissor - over the years.

However, there is a simpler abstract game, which it seems to make more sense to use with computer tournaments - the Matching pennies game.

That game reduces the number of possible plays from three to two: heads and tails.

One player, the matcher, tries to copy the state of the opponent's penny. The other player, the mismatcher, tries to create a mismatch between them.

[game demonstration]

As with rock-paper-scissors becoming good at the game necessarily involves the ability to identify patterns in your opponent's responses. You have to predict what your opponent is thinking - and if your opponent is doing the same, you have to predict what they predict you are thinking. This is reminiscent of the scene with the Sicillian in the movie, The Princess Bride:

The Sicillian, in: The Princess Bride

The Matching pennies game resembles some real-world situations - for example, penalty shootouts. There the goalie dives left or right - and the kicker shoots left or right. If there is a match, the goalie may save, whereas if there is a mismatch, the kicker may score.

In the Matching pennies game, draws become impossible - and only wining and losing are possible outcomes.

At first it may seem that the players are following asymmetrical strategies - but in fact there is a nice symmetry between them - any matcher can be turned into a mismatcher by simply inverting signals in the sensory channel which tells it what its opponent just played.

Matching pennies has a mixed strategy Nash equilibrium - which consists of playing randomly. If both players follow this strategy, neither can benefit from deviating from it. However, that doesn't mean that the best way to play the game is to play randomly. Random play fails to exploit stupid opponents - and that is important in tournaments - or when playing against sub-optimal opponents.

Matching pennies has another problem - it only gives a prediction - and not a forecast. In other words, what you usually want when predicting the future is not a best-guess at what will happen - but rather a probability distribution over the possible outcomes.

This can be neatly resolved by having both the players act as bookies - and make them set odds on the opponent's play in each round. They then accept bets - and payout according to the system of payoffs I described in a previous video on this topic. To leave the dynamics of the game largely unchanged, the opponent doesn't get to see the odds - or the payouts - just the state of their opponent's coin in each round.

There don't currently seem to be any very significant computer-prediction prizes or tournaments. There is a compression prize - but it is file compression rather than stream compression - which is not so relevant - and it deals with one file type - whereas a general purpose system seems more desirable. So - an obvious thing to do is to set up some computer-prediction tournaments. If that is done, I think it should probably be based around the Matching pennies game.

For the sake of maximal simplicity - for the sake of encouraging participation - I think that the betting scheme above should probably not be used initially in the protocol of any early tournaments. Let's just play matching pennies to start with.


Other researchers

Bill Hibbard has also noticed the significance of the matching pennies game in the context of machine intelligence.

Here is his "Adversarial sequence prediction" video:

Adversarial sequence prediction

Adversarial Sequence Prediction - Bill Hibbard - the video
Adversarial Sequence Prediction - Bill Hibbard - the paper

Matching pennies links

Matching pennies - wikipedia
Matching pennies -
Penny matching machines

Compression and prediction

Prediction by Compression - Joel Ratsaby

Other Links

Practical competitive prediction
This website is a wiki for research in On-line Prediction
Prediction and Forecasting - Facebook group
Discrete sequence prediction and its applications
Google Wants to Own the Future - by Predicting It
Google scribe - press tab to generate predictive text
Prediction scene from The Princess Bride

Tim Tyler | Contact |