It’s even worse than that, the function for the maximum number of nodes you end up before they start going down, if you play using the worst possible strategy, increases faster than any function which Peano arithmetic can prove to be total (i.e., it grows faster than any Turing machine run on various inputs, which Peano arithmetic can prove to halt for any input). To say that this grows faster than the Ackermann function is putting it very mildly.
I was skeptical at first, but consider it this way: At each step you make a subtree simpler, and then insert an arbitrary number of copies of the simpler subtree. Eventually you must end up with a large number of copies of the simplest possible subtree, a single node off the root. Those don’t grow the hydra when removed, so you you chop them all off and then win.
I found I could see this intuitively if I chopped the top-most head of the most-complex tree for the first several rounds, in most configurations; you’ll see whatever tree you’re working on get wider, but shorter. It helps to lower the starting number of nodes to 7 or so, as well.
I’m going to have to read the proof of the hydra game, because I pretty quickly got over 2.8k nodes and still in increasing...
It’s even worse than that, depending on how you start, you can easily get 100s of thousands of nodes...
It’s even worse than that, the function for the maximum number of nodes you end up before they start going down, if you play using the worst possible strategy, increases faster than any function which Peano arithmetic can prove to be total (i.e., it grows faster than any Turing machine run on various inputs, which Peano arithmetic can prove to halt for any input). To say that this grows faster than the Ackermann function is putting it very mildly.
Well, it doesn’t say you have to win quickly.
I was skeptical at first, but consider it this way: At each step you make a subtree simpler, and then insert an arbitrary number of copies of the simpler subtree. Eventually you must end up with a large number of copies of the simplest possible subtree, a single node off the root. Those don’t grow the hydra when removed, so you you chop them all off and then win.
I found I could see this intuitively if I chopped the top-most head of the most-complex tree for the first several rounds, in most configurations; you’ll see whatever tree you’re working on get wider, but shorter. It helps to lower the starting number of nodes to 7 or so, as well.
Yes, while it was clear on a second reading this was also clear, thanks.