Optimal decision in game of Memory

Question

Suppose two players are playing a game of Memory with $2n$ tiles consisting of $n$ distinct pairs. (To play, you publically reveal two tiles. If they match, you keep them and take another turn; if they do not match, you turn ends and the other player takes a turn. The goal is to collect as many pairs as possible.)

Also suppose that the players have perfect memories and know the identity of $k$ tiles from previous turns. In effect, tiles, once revealed, stay revealed.

It is your turn and you reveal an unknown tile and find it does not match any of the $k$ known tiles. Under what conditions on $n$ and $k$ is the ideal strategy (to maximize the number of pairs you collect in this game) to select an already revealed (non-matching) tile rather that to reveal a new tile and possibly providing more information to your opponent?

Answer 1

Here is answer (optimal strategy, dynamic optimization, optimal expected value): http://library.utia.cas.cz/separaty/2010/E/kubena-pexeso%20%28concentration%20game%29%20as%20an%20arbiter%20of%20bounded-rationality%20models.pdf

Let as denote for the position [n, k], k<=n: A(n,k)=E(payoff of the player minus payoff of the opponent) and A(n,k)=n if k>=n. The strategy-tree

• 0) Turn over two known cards
• 1) Turn over first a known card, then an unknown card
• 2) Turn over first an unknown card, then
• a0) in case it builds a pair with a known card
• a1) turn over an unknown card
• a2) turn over the corresponding known card
• b) if it does not build a pair with any known card
• b0) turn over another unknown card b1) turn over any known card (some positions exclude some of the mentioned strategies, in particular in case [n,0] , the strategies 0), 1), 2a1) and 2b1) are excluded and the case [n,1] excludes 0)

implies a recurrent formula, if strategy 0 is forbidden

$$ A(n,k)=\frac{k}{2n-k}(1+A(n-1,k-1))+\frac{2n-2k}{2n-k}max[-A(n,k+1),\frac{1}{2n-k-1}(1+A(n-1,k))-\frac{k}{2n-k-1}(1+A(n-1,k+1)-\frac{2n-2k-2}{2n-k-1}A(n,k+2)] $$ for k>=2 and

$$ A(n,0)=\frac{1}{2n-1}(1+A(n-1,0))-\frac{2n-2}{2n-1}A(n,2) $$

With a boundary condition $$ A(1,1)=1,\quad A(n,k)=n\; if\; k\geq n $$

But if A(n,k)<0, strategy 0 become optimal, and if k>=2, strategy 0 become feasible. So, position [n,k] is deadlock, equivalent to stalemate in the game of chess.