My question is which player has a winning strategy in the two-player version of the Killing the Hydra game?
In their amazing paper,
- Kirby, Laurie; Paris, Jeff, Accessible independence results for Peano arithmetic, Bull. Lond. Math. Soc. 14, 285-293 (1982), ZBL0501.03017,
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 involves some fascinating issues in mathematical logic, because of its connection with Goodstein's theorem. Specifically, what Kirby and Paris proved is
Theorem.
Every strategy in the Killing the Hydra game will eventually succeed in killing the Hydra; and
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.