Cooperative guessing against an evil god

Question

Following this: Cooperative guessing game:

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 draws 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 indicates whether the guess was correct. If so, the players score the trick. The first player then draws a new card from the first pile, so that he has 5 cards in hand, and plays 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.

One can ask a little bit different question with a totally different result: What is the optimal strategy to guarantee scoring as many tricks as possible, independently of deck shuffling outcomes?

Assume that all shuffling is done by an evil god, who knows all about the game, and the strategy that players have chosen, and wants them to score as little as possible.

I know that at least 5 is possible (just encode each 5th card with previous 4), but I've been told that 6 is possible. It may be more.

Answer 1

Here is the technique to get guaranteed 5 tricks as mentioned by the OP. You can use this as a starting point to see if you can get more.

First, we will divide the game into 5 sub games of 5 plays each. We will win one trick each sub game (possibly more, but not guaranteed). At the end, there will be one card left to guess, but we won't be able to guarantee the outcome.

Each sub game will be played as follows:

1. Player one starts with 5 cards. He will order them in some way, thus encoding the 5th card with the other 4.
2. Player one will then play the cards in order for the next 5 turns. The new cards that are drawn to replace the old are used for the next sub-game.
3. Player two will see the first 4 cards played by player one, and make random guesses. After each guess, he will be told if he was right or not, so player two will know exactly which cards player one played. Since the order of the first four can be used to uniquely identify the 5th, player two will know the 5th card about to be played by player one before it is even played. Thus, it can be guessed correctly every time.
4. At the end of a sub-game, the player one will have drawn 5 new cards with which to play the next sub-game.

After 5 rounds, they will have played 5 rounds of these sub-games, thus guaranteed themselves at least 5 tricks. The last card drawn played and guessed at random by player two.

Answer 2

10 tricks

I suspect that one or two more is possible, but that may require a ridiculously complicated ruleset. As if the following wasn't bad enough already.

First 3 tricks:

Cost 4 cards each.

• The cards are enumerated 1 through 52, and they are divided into 4 virtual groups, numbered 1 to 4, of 13 cards each. Each group is considered circular, so card 1 in a group comes right after card 13 in the same group. In any pair of cards from one group there is a distinct first card, defined as the card that is the fewest steps from the other card in positive direction, so for instance between card 3 and 10, 10 is the first card, as there is 6 steps up from 10 to 3, but 7 steps from 3 to 10.
• The first player finds one of the following combinations in hand:
  1. 4 cards from the same group.
  2. 2 cards from the same group, and 3 other cards from different groups (though one of them may be from the same group as the 2 cards).
  3. 2 cards from each of 2 different groups.

• Depending on the combination, the cards are played like so:

  1. A pair from is chosen so that the distance is no greater than 3, the first card is played, the other card from the pair is played immediately afterwards if the distance is 1, one card is played in between if the distance is 2, and two cards are played in between if the distance is 3. The other cards from the group are used as filler for this purpose.

  2. The first of the cards from the 2 card group is played, then 2 of the other 3 cards are used to mark the distance as a number from 1 to 6, depending on their group, like so:

     1. 1-2 or 3-4
     2. 2-1 or 4-3
     3. 1-3 or 2-4
     4. 3-1 or 4-2
     5. 1-4 or 2-3
     6. 4-1 or 3-2

     And finally the other card from the 2 card group is played.

  3. If one of the pairs is 1 or 2 apart, play that like case 1. Otherwise if one pair is an odd number apart, and the other pair is an even number apart, play the first card from the pair from the lower numbered group. Other-otherwise play the first card from the higher numbered group. Then play both cards from the other group, with the first first if the distance between the cards of the first played group is 3 or 4. Then play the last card of the first played group.

The second player will always get at least one guess right by always guessing on the cards of the same group as the first card played, 1 and 2 higher respectively for the second and third card played, if possible, and if that fails deduce the value of the fourth card from the above rules.

Next 3 tricks:

Cost 3 cards each.

• The remaining 28 cards are implicitly enumerated 1 through 28, this requires that both players remember all the played cards. They are similarly split into 4 virtual groups of 7 cards each.

• The first player finds one of the following combinations in hand:

  1. 3 cards from the same group.
  2. 2 cards from the same group, one card from the group below, and one card from the group either 1 or 2 above.
• Depending on the combination, the cards are played like so:
  1. Just like case 1 in the first 4 tricks, only the difference can be no larger than 2.
  2. Play the first card of the pair, then the second if they are 1 apart, inject the card from the group below if they are 2 apart, or the card from the group above if they are 3 apart.

Last 4 tricks:

Using the last 5 cards.

• The remaining cards are enumerated 1 through 10, then the first player plays card 1 if he has it, and this step is repeated with the cards enumerated 1 through 8, 6, 4 and finally 2.

• When the first player doesn't have card 1, the other cards form a loop of 9, 7, 5, 3 or 1 card. He chooses the one starting point in this loop where the following is possible.

• He plays the first of a series of consecutive cards, the second player may not guess this card.

• He plays the last card of the same series. Since all the cards in between are in the first players hand, they cannot be drawn from the pile, so the second player can always identify this card.

• If there is more than one card between the series and the following series, each extra card in the gap is marked by playing one of the cards that the second player already know that he has, then the last card of the following series is played, and the process is repeated for each series and gap.

Example last 4 tricks:

After enumeration the cards in hand are: 2, 5, 6, 9, 10. The pile has 1, 3, 8, 4, 7 in that order.

Player 1 has to start with 9 in this case, the pile plays 1. Player 2 guess 1, so this trick is lost.

Player 1 mark the end of his series from 9 to 2 by playing 2, the pile plays 3. For player 1 to have played 3 in this scenario he must have had 10, 2 and 3 on hand, but that is impossible since either 2 or 3 must have come from the pile, so player 2 can conclude that he has to guess 2. He also now know that player 1 has 10 in hand as that is between 9 and 2.

Player 1 plays 10 to mark the double gap between 2 and his next card 5. The pile plays 8. Player 2 of course guess 10, and since a known card was played, rather than a card from the next series, player 2 now know that there is an extra gap after 2, so he will be looking for 5 or above in the next trick.

Player 1 plays 6, to mark the end of the 5 to 6 series, the pile plays 4. Player 2 knows that player 1 hasn't got 4, since he marked that by playing the known 10, so he looks for 5 or above, the closest card for that criteria is 6, so that is his guess. Player 2 now know that player 1 has 5 in hand, as that is must be that start of the series when the gap between the first and the second series is 2.

Player 1 plays 5, the pile plays 7. Player 2 know that Player 1 has 5, so that is his guess.