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.
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.
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