Here's an introduction to the ordinary Winner (card game):

http://en.wikipedia.org/wiki/Winner_(card_game)

I'm thinking about a simplification of the game.

** I've copied this problem to cstheory **

It is a two-player game.

We use $w(i, A, B)$ to describe a situation. ($i \in \mathbb{Z}, i \ge 0$, $A, B \subseteq\left\{1, 2, \cdots, n\right\}$)

Every time, one of the two players will receive a situation $w(i, A, B)$. (Postscript: $B$ is known to the player)

If $B = \emptyset$, the player loses.

Otherwise the player have two choices.

He could throw either $w(0, B, A)$, which means pass, or $w(j, B, A - \{j\})$, where $j \in A, j > i$, to the other player.

The game starts with the first player receiving $w(0, A_0, B_0)$.

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

Postscript:

We can describe it more formal.

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 ) = \left\{ \begin{array}{ll} \mathrm{False} & B = \emptyset \\\\ \mathrm{True} & \exists j \in A: j > i, f(j, B, A - \left\{j\right\}) = \mathrm{False} \\\\ \mathrm{True} & f(0, B, A) = \mathrm{False} \\\\ \mathrm{False} & \textrm{otherwise} \end{array} \right. $$ Try to find out an algorithm to calculate $f$.

Ordering $\mathrm{Bool}$ with $\mathrm{False} < \mathrm{True}$, we can claim that $w(i, A, B)$ is better than $w(i', A', B')$ if and only if $f(i, A, B) \ge f(i', A', B')$

Here are some wrong strategies:

- Each time throw the smallest card. Let $n = 3, A = \left\{1,3\right\}, B = \left\{2\right\}$, the winning strategy for $w(0, A, B)$ is throw $w(3, B, A - \left\{3\right\})$ to the other. If he throw $w(1, B, A - \left\{1\right\})$, he will lose.
- Each time throw the smallest card except when the other player only has one card. It is a stronger strategy than 1, but it is also wrong. Only think about $w(0, \left\{1, 4, 6, 7\right\}, \left\{2, 3, 5, 8\right\})$. You found that if you keep strategy 2, you will lose, and there's a winning strategy when you throw the card $7$ at first.

`$\{1,\dots,n\}$`

) and 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. $\endgroup$ – Guillaume Brunerie Jan 28 '12 at 7:45