Matthew's blog
2024-06-16 Chaos in 3-pile Nim
This exposition is based on results in “Combinatorial Games with a Pass: A Dynamical Systems Approach” by Morrison, Friedman, and Landsberg.
Nim
You can play against the computer in Nim-with-a-pass to get a feel for the game:
This computer opponent plays a basic strategy. In the next section, we'll devise and visualize optimal play for 3-pile Nim-with-a-pass.
Games with passes
While ordinary 3-pile Nim has been solved, adding a pass move (which can be used once per game by either player in a non-terminal position) dramatically increases the game's structure and complexity. In this paper, we will follow an approach taken by Morrison, Friedman, and Landsberg to view games as dynamical systems by defining an operator that acts on sets of \(\mathscr{N}\)-positions according to the game's rules. Through the dynamical lens, games with passes can be understood as generic games, which are classes of games with perturbed \(\mathscr{N}\)-positions. This framework helps to explain the intriguing scale invariance and complex geometric structure of 3-pile Nim-with-a-pass as arising from generic Nim's tendency towards an attractor.
A pass move in a combinatorial game allows either player to transfer the turn to the other. Once used by either player, the pass may not be used again, and it cannot be used from a terminal position. The goal of this section is to study 3-pile Nim with a pass.
Pure 3-pile Nim
Before tackling Nim-with-a-pass, we'll first analyze traditional Nim. In 3-pile Nim, a game position can be represented by a triplet of nonnegative integers \((x, y, z)\). Our goal is to study the set of \(\mathscr{P}\)-positions as a three-dimensional object, which we'll call the \(\mathscr{P}\)-set. We know that this set is characterized by triplets whose XOR sum is zero, but this framework will generalize to the pass version. Consider partitioning the position space into two-dimensional “sheets” indexed by \(x\), with \(y\) and \(z\) being coordinates within a sheet.
Definition 1
The loser sheet at level \(x\), denoted \(L^{x}\), is an infinite Boolean matrix which is 1 at \((y, z)\) if and only if \((x, y, z)\) is a \(\mathscr{P}\)-position.
Stacking the loser sheets recovers the \(\mathscr{P}\)-set. The loser sheets can be obtained from another class of sheets that record instant winners.
Definition 2
A position \((x, y, z)\) is an instant winner if there is a \(\mathscr{P}\)-position \((x', y, z)\) with \(0 \le x' < x\). The instant-winner sheet at level \(x\), denoted \(W^{x}\), is an infinite Boolean matrix which is 1 at \((y, z)\) if and only if \((x, y, z)\) is an instant winner.
While 1 in an instant-winner sheet indicates a \(\mathscr{N}\)-position, 0 can mean either a \(\mathscr{P}\)-position or a \(\mathscr{N}\)-position that decrements \(y\) or \(z\) to reach a \(\mathscr{P}\)-position.
Example
The first \(3 \times 3\) entries of \(L^1\) and \(W^1\) are
\[ L^1=\begin{bmatrix}0&1&0\\1&0&0\\0&0&0\end{bmatrix}, \qquad W^1=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}. \]
Note that while \((1, 0, 2)\) is an \(\mathscr{N}\)-position, the entry \(W^1_{0,2}\) is zero because the winning move is not to decrement 1 but rather to move in \(z\) from 2 to 1.
The point of instant-winner sheets is that we can define an operator \(\mathcal{R}\) such that \(W^{x+1} = \mathcal{R} W^x\) and another operator \(\mathcal{M}\) such that \(L^x = \mathcal{M} W^x\). This means instant-winner sheets encode the \(\mathscr{P}\)-set and that the \(\mathscr{P}\)-set is indirectly described by the discrete-time dynamical system that iterates the map \(\mathcal{R}\).
Definition 3
Let \(W^x\) be an instant-winner sheet. The supermex operator \(\mathcal{M}\) acts on \(W^x\) via the following algorithm:
- Set \(\mathcal{M} W^x = \mathbf{0}\) (the zero matrix), \(T = W^x\), and \(y = 0\).
- Let \(z_s = \operatorname{mex}\{ z \mid T_{y,z} = 1 \}\). Set \((\mathcal{M} W^x)_{y,z_s} = 1\) and \(T_{y+t, z_s} = 1\) for all \(t \ge 0\).
- Set \(y \gets y + 1\) and repeat (2).
Proposition 1
\(L^x=\mathcal MW^x\).
We'll show by induction that for any \(y\), the position \((x, y, z_s)\) is a \(\mathscr{P}\)-position. Since \(T_{y, z_s} = 0\), it must be that \(W^x_{y, z_s} = 0\), so there are no \(\mathscr{P}\)-positions with smaller \(x\). By construction, there are no \(\mathscr{P}\)-positions with smaller \(z\), since \(T_{y,z} = 1\) implies that either \(W^x_{y,z} = 1\) (so \((x, y, z) \in \mathscr{N}\)) or there is \(y' < y\) such that \((x, y', z) \in \mathscr{P}\) (so \((x, y, z) \in \mathscr{N}\)). There are also no \(\mathscr{P}\)-positions with smaller \(y\), since there are no \(y' < y\) such that \((x, y', z_s) \in \mathscr{P}\). Since \((x, y, z_s)\) does not have any subpositions in \(\mathscr{N}\), it must be in \(\mathscr{P}\).
Now, consider any position \((x, y, z)\) for which \((\mathcal{M}W^x)_{y,z} = 0\). If \(z < z_s\), we saw above that \((x, y, z)\) is an \(\mathscr{N}\)-position. Otherwise, if \(z > z_s\), then \((x, y, z)\) can reach the \(\mathscr{P}\)-position \((x, y, z_s)\). Thus, \((x, y, z)\) is an \(\mathscr{N}\)-position.
To define \(\mathcal{R}\), we first need to define two basic operators. Given arbitrary sheets \(A\) and \(B\), the addition operator \(+\) takes the elementwise logical OR of \(A\) and \(B\), and the identity operator \(\mathcal{I}\) returns its input.
The next result gets \(W^x\) from loser sheets. It also motivates visualizing \(W^x\) instead of \(L^x\).
Proposition 2
\[W^x=L^0+L^1+\cdots+L^{x-1}.\]
Recall that the instant-winner sheet at \(x\) is 1 at \((y, z)\) if there is a \(\mathscr{P}\)-position \((x', y, z)\) at a lower \(x'\). But the loser sheet at \(x'\) consists of all \(\mathscr{P}\)-positions \((x', y, z)\), so the loser sheets at \(0\) through \(x-1\) describe all \(\mathscr{P}\)-positions reachable from level \(x\).
Proposition 3
Define \(\mathcal{R} = \mathcal{I} + \mathcal{M}\). Then \(W^{x+1} = \mathcal{R} W^x\).
By Proposition 2, we have
\[ W^{x+1}=L^0+\cdots+L^{x-1}+L^x =W^x+\mathcal MW^x =\mathcal RW^x. \]
By taking \(W^0 = \mathbf{0}\) (since taking stones from \(x = 0\) is not legal), we obtain any \(W^x\) by iterating \(\mathcal{R}\). Computationally, we take a finite-sized Boolean matrix. The instant-winner sheets of 3-pile Nim exhibit scale invariance in the sense that \(W^x\) is geometrically similar to \(W^{2x}\) up to rescaling. However, this is to be expected since \(2x \oplus 2y \oplus 2z = 0\) if \(x \oplus y \oplus z = 0\), so \((2x, 2y, 2z)\) is a \(\mathscr{P}\)-position if \((x, y, z)\) is.
3-pile Nim-with-a-pass
We now add the pass to 3-pile Nim. To keep track of the pass, a hat on \(W^x\) or \(L^x\) indicates that the pass is available. That is, \(\hat{W}^x\) consists of \(\mathscr{N}\)-positions such that there is a \(\mathscr{P}\)-position on a lower \(x\) level (while keeping the pass), and \(\hat{L}^x\) consists of \(\mathscr{P}\)-positions where the pass is available. We will also sometimes refer to a specific position \((x, y, z; p)\), where \(p = 1\) if the pass is available and 0 otherwise.
The iterative mapping changes slightly:
Proposition 4
\[ \hat{W}^{x+1} = \hat{W}^x + \mathcal{M}(\hat{W}^x + L^x). \]
Similarly to Proposition 2, we have \(\hat{W}^{x} = \hat{L}^0 + \hat{L}^1 + \cdots + \hat{L}^{x-1}\). To obtain the loser sheet from an instant-winner sheet, the pass move must also be considered. The \(\mathscr{N}\)-positions arising from the pass move are positions \((x, y, z; 1)\) such that \((x, y, z; 0)\) is a \(\mathscr{P}\)-position, which is exactly \(L^x\). Hence, \(\hat{L}^{x+1} = \mathcal{M}(\hat{W}^x + L^x)\) by a proof similar to that of Proposition 1.
Treating \(L^x\) as a sequence of constants, we get another iterated dynamical system starting from \(\hat{W}^0 = \mathbf{0}\). The following figure visualizes the geometry of the resulting instant-winner sheets. In comparison with the structure of ordinary Nim, we see dramatically different geometry reminiscent of a fractal. The sheets exhibit scale invariance again, but in a more complex manner that seems to converge towards a fixed point with noisy local behavior that tends towards an overall global shape. Note the slight differences between \(\hat{W}^{280}\) and \(\hat{W}^{304}\), while \(\hat{W}^{152}\) and \(\hat{W}^{304}\) are very similar globally, suggesting that the dynamics have a factor-of-2 periodicity. It seems unlikely that the \(\mathscr{P}\)-set can be characterized cleanly.
Stacking the loser sheets recovers the \(\mathscr{P}\)-set:
Perturbed games
In this section, we'll define a class of Nim variants of which Nim-with-a-pass is an instance. The instant-winner sheets of these variants exhibit similar complex geometry.
Generic 3-pile Nim
Definition 4
The variant sheet at level \(x\), denoted \(V^x\), modifies the rules of Nim by specifying positions that are forced to become \(\mathscr{N}\)-positions.
An instance of generic Nim specifies the variant sheets. For example, adding the pass move is the same as setting \(V^x = L^x\), since any \(\mathscr{P}\)-position becomes an \(\mathscr{N}\)-position with the pass. We define the instant-winner and loser sheets for generic Nim analogously to before, where loser sheets \(\tilde{L}^x\) consist of \(\mathscr{P}\)-positions at level \(x\) and instant-winner sheets \(\tilde{W}^x\) consist of \(\mathscr{N}\)-positions that can move to \(\mathscr{P}\)-positions at lower \(x\).
As before, we obtain instant-winner sheets from loser sheets through the identity \(\tilde{W}^x = \tilde{L}^0 + \tilde{L}^1 + \cdots + \tilde{L}^{x-1}\). Just like in Nim-with-a-pass, the supermex operator almost recovers loser sheets from instant-winner sheets, but must also consider the forced \(\mathscr{N}\)-positions from variant sheets. In particular, we have \(\tilde{L}^x = \mathcal{M}(\tilde{W}^x + V^x)\).
Thus, the dynamical system for generic Nim starts from \(\tilde{W}^0 = \mathbf{0}\) and iterates the map \(\tilde{W}^{x+1} = \tilde{W}^x + \mathcal{M}(\tilde{W}^x + V^x)\). We can think of \(\{V^x\}\) as perturbing the original game.
The Nim Attractor
We now explore two examples of perturbations and visualize the resulting instant-winner sheets. Code for these numerical results can be found in the project repository. In both examples, we take finite sheets of size 600 and visualize \(\tilde{W}^{300}\).
On the left of the following figure, we set \(V^0_{1,1} = 1\) and all other \(V^x = \mathbf{0}\).
On the right of the figure, let the sheet size be \(m\). We pick a random entry of each column of every \(V^x\) to be 1 by drawing \(j\) uniformly from \([0, m-1]\) for each \(i\) and setting \(V^x_{i,j} = 1\).
The instant-winner sheets of both examples have similar geometric structure to the instant-winner sheets of Nim-with-a-pass, with the central column and fractal-like spikes emanating from the solid corner. Empirically, generic 3-pile Nim appears to have an attractor in that different perturbations result in similar global structure. This attractor seems to encompass a variety of types of perturbations, arising from even a single adjustment to the \(\mathscr{P}\)-positions. It also seems to be robust, since in one example we added random perturbations to every column of every variant sheet and still recovered the same structure.
Other games
The same analysis of recasting a combinatorial game into a dynamical relation and visualizing slices of its position space applies to other games, such as 3-row Chomp.
References and source
- Rebecca Morrison, Eric Friedman, and Adam Landsberg, “Combinatorial Games with a Pass: A Dynamical Systems Approach,” Chaos 21, 043108 (2011).
- Eric J. Friedman and Adam S. Landsberg, “Nonlinear Dynamics in Combinatorial Games: Renormalizing Chomp,” Chaos 17, 023117 (2007).
- Matthew Shang, “Nim with Pass,” source code for the numerical experiments (2024).
- Original class-project PDF.