Matching Game Perfect Play

Buzzles
21

I guess it kind of makes sense that it would be linear — this means that for every additional pair, you need an additional 1.61 turns on average. I guess you tend to reach some kind of steady state where the number of cards you know is a certain percentage of the total cards, and the tendencies to decrease the number of cards you know (by picking a match) and increase (by picking a new unknown card) balance each other out. On the other hand, in the real world, I would expect the function to grow faster than linear, since the more cards there are, the harder it is to remember them.

Also, I have no idea what the significance of the number 1.613706… is. It seems kinda close to the golden ratio but I’m pretty sure that’s just a coincidence.

4 Likes
22

Using @poisson’s recurrence to generate more terms, and taking successive differences, I was able to figure out that the numerators for p+2 follow a 6th-degree polynomial, then use Wolfram Alpha to find it:

P(p+2|p,0) = f(p) / (2p-1)!!

where

\displaystyle f(p) = \frac{(p-2)(p-1) p (p+1)(2p^2-2p-3)}{36} = \binom {p+1} 3 \frac{(p-2)(2p^2-2p-3)}{6}

The numerators for p+3 follow a 9th degree polynomial but I’m having some trouble determining it.

The 2p^2 - 2p - 3 term is unexpected, as it doesn’t factor into linear terms over the integers (the roots are (1 \pm \sqrt 7)/2). I was kinda hoping/expecting that f(p) would be something like a product of two binomial coefficients.

3 Likes
23

This is so cool! So, so far we have, for p pairs of cards:

turns   probability  
p   \dfrac{p! 2^p}{(2p)!}=\dfrac{1}{(2p-1)!!} maximum luckiness, every turn reveals a match
p+1   \dfrac{2 \binom{p+1}{3}}{(2p-1)!!} one more turn than there are pairs
p+2   \dfrac{\binom {p+1} 3 (p-2)(2p^2-2p-3)/6}{(2p-1)!!} two more turns than pairs
…   … [general case goes here!]
2p-1   \begin{cases} 1 & \text{if } p=1 \\ \dfrac{2^p-2}{(2p-1)!!} & \text{if } p>1 \end{cases} maximally unlucky

(And just to repeat Brent’s note about double factorial since it’s not what it looks like: n!! = n\cdot(n-2)\cdot(n-4)\cdots down to 2 or 1 depending on whether n is even or odd.)

I double-checked everything above up to 100 pairs of cards. I don’t know what’s up with that ugly special case for the 2p-1 formula but I needed it to make everything match the recurrence relation. (And we can see that it’s true for the p=1 case because that makes 2p-1=1 which is to say, the probability of it taking 1 turn when you have just 1 pair of cards, which is indeed 100%.)

2 Likes
24

We can get a recurrence relation for the expected value, perhaps similar to poisson’s for the distribution. Can Wolfram solve this into a closed form?

I had somewhat different notation: c is the number of cards, m_u the number of unpaired cards in our memory, and m_p the number of paired cards in our memory (this can only be 0 or 2). E gives the expected number of turns taken as a function of those variables. We have:

\begin{align} E(0,0,0) = 0 \\ E(c,m_u,2) = 1 & + E(c-2,m_u,0)\\ E(2,1,0) = 1 \\ \text{otherwise} \\ E(c,m_u,0) = 1 & + \frac{m_u}{c-m_u}E(c-2,m_u-1,0) \\ & + \frac{c-2m_u}{(c-m_u)(c-m_u-1)}(E(c-2,m_u,0) \hspace{2cm}\\ & + m_uE(c,m_u,2)+c-2(m_u-1)E(c,m_u+2,0)) \end{align}

I wonder if this is correct / gets the same expected value results as Danny computed before.

3 Likes
25

Ooh! Thanks for this! I’m eager to try but you currently have a mismatched parenthesis and I’m having trouble debugging it. (Also we probably need more base cases to avoid division by zero.)

1 Like
26

@wantonhalo I’m failing to get your recurrence relation to work! It looks like a really good approach though, so lemme try to understand it…

(Btw, @bee jumped in and helped me figure out the following.)

There are c cards on the table. Of those c cards, there are u that you know and that you don’t know the match of. Also there are p out of the remaining c-u cards that you know and which you do know the match of. (As you @wantonhalo says, if p ever becomes 2 then you know a match which you’ll immediately grab on your next turn.) We’re looking for the expected number of turns as a function of c, u, and p which we write as E(c,u,p).

So we have the following cases:

  1. With zero cards on the table, you’re done in zero turns. E(0,u,p)=0.
  2. With 2 cards on the table, you’re done in 1 turn. E(2,u,p)=1.
  3. If you know a matching pair then the number of turns is 1 more then if that pair wasn’t there at all. (This is the parenthetical above). E(c,u,2) = 1 + E(c-2,u,0).
  4. Your first flip matches one of the u cards you know. Each of the u cards you know has its match on the table as one of the c-u unknown cards. So there’s a \frac{u}{c-u} probability that you’ll pick one of those. If you do then you remove 2 cards from the table, one of which is one of your known cards. So E(c-2,u-1,0).
  5. Dumb luck! Your first flip doesn’t match anything but your second flip matches the first flip. This happens iff the first flip is not a match of any of the u cards – probability \left(1-\frac{u}{c-u}\right) – and then the second flip is the exact needed card – probability \frac{1}{c-u-1}. Multiply those probabilities for the probability of lucking out on a greenfield match. If that happens, we grab the match and have E(c-2,u,0).
  6. We flip over two new cards that don’t match each other but the second flip reveals a new match. So again we have probability \left(1-\frac{u}{c-u}\right) for the first flip not matching anything, and then with probability \frac{u}{c-u-1} the second flip matches one of the u already-known cards. In this case, we have E(c,u,2) or 1+E(c-2,u,0).
  7. We memorize two new cards with no new matches learned. Like case 5, this means first flipping over a non-match – probability \left(1-\frac{u}{c-u}\right) – and then not hitting any of the u+1 cards known after the first flip, so probability 1-\frac{u+1}{c-u-1}. If this happens then we have the same number of cards on the table but 2 more known unpaired cards, E(c,u+2,0).

Putting all that together, we’re getting the following for the general case:

\begin{align} E(c,u,0) = 1+ &\dfrac{u}{c-u}E(c-2,u-1,0) & \text{ (find match)} \\ + & \left(1-\dfrac{u}{c-u}\right)\dfrac{1}{c-u-1}E(c-2,u,0) & \text{ (dumb luck)} \\ + & \left(1-\dfrac{u}{c-u}\right)\dfrac{u}{c-u-1}E(c,u,2) & \text{ (learn match)} \\ + & \left(1-\dfrac{u}{c-u}\right)\left(1-\dfrac{u+1}{c-u-1}\right)E(c,u+2,0) & \text{ (bupkis)} \end{align}

But I think it must still have a bug somewhere because when I put that in Mathematica and ask for E(2,0,0) it complains about division by zero.

1 Like
27

Does Mathematica carry out multiplication lazily or strictly in the second argument? e.g. if you define f(x) = (x - x) * f(x+1) will it evaluate to 0, or will it go into infinite recursion? This is relevant because of the last “bupkis” case. When evaluating E(2,0,0) the probability of this case is zero (intuitively it is obvious that this case can’t happen when there are only 2 cards left, and algebraically 1 - (u+1)/(c-u-1) = 1 - 1/(2-0-1) = 1-1 = 0), but if the recursive call happens anyway, it will be to E(2,2,0) which makes no sense, and leads to evaluating things like u/(c - u) = 2/(2 - 2).

I had to deal with this very carefully when defining my Haskell version of @poisson 's recurrence.

2 Likes
28

Also, it should be possible to get rid of the last parameter, since it is only ever 0 or 2. Just substitute 1 + E(c-2,u,0) in for E(c,u,2) in the “learn match” case; then all the calls to E have zero as the last argument so you can just get rid of it.

2 Likes
29

Ah, smart, yes, it turns out that Mathematica is hard-working! I.e., it is too dumb to optimize away the recursive call in such cases.

Also smart. I came to the same conclusion when debugging my Wolframaic.

Which, update! The following gives the correct results for expected number of turns:

e[c_, u_] := e[c, u] = Which[
  c == 0, 0,
  c == 2, 1,
  u == c, c/2,
  c-u-1 == 0, 0,
  True, 1 +
    u/(c-u) e[c-2, u-1] + (* first flip matches one of the u cards *)
    (1-u/(c-u)) 1/(c-u-1) e[c-2, u] + (* dumb luck *)
    (1-u/(c-u)) u/(c-u-1) (1+e[c-2, u]) + (* 2nd flip matches 1 of the u cards *)
    (1-u/(c-u)) (1-(u+1)/(c-u-1)) e[c, u+2] (* 2 greenfield flips match bupkis *)
   ]

(Thanks again to @bee for fixing errors here.)

Unfortunately, I’m failing to get Mathematica to make any progress on solving the recurrence relation in closed form, though it’s entirely possible I’m doing it wrong…

3 Likes
31

I have approached the problem in a bit of a different way, by imagining the cards lying in a 1-dimensional array, and working on the cards from left to right. If we have perfect memory, every card gets drawn either one time or two times.

We’re going to calculate for every index of the array the expected number of times this card is drawn. The expected number of draws of a card at a certain index is dependent on two things:

  1. Whether the card is left card (L) of the pair or the right card (R) of the pair.
  2. Whether the card is opened as the first card (F) in a turn or the second card (S) in a turn.

This means that the card at every index is one of the four possible types of cards: LF, LS, RF, RS

We can calculate the expected number of turns by summing the probabilities of the four types of cards. We know that a RF card is only drawn once, as we can match it immediately with its corresponding left card.

We know that a LS card is always drawn twice, once to observe it and once to match it with its corresponding right card.

For a LF card and a RS card, it depends on whether it is a “lucky draw” or not. If it is a lucky draw, both cards are drawn once, otherwise they are drawn twice. Therefore, we’ll further divide the LF and RS cards into two groups:

  1. Lucky left first cards (LLF) and lucky right second cards (LRS)
  2. Unlucky left first cards (ULF) and unlucky right second cards (URS)

This means that we now have six different types of cards: LLF, ULF, LS, RF, LRS, URS

If we know for every index of the array of cards the probability of being of a certain card type, we can calculate the expected number of draws of the card at a certain index. By summing the expected number of draws of all cards, and dividing by 2, we can estimate the expected number of turns. I have implemented this here: Google Colab

I get the same results as the other approach for the expected values. Two interesting plots:

image
image

2 Likes
32

I note that the probability in your graphs of getting a “lucky draw” is basically zero, which makes sense, and the probability goes to zero as n goes to infinity. How close are the results if we simply pretend those types of cards don’t exist?

1 Like
34

Although the number of lucky draws per draw goes to zero as c goes to infinity, the number of lucky turns per game seems to stabilize around a value of about 0.70 lucky turns per game…

image

1 Like
35

Interesting!

36

If we separate the even and uneven indices, we get much smoother curves.

image
image1167×333 72.3 KB

image
image1167×333 23.7 KB

3 Likes
37

Let’s try to explain the linear relationship @dreev saw for a large number of cards. We will not be too rigorous.

Let T{\left(c, u\right)} be the expected number of turns remaining, given that there are c cards remaining of which we know u. Consider the aforementioned recurrence relation for the expectation of the number of turns remaining

\begin{align}T{\left(c,u\right)} &= 1 + \frac{u}{c-u} T(c-2, u-1) + \left(1 - \frac{u}{c-u}\right) \frac{1}{c-u-1}T(c-2, u) \\&+ \left(1 - \frac{u}{c-u}\right) \frac{u}{c-u-1}\left(1+T(c-2, u) \right) \\&+ \left(1 - \frac{u}{c-u}\right) \left( 1 - \frac{u+1}{c-u-1}\right)T(c, u+2) \end{align}

We seek an approximate scaling solution T{\left(c, u\right)} \approx c \tau{\left(u/c\right)} \equiv c \tau{\left(f\right)}. Here now \tau is a continuous function of a real-valued argument. Our solution will only be valid in the limit c\to\infty at fixed f.

The idea is to expand both sides of the equation in powers of 1/c and solve it at the lowest nontrivial order. The terms at different values of c, u on the right-hand side, in this continuum limit, are approximated as derivatives.

So we just put the right hand side of the recurrence relation in mathematica, in terms of our scaling function \tau, and ask it to expand everything in powers of 1/c.

The lowest order term is just c \tau{(f)} = c \tau{(f)}, which is automatically satisfied.

The first nontrivial order is order one (c^0), which gives the differential equation

1 - f - f^2 +2 f ( 3 f - 2) \tau{(f)}+ (2 - 9 f + 13 f^2 - 6 f^3) \tau'{(f)} = 0

The general solution to this equation (per Mathematica, persumably by pulling all the \tau to one side and integrating) is:

\tau{(f)} = \frac{1 + 2 (1 - f)^2\left( \phi + \log((2 - 3 f)/(1-f))\right)}{4 f - 2}

for any constant \phi.

The boundary condition is \tau{\left(1/2\right)} = 1/2. We may easily verify that this BC is satisfied by \phi=-2, by plugging that in and then taking the limit f \to 1/2.

Our desired limiting time to finish the game is then c \tau{\left(0\right)}. This evaluates to

\lim_{c\to\infty} \frac{T}{c}= \left(\frac{3}{2} - \log{2}\right) \approx 0.80685.

Since the number of cards is twice the number of pairs, this seems to agree with @dreev’s numerical 1.6137-ish

3 Likes
38

Holy cow, yeah, here’s @poisson’s exact value compared to my numerical estimate:

1.6137056388801093812\ldots = 3-\log 4
1.6137058119738408985

Nice work! Now what about that 0.51154898513237434532?

PS: I replaced that 1.6137… number with the closest that Mathematica running on my laptop can get, namely the slope of the function (expected number of turns of perfect play with p pairs of cards) at p=476. There’s no doubt that @poisson is right that it’s converging to 3-\log 4 in the limit.

2 Likes
39

Hahaha I suspect that’s impossible to get an exact answer for. For any finite number of cards, of course the true function is not linear. The intercept you get by fitting has to be vaguely in the neighbourhood of 0-1 because you need to get the answer 1 for one pair, but beyond that the specific number you get is kind of just some weird result of the best fit of a line to a non-linear function sampled on some particular discrete set of points.

The actual “future work” I want to do is to estimate the shape of the tails of the distribution for a large number of cards…

1 Like
40

Incredibly minor update:

I thought to try to give some of my ideas for getting the approximate distribution for a large number of cards to chatGPT o4—and it confidently derived a clearly-incorrect answer. Welp. I’ll give it another proper attempt—by hand—one day…

2 Likes
41

Big update! I think the new Claude 5 Fable model may potentially have solved this problem?

What follows is written by Claude:

The result

For p pairs, the number of turns T under perfect play takes values in \{p, \dots, 2p-1\}, and for w = 1, \dots, p-1:

P(T = p + w) \;=\; \frac{1}{(2p-1)!!}\sum_{n=1}^{\min(w,\,p-w)} \frac{(p+n)!}{n!\,(p-w-n)!}\sum_{\substack{j_1+\cdots+j_n = 2n+w\\ j_i \ge 3}}\;\prod_{i=1}^{n}\frac{2^{\,j_i-1}-2}{j_i!}

with P(T = p) = 1/(2p-1)!! as the w = 0 case. The inner sum runs over the ways of writing 2n+w as an ordered sum of n parts, each part at least 3. Everything is a finite sum of factorials and powers of 2, no recursion or DP left, closed-form in the same sense as the derangement formula. It reproduces every probability computed in this thread exactly, including @byorgey’s p = 6, 7, 8 rows from post 12.

It also settles the conjectures from posts 11 and 12:

  • the (2p-1)!! denominators are real,
  • P(T = 2p-1) = (2^p - 2)/(2p-1)!! (this is just the n = 1 term of the formula),
  • the second column really is 2\binom{p+1}{3}, i.e. P(T = p+1) = \frac{(p-1)p(p+1)}{3\,(2p-1)!!}.

Worked example. p = 4, T = 6, so w = 2. The sum has two terms. For n=1, the only composition of 2n+w=4 into one part \ge 3 is (4), giving \frac{5!}{1!\,1!}\cdot\frac{2^3-2}{4!} = 30. For n=2, the only composition of 6 into two parts \ge 3 is (3,3), giving \frac{6!}{2!\,0!}\cdot\left(\frac{2^2-2}{3!}\right)^2 = 40. Total: \frac{30+40}{7!!} = \frac{70}{105} = \frac{2}{3}, matching the table. :white_check_mark:

Proof sketch

This builds directly on @byorgey’s reformulation in post 10 (flip unknowns left to right, so the whole game is a deterministic function of the deal). Parse the deal into blocks: a card whose mate was already seen forms a 1-block, and a brand-new card grabs the next card to form a 2-block. The four possible block types are exactly the four possible turn outcomes (mate-known match, lucky match, “second card matches some other known card”, and two new cards), and chasing the turn accounting gives T = p + W, where W is the number of 2-blocks whose two cards differ.

Then a small miracle: the probability of any given block pattern is (number of ways the repeat-cards choose which open card they close) divided by (2p-1)!!, because all the other probability factors multiply to 2^p\,p! regardless of the order in which things happen. So computing the distribution of W reduces to a weighted counting problem. Lucky blocks decouple into a binomial coefficient, and the rest decomposes bijectively into independent components, one per “two new cards” turn: each such turn opens two chains of cards, and a component spanning j positions has internal weight 2^{j-1}-2. The exponential formula then assembles the pieces into the sum above.

Connections to the literature

It turns out this exact game has a small academic literature that this thread independently rediscovered chunks of:

  • Velleman & Warrington, What to Expect in a Game of Memory (American Mathematical Monthly, 2013). They prove the obvious strategy is optimal, so “perfect play” is well-defined and is what everyone here assumed. (I also re-verified this by exact dynamic programming over all game states up to 120 pairs, including the sneaky option of a deliberately wasteful second flip: it never helps, not even by a tie.) Their main theorem: E[T] = (3 - 2\ln 2)\,p + \frac{7}{8} - 2\ln 2 + o(1).
  • Which means @dreev’s regression in post 20, 1.6137060\,p - 0.51155, had already found 3 - 2\ln 2 = 1.6137056\ldots and \frac{7}{8} - 2\ln 2 = -0.5112944\ldots to about five decimal places without knowing it.
  • Acan & Hitczenko, On a memory game and preferential attachment graphs (2014), proved that T is asymptotically normal (and, fun fact, that the block lengths match vertex degrees in a preferential attachment graph).

Neither paper gives the exact finite-p distribution, and the numerator triangle 1;\ 1, 2;\ 1, 8, 6;\ 1, 20, 70, 14;\ \ldots is not in OEIS, so as far as I can tell the closed form above is new.

Verification script

Full disclosure given post 40: This is written by Claude. This script is the antidote to confidently-derived-but-wrong: it verifies the formula independently, by literally playing the game on every one of the 113,400 essentially-distinct deals up to p = 5, and against @poisson’s recurrence from post 16 (with @byorgey’s correction from post 18) in exact rational arithmetic up to p = 14.

2 Likes