Winning strategy for a nim-esque game (Combinatorial Game Theory)

Question

The rules of the game are as follows:

• There are two players.
• The game starts with N number of game pieces arranged side by side in a row.
• Taking turns, each player removes one game piece.
• A piece can only be removed if there is another piece immediately to its right.
• A player loses if they cannot remove a piece.

For instance, if the current game-state is XOOXXX, where X denotes a game piece and O an empty space, only the pieces on the 4th and 5th spaces can be removed. The pieces on the 1st and 6th spaces do not have another piece immediately to their right. If the piece on the 5th space is removed, the game-state becomes XOOXOX. There are now no removable pieces, and the player whose turn it is to remove a piece loses.

I have not been able to deduce an optimal strategy for this game, but here are some of the thoughts I have had (which might not be of interest):

There are essentially two types of moves, one where one piece is removed OXX --> OOX, and one where one piece is removed and another is left unremovable XXX --> XOX (the leftmost piece can no longer be removed). Since the second type is essentially removing two pieces from the pool of removable pieces, I was thinking it should be possible to do something with parity, e. g. always make sure there are an odd number of removable pieces, but I haven't gotten anywhere with this.

As the game progresses, the pieces are split into smaller and smaller groups of adjacent pieces, so another idea I had was to treat every group as its own subgame, but I think this is a dead end as the same player can make several moves in a group if the other player leaves it alone.

I was also thinking it might be possible to apply some kind of induction or dynamic programming logic, but I'm not very good at that.

Any input on the matter is greatly appreciated :)

Answer 1

Not a full answer, but a few notes:

• Pretty straightforwardly, there is no interaction between segments of X's; as soon as there's an O between them then the presence of one no longer affects any moves in the other. This means that we only have to keep track of the lengths of the segments.
• Slightly less obviously, the only segment in which the 'there is a piece immediately to its right' constraint matters is in the single-piece segment. For instance, for a segment of length four, we're not allowed to take the rightmost X and turn it into a segment of length three — but we can still take the leftmost X with exactly the same result, so the constraint has no effect.

Between these, we get that the nim-value $\nu_n$ of a run of length $n$ is $\mathop{mex}_{0\leq i\lt n}(\nu_i\oplus\nu_{n-i-1})$, where $\mathop{mex}$ denotes the 'minimal excluded' value, with initial conditions $\nu_0=\nu_1=0$. Now the simplest thing to do is to just go look in Winning Ways for your Mathematical Plays, but since my copy is currently 3000 miles away, the next simplest thing to do is to start calculating and look for a pattern. We get $\{\nu_i: i\geq 0\}$ $=\{0, 0, *1, *2, 0, *1, *2, *3, *1, *2, *3, *4, 0, \ldots\}$, and this is enough to look for a pattern — which is to say, 'cheat' and look on OEIS for the sequence. Doing this, we come to https://oeis.org/A046695 which has more information and references.