Analysis of the Memory Game

I spent an unhealthy chunk of my weekend studying one of the simplest possible children’s games, which turns out to have some surprisingly complex and interesting strategy.  I remember it as Concentration, also known as Memory.  (There is a very cool Android solitaire version of the game here, which is what got me started thinking about this problem and spending so much time on it.  Thanks a lot, Brian. :))

Rules of the game

The rules are simple: the game begins with a deck of n matching pairs of cards (2n cards total), shuffled and arranged face-down on a table.  A player’s turn consists of flipping up two cards, one at a time.  If they match, the player removes the pair and takes another turn.  Otherwise, the cards are returned face-down to the table and the next player takes a turn.  Play continues until all pairs are removed (or until all players agree to end the game), at which point the player with the most collected pairs wins the game.

The references at the end of this post provide extensive analysis of the game for two players.  However, there are some interesting additional subtleties in rules and strategy that seem to have been either missed or omitted.  Following is a summary of my analysis of the game, with a focus on these additional details.

First, how is this a game of strategy?  As its name implies, the game is intended to be a memory exercise, remembering the locations of previously revealed matching cards.  Playing against a person– or a computer– with a perfect memory would not be much fun… unless we leveled the playing field by modifying the rules slightly, so that selected unmatched cards remain face-up on the table even after a player’s turn ends.  In this version of the game, everyone has a perfect memory, since all previously selected but unmatched cards are visible and known to both players.

This new game might seem rather boring: on each turn, simply collect any face-up pairs, flip up a face-down card, collect the new pair if possible, otherwise flip up another face-down card.  Right?  Wrong.  Optimal strategy frequently consists of seemingly strange moves, such as flipping up a card, and if its match is not known, selecting a known, unmatching face-up card, effectively skipping the rest of the turn.  And there are still stranger moves, as we shall see.

Game states

We can represent a game state as a tuple , where is the total number of pairs of cards still on the table, is the number of face-up cards on the table, and is the number of face-up matched pairs on the table.  The game state must satisfy

Finally, is the “score” of the next player to move, or the difference of the numbers of pairs collected by each player.  The initial state of a game is of the form .

Optimal strategy depends on what we are playing for.  That is, what is the value of a completed game ?  The references focus on the case where, for example, each player wins one dollar from the other player for each pair collected.  In this case, we are trying to maximize the expected gain, or expected value of .  However, I think a more common and realistic valuation is simply “win, lose, or draw,” with , which corresponds to maximizing the probability of winning, disregarding the margin of victory.  [Edit: After some discussion, I realized that this correspondence only holds when ties are impossible; i.e., the number of pairs is odd.  For even , the game may end in a draw, and maximizing the expected value of does not necessarily maximize the probability of winning outright.]

Moves

A move by a player is a two-step process, consisting of selecting two cards, with the observation of the first card possibly affecting the choice of the second.  Considering all possible such selections, even “those that might not look clever,” as Gerez puts it, there are 9 different moves:

1. PP: collect a face-up matching pair (and take another turn).
2. OO: pick up two face-up (“old”) but non-matching cards, effectively skipping the turn.  (This is what Zwick refers to as a 0-move.)
3. PN: pick up one of a face-up pair and a face-down (“new”) card, effectively skipping the turn while revealing an additional card.
4. ON: pick up a face-up non-paired card and a face-down card.
5. NPO: pick up a face-down card and its match if known, otherwise a non-matching face-up card.  (This is what Zwick refers to as a 1-move.)
6. NPN: pick up a face-down card and its match if known, otherwise another face-down card.  (This is what Zwick refers to as a 2-move, and is the move that many players might use exclusively.)
7. NNN: pick up two face-down cards.
8. NON: pick up a face-down card and, if its match is known, a non-matching face-up card (leaving a known pair on the table!), otherwise another face-down card.  (This is what Gerez and Zwick refer to as a “sacrifice.”)
9. NNO: pick up a face-down card and, if its match is known, another face-down card (leaving a pair on the table), otherwise a face-up card.

The OO move is particularly interesting, since it effectively amounts to a “pass,” which raises the question of how to ensure that the game terminates.  In the gain-maximizing case focused on in the references (i.e., ), it is not difficult to show that the game is symmetric, in the sense that if the OO move is optimal for one player, then it is optimal for the other as well.  In other words, if one player wants to end the game, the other player will agree to end the game as well.

However, when the goal is to maximize the probability of winning, the game is no longer symmetric, and things get more complicated.  There are several different reasonable rule variations that deal with the OO move, each of which yields slightly different strategy and advantage for each player, in approximately decreasing order of my personal preference:

1. “Agreed end:” A player may make an OO move, and if the other player also makes an immediately following OO move, then the game ends.
2. “Ko rule:” This is similar to the ko rule in Go that prohibits returning to the same game state: an OO move may not be immediately followed by another OO move.
3. “Quit while you’re ahead:” An OO move unilaterally ends the game, with the outcome determined by the current difference of collected pairs.  In the gain-maximizing case only, this is equivalent to an agreed end as in (1).
4. “Withdraw:” An OO move unilaterally ends the game in a draw.

Of course, given all of these complications, another possibility is to simply disallow the OO move altogether.  This variant actually yields the most interesting optimal playing strategy.  In the game where the objective is to maximize the probability of winning, and the OO move is prohibited, the following table shows a portion of the optimal playing strategy, for game states of the form :

Optimal strategy for game states (n, k, 0, 0).

For brevity and clarity, the common NPO and NPN moves are indicated by 1 and 2, respectively.  There are a couple of unexpected weird moves: for game states with , the optimal strategy is the NON “sacrifice.”  Also, for (i.e., the game is tied and six cards remain on the table with one face-up), you can psyche out your opponent with an NNO move: if you happen to flip up the matching card, leave the pair on the table and flip up another face-down card!

A final computer science note: analysis of optimal strategy for the Memory game is essentially a dynamic programming problem.  Mathematica’s automatic memoization once again makes this particularly easy; source code in PDF format is available here.

References:

1. S. H. Gerez, An Analysis of the “Memory” Game, 65-Afternoon Project Report (in handwritten Dutch with English summary).  University of Twente, 1983. [PDF]
2. I. Stewart, Concentration: a winning strategy.  Scientific American, 265(4) (October 1991):103-105.
3. U. Zwick and M. S. Paterson, The memory game.  Theoretical Computer Science, 110 (1993):169-196. [PDF]