# A simplified version of card game Winner

Consider the following two-player game, which is a simplification of the card game called Winner. (The following formulation was taken from a comment by Guillaume Brunerie on MathOverflow.)

There are two players A and B. Each player has a set of cards (a subset of $\{1,\dots,n\}$), visible from both players. The aim of the game is to get rid of its own cards. The first player plays any card on the table, then the other player must play a (strictly) bigger card, and so on until one of the players cannot play or decides to pass. Then the cards on the table are discarded, and the other player start again by playing any card (which will be followed by a bigger card). And so on until one of the two players run out of cards and win the game.

I want to know the best strategy for the players (if he can win).

### Formal definition

Denote by $w(i,A,B)$ the configuration of the game where the set of the first player's cards is $A$, the set of the second player's cards is $B$, and the largest card on the table is $i$, where $i=0$ means that there is no card on the table. I would like an algorithm to compute, given $i,A,B$, whether the first player has a winning strategy in configuration $w(i,A,B)$.

Formally, I would like an algorithm to compute the function $f$ defined as follows:

Let $\mathbb{Z}_n = \left\{1, 2, \cdots, n\right\}$, $\mathrm{Bool} = \left\{\mathrm{False}, \mathrm{True}\right\}$.

Function $f:\;\left\{ 0, 1, \cdots, n \right\} \times 2^{\mathbb{Z}_n} \times 2^{\mathbb{Z}_n} \to \mathrm{Bool}$

where $$f ( i, A, B ) = \begin{cases} \mathrm{False} & B = \emptyset \\ \mathrm{True} & B \ne \emptyset \land \exists j \in A: j > i, f(j, B, A - \left\{j\right\}) = \mathrm{False} \\ \mathrm{True} & B \ne \emptyset \land f(0, B, A) = \mathrm{False} \\ \mathrm{False} & \textrm{otherwise} \end{cases}$$

### Wrong strategies

Here are some wrong strategies:

1. Always play the smallest card. Let $n = 3, A = \{1,3\}, B = \{2\}$, the winning strategy for player A in configuration $w(0, A, B)$ is to play card $3$. If player A plays card 1, he will lose.
2. Play the smallest card unless the other player has only one card. It is a stronger strategy than strategy 1, but it is also wrong. Only think about configuration $w(0, \{1, 4, 6, 7\}, \{2, 3, 5, 8\})$. If player A uses strategy 2, he'll lose: $1\rightarrow2\rightarrow4\rightarrow5\rightarrow6\rightarrow8\rightarrow\textrm{pass}\rightarrow3$, thus player A lose.
• This question is interesting, but please try to make it as readable as possible. For example, you do not have to copy Guillaume Brunerie’s comment verbatim including the “I think it is A that should be known to the player…” part, which is different from the assumption in your question and can only confuse readers. Also, please consider to remove the first formulation of the three: the second formulation gives an intuitive understanding, the third gives a formal definition, and I do not think that the first serves any purpose. Jun 20, 2012 at 15:18
• Possibly the best way to analyze this is to write a program that figures out the optimal moves for any position, and look for patterns. There is no a priori reason that this game should have a nice strategy. Jun 20, 2012 at 16:09
• I would start for a strategy with a small number of cards and work up from there. For example, if each player has 2 cards, then whichever player has the highest card wins, regardless of which player has the next turn. He plays the highest card, the other player must pass, then he plays his last card.
– Joe
Jun 20, 2012 at 19:44
• Can anybody help me to redescribe the GB's decription to follow postscript 1? I feel sorry that I'm not a native speaker and describing such complex game is out of my ability. Jun 21, 2012 at 2:48
• @Tsuyoshi: If player A always plays the smallest card, player B wins. If player A plays card 1, and doesn't always play the smallest card, player A can win. This means that there's a smaller counterexample to strategy 2 always winning. Jun 22, 2012 at 20:52

A related game was studied by Jeff Kahn, Jeff Lagarias and Hans Witsenhausen, in the series of articles Single-Suit Two-Person Card Play I, II, III, and On Laskar's Card Game. In the game they studied, each player has $n$ cards, dealt from $2n$ cards numbered $1$ $\ldots$ $2n$. Each trick consists of two cards, the higher card wins the trick, and the winner leads. The object is to take the most tricks.