A simplified version of card game Winner

Question

I've asked this problem in MathOverflow, without any satisfactory answer.

Consider the following two-player game, which is a simplification of the card game called Winner. (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.

Answer 1

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.