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 research 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 reseach 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.
