Artigo Acesso aberto Revisado por pares

Chomp, Recurrences and Chaos(?)

2004; Taylor & Francis; Volume: 10; Issue: 13-15 Linguagem: Inglês

10.1080/10236190410001652720

ISSN

1563-5120

Autores

Doron Zeilberger,

Tópico(s)

Artificial Intelligence in Games

Resumo

In this article, dedicated with admiration and friendship to chaos and difference (and hence recurrence) equations guru Saber Elaydi, I give a new approach and a new algorithm for Chomp, David Gale's celebrated combinatorial game. This work is inspired by Xinyu Sun's "ultimate-periodicity" conjecture and by its brilliant proof by high-school student Steven Byrnes. The algorithm is implemented in a Maple package BYRNES accompanying this article. By looking at the output, and inspired by previous work of Andries Brouwer, I speculate that Chomp is chaotic, in a yet-to-be-made-precise sense, because the losing positions are given by "weird" recurrences.

Referência(s)