Extended Sprague-Grundy theory for locally finite games, and applications to random game-trees
- Resource Type
- Book
- Authors
- Martin, James B.
- Source
- Combinatorial Game Theory: A Special Collection in Honor of Elwyn Berlekamp, John H. Conway and Richard K. Guy. :343-366
- Subject
- Language
The Sprague-Grundy theory for finite games without cycles was extended to general finite games by Cedric Smith and by Aviezri Fraenkel and coauthors. We observe that the same framework used to classify finite games also covers the case of locally finite games (that is, games where any position has only finitely many options). In particular, any locally finite game is equivalent to some finite game. We then study cases where the directed graph of a game is chosen randomly and is given by the tree of a Galton-Watson branching process. Natural families of offspring distributions display a surprisingly wide range of behavior. The setting shows a nice interplay between ideas from combinatorial game theory and ideas from probability.