# 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. Jan 28, 2012 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) Jan 28, 2012 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.
– user20948
Jan 28, 2012 at 8:08
• I updated my answer. Jan 28, 2012 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 Jan 29, 2012 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.) Jan 30, 2012 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. Jan 31, 2012 at 23:45