Shared publicly  - 
 
Try playing +Andrej Bauer's version of Hercules versus the Hydra! It's here: http://tinyurl.com/yt6rmm

At each stage, click on a blue 'head' to cut it off.  Your goal is to cut off all the heads.  But the heads grow back.  At the nth stage, the Hydra grows n new copies of the part above and including the branch directly below the head you cut off.  If that sounds confusing, just try the game and see how it works.

No matter how you play this game, you'll eventually win.  This fact can be shown using mathematical induction up to the ordinal

ε₀ = ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^..........

But it may take a long time to win - perhaps much longer than the age of the universe!  If you get frustrated, set the initial size to something small.  Then the game gets easy.

Can you see why you'll always eventually win?  +Andrej Bauer sketches the proof in his explanation of the game:

http://math.andrej.com/2008/02/02/the-hydra-game/

#bigness  
26
5
John Baez's profile photoToby Bartels's profile photoHarald Hanche-Olsen's profile photoDouglas Thomas Ryddner's profile photo
16 comments
 
I don't have the patience to win the game in the version that automatically comes up, with initial size 9.  I think I'm playing it optimally, but after 100 steps the hydra has 83,703 heads.  Can anyone do better?
 
What? I just beat it with 9 heads(70 steps). You try cutting the roots after you have created another row. Then remove the row. 

Repeat until 1
 
Actually I was lucky. There was only 1 level to each head for me so it was easy
 
I began playing it with 9 heads, following my strategy from the other thread, but it crashed on step 119 with size 7124.  Everything below the row that I was working on had long since become illegible.
 
I beat it with 104 steps with 9 heads, but your success will be dependent on the graph that you start with the game does a partial combinatoric(?) expansion - another go had me beating it with 4000 some-odd steps...
 
It seems like "click on the rightmost" is a fairly quickly winning strategy.
 
I hadn't realized that each time you start the program it creates a different tree with 9 nodes.  I may have been using a suboptimal strategy, but it sounds like Peter was immensely lucky his first time! 
 
I finish 9 in 39 steps. And then even in 25 steps. It strongly depends on initial...
 
In the best case, you can finish 9 in 9 steps (but I haven't done that).
 
From a very cursory look at this game, I would conjecture that an optimal strategy will always prescribe removing one of the tallest heads (i.e., the farthest from the root). But which one? A greedy strategy would be to always strive for the lowest possible ordinal in each step. But greedy strategies are frequently far from optimal.
 
I was going for the highest ordinal at each step, but my bad luck at the game makes me suspect my strategy was suboptimal,  maybe even pessimal.
 
It seemed to me that going for the heads up higher made for a very long game, while going for the lower heads first and chopping off heads from right to left typically got me winning within 100 or so turns (that's with size 9). It also seems like there's huge differences in difficulty between certain games, even of the same size.
 
I was thinking that chopping off the highest heads soon would be better because the highest heads tend to create the most new heads, so it's good to 'get it over with' in early stages of the game.  But reading what I wrote I instantly see it's not that simple: the number of new heads is not a function of the height of the head you cut off; it's the stage number times the number of heads that will regrow when you cut off that head!
 
I'm a bit confused by the wording: "the number of new heads is not a function of the height of the head you cut off; it's the stage number times the number of heads that will regrow when you cut off that head!"

Wait... so the number of new heads is not the number of heads that will regrow when you cut off that head? What do you mean by each then in that case?
Add a comment...