13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What happens to the cards if the players do not score the trick? Are both cards shuffled into one pile, one into each pile, etc.? $\endgroup$ – Aggie Kidd Mar 31 '15 at 18:40
  • 1
    $\begingroup$ @AggieKidd In case of a wrong guess the cards are put aside as non-scored, and are used no further. $\endgroup$ – aaaaaaaaaaaa Mar 31 '15 at 19:17
  • $\begingroup$ Who shuffles the cards? $\endgroup$ – leoll2 Mar 31 '15 at 19:31
  • 2
    $\begingroup$ To be clear, this is not a question about finding loopholes. I don't mind sporting attempts at solving it that way, but there must be a fair limit to how hard one can wilfully misunderstand the rules. $\endgroup$ – aaaaaaaaaaaa Mar 31 '15 at 20:03
  • 1
    $\begingroup$ @JonTheMon Both players see both cards when they are turned face up. But do remember that the first player does not know what card the pile will provide when he choose what card to play. $\endgroup$ – aaaaaaaaaaaa Mar 31 '15 at 20:12
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A serious attempt at a solution, but you are right that better solutions can be found. $\endgroup$ – aaaaaaaaaaaa Apr 1 '15 at 5:35
  • $\begingroup$ I wonder, why have you chosen coefficient "14"? Why not 52/5 or 52/4? $\endgroup$ – klm123 Apr 12 '15 at 8:56
  • $\begingroup$ Btw with your strategy and 1million games simulated my program got ~21.3 = 82% :) idk, may be I have a mistake, have you tried more games? and "14" is really optimal, though I don't know why... $\endgroup$ – klm123 Apr 12 '15 at 11:30
  • $\begingroup$ @klm123 14 is chosen because it is the smallest one which ensures the suit changes each time. I only ran 100 tests and could tell the standard deviation was high. That the actual accuracy is higher does not surprise me at all. I havent found or had an idea for a better strategy. $\endgroup$ – kaine Apr 12 '15 at 13:12
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Here is a specific $T_i$ which I would guess does well. Call the cards 1, 2, ..., 52. Every $T_i$ is a cyclic order, e.g. 3 > 2 > 1 > 52 > 51 > ... > 4. The starting point of the cyclic order increases by 33 cards every round (golden ratio hype). Will Monte Carlo test when I'm not in an airport. $\endgroup$ – Lopsy Apr 12 '15 at 15:20
  • $\begingroup$ What does "total order" mean and why there are exactly 26 of them? $\endgroup$ – klm123 Apr 12 '15 at 17:11
  • 1
    $\begingroup$ @klm123 Good questions! A "total order" is a way to order the cards from smallest to biggest. One example of a total order is to take the names of all the cards (e.g. "eight of spades") and order them alphabetically. In this solution, a "uniformly random total order" is one chosen at random where all 52! possibilities are equally likely. The strategy uses one total order per round ($T_i$ on round $i$), so since the game has 26 rounds, it uses 26 total orders. $\endgroup$ – Lopsy Apr 12 '15 at 17:39
  • 1
    $\begingroup$ I understood your answer now. Thank you. But I can't agree with the logic, which you call "linearity of expectations" (or may be you missed some steps which you find obvious and I don't). What proves that independent total orders gives the average result? may they give the best result. (and Ti can never be independent, since they all depends on the same 52 cards) $\endgroup$ – klm123 Apr 12 '15 at 18:05
  • $\begingroup$ I wrote a response to your comment, and then realized my answer's explanation was pretty, um, let's say 'laconic' to be nice. I've edited my answer to hopefully explain things better. $\endgroup$ – Lopsy Apr 12 '15 at 20:37
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A legit strategy, though it seems like a waste of opportunity space to make a choice simply between two colours when you have 5 cards to choose from. Better is definitely possible. $\endgroup$ – aaaaaaaaaaaa Mar 31 '15 at 20:22
  • $\begingroup$ Oh, probably. I thought you only got to look at one of the cards before each guess. I'll have to rethink it a bit.... $\endgroup$ – JonTheMon Mar 31 '15 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.