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.

Review text

The authors investigate the generalized Sprague-Grundy function for combinatorial games on locally path-bounded infinite cyclic graphs. \textit{C. Smith} [J. Comb. Theory 1, 51-81 (1966; Zbl 0141.36101)] had noticed that a transfinite generalization of the remoteness function could be used to determine optimal strategies for combinatorial games on arbitrary graphs. This function was further investigated by \textit{A. S. Fraenkel} and \textit{Y. Yesha} [J. Comb. Theory, Ser. A 43, 165-177 (1986; Zbl 0622.05030)] for the case of finite cyclic graphs. In general, Smith's function takes transfinite ordinal values. The authors of the paper under review say that ``it is easier to compute with finite than with transfinite ordinals (p.~14), therefore they try to find a class of (infinite) graphs on which the generalized Sprague-Grundy function takes only finite values. They show that for every locally path-bounded graph there is a generalized Sprague-Grundy function with finite values.

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

• Algebraic solutions of partizan games with cycles
• Graphs and composite games
• 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?)
• 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)

• 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
• Impartial games with entailing moves
• Learning of winning strategies for terminal games with linear-size memory
• Sprague-Grundy functions for certain infinite acyclic graphs
• 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)