Find the best strategy for a card game

Question

A box of poker cards consists of $52$ cards, and are divided randomly into $13$smaller decks of $4$ cards. Two players play a game as following:

• Each time a player pick a card from a deck and remove that deck from the table
• The number ($2$ to $10$, Jacks, Queen, King, Ace) of the chosen card in each move must not repeat

The person who cannot pick any other card loses the game. If all $13$ cards are chosen, then it is a tie. Is there a winning strategy for any of the players?

P/S: I would say that as a tie result can happen, a person would prefer to consider "not losing the game" before thinking about winning it.

I have tried this game and believe that the number of pairs in a 4-card deck can affect the winning strategy and that the first one can "not lose" (at least tie). However, I cannot prove this. I created this problem is based on the question: "Prove that if only one person plays this game, there is always a way to pick 13 cards of different types."

Answer 1

Whether or not there is a winning strategy, and which player wins, may depend on how the cards are randomly divided. It seems to me that there is a straightforward dynamic programming algorithm to determine this in specific cases, but I'm not completely sure it's practical.

If we are down to one pile (deck) and one unchosen rank, then it's easy to determine the outcome. If the unchosen rank occurs in the the pile, the game is a draw; otherwise it's a win for the second player. There are $13*13=169$ possibilities, and we record them. Then for $k=2,3,\dots,13$ we investigate each of the $\binom{13}{k}^2$ possibilities for piles remaining and available ranks, referring to the already computed outcomes for $k-1$ to evaluate them.

We need to make sure that we don't include impossible "possibilities". If all $4$ cards of a rank not listed as unchosen are present in the piles listed as remaining, then this situation cannot occur in play and should be discarded.

Note that $\binom{13}{k}^2\leq\binom{13}{6}^2=2,944,656$, so this may well be feasible. If we keep a record of all the intermediate results, then we have a strategy. At each turn the player makes one of the plays giving the best result from his point of view. If we record the value of a play as $1,0,$ or $-1$ according to whether the first player wins, draws, or loses, then the first player always wants to make a play with the highest value, and the second player always wants to make a play with the lowest value. After a play is made, we can delete situations that are no longer possible.

EDIT

We evaluate at most $$\sum_{k=1}^{13}\binom{13}{k}^2=-1+\sum_{k=0}^{13}\binom{13}{k}^2=-1+\binom{26}{13}=10,400,599$$ configurations, by Vandermonde's identity, so it should be doable.

EDIT

I wrote a python script that deals a random game and evaluates it. I've run a handful of trials and each game was a draw. Unfortunately, the script takes a few minutes per game, so there's no chance of running a good-sized sample. If I get ambitious, I'll implement it in a systems programming language and run a real experiment.

Answer 2

This is not a complete answer but it shows that in a "smaller" game, who will win can depend on the distribution of cards.

Take only the pile with four $2$s, four $3$s, four $4$s, four $4$s, four Aces. Arrange decks like this: First deck has four $2$s, second four $3$s, and so on. It is clear that the first player has winning strategy.

To see that the second can have a winning strategy, arrange decks like this:

• deck $A$ consist of three $2$s and an Ace
• deck $B$ consist of three $3$s and an Ace
• deck $C$ consist of three $4$s and an Ace
• deck $D$ consist of three $5$s and an Ace
• deck $X$ consist of $2$, $3$, $4$ and $5$

It will not be hard that the second player has winning strategy. I will write shortly what moves can happen ignoring symmetry.

Case I:. Player one takes $2$ from $X$, player two responds with Ace from $B$. Game over for player one.

Case II:. Player one takes Ace from $A$, player two responds with $3$ from $X$. Game over for player one. So we are down to the only following case

Case III: Player one takes $2$ from $A$. Player two responds $3$ from $B$.

Case III.1. Player one takes $4$ from $C$, player two responds $5$ from $D$. Game over for player one.

Case III.2. Player one takes Ace from $C$, player two responds $5$ from $X$. Game over for player one.

Case III.3 Player one takes $4$ from $X$, player two responds Ace from $D$. Game over for player one.

This indicates that in the original game, probably both players can have winning strategies depending on the initial distribution of cards. Whether or not there is some "nice" property of distribution that will tell you who has the winning strategy, I don't know. I suspect the answer is "no" since most games, as verified by saulspatz end in draw.

Edit 1

It is easy to see that the original game can have both players as winners by expanding these distributions with decks of four $6$s, four $7$s, ..., four Kings. In the first arrangement it is clear that the first player can win. In the second whenever first player picks a card from first five decks, described as above, player two makes a counter move described as above. If first player chooses one of the remaining $8$ decks, player two chooses some other of the remaining $8$ decks, and since $8$ is even, player two will make the last move in those $8$ decks.

Edit 2

I wrongly imagined when it is a tie for the first part of the post, since in the first arrangement it is a tie, not win for player one. However, player one can have a winning strategy in $13$ cards game for the following configuration. Ace to $5$ as in example above. $6$ to $10$ same as Ace to $5$. And then four Jacks, four Queens, four Kings. Player one takes a Jack. At an point player two plays Ace to $5$, player one plays corresponding move in the same set. He will play the last move in that set as described above. Same for set $6$ to $10$. If player two takes Queen or King, player one takes the remaining of the two, so he is last in that set as well.

Considering this, it might not be possible to construct winning configuration for first player in smaller game, since he has to make two ranks unused in order to win.