More on the Sprague–Grundy function for Wythoff's game

Summary

Abstract. We present two new results on Wythoff's Grundy function G. The first one is a proof that for every integer g > 0, the g-values of G are within a bounded distance to their corresponding 0-values. Since the 0-values are located roughly along two diagonals, of slopes ø and ø⁻¹, the g-values are contained within two strips of bounded width around those diagonals. This is a generalization of a previous result by Blass and Fraenkel regarding the 1-values.

Our second result is a convergence conjecture and an accompanying recursive algorithm. We show that for every g for which a certain conjecture is true, there exists a recursive algorithm for finding the n-th g-value in O(log n) arithmetic operations. Our algorithm and conjecture are modifications of a similar result by Blass and Fraenkel for the 1-values. We also present experimental evidence for our conjecture for small g.

Introduction

The game of Wythoff is a two-player impartial game played with two piles of tokens. On each turn, a player removes either an arbitrary number of tokens from one pile (between one token and the entire pile), or the same number of tokens from both piles. The game ends when both piles become empty. The last player to move is the winner.

Wythoff's game can be represented graphically with a quarter-infinite chess-board, extending to infinity upwards and to the right (Figure 1).