Algorithm on winning strategy of Winner (Simplified card game)

Question

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.

Answer 1

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.