Introduction
The memory game is a common children's game played with a set of cards. The cards have a pictures on one side and each picture appears on two (or sometimes four) cards. The game starts with all the cards face down and players take turns to turn over two cards. If the two cards have the same picture, then they keep the cards, otherwise they turn the cards face down again. The winner is the person with the most cards when all the cards have been taken.
We have several different versions of the game (the difference being the pictures), and I have played with many, many times. When playing with a two year old, it sometimes feels like they are just turning cards over at random. Which made me wonder:
- what's the average number of turn it would take to play if you picked cards at random
- how much quicker would it be if you removed some cards (we sometimes play just the goodies in the PJ masks game)
- how much quicker would it be if you played perfectly (or just didn't turn non-matching cards back over)
The rules
For the purposes of this article, I'm going to consider a one-player version of the game:
- The deck consists of n different card types (either n pairs of cards or n sets of 4 cards), labelled A, B, C, ... etc.
- Each turn, you flip over two cards (one at a time, so you can see the first one before picking the second)
- If the two cards match, then they are removed from the game, otherwise they are returned
- The game ends when all the cards are removed
Random strategy
When cards are picked at random the player effectively has no memory of what they have turned over previously.
To get a feel for how long games take, let's start with the simplest game and work our way up. With one pair of card ($n = 1$), the game is trivial: both cards get turned over on the first turn, they match and the game is over. So with $n = 1$, the expected number of turns, $E(t) = 1$.
With $n = 2$, the game becomes more interesting. We turn over one card, which we'll call A. That leaves us with three cards to pick from: the other A and two Bs. So the chance of getting a match on the first turn is one in three or $\frac{1}{3}$.
If we do get a match, then the game reduces to the trivial state where $n = 1$, and so the total number of turns, $t$ will be 2. If we don't get a match, then the game resets to its original state, and we have to try again. Every turn, we have a $\frac{1}{3}$ chance of getting a match.
The probability distribution for number of turns to get the first match is therefore an exponential distribution, with $\lambda = \frac{1}{3}$. The mean value for this distribution is $\lambda^{-1}$, so the expected number of turns to get the first match is:
$\qquad E(\text{match}) = \left(\frac{1}{3}\right)^{-1} = 3$
So the expected number of turns to complete the game, when $n = 2$, is $E(t) = 3 + 1 = 4$.
Another way we can calculate this is define $E(t)$ in terms of itself. We know if we have two pairs face down, then there is a $\frac13$ chance that the game takes two turns, and a $\frac23$ chance that we spend a turn and end up back in the same situation we started at. If that happens, then the expected number of turns is, weirdly, one more than the expected number of turns to win in this situation.
In other words, $E(t) = \frac13(2) + \frac23(E(t) + 1)$.
$ \qquad \begin{align} E(t) &= \frac{2}{3} + \frac{2}{3} \cdot E(t) + \frac{2}{3} \\ E(t) &= \frac43 + \frac23 \cdot E(t) \\ \frac13 \cdot E(t) &= \frac43 \\ E(t) &= 4 \end{align} $
With $n = 5$,
- the probability of getting a match on the first turn is $p = \frac15$
- the expected number of turns to get a match is $\left(\frac{1}{5}\right)^{-1} = 5$
- the expected number of turns to complete the game is $E(t) = 5 + 3 + 1 = 9$
With $n = 7$, we expect to take $7$ turns to get the first match, and $7 + 5 + 3 + 1 = 16$ turns in total.
With $n$ pairs, the expected number of turns get the first match is the nth odd number ($2n - 1$), and the expected number of turns to complete the game is the sum of the first $n$ odd numbers:
$\qquad \normalsize E(t) = \Large \Sigma^{\normalsize n}_{\normalsize i=1} \normalsize 2n - 1 = n^2$
Rather neatly, it turns out that the sum of the first $n$ odd numbers is $n^2$ as can be seen in this diagram.
Conclusion: if you play at random, the expected number of turns to complete a game with $n$ pairs is $E(t) = n^2$.
Perfect strategy
Going, from one extreme to the other, what if you have perfect memory (or if you just don't turn the cards back over). Now you have to have a strategy, but the perfect strategy is quite straightforward: if you can make a pair, then make a pair, otherwise turn over a card you haven't previously seen. Do this for both cards you pick on your turn.
Starting back at $n = 1$, the game is, again, trivial. You will win in one turn no matter regardless of your strategy. With $n = 2$, there are two options for what can happen. Either you get a match on your first turn, in which case you also get a match on your second turn and the game is over in two turns. Alternatively you pick A then B on your first turn. In which case, on your second turn you pick a new card, which must be either A or B, allowing you to get a match, so the game take three turns.
The chance that of getting a match on your first turn is $\frac{1}{3}$ as we calculated for the random strategy. So $E(t) = 2\left(\frac{1}{3}\right) + 3\left(\frac{2}{3}\right) = \frac{8}{3}$, just over one turn quicker than if you play at random.
With $n = 3$ things get trickier.
Permutations
Another way to attack the problem is to consider order in which we could turn over the cards. If we consider the $n = 2$ situation, then there are three possible orders of cards. Remember that whatever card we turn over first, we call A, so the first card must be A. The second A can then be in one of the three remaining spaces. So the three sequences are AABB, ABAB, and ABBA.
The sequence AABB will result in us getting a pair on the first turn and so winning the game in two turns. The sequences ABAB and ABBA will not get a pair on the first, but will on the second, and so take three turns. As before, $E(t) = \frac{1}{3}(2) + \frac{2}{3}(3) = \frac{8}{3}$.
With $n = 3$, there are 15 possible sequences. The first card must be A again, and there are five remaining choices for the second A. Then the first B must go in the first available slot, leaving three options for the second B. This leaves two spaces for the two C cards, and so only one way to place them, giving $5 \times 3 \times 1 = 15$ possibilities.
Sets of four
In the version of the game we have, instead of pairs of cards there are four of each card type. This makes the game easier, but the analysis harder. Now there are some situations where we can't treat the card types as interchangeable.
As before, with $n = 1$ (meaning one set of four cards), the game is trivial. The only difference is that the game last two turns.
With $n = 2$, there are different states the game can be in. We can the possible game states as circles showing the cards remaining. The arrows show which states we can transition between (which include from one state to itself if we don't get a pair that turn). This way of modelling the system is called a Markov chain.
The first part of the chain is similar to the situation we have dealt with before. After drawing one card, which we'll call A, there is a $\frac{3}{7}$ chance of getting a second A and a $\frac{4}{7}$ of getting a B. The expected number of turns to get a match is $E(\text{match}) = \left(\frac{3}{7}\right)^{-1} = 2 \frac{1}{3}$ turns.
The 4B state is trivial, and the 2A2B state is the simply a game with pairs, which we have dealt with. The just leaves the 2A4B state to consider.