Extended Sprague-Grundy theory for locally finite games, and applications to random game-trees

zbMATH Open1490.91042MaRDI QIDQ3390733FDOQ3390733

Authors

Publication date 25 March 2022

Full work available at URL https://arxiv.org/abs/2107.08428

Mathematics Subject Classification ID

Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Games involving graphs (91A43) Combinatorial games (91A46)

Abstract: For a collection of papers in memory of Elwyn Berlekamp (1940-2019), John Conway (1937-2020), and Richard Guy (1916-2020). 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 behaviour. The setting shows a nice interplay between ideas from combinatorial game theory and ideas from probability.

Recommendations

• Extended Sprague–Grundy theory for locally finite games, and applications to random game-trees
• Infinite cyclic impartial games
• Computing strategies for graphical Nim
• The generalized Sprague-Grundy function and its invariance under certain mappings
• scientific article; zbMATH DE number 3900780

Cites work

• scientific article; zbMATH DE number 3124339 (Why is no real title available?)
• scientific article; zbMATH DE number 3520176 (Why is no real title available?)
• scientific article; zbMATH DE number 2004829 (Why is no real title available?)
• Combinatorial game theory
• Galton–Watson games
• Graphs and composite games
• Infinite cyclic impartial games
• Probability. An introduction
• Random trees and applications
• Strategy for a class of games with dynamic ties
• The generalized Sprague-Grundy function and its invariance under certain mappings

Cited in

(7)

• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Combinatorial games on multi-type Galton-Watson trees
• Infinite cyclic impartial games
• A direct independence proof of Buchholz's Hydra Game on finite labeled trees
• Lit-only \(\sigma \)-game on pseudo-trees
• Extended Sprague–Grundy theory for locally finite games, and applications to random game-trees
• scientific article; zbMATH DE number 7614167 (Why is no real title available?)

This page was built for publication: Extended Sprague-Grundy theory for locally finite games, and applications to random game-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3390733)