The Matching Pennies 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:

MATCHER\MISMATCHER	MISMATCHER has HEADS	MISMATCHER has TAILS
MATCHER has HEADS	Pennies match: MATCHER wins	Pennies don't match: MISMATCHER wins
MATCHER has TAILS	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.

Transcript

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:

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 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.

Enjoy,

Other researchers

Here is his "Adversarial sequence prediction" video:

Adversarial sequence prediction

Matching pennies links

Compression and prediction

Other Links