Memory Game

In the seventh episode of this season (22nd) of Survivor, two contestants played the Memory Game to see who would remain on the show. In the Memory Game you score points by flipping over pairs of the same card. Whoever identifies the most pairs wins. The Survivor version had 20 tiles (10 unique pairs) laid face down. The contestants took turns flipping over two tiles per turn. If you flipped over identical tiles (a pair) you received a point and those two tiles were removed from the game. If the contestant flipped over non-identical tiles, the tiles were returned to their face down position. The players alternated turns regardless of whether they scored a pair or not. First to get five pairs won the game. Watching the game, I had two questions:

1. Is it better to go first or second?
2. With the second part of your turn, if you do not have a 100% chance of getting a pair is it better to flip an already known tile or try to flip an unknown tile?

This post is about the first question. The second question I may take up in another post. Unfortunately I was unable to completely answer the first question but laid the groundwork to solving it (if I had some programming skills it would be easy to finish).

I approached the problem by starting with the simplest case: 2 tiles (1 unique pair). Obviously you want to go first in this situation. Flip over two tiles and you win. For the next case 4 tiles, I had to develop a few rules.

1. If there is an odd number of pairs, whoever gets the majority of pairs wins.
2. There are no ties. If there is an even number of pairs, whoever gets half the pairs first wins.
3. All players are assumed to have perfect memory (ie once a tile is flipped over, they never forget its position).
4. A player must flip over two tiles per turn.

Rule 2. means that whoever gets the first pair in a 4 tile game wins. In this case, the person going second has large advantage. The person who goes first only wins 33% of the time. The person who goes second wins 67% of the time. Why is this so? In Memory there are two ways to get a pair. The first method of scoring is to flip over your first tile and already know the position of its match on the board. The second method of scoring is to flip over your first tile, not know the position of its match, and then have to randomly guess and find its match. Player 1 (P1) cannot score a pair the first way as all the tiles are unknown. That leaves only the second way. P1 flips over a tile and that leaves three remaining unknown tiles, any of which can be a match for the first tile. Thus P1 has a 1/3 chance of getting the first pair and winning. If P1 does not get a match, then Player 2 (P2) knows two of the tiles before his turn starts and is guaranteed to be able to find a match on his turn through the first method of scoring. This was one of my first findings:

Finding #1: Let n be the number of tiles left in the game. Let m be the number of known tiles (at the beginning of the players turn). If m is greater than or equal to n/2, then a player will score a pair 100% of the time.

I am not explaining it well but it makes sense if you think about it a bit. In the 4 tile game where P1 does not score on his first turn, P2 starts his turn in an n = 4, m = 2 game (there are 4 tiles left and 2 of them are known). P2 begins his turn by flipping over one of the unknown tiles. Whichever one he selects, he already knows the position of its match. If you know exactly half the tiles (m = n/2) on the board then the next unknown tile you flip, you will know exactly where its match is.

Finding #2: The chance of scoring a pair with the second method is equal to 1/(n-m-1).

Remember that the second method is a player flips over an unknown tile, does not know its match and then randomly has to guess for its match from the remaining unknown tiles. The numerator is 1 because you know that one and only one of the unknown tiles is the match for your flip. The denominator is the amount of remaining unknown tiles (total number of tile less known tiles (at the start of the turn) less 1 (the tile you just flipped over).

Finding #3: The chance of scoring a pair with the first method is equal to either 100% ("Solved Pair") or m/(n-m).

A Solved Pair is when your opponent accidentally finds you a match with their second flipped tile. P1 flips an unknown tile and then tries to score a pair using the second method. If the second tile P1 flips matches one of the m known tiles then P2 has a Solved Pair. P2 now knows the position of both tiles in the pair and flips them, thus getting a match 100% of the time. If a player does not have a solved pair then he flips an unknown tile. The player is choosing between the n-m unknown tiles and hoping to find the second half of the known tiles. Thus he is searching for the m second half's out of the n-m unknown tiles: m /(n-m).

Using those findings, I found that P1 has a 47% chance of winning a n = 6 game and a 54% chance of winning a n = 8 game. However as n grows, it gets more and more complicated to figure out the chance of winning. There are many different ways a game can unfold and the calculations are too tedious for me to want to do by hand so I stopped at the n =8 game.

For example in the n = 10 game, a player can win by scoring the first 3 pairs or by scoring the first 2 pairs and then the 5th pair, etc. Then to further complicate things, there are a multitude of different ways that a player win within each of the scoring outcomes. Like in the P1 gets the first three pairs game there are many different was P1 can accomplish this (ie get 3 pairs in a row on his first three turns or get 3 pairs in three of his first four turns where missed on his first turn, or gets 3 pairs in his first four turns when he missed on his second turn etc). As you can see it involves more rote computation than I would like to do. However a computer program or someone with some experience with Markov chains could come up with an a solution.

I was able to make a table that tells the players chance of scoring a pair on that turn. For any n tile game with m tiles known, I can tell you what % chance a player has of scoring a pair on that turn. A program could take that table and use it as a reference as it calculates the various ways a game can unfold. The computer would then have a bunch of saved states that it can reference when calculating the % chance each player has of winning the game at that time. I completed a couple of states for the heck of it and some clear patterns and rules emerge. The calculations are straightforward and could be programmed.

Unfortunately I did not solve my initial problem and can only guess at whether or not it is better to go first or second. For an n = 20 game, I would speculate that each player would have around a 50% chance of winning regardless if they went first or second. The number of ways to victory grows at such a large rate as n increases, that the importance of the first turn would mean less and less. The roughly 5% chance P1 has of making a pair in his first turn is counter-balanced by the increased odds P2 had of making a pair if P1 fails to make a pair.