Book contents
More on the Sprague–Grundy function for Wythoff’s game
Published online by Cambridge University Press: 28 February 2011
Summary
We present two new results on Wythoff’s Grundy function 𝒢 The first one is a proof that for every integer g ≥ 0, the g-values of are within a bounded distance to their corresponding 0-values. Since the 0-values are located roughly along two diagonals, of slopes φ and φ1, 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.
The game of Wythoff [10] 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 chessboard, extending to infinity upwards and to the right . We number the rows and columns sequentially 0, 1,2,..... A chess queen is placed in some cell of the board. On each turn, a player moves the queen to some other cell, except that the queen can only move left, down, or diagonally down-left. The player who takes the queen to the corner wins.
An impartial game can be represented by a directed acyclic graph G = (V, E). Each position in the game corresponds to a vertex in G, and edges join vertices according to the game’s legal moves. A token is initially placed on some vertex υ ∈ V. Two players take turns moving the token from its current vertex to one of its direct followers. The player who moves the token into a sink wins.
Information
- Type
- Chapter
- Information
- Games of No Chance 3 , pp. 377 - 410Publisher: Cambridge University PressPrint publication year: 2009
Accessibility standard: Unknown
Accessibility compliance for the PDF of this book is currently unknown
and may be updated in the future.