# Find the best strategy for a card game

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."

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.

• So, what I imagine here is that, you have narrowed down to a very few cards. But that is not the case, since I think you are mistaking losing with cannot pick a card type. Remember that, if player one cannot pick ace then player two, in his later moves, will also not able to pick ace. So if we have 13 cards, and for example; player one has a strategy to make sure that the number of "disabled card" even, then he still wins Commented Mar 24, 2020 at 3:19
• I did mistake losing to tie, but I hoped I explained that in edits. I will try to clarify once more. For complete deck of 52 cards, second player has winning strategy if Ace - 5 are arranged as described and other decks are four 6s, ..., four Kings. First player has winning strategy if Ace - 5, and 6 - 10 are arranged as described and other decks are four Jacks, four Queens, four Kings. Does this sound ok to you? Commented Mar 24, 2020 at 14:14
• I don't this is how the game works. In your Case 1, you say the game is over, but player 1 can choose a $3$ from pile B or a $4$ from pile $C$ or a $5$ from pile $D$. Commented Mar 24, 2020 at 18:14
• I didn't write it in full detail. For Case $1$, he can't choose $3$ from $B$, since Ace from $B$ is already taken. So, he can choose either $4$ from $C$, or $5$ from $D$. Suppose he takes $4$ from $C$, then player two responds with $5$ from $D$. Now it is game over for player one. Commented Mar 24, 2020 at 23:47
• @prosinac but I think that because you limited the game to only 5 cards, you have also limited the first person chance to bounce back, that is, playing a card that makes it impossible for the second person to win. I mean, if there are an even number of "disabled cards" then the first player win right? Commented Mar 25, 2020 at 8:14

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.

• @saulsptaz I appreciate your solving this, however, I will need more elaboration. First, it is not always "down to the last pile of 4 card". As you have realised, there can be a pile where the all the cards have already been picked. There can be two piles that cannot be picked as follow: 1 We pick the first 8 ranks as 2,3,4,5,6,7,8,9; 2 Now we have the two decks as follow: (2,2,4,5) and (7,8,3,6) for instance. This is absolutely possible. The second things is that I don't get why there are 13*13=169 possibilities at the end? Please explain this, thank you Commented Mar 6, 2020 at 3:57
• There are only $169$ possibilities (at most) because there are only $13$ ranks that can be the last ranks, and only $13$ piles that can be the last pile. Commented Mar 24, 2020 at 4:28
• Ok thanks for the explanation. It got a lot clearer now. Commented Mar 24, 2020 at 4:36
• @MinhTrungDang Actually, I think my script was computing the correct values, but due to a typo, I was printing the wrong ones! The very first game I tried after correcting this was a win for the first player! I'm still trying to convince myself that I've got it right this time. Commented Mar 25, 2020 at 21:43
• Yeah, now is the time when I would say "I told you" and drop a haha to this comment. The thing is now we should prove this my mathematics right? Or can we ever do this....? Commented Mar 26, 2020 at 3:17