Computing Remoteness Functions of Moore, Wythoff, and Euclid's games

Autor:	Boros, Endre, Gurvich, Vladimir, Makino, Kazuhisa, Vyalyi, Michael
Rok vydání:	2023
Předmět:	Mathematics - Combinatorics Computer Science - Computer Science and Game Theory 91A05 91A46 91A68
Druh dokumentu:	Working Paper
Popis:	We study remoteness function $\mathcal 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)$ is odd. The odd values of $\mathcal 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)$ for games Euclid and generalized Wythoff. For Moore's NIM we give a simple explicit formula for $\mathcal R(x)$ if it is even and show that computing it becomes an NP-hard problem for the odd values. Comment: 22 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2311.02685 Zobrazit plný text záznamu View this record from Arxiv