<p>This should probably be a comment, but it's too long. </p>

<p>A related game was studied by Jeff Kahn, Jeff Lagarias and Hans Witsenhausen, in the series of articles <em>Single-Suit Two-Person Card Play I, II, III,</em> and <em>On Laskar's Card Game.</em> 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. </p>

<p>They proved a number of interesting facts about the optimal strategy, but were unable to find an efficient algorithm for optimal play, and were also unable to prove that it was NP-hard. </p>

<p>For the <em>misère</em> game, where each person tries to take the fewest number of tricks, they were able to give the optimal strategy.</p>

<p>For the most part, these results were obtained by first looking at the results of a computer program which found the optimal strategy for small instances, then looking for patterns to obtain conjectures, and finally proving these conjectures. I suspect that this would also be a fruitful approach to take for the OP's game.</p>

CC BY-SA 3.0
2012-06-24T02:30:53.173Z
2012-06-24T02:30:53.173Z
Peter Shor 
<p>I've asked this problem in <a href="https://mathoverflow.net/questions/86884">MathOverflow</a>, without any satisfactory answer.</p>

<p>Consider the following two-player game, which is a simplification of the card game called <a href="http://en.wikipedia.org/wiki/Winner_%28card_game%29" rel="nofollow noreferrer">Winner</a>.  (The following formulation was taken from a comment by Guillaume Brunerie on MathOverflow.)</p>

<p>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.</p>

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

<h3>Formal definition</h3>

<p>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)$.</p>

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

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

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

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

<h3>Wrong strategies</h3>

<p>Here are some wrong strategies:</p>

<ol>
<li>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.</li>
<li>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.</li>
</ol>

CC BY-SA 3.0
2012-06-20T15:18:30.813Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-20T16:09:49.947Z
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.
Peter Shor 
CC BY-SA 3.0
2012-06-20T19:44:41.467Z
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
CC BY-SA 3.0
2012-06-21T02:48:26.973Z
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.
Yai0Phah
CC BY-SA 3.0
2012-06-21T12:54:56.147Z
I tried to rewrite the whole question based on Guillaume Brunerie’s formulation.  Feel free to revert if you do not like it.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-21T12:57:24.023Z
I do not understand the explanation why strategy 2 in the “wrong strategies” part is incorrect.  How does player B win after player A plays card 1?  And what does “might have a winning strategy” mean?  (“might” means you are not sure if player A has a winning strategy or not, but if this is the case, it provides no information.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-21T15:31:11.247Z
@TsuyoshiIto Edited. Strategy is wrong, which doesn't mean player A would lose when he throw out $1$. I remember that player A has winning strategy, but it's too old-story, so I'll try to write a computer program to search for the winning strategy.
Yai0Phah
CC BY-SA 3.0
2012-06-22T11:44:13.687Z
@TsuyoshiIto You're right, but there's also a winning strategy for $7$. I wrote a simple program. [Here's](https://gist.github.com/2972260) my ugly code.
Yai0Phah
CC BY-SA 3.0
2012-06-22T20:52:50.720Z
@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.
Peter Shor 
CC BY-SA 3.0
2012-06-23T05:22:09.900Z
@PeterShor I can't get the meaning of the last sentence of your comment. There might be no nice strategy, but either there's a polynomial time algorithm to determine $f$, or it's impossible. I think this game is very famous, so it might have been studied.
Yai0Phah
CC BY-SA 3.0
2012-06-24T02:04:13.340Z
@Peter: Thanks!  Now I see that player A indeed has a winning strategy after playing card 1, if he is not forced to play according to strategy 2.
Tsuyoshi Ito
<gt.game-theory><card-games>
A simplified version of card game Winner
Yai0Phah
# A simplified version of card game Winner

(Asked by: username_0 on 2012-06-20)

I've asked this problem in [MathOverflow](https://mathoverflow.net/questions/86884), without any satisfactory answer.

Consider the following two-player game, which is a simplification of the card game called [Winner](http://en.wikipedia.org/wiki/Winner_%28card_game%29). (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.

**Tags:** gt.game-theory, card-games

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_0**: 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.  
> **username_1**: I tried to rewrite the whole question based on Guillaume Brunerie’s formulation.  Feel free to revert if you do not like it.  
> **username_1**: I do not understand the explanation why strategy 2 in the “wrong strategies” part is incorrect.  How does player B win after player A plays card 1?  And what does “might have a winning strategy” mean?  (“might” means you are not sure if player A has a winning strategy or not, but if this is the case, it provides no information.)  
> **username_0**: @TsuyoshiIto Edited. Strategy is wrong, which doesn't mean player A would lose when he throw out $1$. I remember that player A has winning strategy, but it's too old-story, so I'll try to write a computer program to search for the winning strategy.  
> **username_0**: @TsuyoshiIto You're right, but there's also a winning strategy for $7$. I wrote a simple program. [Here's](https://gist.github.com/2972260) my ugly code.  
> **username_2**: @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.  
> **username_0**: @PeterShor I can't get the meaning of the last sentence of your comment. There might be no nice strategy, but either there's a polynomial time algorithm to determine $f$, or it's impossible. I think this game is very famous, so it might have been studied.  
> **username_1**: @Peter: Thanks!  Now I see that player A indeed has a winning strategy after playing card 1, if he is not forced to play according to strategy 2.  

---

## 1 answers

### Answer by username_2 on 2012-06-24. Score: 4

This should probably be a comment, but it's too long.

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.

They proved a number of interesting facts about the optimal strategy, but were unable to find an efficient algorithm for optimal play, and were also unable to prove that it was NP-hard.

For the *misère* game, where each person tries to take the fewest number of tricks, they were able to give the optimal strategy.

For the most part, these results were obtained by first looking at the results of a computer program which found the optimal strategy for small instances, then looking for patterns to obtain conjectures, and finally proving these conjectures. I suspect that this would also be a fruitful approach to take for the OP's game.


---

