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 ?
Best Answer
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.