49
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I suspect that there's a fairly natural ruleset such that every clopen game of rank $<\epsilon_0$ can be represented as a two-person hydra game, possibly up to some fairly benign transformations; if so, for each ${\bf d}\le_T{\bf 0^{(\epsilon_0)}}$ there will be a game of that type all of whose winning strategies compute ${\bf d}$ (and since every clopen game of rank $<\epsilon_0$ has a winning strategy computable in ${\bf 0^{(\epsilon_0)}}$ that's optimal). $\endgroup$ – Noah Schweber May 10 at 20:53
  • 3
    $\begingroup$ This is a wonderful question and I regret that I can only give it one upvote. $\endgroup$ – JoshuaZ May 10 at 20:57
  • 3
    $\begingroup$ Maybe the analysis of Hackenbush game might be useful, and equivalently there a might be a natural way of analysing this game as version of Nim that grows more heaps? $\endgroup$ – omer May 10 at 21:01
  • 2
    $\begingroup$ I suggest the following variant, which avoids making arbitrary assumptions about how the hydra grows heads, and which may be more amenable to an explicit description: first Alice plays as Hercules, then Bob plays as the Hydra (i.e., chooses the number of copies made), then Bob plays as Hercules, then Alice plays as the Hydra, and so on. $\endgroup$ – Gro-Tsen May 10 at 22:44
  • 4
    $\begingroup$ Is this necessarily a simple problem? Given an arbitrary non-drawn chess position, either White has a winning strategy from that position or Black does, but figuring out which one has it can be extremely difficult, and analysis must be specific to that position. These hydras can be much more complex than chess positions. You may have to just calculate it to the end. In fact maybe there could be a complexity result lurking in this question. I mean it takes stronger axioms than PA to prove that the game is guaranteed to end at all... $\endgroup$ – none May 11 at 1:39
21
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Great! This is excellent. For those readers who might benefit, here is an accessible account of transfinite Nim that I wrote on my blog a few years back: jdh.hamkins.org/transfinite-nim. $\endgroup$ – Joel David Hamkins May 11 at 9:06
  • $\begingroup$ Thanks! I will be sure to check it out; it might make the problem easier to attack. $\endgroup$ – Pedro Juan Soto May 11 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.