8
$\begingroup$

Background

I recently came across a game called "Staircase Nim". In this game, there is a staircase with $N$ steps, indexed from $0$ to $N-1$. There are $A_j$ coins laying on step $j$. Two players take turns. On each turn, a player selects a step $j>0$ and moves one or more coins from it to step $j-1$. The last player who can make a valid move wins, i.e all coins are on step $0$ after that move.
It turns out that this game is equivalent to Nim if you only consider the odd indexed steps of the staircase. More information on this game can be found in this blog post.

The Game

After I saw this, I thought about a slight variation of this game: Instead of moving the coins to step $j-1$, a player chooses a step $k$ between $0$ and $j-1$ and moves the coins to step $k$.
I now want to find an efficient way to determine which player can win this new game for a given initial configuration.

(Everything below this line is just my own research and is not part of the actual question.)


Observations/Things I Tried

  • $A_0$ is irrelevant: You can't move the coins on step $0$ any lower, so they are useless.

  • If step $2x-1$ has the same amount of coins as step $2x$ ($A_{2x-1}=A_{2x}$, $x\geq1$), the second player will win.
    Proof: Let's call a state of a game with $A_{2x-1}=A_{2x}$ ($x\geq1$) balanced. Every other state is called unbalanced. For every pair of steps $2x-1$ and $2x$ ($x\geq1$), step $2x-1$ is called the neighbor of $2x$ and vice versa.
    If the first player is presented with a balanced state, every move will result in an unbalanced state. After that, the second player will always be able to restore the state to a balanced state. This can be shown by considering different cases for the move of the first player:
    If the first player moves $c$ coins from step $j$ to step $k$ in a balanced state, there are three possible cases:

    1. Step $k$ is the neighbor of step $j$:
      If $c$ coins are moved from step $j$ to step $k$, $A_j$ will not be equal to $A_k$. Since step $j$ and step $k$ are neighbors, the resulting state is unbalanced. The second player can create a balanced state by moving $2c$ coins from step $k$ to step $0$ ($A_j$ and $A_k$ will be equal after that).

    2. $k=0$:
      Let step $j'$ be the neighbor of step $j$. Moving $c$ coins from step $j$ to step $0$, will lead to $A_j\neq A_{j'}$, creating an unbalanced state. The second player can restore this to a balanced state by moving $c$ coins from step $j'$ to step $0$.

    3. Else:
      Let step $j'$ be the neighbor of step $j$ and step $k'$ the neighbor of step $k$. Moving $c$ coins from step $j$ to step $k$ will lead to $A_j\neq A_{j'}$ and $A_k\neq A_{k'}$, which is an unbalanced state. By moving $c$ coins from step $j'$ to step $k'$, $A_j$ will be again equal to $A_{j'}$ and $A_k$ will be equal to $A_{k'}$. Thus the second player can create a balanced state.

    With this strategy, the second player can ensure that his turn will always start with an unbalanced state and that the first player will always start with a balanced state. The final state of the game (all coins on step $0$) is a balanced state. That means that the first player will eventually get the final state at the start of his turn. Therefore he loses and the second player wins.

  • I wrote a program that can determine whether the first or the second player will win for a given configuration. The algorithm is basically Minimax with memorization: It considers every possible game state that can be reached from the starting configuration and calculates the winner for each of these states recursively. Because this algorithm has a really bad time complexity, the program can only handle small amounts of coins and steps before the execution time gets too large. The source code can be found here.
    The following image visualizes the output of the program for all initial configuration with $0\leq A_1,A_2\leq20$ and $0\leq A_3\leq5$ ($A_j=0$ for $j\geq4$, $A_0$ is irrelevant). If a cell of the table is green, the first player wins this game configuration. If it's red, the second player wins.

    Visualization of game configurations

    As you can see, there is a clear pattern for $0\leq A_3\leq4$. But for $A_3=5$, I cannot make out any order. It looks quite chaotic to me. If you go higher than $A_3=5$, it's even more chaotic.

  • I tried to find the losing state sequence for $A_3=5$ in OEIS, but there was no match.

  • I also searched for this game online, but I could only find the Staircase Nim without my modification. If you can find something, please let me know.

Update 1

After I had written this post, I looked at the losing state sequence for $A_3=5$ again and noticed a pattern.
Let's define a sequence $\{L_{A_3}(A_1)\}$ of losing states the following way: Let $L_{A_3}(A_1)$ be the value of $A_2$ for which the game state with these particular $A_1$, $A_2$, and $A_3$ is a losing state. For example, if you want to figure out $L_5(2)$, you can look at the table for $A_3=5$ above. In the row with $A_1=2$, there is only one losing state at $A_2=10$. That means that $L_5(2)=10$. If you think about how the values are calculated, you can easily see that there can only be at most one losing state within a row.

Let's look at the first few terms of $\{L_5(A_1)\}$:

$$ \{L_5(A_1)\}_{A_1=0}^{20}= \{11,7,10,12,13,2,0,3,1,16,4,5,8,6,21,9,22,20,25,27,14\} $$

As you may have noticed, there isn't an obvious pattern in these numbers. But when you look at more terms of the sequence, you can see that $L_5(A_1)$ is always very close to $A_1$, even for large $A_1$. So let's have a look at the difference between $L_5(A_1)$ and $A_1$. We will define a new sequence $\{\hat{L}_{A_3}(A_1)\}$ that captures this difference, i.e. $\hat{L}_{A_3}(A_1)=L_{A_3}(A_1)-A_1$.

Let's look at these difference-values for $A_3=5$:

$$ \{\hat{L}_5(A_1)\}_{A_1=0}^{20}= \{11,6,8,9,9,-3,\underline{-6,-4,-7,7,-6},\underline{-6,-4,-7,7,-6},6,3,7,8,-6\} $$

You can see that the pattern $-6,-4,-7,7,-6$ repeats once, but the values before and after it seem quite random. In order to see the hidden pattern, we need more terms. The terms until $A_1=77$ are:

$$ \begin{align} \{\hat{L}_5(A_1)\}_{A_1=0}^{77}=\{ &11,6,8,9,9,-3,-6,-4,-7,7,-6,-6,-4,-7,7,-6,6,3, \\ &7,8,-6,-6,-4,3,7,-8,-7,-4,7,7,-6,6,-4, \\ &7,8,-6,-6,-4,3,7,-8,-7,-4,7,7,-6,6,-4, \\ &7,8,-6,-6,-4,3,7,-8,-7,-4,7,7,-6,6,-4, \\ &7,8,-6,-6,-4,3,7,-8,-7,-4,7,7,-6,6,-4\} \\ \end{align} $$

After $18$ terms, a pattern is visible. The pattern consists of $15$ numbers repeating over and over again. This pattern seems to go on forever, but I can't prove it.

When you inspect $\{\hat{L}_6(A_1)\}$, you can see a similar behavior: The first $62$ terms look random but after that, a sequence of $105$ numbers seems to repeat forever. The same is true for $A_3=7$ and $A_3=8$.

The following table shows the lengths of the repeating pattern and the number of terms before it starts (offset) for different $A_3$:

Table of pattern length and offset

The pattern length and the offset seem to grow as $A_3$ gets larger. You can also notice that the pattern length for $A_3=j$ is an integer multiple of the pattern length for $A_3=j-1$. I can't make out a similar pattern for the offset values.

The values within a repeating pattern for $A_3\geq5$ seem very random to me. The pattern for $A_3=5$ $(7,8,-6,-6,-4,3,7,-8,-7,-4,7,7,-6,6,-4)$ doesn't look like it has any order. It would be nice to have a formula for predicting the pattern for a given $A_3$.

Update 2

Upon closer inspection, I realized something: If you look at the sum of all numbers within a pattern for some $A_3$, you will get $0$.

Table of pattern sums

I have checked this property for $A_3\leq8$, but I believe that it holds for all $A_3$.
This gives me some hope for finding a formula for the values of a pattern. They may not be that random after all.

Update 3

Generalization of the game

Since I haven't made any further progress with predicting the patterns, I decided to look at a generalized version of the game: Instead of moving the coins from step $j$ to a step $k$ between $0$ and $j-1$, step $k$ is now resticted to be at most $r$ steps below step $j$. That means $k$ lies between $j-r$ and $j-1$. We will call this game $S_r$. $S_1$ is therefore the original "Staircase Nim" where you could move coins only from step $j$ to step $j-1$. My (first) modification of the game is called $S_\infty$ because $k$ can be arbitrarily smaller than $j$.

In $S_1$, you can observe that the even-numbered steps are irrelevant. This means that the number of coins on these steps ($A_0, A_2, A_4,\dots$) doesn't affect the outcome of the game. For the general game $S_r$ you can make a similar observation: Step $j$ is irrelevant if $j$ is divisible by $r+1$.

Proof: To make things easier we will color the steps: Step $j$ is colored red if $j$ is divisible by $r+1$, otherwise it's colored blue.
Let's consider yet another similar staircase game $S'_r$. It is almost the same as $S_r$, but all coins on red steps will be instantly removed from the staircase. This includes coins that are moved there during the game. For any game $S_r$ played on a certain initial configuration we can also imagine $S'_r$ played with the same initial configuration (coins on red steps get removed at the beginning of the game). Let's call the player that wins $S'_r$ player $X$. We will now prove that player $X$ also wins $S_r$.

Player $X$ can use the following strategy to win: He pretends that they are actually playing $S'_r$ and not $S_r$, which means that he considers the coins on red steps as removed.
There is only one problem: What if the opponent makes an "illegal" move by moving a "removed" coin from a red step back into the game. Note these coins can only be moved to a blue step because two red steps are at least $r+1$ steps apart.
In this case, player $X$ can just move these coins back to the next lower red step. This is always possible since every blue step is at most $r$ steps above the next lower red step. This move undoes the move of the opponent: All coins that were previously on a red step are still on a red step and the coins on the blue steps remain unchanged. If you look at the staircase from the perspective of player $X$, the game state hasn't changed and player $X$ is still in a winning position.

Since player $X$ wins $S'_r$, he will therefore also win $S_r$. Because the red steps are irrelevant in $S'_r$ they are also irrelevant in $S_r$.

Analysis of losing states

We will now analyze the losing states for $S_r$. First, we must choose a value for $r$: We know from $S_\infty$ that the patterns for $A_3\geq5$ are chaotic and at least for now unpredictable. Since we only looked at configurations where the highest step with coins was step $3$, will find the same patterns in $S_r$ with $r\geq3$. That's why we should look at $r<3$. For $r=1$ we already know the solution, so the only other option is $r=2$.

The following image visualizes the losing states of $S_2$ for all initial configurations with $0\leq A_1,A_2\leq20$ and $0\leq A_4\leq5$ ($A_j=0$ for $j\geq5$, $A_0$ and $A_3$ are irrelevant). The losing states are colored red.

Visualization of losing states

You can see a pattern for $0\leq A_4\leq2$, but for $A_4\geq3$ the chaos takes over again. I really hoped for something more regular. I thought that analyzing $S_2$ might help to solve $S_\infty$, but right now it doesn't look like it. Anyway, I will do further analysis of $S_2$ in another update.

Update 4

Analysis of the losing state sequences

Okay, let's look at the losing states of $S_2$. We will define a sequence of losing states in a way very similar to those of $S_\infty$:

Let $L_{A_4}(A_1)$ be the value of $A_2$ for which the game state with these particular $A_1$, $A_2$, and $A_4$ (all other steps are empty) is a losing state. We will also define $\hat{L}_{A_4}(A_1)=L_{A_4}(A_1)-A_1$ as we did before.

Let's inspect the first few terms of $\hat{L}_{3}(A_1)$ ($A_4=3$ is the smallest value that seems chaotic):

$$ \{\hat{L}_3(A_1)\}_{A_1=0}^{30}= \{3,3,4,4,-4,3,-5,-5,1,-4,4,1,-2,2,2,-4,2,2,-5,\underline{2,2,-4},\underline{2,2,-4},\underline{2,2,-4},\underline{2,2,-4}\} $$

After $19$ terms of chaos, a repeating pattern of length $3$ emerges. This is analogous to the losing sequences we inspected for $S_\infty$. Also, it holds for larger $A_4$. Here is a table showing the length and the offset of the repeating pattern for certain values of $A_4$:

Table for pattern length and offset

As you can see, the length and the offset seem to grow as $A_4$ gets larger, which also is the case for $S_\infty$. The pattern length is again an integer multiple of the previous value, except for $A_4=5$. The offset values look random, except for the value of $16$ repeating once.
If you add the values of a particular pattern together, you again get $0$:

Table of pattern sums

I think that there is such an infinitely repeating pattern with sum $0$ for any $A_4$, but (of course) I can't prove it.

Conclusion

After looking deeper into this, I can say that $S_2$ doesn't seem to be any easier to solve than $S_\infty$. But don't worry, I still have some ideas to generalize the game even further and to look at it from a different angle. Maybe one of these ideas will lead to a breakthrough.

$\endgroup$
4
  • 1
    $\begingroup$ This is really interesting for such a simple sounding game. I don't have time to make a big post, but $A_3=5$ eventually settles into a (complicated) repeating pattern, and $A_3=6$ looks like it will if I give it enough computation time ($A_1,A_2\le140$ isn't enough), too. Probably each value of $A_3$ does, eventually. But I don't know what the formula for arbitrary $A_3$ would be like, if there's a good way to state the general pattern at all. $\endgroup$
    – Mark S.
    Oct 16, 2020 at 2:25
  • $\begingroup$ @Mark S. After I had written this post, I looked at the values for $A_3=5$ again and also realized a pattern. It's interesting that the pattern doesn't start with the first term: the first few terms don't have any visible order. I computed the first 1000 terms of $A_3=6$ and also found a pattern. $\endgroup$
    – Tc14
    Oct 16, 2020 at 12:24
  • 1
    $\begingroup$ @Mark S. If compare the "length" of the pattern for different $A_3$, you can see that the length of one $A_3$ is a multiple of the previous length: $A_3=0$ has length $1$, $A_3=1$ to $A_3=4$ have length $5$, $A_3=5$ has length $15$, and $A_3=6$ has length $105$. I think this pattern will continue for larger $A_3$. $\endgroup$
    – Tc14
    Oct 16, 2020 at 12:32
  • 1
    $\begingroup$ As an aside, the Grundy values for $A_3=0$ are A296339, but I couldn't find information about $A_3>0$ in the OEIS. The "pattern doesn't start with the first term" is a relatively common theme in Combinatorial Game Theory. It comes up most famously in the Octal Periodicity Theorem, but also in the Nim variant asked about in index-k Nim variant - is it still a Nim? and other games. $\endgroup$
    – Mark S.
    Oct 16, 2020 at 12:32

0

You must log in to answer this question.

Browse other questions tagged .