Math Trivia: Concentration

You probably know about the game of Concentration.

Some number of pairs of matching cards (often 27 pairs, but well just assume it is an odd number and at least 5) are placed face down on a table. Players take turns flipping over two cards, and checking whether they match. The cards are chosen and flipped one at a time. If the cards match, they are removed and the player who flipped them gets a point and gets another turn. When all the cards are removed, the player who has the most points wins.

What you probably don’t know is that if the first player plays optimally, he will lose with probability at most 45%. What you probably won’t believe is that if the second player plays optimally, he will lose with probability at most 45%.

What about the other 10% of the games? They never end! Both players just continue picking up cards that they already know about, to avoid giving any information to the other player. I will now give a sub-optimal, but simple strategy that is similar to the optimal strategy. It will win most games you play if the person you are playing against is naively flipping over cards and giving away information.

If there are two or more completely hidden pairs, flip a new card. If it matches a card you’ve seen before, take the match, if not, flip a card you already know (If possible).

If there is only one completely hidden pairs, never flip any new cards.

If there are no completely hidden pairs, flip a new card, then flip the card that matches it.

I haven’t checked that this particular strategy works for small numbers of cards, but a strategy that loses only 45% of the time exists as long as there are at least 5 pairs. For large n, notice that you win rough half the points won before the second to last pair is revealed. After the second to last pair is revealed, if your opponent wants the game to end. He has to keep flipping new cards. He will win all the pairs until he flips the first card in the last pair. Then, assuming he cannot successfully match it, you win all the remaining pairs. You therefore on average about 2/3 of the pairs after the second to last pair is revealed.

Notice that if both players play this strategy (or the optimal one), games with lots of pairs often do not finish. The actual optimal strategy is complicated, because you are trying to maximize probability of winning and not just the expected number of points, and because this is a discrete problem with lots of special cases, but hopefully this gives you a rough idea.

If you want to rigorously check my claim, you can easily write a program to recursively compute the probability of winning in different states of the game. There aren’t that many equivalence classes of states.