[Math] In the two-person Killing the Hydra game, what is the winning strategy

combinatorial-game-theorygoodstein-sequencesindependence-resultslo.logicpeano-arithmetic

My question is which player has a winning strategy in the
two-player version of the Killing the Hydra game?

In their amazing paper,

Laurie Kirby and Jeff Paris introduced the Killing the Hydra game,
in which one attempts to kill the Hydra by cutting off its heads.
At stage $n$, when you make a cut, just below a head, the Hydra grows $n$ copies of
itself, copies of the position from one lower node (if any) up to the node preceding the neck that had been cut, and whatever is above that node. To illustrate, here are some initial moves in the Hydra
game:

The Hydra game

The Hydra game involves some fascinating issues in mathematical
logic, because of its connection with Goodstein's
theorem.
Specifically, what Kirby and Paris proved is

Theorem.

  1. Every strategy in the Killing the Hydra game will eventually succeed in
    killing the Hydra; and

  2. This fact is not provable in Peano Arithmetic (PA).

My question here, however, is concerned with the natural
two-player version of the game. Specifically, given a finite
Hydra tree, we play a two-player version of the Killing the Hydra
game, where each player makes a cut on their turn, and the Hydra
grows new heads according the original Hydra rules. The first
player without a move loses—you want to cut the very last head.

Question. Which player has a winning strategy? What is the
winning strategy?

Since every play of the game will lead eventually to a win for one
of the players, it follows by the fundamental theorem of finite
games that one of the players will have a winning strategy. Which
player is it that has the winning strategy? And what are the
winning moves?

The Kirby-Paris theorem is quite robust with respect to the game rules, for it works even when the Hydra grows many more than $n$ copies at stage $n$, or fewer; but I expect that the two-player version might be sensitive to such changes in the rules. Please provide an answer for any reasonable version of the game to which the Kirby-Paris theorem still applies.

Best Answer

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

  1. $0 \in \mathcal{H}$
  2. $ n \in \mathbb{N} \implies \omega^n \in \mathcal{H}$
  3. $ \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:

  1. making a cut on $\kappa$ wins the game,
  2. making a cut on $\omega^0 = 1$ wins the game,
  3. or none of the above

but these are respectively true if and only if

  1. 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
  2. the position $\kappa$ is a losing position, but this is true iff the first case is true
  3. 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

  1. Player 1 cuts $\kappa$ then Player 2 cuts $\kappa$
  2. Player 1 cuts $\kappa$ then Player 2 cuts $\lambda$
  3. Player 1 cuts $\lambda$ then Player 2 cuts $\kappa$
  4. 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.

Related Question