Combinatorial Games with a Pass: A Dynamical Systems Approach

TitleCombinatorial Games with a Pass: A Dynamical Systems Approach
Publication TypeConference Paper
Year of Publication2011
AuthorsMorrison, R., Friedman E., & Landsberg A. S.
Other Numbers3189
Abstract

By treating combinatorial games as dynamical systems, we are able to address alongstanding open question in combinatorial game theory, namely, how the introductionof a “pass” move into a game affects its behavior. We consider two well knowncombinatorial games, 3-pile Nim and 3-row Chomp. In the case of Nim, we observethat the introduction of the pass dramatically alters the game’s underlying structure,rendering it considerably more complex, while for Chomp, the pass move is found tohave relatively minimal impact. We show how these results can be understood by recastingthese games as dynamical systems describable by dynamical recursion relations.From these recursion relations we are able to identify underlying structural connectionsbetween these “games with passes” and a recently introduced class of “generic (perturbed)games.” This connection, together with a (non-rigorous) numerical stabilityanalysis, allows one to understand and predict the effect of a pass on a game.

Acknowledgment

This paper is dedicated to the memory of David Gale, who originally suggested this problemto us. EJF’s research has been supported in part by the NSF under grant CDI-0835706.

URLhttp://www.icsi.berkeley.edu/pubs/algorithms/combinatorialgames11.pdf
Bibliographic Notes

Proceedings of the 4th International Conference on Chaotic Modeling, Simulation, and Applications (CHAOS2011), Agios Nikolaos, Greece

Abbreviated Authors

R. Morrison, E. Friedman, and A. Landsberg

ICSI Research Group

Algorithms

ICSI Publication Type

Article in conference proceedings