Infinite cyclic impartial games

DOI10.1016/S0304-3975(00)00074-8MaRDI QIDQ1589503zbMATH OpenOpenAlexFDO

Authors O. Rahat, Aviezri S. Fraenkel

Publication date 12 December 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

generalized Sprague-Grundy functioninfinite cyclic gameslocally path-bounded digraphs

Mathematics Subject Classification ID

2-person games (91A05) Combinatorial games (91A46)

Abstract: We define the family of {it locally path-bounded} digraphs, which is a class of infinite digraphs, and show that on this class it is relatively easy to compute an optimal strategy (winning or nonlosing); and realize a win, when possible, in a finite number of moves. This is done by proving that the Generalized Sprague-Grundy function exists uniquely and has finite values on this class.

Recommendations

• The generalized Sprague-Grundy function and its invariance under certain mappings
• Extended Sprague-Grundy theory for locally finite games, and applications to random game-trees
• Extended Sprague–Grundy theory for locally finite games, and applications to random game-trees
• Infinite games played on finite graphs
• Computing strategies for graphical Nim

Cites work

• scientific article; zbMATH DE number 3136760 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 3521877 (Why is no real title available?)
• scientific article; zbMATH DE number 3520176 (Why is no real title available?)
• Algebraic solutions of partizan games with cycles
• Graphs and composite games
• Loopy Games
• Partizan octal games: Partizan subtraction games
• Selective sums of loopy partizan graph games
• Slow joins of loopy games
• Strategies for compounds of partizan games
• Strategy for a class of games with dynamic ties
• The generalized Sprague-Grundy function and its invariance under certain mappings

Cited in

(6)

• Extended Sprague-Grundy theory for locally finite games, and applications to random game-trees
• Learning of winning strategies for terminal games with linear-size memory
• Impartial games with entailing moves
• Sprague-Grundy functions for certain infinite acyclic graphs
• The generalized Sprague-Grundy function and its invariance under certain mappings
• Cyclical games with prohibitions

This page was built for publication: Infinite cyclic impartial games

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