Nonlinear Dynamics in Combinatorial Games: Renormalizing Chomp

Authors

Eric J. Friedman, Cornell UniversityFollow
Adam S. Landsberg, Claremont McKenna College; Pitzer College; Scripps CollegeFollow

Document Type

Article

Department

WM Keck Science

Publication Date

6-11-2007

Abstract

We develop a new approach to combinatorial games that reveals connections between such games and some of the central ideas of nonlinear dynamics: scaling behaviors, complex dynamics and chaos, universality, and aggregation processes. We take as our model system the combinatorial game Chomp, which is one of the simplest in a class of "unsolved" combinatorial games that includes Chess, Checkers, and Go. We discover that the game possesses an underlying geometric structure that "grows" (reminiscent of crystal growth), and show how this growth can be analyzed using a renormalization procedure adapted from physics. In effect, this methodology allows one to transform a combinatorial game like Chomp into a type of dynamical system. Not only does this provide powerful insights into the game of Chomp (yielding a complete probabilistic description of optimal play in Chomp and an answer to a longstanding question about the nature of the winning opening move), but more generally, it offers a mathematical framework for exploring this unexpected relationship between combinatorial games and modern dynamical systems theory.

Comments

Previously linked to as: http://ccdl.libraries.claremont.edu/u?/irw,456

Publisher pdf reproduced with permission.

This article can also be found at http://link.aip.org/link/?CHAOEH/17/023117/1

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Recommended Citation

Friedman, E.J., and A.S. Landsberg. "Nonlinear Dynamics in Combinatorial Games: Renormalizing Chomp." Chaos 17.2 (2007): 023117. DOI: 10.1063/1.2725717