It’s hard to imagine a simpler two-player game than Chomp. Start by laying out a rectangular array of cookies. The players take turns picking a cookie, each time removing the chosen cookie and all cookies above and to the right of it. Each move is like taking a square or rectangular bite out of the array. The loser is the player forced to take the poison cookie—the one in the lower left-hand corner.
Though simple, the game is both intriguing and maddeningly frustrating. Mathematicians have proved that the first player can always win. But the proof provides no hint which first moves lead to guaranteed wins. Indeed, nobody has yet come up with an efficient general strategy for succeeding at Chomp.
Winning strategies are known for only two cases. When the array is a square, the first player starts by selecting the cookie that’s diagonally next to the poison cookie. This bite leaves one row and one column, with the poison cookie at the vertex. From that point on, the first player takes from one line whatever his or her opponent takes from the other. Eventually, the second player must take the poisoned piece.
When the array is two columns wide (2 by n), even if it’s not a square, the first player can always win by taking the cookie at the top right so that one of the columns is one cookie shorter than the other. From then on, the first player always plays to restore this situation. The same strategy works for an array two rows high where the first move makes one row one cookie shorter than the other.
Looking beyond these simple scenarios, physicist Adam S. Landsberg of Claremont Mckenna, Pitzer, and Scripps Colleges in Claremont, Calif., and computer scientist Eric J. Friedman of Cornell University provide new evidence of Chomp’s complexity. They reveal that the game has an underlying geometric structure that changes in a manner reminiscent of crystal growth.
By using mathematical tools originally developed for calculating properties of physical systems, Friedman and Landsberg show that the exact location of winning and losing cookies in Chomp varies unpredictably with small changes in the size of the initial array. Nonetheless, they make probabilistic predictions about where a winning position is most likely to be found.
Landsberg described the findings at the Dynamics Days 2006 conference on chaos and nonlinear dynamics, held earlier this year in Bethesda, Md.
“This is a fascinating breakthrough that gives lots of global insight into an otherwise [probably] intractable game,” says mathematician Doron Zeilberger of Rutgers University in New Brunswick, N.J.
Moreover, such a physics-based approach opens a new line of attack for understanding games that are more complicated, Landsberg says. In economics, for example, it may provide insights into online auctions, bargaining strategies, and other gamelike situations.
Strategic stealth
Chomp was invented in the early 1970s by mathematician and economist David Gale of the University of California, Berkeley. Recreational math columnist Martin Gardner was the first person to call it “Chomp,” and the name stuck.
Chomp is an example of a combinatorial game, in which nothing is hidden from the players and no chance is involved. Chess, Go, checkers, tic-tac-toe, and dots-and-boxes also belong to this category.
However, Chomp has an important difference from chess and many other combinatorial games. In Chomp, any move that’s legal at any time during a game would have been legal as an opening move.
Gale took advantage of this characteristic to prove that there’s always a way that the first player can win. He argues, suppose that the first player makes a certain move. There are two possibilities. This move is going to produce either a win or a loss. If it’s a losing move for the first player, the second player must have a move that sets up a win.
But no matter what corner the second player bites off, the first player could have set up the same pattern in the first move. So, there must always be a winning move for the first player. Of course, in a real game, the first player may make mistakes and consequently lose.
Gale used a computer to find the winning moves for arrays that are 3 cookies wide and up to 100 cookies long (3 by n). He found that each of these arrays has a unique winning first move. About 58 percent of the winning moves are two-rows deep, and 42 percent are one row deep. Gale also noted that as n increases, both one-row and two-row winning moves stay the same or increase in width.
But he found one exception. The winning first move on the 3-by-88 rectangle is 2 by 36, which is one unit less than the winning 2-by-37 move on the 3-by-87 rectangle.
Such quirks led Gale to write, “Phenomena like this lead one to believe that a simple formula for the winning strategy might be quite hard to come by.”
There were more broken patterns to come. Subsequent computer investigations by others, for example, showed that not every rectangle has a unique winning move. For example, 8-by-10 and 6-by-13 grids each have two winning moves.
Interestingly, Gale later learned that his game wasn’t entirely his invention. Rather, it’s a special case of a number game invented by mathematician Fred Schuh of the Delft Technical College in the Netherlands in 1950. In Schuh’s game, two players agree on a large number, then make a list of all the divisors of the number, including the number itself but excluding 1. They then take turns crossing out a divisor and all its divisors. The person forced to take the number itself loses.
Experimental math
When Zeilberger learned about Chomp, he decided that the game would be an ideal problem for illustrating the role that computers can play in mathematical research. “I found it a great case study for computer-generated, rigorous experimental mathematics,” Zeilberger says. In effect, a computer is programmed to first conjecture a pattern, then prove it rigorously all by itself.
Zeilberger focused on the 3-by-n case. For a given rectangle, three numbers (x, y, z), describe the configuration of the cookies at any stage in the game, where x specifies the number of columns of height three, y specifies the number of columns of height two, and z the number with height one. Each set of three numbers represents a location in three-dimensional space, and such a position can be classified as either a winner (a player starting from that point can always force a win) or a loser.
Computer investigations of arrays of numbers that represent winning positions for rectangles of different lengths reveal some disorder. But winning positions aren’t scattered completely at random, and there are also strong hints of recurring patterns.
In 2002, Steven Byrnes, then a senior at Roxbury Latin School in West Roxbury, Mass., proved a powerful result about combinatorial games. He showed that Chomp and various other games have a common structure. He found repeating patterns for winning positions in these games, when they’re looked at in the right way.
Byrnes’ “approach was very useful in proving qualitative results,” Zeilberger notes. He now refers to Byrnes’ analysis as a significant step in making sense of these games. For this work, Byrnes was a finalist in the 2003 Intel Science Talent Search and winner of the Siemens Competition for high school students.
Crystal growth
For the sake of simplicity, Landsberg and Friedman last year focused on three-row Chomp, as Zeilberger had done. They also employed Zeilberger’s scheme for characterizing winning and losing positions by three coordinates.
By plotting points representing winning positions, the researchers visualized what was happening. For a given value of x, each plot—which they called a sheet—shows the y and z values of possible winning positions. The researchers could then see what happens to the patterns, from sheet to sheet, as x increases.
Landsberg and Friedman created visualizations of a special subset of the game’s winning positions, known as instant winners. A position is considered an instant winner if nearby moves would lead to a losing position with a smaller x value.
“Once we got going, we were quite fortunate—and frankly surprised—at how rapidly the whole problem broke open, allowing us to identify a crystal-like geometric structure underlying the game,” Landsberg says.
The growth of the instant-winner sheets with increasing x is similar to certain crystal-growth and aggregation processes found in physics. In each case, the structures grow through the accumulation of new points along current boundaries. Moreover, the structure on a large scale resembles the small-scale structure. In the case of Chomp, the geometry of winning positions for small values of x and winning positions for large values of x is roughly the same, after a suitable change in scale.
This geometric similarity on different scales permitted the researchers to use mathematical methods known as re-normalization techniques. These tools have been used with great success in various branches of modern physics, from statistical mechanics and particle physics to nonlinear dynamics, which is popularly known as chaos theory. With the tools, physicists calculate the properties of objects or physical systems that are geometrically similar on different scales.
“To the best of my knowledge,” Landsberg says, “this nonlinear-dynamics/physics approach to combinatorial games is something of a radical departure from what the folks who work on such games normally do.”
As a result of their analysis, Landsberg and Friedman provide a unified, global description of the overall structure of Chomp and related games. One immediate consequence has been to settle some conjectures concerning Chomp.
The researchers show, for example, that all 3-by-n rectangles have a unique winning position. Previously, computer searches had demonstrated that this was true only for arrays up to 130,000 columns long.
The researchers also provide a probabilistic answer to what the opening move should be in a given situation. So, given a combinatorial game’s geometric structure, it may be possible to efficiently zero in on areas where winning moves are most likely to lie.
New pathways
Going beyond Chomp, Landsberg and Friedman conjecture that re-normalization methods can extract probabilistic information about winning any given combinatorial game, even when no simple formula or efficient algorithm appears to be available for computing winning positions.
This suggests a natural pathway toward a new class of algorithms for solving a wide range of combinatorial games. “Finding good algorithms for solving or approximating [simple combinatorial games] is a first step toward understanding the much more complex games that arise at the intersection of computer science and economics,” Landsberg says.
Moreover, one of the hallmarks of dynamical systems and chaos theory is the concept of sensitivity to initial conditions. In effect, one can’t predict the long-term behavior of a dynamical system because of the rapid growth of small uncertainties present at a system’s setup. Because combinatorial games exhibit a related behavior, it’s also possible to characterize a game’s sensitivity to, for example, apparently minor rule changes and to classify games on the basis of that trait. For example, Chomp gives a different geometric representation than the game Nim, where players alternately remove items from three piles (see cover, above).
“Our re-normalization technique for games is not a formal proof,” Landsberg notes. Although re-normalization methods work astonishingly well in physics applications, they aren’t mathematically rigorous.
Whether this novel, physics-based approach to combinatorial games is broadly applicable is uncertain at this stage, Landsberg says. Chomp and its variants represent just a handful of all combinatorial games.
The new results for Chomp don’t even give you a foolproof strategy for winning. But they do show why it’s hard to find the winning move.
