Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?
share|improve this question
    
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

1 Answer 1

up vote 14 down vote accepted

Yes, it has been studied by Johan Wästlund in A solution of two-person single-suit whist, which gives an efficient algorithm to compute the value of a position in this game (Theorem 10.1). He has also studied the more general situation of multiple suits, but with the restriction that each suit is split evenly between the two players, in Two-person symmetric whist. Here some familiar values from combinatorial game theory appear, reflecting the fact that breaking a new suit is generally disadvantageous to the player doing so.

share|improve this answer
1  
I was able to download the first paper from emis.de/journals/EJC/Volume_12/PDF/v12i1r43.pdf –  Gerry Myerson Feb 17 '10 at 2:26
    
Thanks Gerry ! I was able to download it also. –  Ewan Delanoy Feb 17 '10 at 11:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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