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

zbMATH Open1490.91042arXiv2107.08428MaRDI QIDQ3390733FDOQ3390733

Authors:

Publication date: 25 March 2022

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Combinatorial game theory
• Random trees and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Infinite cyclic impartial games
• Strategy for a class of games with dynamic ties
• Title not available (Why is that?)
• Graphs and composite games
• The generalized Sprague-Grundy function and its invariance under certain mappings
• Galton–Watson games
• Probability. An introduction

Cited In (5)

• Title not available (Why is that?)
• Infinite cyclic impartial games
• Extended Sprague–Grundy theory for locally finite games, and applications to random game-trees
• A direct independence proof of Buchholz's Hydra Game on finite labeled trees
• Lit-only \(\sigma \)-game on pseudo-trees

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)