# Mathematical solution for a two-player single-suit trick taking game?

The question on games and mathematics that appeared recently on mathoverflow (Which popular games are the most mathematical?) reminded me of a problem I encountered some time ago : starting with the insane dream of completely solving the game of bridge with a nice mathematical theory, I ended up considering extremely simplified versions of bridge. One of them was as follows : there are only 2 players instead of 4, and instead of the usual deck there are only 2n cards numbered from 1 to 2n. Each player holds half of the deck, so this is a "complete information" game : each player knows exactly what is in his opponent's hand. There are no bids, just a sequence of n moves where each player drops a card ; as in bridge the strongest card wins the trick and the winner of the game is the player with the largest number of tricks in the end (take n odd to avoid draws). Also, the winner of the preceding trick is the first to play (for the very first move the first player is determined by some rule, random or other ; this is immaterial to the subsequent discussion).

This looks like a very basic kind of game, especially amenable to mathematization : for example the set of all initial positions is nicely indexed by the subsets $I$ of $\lbrace 1,2, \ldots , 2n\rbrace$ whose cardinality is $n$ (say $I$ is the set of cards held by the first player). I was however unable to answer the following questions :

• Is there an algorithm which, given the initial position, finds out which player will win if each one plays optimally ? What is the best strategy ?

• Has this game already been studied by combinatorialists ?
-
The Sprague-Grundy theorem might be applicable: en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem –  Qiaochu Yuan Feb 16 '10 at 21:24
Typo in second para - $I$ should range over subsets of $\{ 1, 2, \ldots, 2n \}$. –  Sam Nead Feb 16 '10 at 22:01
@Sam, I just corrected that. –  Alon Amit Feb 17 '10 at 0:15
Just a note: it is disadvantageous to play first, so I'm not sure whether the "natural" version should be that the winner of the previous trick plays first. –  Ori Gurel-Gurevich Feb 17 '10 at 1:00
@ Qiaochu : I'm afraid there is no "normal condition" here, so the Sprague-Grundy theorem is not applicable. –  Ewan Delanoy Feb 17 '10 at 11:49