17
$\begingroup$

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 ?
$\endgroup$
5
  • $\begingroup$ The Sprague-Grundy theorem might be applicable: en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem $\endgroup$ Feb 16, 2010 at 21:24
  • $\begingroup$ Typo in second para - $I$ should range over subsets of $\{ 1, 2, \ldots, 2n \}$. $\endgroup$
    – Sam Nead
    Feb 16, 2010 at 22:01
  • $\begingroup$ @Sam, I just corrected that. $\endgroup$
    – Alon Amit
    Feb 17, 2010 at 0:15
  • $\begingroup$ 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. $\endgroup$ Feb 17, 2010 at 1:00
  • $\begingroup$ @ Qiaochu : I'm afraid there is no "normal condition" here, so the Sprague-Grundy theorem is not applicable. $\endgroup$ Feb 17, 2010 at 11:49

1 Answer 1

21
$\begingroup$

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.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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