The Memory Game (Concentration)
You lay out 2n cards face down. There are n matches to be found. On your turn you pick any card, turn it over, then pick another card and turn it over. If they match, then you keep the match and get another turn. If they don't match, then you turn the cards over and the next player takes their turn. When all matches have been claimed, the player with the most matches wins the game.
The specific problem is to consider the case where there are m matches on the table in a two-player game; you have turned up a card and the matching card has not been seen; k of the face-down cards have been seen before. You have perfect memory and you assume that your opponent does as well. Should you turn up one of the (2m – 1 – k) cards which have never been seen, or should you turn up one of the k cards which have been seen?
There are two simple interpretations of this question. Either you are trying to maximize the probability that you finish with more matches than your opponent, or you are trying to maximize the expected number of matches that you will get. I have only tackled the simpler case where you are trying to maximize the expected number of matches. Perhaps someone else would like to tackle the other?
This turned out to be a richer problem than I had expected. My naive expectation was that you wouldn't want to guess unless almost all of the information was known. For example, you'd guess if there were n matches on the table, n – 1 non-matching cards were previously known, and you just turned up the nth non-matching card. You have to expect your perfect opponent to be able to pick up all of the matches unless you make a match with the next pick. Therefore you guess in this situation and try to pick up this pair and all of the others.
I was mistaken, however, in the following (flat wrong) line of reasoning: When there are n matches on the table (where n is not especially small), and a significantly smaller number m of non-matching cards have been previously revealed, then you shouldn't try to find a match if you turn up the m + 1st non-matching card, because you're almost sure to fail, and you just give your opponent a chance to pick up the easy pair if you happen to match one of the m known cards that are face-down. So there are three outcomes. Either you get a match with probability 1/(2n – m – 1) (that's good), or you give up a match with probability m/(2n – m – 1) (that's bad!), or you let your opponent see an extra non-matching card before you give up your turn with probability 2(n – m – 1)/(2n – m – 1) (that's a little worse than doing nothing). So your chance of a bad outcome is m times worse than your chance of a good outcome, and your neutral outcome is more favorable to your opponent than if you just picked a card everyone knew.
As I said, all flat wrong.
Let's start with some definitions. Define a value function v, which depends on the number of matches on the table n, and the number of non-matching cards that are face-down on the table. We actually need to keep track of two value functions. v0 applies when no card is face up—that is, at the beginning of a turn. v1 applies at the decision point—when one card is face up on the table. To determine v1, we will have to decide whether the perfect player should choose a new card (potentially making a match and continuing) or or choose a card that has been previously seen (thereby passing play to the opponent, but not revealing any new information).
At the beginning of a turn, if one card has been seen from every match on the table, then a perfect player will be able to collect all of the remaining matches. We note that
|(1)||v0(n, n) = n|
We can easily write an expression for the value of v0, since it doesn't involve any decisions. The player must always turn over a card, and it is always in the player's best interest to turn over a new card. (Isn't it? Well, we'll come back to that...) The chance of getting an immediate match with one of the m previously known cards is m/(2n – m), at which point the player makes the match and continues with n – 1 matches on the table and m – 1 face-down cards known. The probability of exposing a card from a new pair is 2(n – m)/(2n – m), in which case the player has to decide whether to try to complete the match by selecting a new card or to deliberately choose a card which has been seen before, even though it doesn't complete a match. We've defined v1 to be the value function for the latter case, so we find
Now we have to deal with the decision. It's easiest to define two more value functions v+ and v– for the two choices. We use v+ for the case when a new card is chosen, and v– for the case where a previously known card is chosen. We can immediately see that
|(3)||v1(n, 0) = v+(n, 0)|
since there is no previously viewed card to choose when m = 0. We can also immediately see that
|(4)||v–(n, m) = –v0(n, m + 1), for m > 0|
since there is no possibility of a match if the player deliberately chooses a card which has been seen before. Considering v+(n, m), we note that there is one way to complete match and there are m ways to choose a match for one of the face down cards which have been previously seen. The remaining combinations reveal another card without finding any pairs. We can write the expression for v1
We need to be explicit about one more relationship
From here, we can easily program a computer or a spreadsheet to do the work. All values of v0 and v1 can be calculated in a single pass for increasing n (and for decreasing m for each n). Feel free to take a look at my spreadsheet solution.
The solution does not look like I thought it would when I posted this topic. Except for some cells in the low-n region, a plot of the "perfect" player's decision matrix looks like a checkerboard. If m + n is odd, then the player should guess, but if m + n is even, then the player should choose a card which has been seen before.
Why? Well, for m close to n, it's pretty understandable. If m = n – 1, then all of the information will be known to the opponent, unless the player can complete the match. That's a case where m + n is odd.
Now suppose that m = n – 1 cards have been seen when a player is ready to start the turn. That player is at a disadvantage. They get to choose until selecting one of the cards in the unseen pair. If n is large, then the player who is forced to go first in this situation will get about 1/3 of the matches and their opponent will get 2/3. Not a good deal. So that's a position you'd like to force your opponent into.
So consider the decision point corresponding to v1(n, n – 2). If the player "passes" by choosing a card which has been seen before, then the opponent is put into the bad situation. In fact, that's even better than completing the match! In fact, that player should have chosen previously known cards for both selections, if the opponent would be a good sport and hunt around for the unseen pair.
If we look at v0, we see that there are negative values of v0(n, m) for m > 2. In those cases, the player would be better off selecting two previously known cards and letting their opponent take over. In other words, two perfect players should lock up and stop making progress in most games.
The differences between v0(n, n), v0(n, n – 1) and v0(n, n – 2) echo through all of the different values of n and m (as long as n is not too small). Is this just an artifact of using the expectated number of pairs as our metric? Does the effect go away if the two players are each trying to maximize their chance of winning?
I haven't answered these questions yet, but I suggest that the question becomes well formed if the players agree that the game ends after each player takes n turns without a match by either player. In this case, a match between two perfect players continues because the player who is behind will be forced to expose a new card or lose the game.
Did anyone suspect that this question was malformed? I was sure that I had asked a question that had an answer, but you often find surprises when you look a little deeper.
Send all responses to .Thanks,