# Algorithm on winning strategy of Winner (Simplified card game)

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:

1. 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$.

2. 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')$

3. Here are some wrong strategies:

1. 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.
2. 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.
-
Just a little reformulation in natural language of the rules : there are two players A and B. Each player has a set of cards (a subset of $\{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. –  Guillaume Brunerie Jan 28 '12 at 7:45
And the notation $w(i,A,B)$ means that the card on the table is numbered $i$ (or $0$ if there is no card on the table), that my hand is $A$ and that the hand of the other player is $B$ (and I think that it is $A$ that should be known to the player, unless I’ve understood the rules in the wrong way) –  Guillaume Brunerie Jan 28 '12 at 7:51

What do you mean by best strategy? Given that the players don’t know the hand of the other player, it is impossible to know what will be a winning strategy.

For example, let’s suppose that I’m the first player and that my hand is {1, 4}.
If the hand of the other player is {4}, I win if I play 4 and I lose if I play 1.
But if the hand of the other player is {2, 3, 5}, I lose if I play 4 and I win if I play 1.

So if my hand is {1, 4}, there is no winning strategy, it depends on the hand of the other player.

(if I understood the rules correctly)

Edit: If you consider that both player know both hands, then the game is finite with perfect information, so you can draw the graph of all possible outcomes and determine recursively the winning and losing positions (as with all finite games with perfect information).

But perhaps there is a winning strategy more easily computable, I don’t know, I will try to see if there is one.

-
Thanks. I meant that when the player received a situation, he not only knew the set $A$ which meant his cards but also knew the set $B$ which meant the other player's cards. As I've written in the postscript in the text, $B$ is known to the player. In other words, either player always knows the cards in his hand and in the other player's hand. Thank you for your comment. –  Frank Science Jan 28 '12 at 8:08
I updated my answer. –  Guillaume Brunerie Jan 28 '12 at 12:41
@Barry Cipra : If one player pass, it is always better for the other player to play its smallest card than to pass –  Guillaume Brunerie Jan 29 '12 at 15:26
@Guillaume, it's not quite true that it's "always" better to respond to a pass by playing your smallest card. Suppose A and B are both holding a 1 and a 2. If A (foolishly) passes, then B should play his 2, not his 1. But I think the basic principle is correct: You should always play something (if you can) rather than nothing. (@Frank, I wasn't suggesting a scenario where one player always passes no matter what the other player does. I was suggesting the conceivability of a scenario where the first player to make an active move loses.) –  Barry Cipra Jan 30 '12 at 14:57
@Zsban, if A holds 1,2,3 and B holds 1,2,4 (and you're starting the game at 0), then A can win by playing 2, but loses if he plays 3. –  Barry Cipra Jan 31 '12 at 23:45