Combinatorial Games with a Pass: A Dynamical Systems Approach
Title | Combinatorial Games with a Pass: A Dynamical Systems Approach |
Publication Type | Conference Paper |
Year of Publication | 2011 |
Authors | Morrison, R., Friedman E., & Landsberg A. S. |
Other Numbers | 3189 |
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 games 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. EJFs research has been supported in part by the NSF under grant CDI-0835706. |
URL | http://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 |