Computing remoteness functions of Moore, Wythoff, and Euclid’s games

Endre Boros (), Vladimir Gurvich (), Kazuhisa Makino () and Michael Vyalyi ()
Additional contact information
Endre Boros: Rutgers University
Vladimir Gurvich: Rutgers University
Kazuhisa Makino: Kyoto University
Michael Vyalyi: National Research University

International Journal of Game Theory, 2024, vol. 53, issue 4, No 11, 1315-1333

Abstract: Abstract We study remoteness function $${\mathcal {R}}$$ R of impartial games introduced by Smith in 1966. The player who moves from a position x can win if and only if $${\mathcal {R}}(x)$$ R ( x ) is odd. The odd values of $${\mathcal {R}}(x)$$ R ( x ) show how soon the winner can win, while even values show how long the loser can resist, provided both players play optimally. This function can be applied to the conjunctive compounds of impartial games, in the same way as the Sprague-Grundy function is applicable to their disjunctive compounds. We provide polynomial algorithms computing $${\mathcal {R}}(x)$$ R ( x ) for games Euclid and generalized Wythoff. For Moore’s NIM we give a simple explicit formula for $${\mathcal {R}}(x)$$ R ( x ) if it is even and show that computing it becomes an NP-hard problem for the odd values.

Keywords: Impartial games; Sprague-Grundy function; Smith’s remoteness function; NP completeness; Polynomial algorithm (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-024-00914-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:53:y:2024:i:4:d:10.1007_s00182-024-00914-2

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-024-00914-2

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().