For which number of pairs is it an advantage to start in memory

Players A and B play memory starting with $n$ pairs of cards. We assume that they can remember all cards which have been turned. At his turn a player will first recall if two cards already turned match. If so he will choose such a pair, turn them and get a pair. If not he will turn uniformly at random a card which has not yet been turned. Then if the corresponding match has turned already he will turn that card and get a pair. If not he will again turn uniformly at random a card which has not yet been turned. As usual if a player gets a pair he can continue. Player A will start. For which $n$ does Player A have an advantage by being able to start and for which $n$ is it actually a disadvantage?

Here is what I considered so far: If $E_{k,l}$ denotes the expected number of pairs the starting player will get when $k$ cards are known and $l\geq k$ cards are unknown one can derive the following recursion formula

$$E_{k,l}=\frac{k}{l} \left( E_{k-1,l-1}+1 \right)\\ +\frac{(l-k)}{l} \frac{1}{(l-1)} \left( E_{k,l-2}+1 \right)\\ +\frac{(l-k)}{l} \frac{k}{(l-1)} \left( \frac{k+l}{2}-1-E_{k,l-2} \right)\\ +\frac{(l-k)}{l} \frac{(l-k-1)}{(l-1)} \left( \frac{k+l}{2}-E_{k+2,l-2}\right).$$ Furthermore we have $E_{k,k}=k$. The expected number of pairs players $A$ resp. $B$ will get are $E_{0,2n}$ resp. $n-E_{0,2n}$. The following list show the expected number of pairs for A and B for $n\leq 24$.

It seems that for larger $n$ the expected number of pairs for $A$ and $B$ are closer together. Can this be proven rigorously? For $n=18$ the expected number of pairs of $A$ and $B$ are equal and the game is fair in some sense. Do there exist other numbers $n$ with that property? Is it possible to give a characterization of the numbers for which $A$ has an advantage?

A has an advantage for $n\in \{ 1,4,7,8,10,11,14,17,18,20,21,23,24,\dots\}$.

B has an advantage for $n\in \{ 2,3,5,6,12,13,15,16,19,22,\dots\}$

Octave code:

n=50; A=diag(0:n-1);A(1,3)=1;

for s=4:2:n-1 for l=s/2+1:s k=s-l; if k>0 A(k+1,l+1)=k/l*(1+A(k,l)); end if l>k A(k+1,l+1)=A(k+1,l+1)-(l-k)/l*k/(l-1)A(k+2,l); end if l>k+1 A(k+1,l+1)=A(k+1,l+1)-(l-k)/l(l-k-2)/(l-1)A(k+3,l-1); end if l>k && l>2 A(k+1,l+1)=A(k+1,l+1)+(l-k)/l/(l-1)(1+A(k+1,l-1)); end end end B=zeros(n/2-1,3); for i=1:n/2-1 B(i,:)=[i (i+A(1,2*i+1))/2 (i-A(1,2*i+1))/2]; disp([num2str(i) ':' num2str(A(1,2*i+1)) ' ' num2str((i+A(1,2*i+1))/2)]); end

B(:,1) rats(B(:,2)) rats(B(:,3))

Awins=''; Bwins=''; for i=1:n/2-1 if A(1,2*i+1)>0 Awins=[Awins ',' num2str(i)]; else Bwins=[Bwins ',' num2str(i)]; end end Awins Bwins

• 1) If Player A turns up a card for which she knows no match, then it might be to her advantage to turn up an already-known card to deny opponent valuable information. 2) Also, higher expected number of pairs turned is not necessarily the same as higher chance of winning. – Boris Bukh Jan 10 '18 at 20:40
• The code implements a different formula than the one stated. Which one is correct? – Max Alekseyev Jan 11 '18 at 6:57
• In the code I first computed the difference of the expected number of pairs of A resp. B. – user35593 Jan 11 '18 at 17:14

This problem has been studied (and solved for many values) in this MSc thesis: Erik Alfthan: Optimal strategy in the childrens game Memory. He defines four strategies:

Bad: open a known card, then an unknown that may match,
Safe: open an unknown card, then a known card, matching if possible,
Risky: open an unknown card, then match if possible, i.e. an known matching card
if possible, otherwise an unknown card that may match,
Passive: open two, known, unmatching cards.


He proves that you should never play 'Bad' and there are situation when 'Passive' would be needed (easy example: 100 pairs and 99 unmatched cards are known, i.e., there's only 1 unknown pair), so the game would never terminate, so he disallows this strategy, i.e., players need to open with an unknown card.

I copy here my favorite table, followed by open problems.

n = number of pairs on board
j = number of unknown pairs
Chosen strategy, 1 : risky, 0 : safe, # : no choice

j:0 1 2 3 4 5 6 7 8 9 ...
n
2 # 1 #
3 # 1 0 #
4 # 1 0 1 #
5 # 1 0 1 0 #
6 # 1 0 1 0 0 #
7 # 1 0 1 0 0 1 #
8 # 1 0 1 0 0 1 0 #
9 # 1 0 1 0 0 0 0 0 #
10 # 1 0 1 0 1 0 1 0 1 #
11 # 1 0 1 0 1 0 1 0 1 0 #
12 # 1 0 1 0 1 0 0 0 1 0 1 #
13 # 1 0 1 0 1 0 0 0 1 0 1 0 #
14 # 1 0 1 0 1 0 0 0 1 0 1 0 1 #
15 # 1 0 1 0 1 0 0 0 1 0 1 0 1 0 #
16 # 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 #
17 # 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 #
18 # 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 #
19 # 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 #
20 # 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 #

The pattern of the table continues, computation with as many as 200 pairs, renders that, except for very small boards, the strategy should be Safe when $j$ is even and Risky when $j$ is odd.

Conjecture 1. [Alfthan] Except for smaller boards, $n < 16$, the optimal strategy is to use the risky strategy when $j$ is odd and safe strategy when $j$ is even.

Conjecture 2. [Alfthan] Except for smaller $j$, $j < 18$, the expected number of gained cards is monotone in $n$ for fixed $j$, growing if $j$ is even and declining if $j$ is odd.

Update: I've just discovered this nice blogpost about the same game: https://possiblywrong.wordpress.com/2011/10/25/analysis-of-the-memory-game/

This has a 5. possible strategy that Alfthan seems to have missed:

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 might be advantageous in some cases, so if we allow this move, the above table gets changed! See the blogpost for details.

There is also an older paper which the above thesis doesn't refer to: U. Zwick & M. S. Paterson, "The memory game", Theoretical Computer Science 110 (1993), 169-196. I havent looked at the details.