Infinite cyclic impartial games

DOI10.1016/S0304-3975(00)00074-8zbMATH Open0976.91008arXivmath/9809077OpenAlexW2070819446MaRDI QIDQ1589503FDOQ1589503

Authors: O. Rahat, Aviezri S. Fraenkel 

Publication date: 12 December 2000

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

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.

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

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

zbMATH Keywords

generalized Sprague-Grundy functioninfinite cyclic gameslocally path-bounded digraphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Partizan octal games: Partizan subtraction games
• Slow joins of loopy games
• Strategy for a class of games with dynamic ties
• Title not available (Why is that?)
• Loopy Games
• Graphs and composite games
• The generalized Sprague-Grundy function and its invariance under certain mappings
• Algebraic solutions of partizan games with cycles
• Strategies for compounds of partizan games
• Selective sums of loopy partizan graph games

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)