Cooperative guessing game

Question

A standard deck of 52 cards is shuffled and split into two piles of 26 cards each.

Two players cooperate, they must score as many tricks as possible.

The first player draw 5 cards from the first pile, he then plays one of them face down, and the card from the top of the second pile is played face down. The two cards are shuffled and turned face up. The second player must now guess which of the two cards the first player played. The first player indicate whether the guess was correct. If so, the players score the trick. The first player then draw a new card from the first pile, so that he has 5 cards in hand, and play a new card face down etc. The process is repeated until the second pile is empty and 26 tricks have been played. As the first pile runs out, the last 4 rounds are played with a reduced hand size.

The players have no way of passing information to one another during the game beyond what is explicitly stated above. They may however agree on a strategy before the game begins.

What is the optimal strategy for scoring as many tricks as possible? And how many tricks will this strategy score on average?

Hint:

One could think that there would be a hard limit on the probability of scoring any trick at $5/6$, dropping to $4/5$, $3/4$, $2/3$ and $1/2$ on the last tricks, thus making the search for any strategy yielding more than $21.05$ tricks on average futile. One would be wrong.

Answer 1

The best strategy I have found in terms of maximizing average number of tricks is as follows but I believe there is likely a better one:

I assigned each turn a value $N$ such that for turn $n$, $N=n*14 \mod 52$. Simularly each card was assigned a number $C$ such that (for instance) a 5 of hearts is $C=0*13+5-1=4$ while a Jack of spades is $C=3*13+11-1=49$. The details here don't matter as long as each card has a unique value between 0 and 51 inclusive.

Each turn the first player plays the card in his hand with the value $C$ closest to the turn number $N$ noting that this is a circle so 0 and 51 are very close. The second player assumes the card with the $C$ value closer to the turn number $N$ is the card the first player wanted him to pick.

I have simulated 100 games of this and have received an average value of $20.5$ tricks per game. The minimum observed was a $15$ and the maximum was $26$.

Please note that this does not guarentee a good outcome as there is a very small but finite chance that you could score 0 tricks.

Answer 2

I can beat the "one could think" bound in the question.

First, here's a strategy that matches the "one could think" bound. Call the picker Alice and the guesser Bob. The players choose a sequence $T_1, T_2, ... T_{26}$ of independent uniformly random orderings of the 52 playing cards. (Each $T_i$ is some ordering of the cards from lowest to highest, and all the $T_i$ are picked at random from all 52! possibilities.) Every round $i$, Alice plays the card which $T_i$ says is largest, and Bob guesses the card $T_i$ says is larger.

Alice loses a round iff the hidden card is larger, $T_i$-wise, than all of hers. Therefore, the chance of winning round 1 is $5/6$. What about round 2? You might worry that the rounds are dependent -- for example, that after round 1, Alice might be more likely to have the eight of clubs, and that screws up the chances. But, by picking a uniformly random $T_2$, Alice and Bob are in effect randomly relabeling all of the cards before round 2 starts. This destroys any dependency of the cards upon the previously played rounds. Therefore, round 2 has the same winning chance as round 1: $5/6$.

The logic continues for rounds 3 and above. The sum for all rounds is $\frac 56+\frac 56+\cdots+\frac 56+\frac 45+\frac 34+\frac 23+\frac 12$, which is exactly the "one would think" bound.

However!! Some choices of the $T_i$'s are exceptionally bad. For example, if all of them are equal (e.g. Alice plays the highest value card every round), then Alice will often run out of high cards and become sad. I believe you can argue that in this case the win rate will be 1/2.

This is a sequence of orders which does worse than average. Since there is a sequence that does worse than average, there must also be one which does better than average. (Cuz otherwise it wouldn't be, ya know, the average.) Therefore, by using this better sequence, Alice and Bob beat the "one would think" bound.

Edit: Thanks klm123 for asking good questions, I've hopefully made the explanation much better.

Edit 2: Here's a specific $T_i$ sequence which, in simulation, beats all the other answers so far. Call the cards 1 through 52. Every $T_i$ is some cyclic ordering, for example, 3 > 2 > 1 > 52 > 51 > ... > 4. In round 1 the ordering is 52 > 50 > ... > 1. In round 2 it's 19 > 18 > ... > 20 : the same cycle, rotated backwards by 33. The cycle continues shifting backwards 33 cards every round (golden ratio hype). After 100,000 simulated rounds, this strategy averaged 21.7.

Answer 3

I like the kaine's answer, but it doesn't use the fact, that the second player knows all the cards the first player has put on the table in all previous tricks. The other idea would be: that the first player can give a hint about his next card.

For example, among 5 cards there are always 2 with the same suit. So the first player can put one of them first, then the second one. And the second player then knows the suit of the second card for sure, even though he have to guess everything about the first card. Also there are quite high probability (1-(3/4)^5) = 76% that to the 3rd trick the first player will get a card with the suit again. So the second player can continue guessing that the suit hasn't been changed from last trick. Furthermore to the 13 ranks of the cards one can apply the same strategy kaine's applied to 52 cards simultationsly with using hints-strategy.

The obvious flow of the strategy is the point when suit is changed and the second player guesses incorrect suit (but only in an unfortunate situation when there is a card from the second pile with this suit). One can reduce an influence of this flow using 2 colours of the cards instead of 4 suits, then there is at lease 3 cards with the same colour at the beginning, and 1.5 card with this colour will be drawn during first 3 tricks, and +0.75 cards during next 1.5 tricks, etc, this makes like 5 cards of the same color in a row. Plus when the color is changed that means that the first player has 5 cards of the same color at his hand! and won't need to change a color for a long time. Meanwhile with the 26 cards of the same color one can freely use kaine's strategy.

Again, the problem is that the kaine's strategy is not quite predictable, and probability can be change easily by using N(n) formula.
And, as a matter of fact, my simulation gives the following results:

1. Strategy with 4 suits + kaine's strategy with tuned parameters gives 21.04 = 80.9% correct guess rate.
2. Strategy with 2 colors + kaine's gives 20.92 = 80.4% correct guess rate.
3. Pure Kaine's gives 21.3 = 82.1% correct guess rate.

This is quite unexpected result for me, but I can't find any bug in my program, so I think the thing is number of cards in groups, for 26 and 13 card decks is much harder to apply kaine's strategy than for 52 card deck and this neutralises hints advantage. But I really hope that someone can retest my idea and get something more usefull from it.

Answer 4

I think you can get to around 3/4 wins by having this system:

Designate one color even (say, red), and one color odd. Every turn, you put down the color of card of your turn. For the flip card, if it is your color, pick that; otherwise, pick the other card.

There is the chance of the top card being the same color, but about 50% chance of it not. And if they pick your card, it's the right color. The way this starts to break down is when you run out of cards of a color. I suppose you could have a system where when you run out of cards of a certain color, you know that color will be used for the next 4 tricks.