Generalized Algorithm for Wythoff's Game with Basis Vector $(2^b,2^b)$

Shubham Aggarwal, Jared Geller, Shuvom Sadhuka, Max YuarXiv 2016 · DOI · arXiv

Abstract

Wythoff's Game is a classic variation of Nim where players can remove stones from one pile or an equal number from both. While the standard game is solved via the golden ratio, generalizations involving restricted diagonal moves—specifically the $(b, b)$ game where diagonal moves must be multiples of $b$—remain a subject of active research. This paper presents a generalized algorithm for identifying the set of P-positions (losing states) for games where $b$ is a power of two ($2^k$). We demonstrate that these games exhibit a unique cyclic behavior modulo $b^2$, allowing for an inductive construction of winning strategies. Furthermore, we conjecture that this specific periodic structure is exclusive to bases that are powers of two.

Introduction to Wythoff's Variations

In the standard Wythoff’s Game, two players take turns removing stones from two piles. A move consists of either taking any number of stones from a single pile (a Nim move) or taking an equal number of stones from both piles. The set of P-positions $C$ is defined by the pairs $(\lfloor k\phi\rfloor, \lfloor k\phi^2 \rfloor)$ and their permutations, where $\phi$ is the golden ratio.

The $(b, b)$ game generalizes this by restricting diagonal moves to $kb$ stones, where $k$ is a positive integer and $b$ is a fixed basis. While solutions for $b=1$ and $b=2$ were previously established, a general framework for arbitrary $b$ has been elusive. This research focuses on the case where $b = 2^m$, uncovering a recursive and modular structure that governs the game's evolution.

Algorithmic Methodology and Difference Sequences

The core of our approach relies on the Minimum Excluded Value (Mex) Rule. In impartial games, a position is a P-position if all moves from it lead to N-positions (winning states), and an N-position is one from which at least one move leads to a P-position. By identifying the smallest non-negative integers not already present in the set of previous P-positions, we can iteratively build the sequence of losing states.

Sample P-positions $(x_i, y_i)$ and their differences $d_i$ for a specific game instance.

As shown in the table above, the differences $d_i = y_i - x_i$ are central to the game's structure. For games where $b$ is a power of two, these differences follow a periodic pattern modulo $b^2$. We utilize a concatenation operator and an addition operator to inductively construct the P-positions for a $(2a, 2a)$ game using the known positions of an $(a, a)$ game. This recursive scaling suggests that the state space of these games is not merely a sequence but a structured multiset.

Geometric Insights and Asymptotic Slopes

Visualizing the P-positions on a 2D grid reveals a striking fractal-like self-similarity. As the basis vector $a$ increases, the clusters of P-positions tend to align along specific linear trajectories.

Visual distribution of P-positions across different game parameters, showing the evolution of clusters and slopes.

We propose that the asymptotic slope $\alpha$ of these positions is governed by the formula: $$\alpha = \frac{\sqrt{4a^2+1}+1}{2a}$$ This formula explains the convergence of the game toward standard Nim behavior (where the slope is 1) as $a$ becomes very large. Interestingly, when extended to three piles, the P-positions generate a 3D structure visually reminiscent of the Sierpinski Sponge, further linking simple combinatorial rules to complex fractal geometry.

Conjectures and Future Directions

A significant finding of this work is the "Power of 2 Uniqueness" conjecture. Our algorithm successfully identifies P-positions for any $(2^m, 2^m)$ game, but empirical evidence suggests that the required cyclic structure modulo $b^2$ does not exist when $b$ is not a power of two (e.g., the $(3, 3)$ game).

Future research will explore more complex numeration systems, particularly those involving Pisot-Vijayaraghavan (PV) numbers, to address these non-power-of-two cases. Additionally, a full algorithmic characterization of N-dimensional Wythoff variations remains an open challenge for the field of combinatorial game theory.

Summary updated

Abstract

Wythoff's Game is a variation of Nim in which players may take an equal number of stones from each pile or make valid Nim moves. W. A. Wythoff proved that the set of P-Positions (losing position), $C$, for Wythoff's Game is given by $C := \left\{ (\lfloor kϕ\rfloor, \lfloor kϕ^2 \rfloor), (\lfloor kϕ^2 \rfloor, \lfloor kϕ\rfloor) : k \in \mathbb Z_{\geq 0} \right\}$. An open Wythoff problem remains where players make the valid Nim moves or remove $kb$ stones from each pile, where $b$ is a fixed integer. We denote this as the $(b,b)$ game. For example, regular Wythoff's Game is just the $(1,1)$ game. In 2009, Duch${ê}$ne and Gravier proved an algorithm to generate the set of P-Positions for the $(2,2)$ game by exploiting the periodic nature of the differences of stones between the two piles modulo $4$. We observe similar cyclic behaviour for any $b$, where $b$ is a power of $2$, modulo $b^2$, and construct an algorithm to generate the set of P-Positions for this game. Let $a$ be a power of $2$. We prove our algorithm works by first showing that it holds for the first $a^2$ terms in the $(a,a)$ game. Next, we construct an ordered multiset for the $(2a,2a)$ game from the $a^2$ terms, and an inductive proof follows. Moreover, we conjecture that all cyclic games require $a$ to be a power of $2$, suggesting that there is no similar structure in the generalised $(b,b)$ game where $b$ isn't a power of $2$. Future directions for generalising this result would likely utilise numeration systems, particularly the PV numbers.
BibTeX
@misc{aggarwal2016generalized,
  author = {Shubham Aggarwal and Jared Geller and Shuvom Sadhuka and Max Yu},
  title = {{Generalized Algorithm for Wythoff's Game with Basis Vector $(2^b,2^b)$}},
  year = {2016},
  eprint = {1612.03068},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1612.03068},
}

Loading related content...

Figure