Opinion
Computing Applications Last byte

Puzzled: Solutions and Sources

Last month (Aug. 2013) you needed to win several chess games in a row, alternately playing white and black, and had to decide with which color you should start.
Posted
  1. Introduction
  2. 1. White or black?
  3. 2. Still need two in a row.
  4. 3. 10 in a row.
  5. Author
  6. Footnotes
Peter Winkler

The first puzzle was adapted from Martin Gardner’s Colossal Book of Short Puzzles & Problems (W. W. Norton & Co., New York, 2006), Problem 2.10. In his solution, Gardner observed since you need to win two in a row of three games, you must win the middle game; moreover, you must win a game with the black pieces, so having two chances to do it seemed like a good idea. There are two arguments for playing black first, even though it means you get to play white only once. In fact, neither argument is conclusive by itself, nor do they constitute a proof even together. Gardner offered an algebraic proof that starting with black is best, but extending it to the second and third puzzles would be too horrible to contemplate. Is there a watertight argument that circumvents algebra? Yes. Probabilists sometimes use a technique called "coupling" in which random events are tied to the same experiment, and it can be used to good effect here.

Back to Top

1. White or black?

Imagine you play four games against Ioana, alternating white-black-white-black, or WBWB. You must still win two in a row and decide ahead of time whether to discount the first game or the last. This question is clearly equivalent to the earlier one, but now you are in a position to limit the discussion to outcomes in which the decision makes a difference: namely, WWLX and XLWW. In words, what you decided matters only if you win the first two games and lose the third (in which case you should have discounted the fourth) or if you win the last two games and lose the second (in which case you should have discounted the first). The first two and last two games are both WB, so it comes down to comparing the probability of losing the third game with the probability of losing the second game. Since you are black in the second game, the second scenario is more likely, so discount the first game; that is, play BWB.

Back to Top

2. Still need two in a row.

Here you play 17 games, still needing two wins in a row. Note if you start with black you are black, not white, in the middle (ninth) game. Does that change the answer? No. Assume you actually play 18 games, WBWB…WB, and must decide in advance whether to discount the first or last game. Your decision matters only when you win the first two games, lose the third, and win no other two in a row (in which case, you should have discounted the last game) or you win the last two, lose the 15th, and win no other two in a row (in which case you should have discounted the first game). It is easy (but not as easy as before) to see the second scenario as more likely, so again start with black.

Back to Top

3. 10 in a row.

Here you must win 10 in a row out of 49 games, but the argument hardly changes. Begin with black. In general, if the total number of games played is even, time-symmetry implies it does not matter whether you began with white or black. If the total games played and the number of consecutive wins needed are both odd, then, if you made it this far, you should have no trouble showing one should always start with white.

Back to Top

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More