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 (n,k,p,s), where n is the total number of pairs of cards still on the table, k is the number of face-up cards on the table, and p is the number of face-up matched pairs on the table.  The game state must satisfy

0 \leq 2p \leq k \leq 2n

p \geq k - n

Finally, s 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 (n,0,0,0).

Optimal strategy depends on what we are playing for.  That is, what is the value of a completed game v(0,0,0,s)?  The references focus on the case v(0,0,0,s) = s 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 s.  However, I think a more common and realistic valuation is simply “win, lose, or draw,” with v(0,0,0,s) = sgn(s), 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 n of pairs is odd.  For even n, the game may end in a draw, and maximizing the expected value of sgn(s) 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., v(0,0,0,s)=s), 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 (n,k,0,0):

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 (n,n-1,0,0) with n \geq 5, the optimal strategy is the NON “sacrifice.”  Also, for (3,1,0,0) (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]

Use Your Head

Last week I saw an interesting experiment demonstrating a phenomenon that I had not seen before.  In this video clip from a past episode of Top Gear, Clarkson uses a remote key fob to lock a car from a distance of about 40 yards.  He then walks an additional 10-15 yards away from the car, and demonstrates that the key fob no longer works… until he places the fob against his temple and tries again, and it works!

Some additional online searching suggests that this “trick” of using your head to increase the key fob’s range also seems to work as well or even better by placing the fob under your chin, sometimes accompanied by opening your mouth.  There are a lot of proposed explanations for why this works, along with repeated experiments confirming that it does work.  One of the more interesting explanations is the following quote from a 2009 New York Times article:

The trick turns your head into an antenna, says Tim Pozar, a Silicon Valley radio engineer.  Mr. Pozar explains, “You are capacitively coupling the fob to your head. With all the fluids in your head it ends up being a nice conductor. Not a great one, but it works.”

At this point I was certainly intrigued, but skeptical.  I think the experimental setup is very important here, with the potential for either unintended misinterpretation of results… or even the intentional misdirection of a magician’s trick.  The experiment is reproduced again in this Unplggd article:

One step back beyond the point of being out of range, I confirmed that the remote didn’t work. Then I raised the remote [my emphasis], pressed it to my chin, and squeezed the button. I heard a “chirp!” in the distance and saw the headlights flash. Huh. So I started walking backwards. All in all I was able to back up 42 steps, roughly 85 feet, before I was no longer able to make contact with the car by holding the remote to my chin.

Sometimes– as in the neutrino timing experiment mentioned in my last post– science is hard, being some combination of expensive, difficult, or complicated to carry out.  But in this case, it was relatively cheap, easy, and straightforward to simply try it myself, and see what happened.

It is nice being married to a woman who not only tolerates but enables these projects and excursions of mine.  Last Saturday morning, she and I drove to the reasonably flat, completely empty parking lot at the nearby high school.  She recorded the maximum distance from which I could consistently lock the car using the remote key fob, while holding the fob in several different positions and orientations.

(Distances were measured in increments of 10 feet, conveniently marked by the intersections of painted lines on the lot.  By “consistently lock the car” I mean that I could lock the car with each of three button presses, but 10 feet farther away I failed on at least two of three attempts.  I was somewhat surprised that the range actually dropped off this sharply.)

Holding the fob in “typical” fashion, away from my body at approximately chest height and pointing it at the car, the fob’s range was 80 feet; i.e., at 90 feet it stopped working.  As in the above experiments, I then held the fob under my chin… and the fob’s range increased to 110 feet!  So far, so good, although opening or closing my mouth did not appear to make any difference.  I also tried holding the fob to my right temple, where the range increased to 140 feet.

See where this is going?  I think the problem is that, at least in the descriptions I have read or videos I have seen, this is where the experiment ends.  But I also tried holding the fob at chin height, in the same orientation relative to the car, but away from my body, and the range remained at 110 feet.  Similarly, holding the fob at the height of my temple, but away from my body, yielded a range of 140 feet.  (We did actually observe one success out of three attempts at 150 feet.)

Finally, the most effective method that I tried was holding (and pointing) the fob straight up over my head, which increased the range to 190 feet.  In other words, the higher the fob, the longer the range.  We observed no effect of the fob’s position relative to my head, only relative to the ground.

Myth busted?  It would seem so… but I wonder if others have tried this experiment, also distinguishing height above the ground from position relative to the head as separate controlled parameters, and observed different results.  Maybe I was doing something wrong?  It would certainly make for a much cooler “did you know” phenomenon if there really was something to the “capacitive coupling to your head.”