9
$\begingroup$

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.
$\endgroup$
  • 6
    $\begingroup$ This question is interesting, but please try to make it as readable as possible. For example, you do not have to copy Guillaume Brunerie’s comment verbatim including the “I think it is A that should be known to the player…” part, which is different from the assumption in your question and can only confuse readers. Also, please consider to remove the first formulation of the three: the second formulation gives an intuitive understanding, the third gives a formal definition, and I do not think that the first serves any purpose. $\endgroup$ – Tsuyoshi Ito Jun 20 '12 at 15:18
  • 5
    $\begingroup$ Possibly the best way to analyze this is to write a program that figures out the optimal moves for any position, and look for patterns. There is no a priori reason that this game should have a nice strategy. $\endgroup$ – Peter Shor Jun 20 '12 at 16:09
  • 2
    $\begingroup$ I would start for a strategy with a small number of cards and work up from there. For example, if each player has 2 cards, then whichever player has the highest card wins, regardless of which player has the next turn. He plays the highest card, the other player must pass, then he plays his last card. $\endgroup$ – Joe Jun 20 '12 at 19:44
  • $\begingroup$ Can anybody help me to redescribe the GB's decription to follow postscript 1? I feel sorry that I'm not a native speaker and describing such complex game is out of my ability. $\endgroup$ – Yai0Phah Jun 21 '12 at 2:48
  • 1
    $\begingroup$ @Tsuyoshi: If player A always plays the smallest card, player B wins. If player A plays card 1, and doesn't always play the smallest card, player A can win. This means that there's a smaller counterexample to strategy 2 always winning. $\endgroup$ – Peter Shor Jun 22 '12 at 20:52
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.