Puzzled: Games, Roles, Turns

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/GameofHex.html) is played on an 11×11 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 n x n game or the standard 11×11 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.

Back to Top

Back to Top

Back to Top

Back to top