We can think of this as a game of "omega-nim;" to more precise since the game you are describing is impartial, operating under the normal play convention, and finite we have that the Sprague-Grundy Theorem applies. In other words, to every "hydra-ordinal" there is an "omega-nimber."
Already this suggests thinking of the plus signs in the hydra as being something roughly analogous to the heaps in Nim. Let me make this precise.
Definition The set of hydras (or hydrae?), $\mathcal{H}$, is defined recursively as
- $0 \in \mathcal{H}$
- $ n \in \mathbb{N} \implies \omega^n \in \mathcal{H}$
- $ \kappa_0,...,\kappa_{n-1} \in \mathcal{H} \implies \sum_{i}\omega^{\kappa_i} \in \mathcal{H}$
We define the "winner function" as:
Definition We denote by $w(\kappa, n, i )$ the "winner of the game $\kappa$ at the $n^\text{th}$ step if it is currently $i^\text{th}$ player's ($i \in \{0,1\}$) turn to move," i.e. $n $ is the number of hydra heads that will grow out if player $i$ cuts a head off of $\kappa$ and $w(\kappa, n, i )$ is the winner under optimal play. Since $w(\kappa, n, i )= 1- w(\kappa, n, 1- i )$ we will sometimes just consider the case $w(\kappa, n) \overset{\text{def}}{=}w(\kappa, n, 0) $ for simplicity.
The answer to your question is to compute $w(\kappa,1,i)$; but of course, in order to answer it we are going to need to define the following
Definition A strategy is a $\sigma: (\mathcal{H} \setminus \{0\}) \times \mathbb{N} \longrightarrow \mathcal{H} $ such that $\sigma(\kappa,n)$ is a legal position at step $n+1$ that succeeds a legal position at $n$. Equivalently we could have allowed for a "virtual position/move" $-1$ and defined $\sigma': \mathcal{H} \times \mathbb{N} \longrightarrow \mathcal{H} \cup \{-1\}$ as $\sigma'(0,n) = -1$ and $\sigma'(\kappa,n) = \sigma(\kappa,n)$ otherwise. We let $\mathcal{S}$ be the set of all such strategies.
Let us try to define the winning $\sigma$ by taking cases on the different possible "heaps."
The heap has size 0 or 1
Since $w(0,n,i) = 1-i$ the strategy $\sigma(0,n)$ is meaningless (that's we defined $\sigma $ on $(\mathcal{H} \setminus \{0\})$); likewise we see that $w(1,n,i) = i$ so that $\sigma(1,n)$ is forced to be $0$. This easily generalizes to the following case
The hydra is a natural number
It is straightforward to prove by induction that $w(k,n,i) = 1- ((k+i) \% 2)$ where $\%$ is remainder after division since by the rules of the game no new hydras grow after cutting a head off a hydra of the form $\omega^0 + \omega^0 +... + \omega^0 = \omega \cdot k $. Likewise $\sigma(1,n)$
The hydra is of the form $\kappa + 1$
If $\kappa ' = \left( \sum_{i}\omega^{\kappa_i}\right) + 1 = \kappa + 1$ then $w(\kappa' ,n,i) = 1 - w(\kappa' - 1 ,n,i) = 1-w(\kappa ,n,i) $. This can proven by a "sum of games" style proof. The idea is the following: if it is $i$'s turn then either:
- making a cut on $\kappa$ wins the game,
- making a cut on $\omega^0 = 1$ wins the game,
- or none of the above
but these are respectively true if and only if
- The cut $\sigma(\kappa,n)$ loses the game (for the game $\kappa$ not $\kappa+1$) for all $\sigma$
- proof by induction using the following two observations: 1) $\omega^0=1$ (or "parity") is a "loop-invariant" of the game and 2) $\sigma(\kappa,n) < \kappa$ (see the proof of thm 2 of [Kirby; Paris] for the proof of the inequality) 3) eventually we will hit $\kappa \in \omega $ for any strategy $\sigma$ ( once again see [Kirby; Paris]) which is the previous case
- the position $\kappa$ is a losing position, but this is true iff the first case is true
- or none of the above, but this is true iff the first case is false
Therefore the game is lost or won regardless of what move is made; it only depends on the "parity."
The hydra is of the form $\kappa + \lambda $
By a proof by induction and using the fact that $\sigma(\kappa,n) < \kappa$ and $\sigma(\lambda,n) < \lambda $ (see thm 2 of [Kirby; Paris]) we have that
\begin{equation}
w(\kappa + \lambda , n ) = w(\kappa , n ) \oplus w( \lambda , n ) \oplus 1 .
\end{equation}
Since we have already proven it for $\lambda =1$ and we can assume $\kappa > 2$ we can take the following cases in the induction
- Player 1 cuts $\kappa$ then Player 2 cuts $\kappa$
- Player 1 cuts $\kappa$ then Player 2 cuts $\lambda$
- Player 1 cuts $\lambda$ then Player 2 cuts $\kappa$
- Player 1 cuts $\lambda$ then Player 2 cuts $\lambda$
Which all lead to smaller cases to which we can apply the induction hypothesis.
Lets verify for simple examples: since $\sigma(\omega,n) = n $ we have that $w(\omega,n) = n \% 2 $ and also $w(0,n) =1$ which agrees with $w(\omega+ 0 ,n) = n \% 2 = w(\omega , n ) \oplus w( 0 , n ) \oplus 1$. Similarly $w(\omega+ 1 ,n) = n \oplus 1 = w(\omega , n ) \oplus w( 1 , n ) \oplus 1$ and more generally we have that $w(\omega+ k ,n) = n \oplus k = w(\omega , n ) \oplus w( k , n ) \oplus 1$. Likewise by a second induction we have that
\begin{equation}
w\left(\sum_i \kappa_i , n \right) = 1 \oplus \bigoplus_i w( \kappa_i , n ) .
\end{equation}
The hydra is of the form $\omega ^ \kappa $
The point here is that is $\omega ^ \kappa \neq \omega ^ {\lambda +1}$ for all $\lambda \in \mathcal{H}$ then all of the cuts are made inside of the $\kappa$. By induction, we also see that if $\omega ^ \kappa = \omega ^ {\lambda +1}$ then $w(\omega^\kappa,n)$ only depends on the parity of $n$ since if $\sigma$ is the "subtract 1" cut then $\sigma(\omega^\kappa,n) = \omega^\lambda \cdot n$ and $w(\omega^\lambda \cdot n, n+1, 1 ) = \bigoplus_i w( \omega^\lambda , n+1 ) $ by the previous section, so that $w(\omega^\kappa, n ) = \min\{1 \oplus \bigoplus_i w( \omega^\lambda , n + 1) ,1 \oplus w(\kappa, n )\}$ by a similar proof to the last section. The second term corresponds to the following: if player 0 can lose/win the game $\kappa$ then $\kappa$ corresponds to an odd/even game, but when the time finally comes to split $\omega^1$ player 1 will be left with an even/odd game.
Best Answer
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$.