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

Abstract

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.

22 pages