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
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
The classical approach to sequence prediction takes the form of the
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
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.
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
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
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.
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: