Communications of the ACM
Last byte
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 runningcaught 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 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 worldPiet Hein and John Nashthe 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 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.
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
©2011 ACM 0001-0782/11/0500 $10.00
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.
No entries found