SELF-SIMILARITY OF 𝒫-POSITIONS OF (2n + 1)-DIMENSIONAL WYTHOFF’S GAME

Yanxi Li, Wen WuFractals 2020 · DOI · arXiv

TL;DR

This paper characterizes the P-positions (losing positions) of a generalized Wythoff's game with an odd number of token heaps. They prove that for a 3-dimensional version of this game, the set of P-positions forms a fractal structure known as the Sierpinski sponge, confirming a long-standing conjecture.

What Problem Does This Paper Address?

Wythoff's game is a classic two-player combinatorial game played with two heaps of tokens. Players can remove tokens from one heap or an equal number from both. The game's P-positions (positions from which the previous player has a winning strategy, meaning the current player will lose if the opponent plays optimally) are well-understood for the 2-dimensional case, famously related to the golden ratio. This paper tackles the challenge of understanding these P-positions in a generalized version of Wythoff's game with an odd number of heaps (specifically, $2n+1$ heaps) and a specific set of allowed moves. A key motivation is to understand the geometric structure of these P-positions, with a particular focus on whether the 3-dimensional case generates a known fractal.

Methods

The core of the paper lies in characterizing the P-positions using the concept of the bitwise exclusive OR (XOR), also known as the Nim-sum. For an $n$-dimensional Wythoff's game with specific move vectors (removing tokens from a single heap or an equal number from all heaps), the authors prove that a position $(x_1, x_2, \dots, x_n)$ is a P-position if and only if the Nim-sum of its components is zero: $x_1 \oplus x_2 \oplus \dots \oplus x_n = 0$.

To establish this, they leverage a general criterion for identifying P-positions in combinatorial games (Lemma 6), which requires showing that any move from a P-position leads to an N-position (a winning position for the next player), and that any move from an N-position can lead to a P-position. The proof involves detailed analysis of binary representations of the heap sizes and how they change under allowed moves.

For the geometric aspect, they introduce a scaled and bounded version of the P-positions, denoted as $P^{(n)}$, and analyze its nested structure. This analysis, combined with concepts from fractal geometry (specifically, iterated function systems), allows them to prove that the closure of the P-positions for the 3-dimensional game is indeed the Sierpinski sponge.

Datasets

Not discussed in the paper. The paper deals with theoretical combinatorial game theory and fractal geometry, not empirical data or machine learning models.

Key Insights and Ideas

  • Nim-sum as the Key: The most significant insight is the elegant characterization of P-positions for the $(2n+1)$-dimensional Wythoff's game using the bitwise XOR operation. This provides a simple and powerful condition for determining winning and losing positions.
  • Fractal Nature of P-positions: The paper confirms the conjecture that the P-positions of the 3-dimensional Wythoff's game with the specified moves generate the Sierpinski sponge. This reveals a deep connection between combinatorial game theory and fractal geometry.
  • Self-Similarity: The P-positions exhibit a strong self-similar structure, meaning that scaled and translated versions of the set of P-positions can reconstruct the entire set. This is a hallmark of fractal objects.
  • Generalization to Odd Dimensions: The work extends the understanding of Wythoff's game beyond the classic 2-dimensional case to a more general class of games with an odd number of heaps.

Key Results

  • Theorem 3: For an odd number $n \geq 3$, the set of P-positions of the $n$-dimensional Wythoff's game with move vectors $\{(1,0,\dots,0), (0,1,\dots,0), \dots, (0,\dots,0,1), (1,1,\dots,1)\}$ is precisely the set of positions $(x_1, x_2, \dots, x_n)$ such that $x_1 \oplus x_2 \oplus \dots \oplus x_n = 0$.
  • Theorem 4: For every odd number $n \geq 3$, the set of P-positions $P^{(n)}$ satisfies a self-similarity relation: $P^{(n)} = \bigcup_{v \in T(n)} (v + P^{(n)})$, where $T(n)$ is a specific set of binary vectors whose Nim-sum is zero.
  • Corollary 5: The closure of the P-positions of the 3-dimensional Wythoff's game is the Sierpinski sponge.

Limitations and Future Work

  • Odd Dimensions: The results are specifically for games with an odd number of heaps ($2n+1$). The behavior for an even number of heaps is not addressed.
  • Specific Move Set: The characterization of P-positions relies on a particular set of allowed moves. Variations in the move set might lead to different P-position structures.
  • Future Work: The paper suggests exploring the geometric properties of $P^{(n)}$ for even $n$ and investigating other variations of Wythoff's game with different move sets. The connection to fractal geometry is a rich area for further exploration.

Summary updated

Abstract

Wythoff’s game as a classic combinatorial game has been well studied. In this paper, we focus on [Formula: see text]-dimensional Wythoff’s game; that is the Wythoff’s game with [Formula: see text] heaps. We characterize their [Formula: see text]-positions explicitly and show that they have self-similar structures. In particular, the set of all [Formula: see text]-positions of 3-dimensional Wythoff’s game generates the well-known fractal set — the Sierpinski sponge.
BibTeX
@inproceedings{li2020self,
  author = {Yanxi Li and Wen Wu},
  title = {{SELF-SIMILARITY OF 𝒫-POSITIONS OF (2n + 1)-DIMENSIONAL WYTHOFF’S GAME}},
  booktitle = {Fractals},
  year = {2020},
  doi = {10.1142/s0218348x21500614},
}
Figure