What is the winning strategy in this pebble game?

Question

Consider the following two-player pebble game. We have finitely many stones on a finite linear track of squares. We take turns, and the allowed moves are:

• move any one stone one square to the left, if that square is empty, or
• remove any one stone, or
• remove any two adjacent stones.

Whoever takes the last stone wins.

Question. What is the winning strategy? And which are the winning positions?

The game will clearly end always in finitely many moves, and so by the fundamental theorem of finite games, one of the players will have a winning strategy. So of course, I know that there is a computable winning strategy by computing with the game tree, and we have a computable algorithm to answer any instance of the question. What I am hoping for is that there will be a simple-to-describe winning strategy.

This is what I know so far:

Theorem. It is a winning move to give your opponent a position with an even number of stones, such that the stones in each successive pair stand at even distance apart.

By even-distance, I mean that there are an odd number of empty squares between, so adjacent stones count as distance one, hence odd. Also, I am only concerned with the even distance requirement within each successive pairs, not between the pairs. For example, it is winning to give your opponent a position with stones at

..O...OO.O....O.....O...........

We have distance 4 in the left-most pair, distance 2 in the next pair, distance 6 in the third pair, ignoring the distances in front and between the pairs.

Proof. I claim that if you give your opponent a position like that, then he or she cannot give you back a position like that, and furthermore, you can give a position like that back again. If your opponent removes a stone, then you can remove the other one in that pair. If your opponent moves the lead stone on a pair, then you can move the trailing stone. If your opponent moves the trailing stone on a pair, then either you can move it again, unless that pair is now adjacent, in which case you can remove both. And if your opponent removes two adjacent stones, then they must have been from different pairs (since adjacent is not even distance), which would cause the new spacing to be the former odd number plus another odd number plus 2, so an even number of empty squares between, and so you can move the trailing end stone up one square to make an odd number of empty squares between and hence an even distance between the new endpoints. Thus, you can maintain this even-distance property, and your opponent cannot attain it; since the winning move is moving to the empty position, which has all even distances, you will win. $\Box$

What I wonder is whether there is a similarly easy to describe strategy that solves the general game.

Answer 1

The positions which are a win for the second player are those with:

• an even number of pebbles in odd-numbered squares, and

• an even number of pebbles in even-numbered squares.

Indeed, from a position in this set $P$, any move will be to a position not in that set, whereas from a position not in that set one can always make a move to a position in that set (if only the number of pebbles in the odd-numbered squares is odd, you can remove one, similarly for the even-numbered, and if both are odd, choose any pebble — that is not at the very leftmost square — and either more it to the left if that square is unoccupied or remove it along with the one to the left if it is).

So, systematically moving to a position in $P$ (as described in the parenthesis in the previous paragraph) provides a winning strategy provided one starts with a position not in $P$.

Answer 2

We can go further and find the nim-value of any position of this game.

Theorem. The nim-value of a position in this game is the Nim-sum of the contributions of its pebbles, where

• Pebbles in odd-numbered squares contribute $1$.
• Pebbles in even-numbered squares contribute $2$.

(Here we count the leftmost square as the $1^{st}$ square.)

Corollary. As in Gro-Tsen's answer, the winning positions (with nim-value $0$) are the ones with both an even number of pebbles in odd-numbered squares and an even number of pebbles in even-numbered squares.

Corollary. All positions have nim-value $0, 1, 2,$ or $3$.

---

The proof relies on the following idea, which is encoded in the lemma below.

Key Insight. A position in this pebble game is equivalent to the sum of an individual game for each pebble with its own private track.

---

Lemma. Given a position $P$ of pebbles $p_1, p_2, ... p_n$, consider the games $P_i$ which each consist of only the single pebble $p_i$ in the same square. Then $P$ is equivalent to $\sum_i P_i$.

Proof. To check this, we need only show that the game $P + \sum_i P_i$ is a zero game, by demonstrating a winning strategy for the second player. So consider the possible moves for the first player in the game $P + \sum_i P_i$:

• If the first player removes two adjacent pebbles $p_i$ and $p_{i+1}$ in $P$, the second player can respond by moving the pebble in $P_{i+1}$ to the left, leaving behind two copies of $P_i$, which nim-cancel.

• If the first player removes any one pebble, the second player responds by removing the corresponding pebble.

• If the first player moves a pebble to the left in $P$, the second player responds by moving the pebble to the left in $P_i$.

• If the first player moves a pebble to the left in a $P_i$, the second player responds by moving the corresponding pebble to the left in $P$. If that move is blocked by a pebble directly to the left, that's fine -- the second player instead removes those two pebbles, noting that there are now two copies of $P_{i-1}$ that nim-cancel out.

---

Proof of Theorem. Because of the Lemma, we need only consider the case of a single pebble in position $i$ (where position $1$ is the leftmost square). By induction on $i$,

• There is always the option to remove the pebble, an option with nim-value $0$.
• If $i$ is odd, there may also be the option to move the pebble to the left, which is an even-numbered square with nim-value $2$. Thus the nim-value in the odd case is $mex(0,2) = 1$.
• If $i$ is even, there is always also the option to move the pebble to the left, which is an odd-numbered square with nim-value $1$. Thus the nim-value in the even case is $mex(0,1) = 2$.

---

How to Evaluate Positions.

Example 1. The nim-value of the position in the question

 . . O . . . O O . O . . . O O . . . . . O

is found quickly by seeing that a pebble in an odd-numbered position contributes nim-value 1, and a pebble in an even-numbered position contributes nim-value 2. So using this mask:

 . . O . . . O O . O . . . O O . . . . . O
 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

yields the Nim-sum

     1      +1+2  +2      +2+1          +1  

which equals 2, so removing any of the even-numbered pebbles (the "2s") is a win.

Example 2. You are playing the sum of the following two positions:

 O . O . . . O O . O    +    O . O O

Evaluate each one with the mask:

 O . O . . . O O . O    +    O . O O
 1 2 1 2 1 2 1 2 1 2         1 2 1 2 
 1  +1      +1+2  +2    +    1  +1+2

This has a Nim-sum of 3, so moving any pebble to the left or removing any two adjacent pebbles (in either component!) is a win.