last byte
DOI: 10.1145/1941487.1941514
Peter Winkler

hexgame.pdf 1 3/16/11 1: 14 PM

Puzzled
Games, Roles, turns
Welcome to three new puzzles. Solutions to the first two will be
published next month; the third is (as yet) unsolved. In each, the issue
is how your intuition matches up with the mathematics.

The theme is games. The twist is a little bit of role-switching, taking the randomness out of poker and putting it into chess.

1.Tired of the vagaries of the random deal, Alice and Bob embark on a game of deterministic draw poker. The 52 cards are spread out face up. Alice chooses five; then Bob chooses five. Alice can now discard any number of cards (which go out of play) and draw a like number, so she finishes with five cards. It’s then Bob’s turn to draw; he has the same options. All actions are deterministic and seen by both players. Finally, Alice and Bob compare hands. Since Alice had the advantage of going first, Bob is deemed the winner if the hands are equally good. Who wins with best play?

2.Clarissa, a computer science major and
president of her university’s
chess club, decides to program
her laptop to play random
chess. At each position, all
possible legal moves are
computed, with one chosen
uniformly at random. The
program is designed to quit
if and only if a checkmate or
stalemate is achieved or if
only the two kings remain on
the board. The following day,
Clarissa finds the program
is still running—caught in a
loop. How could this happen?

3.The game of hex (see, for example, http://
mathworld.wolfram.com/
Gameof Hex.html) is played on
an 11x11 diamond cut from a
hexagonal grid; the figure here
is of a game, which, with best
play, will be won by the red
player. Invented independently
in the 1940s by two beautiful
minds on different sides of
the world—Piet Hein and John
Nash—the game is played by
alternately placing red and
blue stones on the hexagonal
cells. Playing red, Alice makes
the first move, intending to
create an uninterrupted path
of red stones from left to
right. Playing blue, Bob tries
to create a path of blue stones
from top to bottom. It is not
difficult to see that only one
player can succeed, and that by
the time the board is filled one
player must succeed. Also not
difficult to see is that the first
player (Alice) has a winning
strategy. Game theory tells us
that either Alice or Bob has
such a strategy, but it can’t be
Bob because an extra red stone
on the board can never hurt
Alice. The problem is no one
has been able to devise such a
strategy (either for the general
nx n game or the standard
11x11 game). Your problem,
however, is potentially simpler
than devising a winning
strategy: Prove the eminently
plausible statement that one of
Alice’s winning first moves is
the center cell.

All readers are encouraged to submit prospective puzzles for future columns to [e-mail]. Peter Winkler ( [e-mail]) is Professor of Mathematics and of Computer Science and albert Bradley Third Century Professor in the Sciences at Dartmouth College, Hanover, nH.