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

Question

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

Answer 1

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.

Answer 2

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.