Subtle Logic, Winning Game

Seemingly simple games can serve as thought-provoking exercises in mathematical logic. They can provide deep insights into subtle issues that confront logicians who are interested in the foundations of mathematics.

So-called Ehrenfeucht games have proved particularly useful for tackling certain aspects of mathematical logic. They were developed in the 1960s by Andrzej Ehrenfeucht, who is now a computer science professor at the University of Colorado in Boulder.

Ehrenfeucht games can also be studied for their own sake as interesting and often surprisingly subtle games, an approach adopted by Caroline Nguyen of Stuyvesant High School in New York City. Nguyen was one of 40 finalists in the 2001 Intel Science Talent Search (STS). Her goal was to identify, for a specific type of two-player Ehrenfeucht game, the starting positions in which the player moving second will always win.

The game is played with two sequences of zeros and ones. Each sequence can be of any length.

In the opening round of a two-round game, the first player (dubbed "Spoiler") picks a digit (0 or 1) in one of the two sequences. The second player (named "Duplicator") must "duplicate" Spoiler's move by finding a match--a digit of the same value--in the sequence the Spoiler did not select from.

In the second (and final) round, Spoiler picks another digit not yet selected from either of the two sequences. This time, Duplicator must match the value of the digit selected in Spoiler's move and select one that lies on the same side (to the right or left) of the previously selected digit as the one chosen by Spoiler.

Here's a sample game:

A: 0 0 1 1 0 1 0 1

B: 0 1 1 0 0 1

Suppose Spoiler selects the second digit in sequence A:

A: 0 0 1 1 0 1 0 1

B: 0 1 1 0 0 1

In response, Duplicator selects the fourth digit in sequence B:

A: 0 0 1 1 0 1 0 1

B: 0 1 1 0 0 1

In the second round, Spoiler selects the second digit in sequence B:

A: 0 0 1 1 0 1 0 1

B: 0 1 1 0 0 1

This move is to the left of the previous move played in sequence B. To duplicate Spoiler's second move and win the game, Duplicator must select a "1" to the left of the previous move played on sequence A (Spoiler's first move). However, there is only a "0" to the left of Spoiler's first move. Duplicator has no available move, so she loses.

Nguyen notes that in this particular game, Duplicator could have won if Spoiler had not made the best possible move in the first round. For example, if Spoiler had instead selected the fourth digit, there would be sequences of moves that would give Duplicator the victory.

To analyze the game, Nguyen assumed that each player always makes the best possible move. Then, examining the key characteristics of all possible sequences, she found that a given sequence belongs to one of 78 distinct families, or equivalence classes. Duplicator can always win if the both sequences in a given game belong to the same class.

It turns out, for example, that two equivalent sequences must have the same first digit and the same last digit. If the first digits of the two sequences are different, Spoiler wins the game.

Future research could extend this analysis to Ehrenfeucht games having more than two rounds or more than two sequences. "Furthermore, one could consider a game with sequences containing the digits 0, 1, and 2," Nguyen notes.

Nguyen's work is one manifestation of her longstanding love for rigorous and creative mathematical proofs. Because of her fascination with the idea of gathering economic data through statistical sampling and modeling human behavior through mathematical economics, she studied game theory and statistics at the Harvard Summer School. Nguyen got the idea of studying Ehrenfeucht games from mathematician Joel Spencer of New York University, but she did the analysis entirely on her own.

Like most research in pure mathematics, "my STS research and any future research [I might do] during and after college most probably will not find practical applications immediately," Nguyen remarks. In the long term, however, such work could lead to some practical benefit; for example, in the development of better modeling techniques for complex economic systems.

Ehrenfeucht himself now focuses his attention on mathematical biology and mathematics education. He and Pat Baggett of New Mexico State University have developed math and technology courses for elementary school teachers. They also invented a strategy game called Tic Tac Twice, which is now available commercially.

References:

Information about the 2001 Intel Science Talent Search and the 40 finalists is available at http://www.sciserv.org/sts/press/20010131.asp and http://www.sciserv.org/sts/60sts/finalist.asp. A brief biography of Caroline Nguyen can be found at http://www.sciserv.org/sts/60sts/Nguyen.asp.

You can learn more about the strategy game Tic Tac Twice, invented by Andrzej Ehrenfeucht and Pat Baggett, at http://www.aristoplay.com/tic.htm and http://www.cs.colorado.edu/~main/projects/tictactwice.html. Information about their "Breaking Away from the Mathbook" project can be found athttp://math.nmsu.edu/breakingaway/.

Ivars Peterson is the mathematics/computer writer and online editor at Science News (http://www.sciencenews.org). He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, Fatal Defect, and The Jungles of Randomness. He also writes for the children's magazine Muse (http://www.musemag.com) and is working on a book about math and art.

NEW! NEW! NEW!

Math Trek 2: A Mathematical Space Odyssey by Ivars Peterson and Nancy Henderson. For children ages 10 and up. New York: Wiley, 2001. ISBN 0-471-31571-0. $12.95 USA (paper).