Optimal decision in game of Memory 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?
 A: 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.
