Two ways to end with no bound

The condition the recursion rests on is that play stops. Every value on this site is defined by a recursion over options, and a recursion over options is well-founded exactly when no position can be played for ever.

Most games here satisfy it for a boring reason: something visibly gets smaller. A Nim heap shrinks, a Domineering board loses two squares, a Hackenbush drawing loses an edge. Count the squares and the game has a length before it starts. At the far end of that grade sits a fixed-length game — Brussels Sprouts lasts the same number of moves however it is played, so the length is not merely bounded but settled before anybody draws anything.

Two games on this site do not work like that, and they fail differently.

Sylver Coinage, and the quantity that goes down #

The rules are two lines. Players alternately name a positive integer that is not a non-negative combination of the numbers already named; whoever names $1$ loses. The game that is a number system is where it lives on this site, and where the first move of $16$ is worth a thousand dollars to whoever settles it.

Termination is not obvious from the rules, because nothing shrinks: the set of named numbers grows, and the numbers themselves can be as large as a player likes. A first move of one thousand and one leaves almost every number still available.

What goes down is the set of numbers still nameable — the gaps of the numerical semigroup generated by what has been named, and the count of them is that semigroup’s genus. Once the named numbers have greatest common divisor one, the gaps are finite, and every move names a gap and therefore removes at least one of them. So the game ends, and it ends within the number of gaps.

That is a bound with a number in it, and the number is computable in a moment: sieve upward until a run of consecutive reachable numbers as long as the smallest generator appears, and count what was missed.

The bound is exact #

A bound is worth what it predicts, and an over-estimate that is never approached is a weak thing. So the longest possible play from each opening was searched for exhaustively.

From $\{5, 7\}$ the gaps number twelve and the longest play is twelve. From $\{4, 7\}$ nine and nine. From $\{5, 6\}$ ten and ten. From $\{2, 3\}$ one and one.

Ten openings, and in every one the longest play uses every gap there is. That is the same kind of statement as a period certifying an infinite claim from a finite window — a computation over a bounded set settling something about every play there is — and it is available here for the same reason: the quantity being counted is finite from the start. The bound is not an over-estimate at all; it is the exact length of the longest game, and a player who wants to draw a game out has a rule for doing it — name a gap that removes only itself.

The smallest position where a player has any choice at all is worth drawing, because at that size the exhaustive search is something a reader can run by eye rather than take on trust.

One generator smaller in each place and the bound has something to bound, because now there is more than one way to spend the gaps.

That last pair of sentences is the reason a bound and a strategy are different objects. The bound says the game is over within three; the winner says it is over in two; and both are exact, because the search that produced them enumerated every play there is.

The hydra, where nothing goes down #

The rules are again two lines. Hercules cuts off a head; if the head had a grandparent, the neck it stood on is copied as many times as the move number, and the copies grow back. The game ends when the hydra has no heads left.

Every chop makes the tree bigger, usually much bigger, and the number of copies grows with the move number. Nothing a reader would think of counting is decreasing: not heads, not necks, not nodes, not depth. The hydra taken on its own terms draws the fight step by step and watches the tree explode; what is wanted here is only the column the drawing sits under.

What goes down is an ordinal — a transfinite label assigned to the tree, where a head is $0$, a node is the sum of the ordinals above it, and depth becomes exponentiation. Chopping a head replaces a large ordinal by a smaller one, however many copies grow back, because the copies are all strictly below the level that was removed.

A descending sequence of ordinals is finite. That is the whole proof, and it needs no bound because it needs no counting. It is the same move the surreal construction makes to get past every finite day, used here for a game whose positions are entirely finite.

What the difference costs #

A four-node hydra — a head two levels deep — dies in twenty chops. Adding a single spare head takes it to twenty-one. Adding a level instead takes it past two hundred and seventy-nine, at which point the tree has passed forty thousand nodes and the computation here stops without the hydra dying.

So a five-node hydra can take seven chops, twenty-one, or more than two hundred and seventy-nine, and nothing about the drawing announces which. There are three of them in the table and those are their three answers. The lengths are not merely large, they are not a function of the size in any usable sense: two of those three differ by a factor of at least thirty-nine, and the six-node one in the table is not finished either.

That is the practical content of the difference. A solver given a Sylver position can print this will be over within twelve moves and be right. A solver given a hydra can print this will end and nothing else — and the second statement, while true, does not let it allocate a buffer, set a search depth, or promise an answer by any particular time.

What a solver actually does with a bound #

The phrase a solver can promise is doing work, and it is worth spending a paragraph on what the promise buys, because it is not merely comfort.

A search over a game tree needs to know how deep it can go. With a length bound in hand the search can be written as a loop with a counter, its memory allocated in advance, and its worst case stated before it runs. Without one it needs a recursion that may exhaust the stack, a memo table that may exhaust the heap, and a caller prepared for either.

That is why the two termination proofs feel so different in practice despite proving the same kind of thing. What an exact evaluator can and cannot reach is a question about sizes, and a game with a per-position length bound has a size; a game without one has to be run and watched.

The hydra makes the point crudely. The computation behind the table above stops two of its nine rows because the tree passed forty thousand nodes, and there was no way to know in advance which two rows those would be — the two are a six-node hydra and a five-node one, and the two five-node hydras that do finish have exactly as many nodes as the one that does not.

The one thing both proofs need #

Neither argument mentions who is winning, and that is not an accident. A termination proof has to work whatever the players do, including badly, because the recursion that computes a value visits every line and not only the good ones.

Sylver’s count decreases on every legal move, chosen well or badly. The hydra’s ordinal decreases on every chop, whichever head Hercules takes — and the hydra’s own choices are not choices at all, since the regrowth is forced. So both proofs quantify over all play rather than over optimal play.

That distinguishes them from the other way a game can be known to end, which is that a player can force it to. Loopy games are where that distinction bites: a position may have infinite lines in it and still be a win for somebody, and the analysis then has nothing to do with a decreasing quantity and everything to do with who can steer.

It also explains why neither game appears on the cost chart the section above pointed at. Every family plotted there has a size on the horizontal axis, and a size is only worth plotting when the length of the game is a function of it. Neither of these two has one that works: two Sylver positions with the same number of gaps agree on the bound and can still want different moves, and three hydras with five nodes each take seven chops, twenty-one, and a number nobody here has counted to.

Why one proof has a number in it #

The two proofs have the same shape and different ingredients, and the shape is worth writing out because it is the shape of every termination proof there is.

Find a quantity that strictly decreases with every move, and take values in a set with no infinite descending chain. Sylver’s quantity is the count of gaps and the set is the natural numbers. The hydra’s quantity is an ordinal and the set is the ordinals below $\varepsilon_0$.

The natural numbers have a property the ordinals do not: a value in them is a bound. Knowing the count of gaps is twelve is knowing the game lasts at most twelve moves, because each move spends one and there are no other units. Knowing a hydra’s ordinal is $\omega^\omega$ is knowing the fight ends, and says nothing at all about how many chops it takes, because a single step down from $\omega^\omega$ can pass through arbitrarily large finite numbers.

So the difference is not about the games. It is about which well-founded set the decreasing quantity lives in, and whether a member of that set can be read as a count.

Both games have an unbounded family #

There is a symmetry worth preserving, because it is easy to read the last two sections as saying Sylver is tame.

It is not. The bound is per position, and it has no upper limit across positions: a first move of $n$ leaves a game whose length grows with $n$, so no number bounds the game as a whole. Sylver Coinage is unbounded-but-finite in exactly the sense the phrase means, and a solver that wanted to promise something before the first move is made can promise nothing.

The hydra is the same, one level up. Its length is bounded per position too — every fight is finite — and the bounding function grows so fast that no expression built from addition, multiplication and exponentiation catches it. The difference is not bounded versus unbounded; it is that Sylver’s per-position bound is computable in a moment and the hydra’s is not computable in any useful sense.

Between those two there is a hierarchy, and the games on this site sit almost entirely at the bottom of it, which is why the recursion works.

Sylver’s proof is not the one it looks like #

One more thing separates the two, and it is why the comparison is worth making at all.

The Sylver argument above appears to be an ordinary induction on a decreasing count, and it is — once the greatest common divisor is one. Before that it is not, because the gaps are infinite and the count does not exist. What guarantees the divisor reaches one is a separate argument, and the classical route to it is Dickson’s lemma: any set of positive integers has finitely many minimal elements under divisibility, so the process of adjoining generators cannot go on for ever without stabilising.

Dickson’s lemma is a finiteness statement with the same flavour as the ordinal argument — a well-quasi-ordering result rather than a count — and it is doing the load-bearing work at exactly the point the count is unavailable. So the honest description of Sylver’s termination is a hard argument that finishes, followed by an easy one with a number in it, and the number is only available on the far side.

Once the count is available it is a very good one, and it is worth seeing how little of the position it needs to know. Two openings can agree on the bound, agree on the largest gap, and be different games.

So the bound is genuinely a bound and genuinely not the analysis. It is a count of the moves that remain, and it is exact about the length while saying nothing about which of them to make — which is the same division the hydra has, with the difference that on the hydra’s side of it there is no count to begin with.

The longest game, and how to play it #

The exhaustive search behind the Sylver column does something a bound alone cannot: it names the play.

To draw the game out to its full length, name a gap whose removal removes only itself. Such a gap always exists while more than one remains — the largest one, the Frobenius number, is always removable on its own, because nothing above it is a gap and nothing below it becomes reachable by adding it to what is there. Take the gaps from the top down and every move costs exactly one, which is the longest the game can possibly last.

That is a strategy for a purpose nobody has: it is a rule for losing slowly rather than for winning. But it is what turns the bound from an inequality into an equality, and it is the reason all ten openings come out at the bound rather than under it.

The two rules are not always opposed, and the position where they coincide is the clearest picture of what the slow rule is doing.

The hydra has the mirror. Hercules can shorten the fight by taking heads near the root, since a head with no grandparent triggers no regrowth at all; the table above uses the opposite rule — always take the deepest head — precisely to see how long the fight can be made. Nothing about the ordinal argument cares which rule is used, and the difference between the two is the difference between twenty chops and a number this machine cannot reach.

What each game is really about #

Sylver Coinage is about numerical semigroups: every position is one, the moves adjoin generators, and the whole game is a walk through the lattice of them. Its termination is a fact about that lattice rather than about the game, and it would be true of any process that adjoins generators, whether or not anybody was competing.

The hydra is about proof strength. It was written down to exhibit a statement that is true, is about finite objects, and cannot be proved by the induction that ordinary arithmetic has available — the fight ends, and saying so needs the ordinals. Its termination is the point rather than a precondition.

So the two games are not two examples of one phenomenon. They are a game whose termination is inherited from an algebraic structure, and a game constructed so that its termination could not be inherited from anything, and the comparison in this essay is really between those two situations.

Two unboundednesses, and only one of them threatens the recursion #

The two games here are both unbounded and it is worth being exact about what each is unbounded in, because the recursion cares about one and not the other.

Unbounded in size means the positions can be arbitrarily large: a heap of any number, a board of any dimensions, a row of any length. Every family on this site is unbounded in that sense and none of them is a problem, because the recursion is about a single position and a single position is finite.

Unbounded in length means a play can go on for ever, and that is the one that bites. The recursion computes a value by recursing into options, and it terminates because every line of play is finite — the condition it rests on. A game where play need not end has no bottom for the recursion to reach, and there is no value to compute rather than a value that is hard to compute.

The two are independent and easy to confuse, because both are described by saying a game has no bound. A game unbounded in size and bounded in length is ordinary; a game bounded in size and unbounded in length is loopy and outside the whole apparatus; and a game unbounded in both is the second problem with the first one added.

That distinction decides which techniques survive. Unboundedness in size costs a closed form and keeps the theory; unboundedness in length costs the theory and leaves a graph to be analysed backwards. Comparing two such games without separating the two senses is comparing a hard instance with a different subject.

What the comparison cannot say #

The hydra lengths here are cut off. Two of the nine positions do not finish inside a cap of forty thousand nodes, and their entries in the table say so rather than reporting a number. A row that stopped because a limit was reached and a row that stopped because the hydra died are different facts, and a table reporting one number for both would be claiming the second.

The Sylver openings are all two-generator positions, which is the case where the gaps are finite from the start. The interesting Sylver positions are the ones after a single move, where the whole difficulty is that the gaps are not yet finite — and this table says nothing about them, because there is nothing to count.

And nothing here measures where a game sits in the hierarchy between the two. That is a real and studied question with a real answer — the strength of the induction needed to prove termination — and it is the rung this pair of games is pointing at rather than reaching.

Where the ladder goes next #

termination has three rungs: the condition the recursion needs, a game that ends with nothing saying when, and now two such games compared.

The rung above is the hierarchy the last section names. Between ends within a computable bound and ends, with no computable bound at all there are levels, each corresponding to a strength of induction, and knowing which level a game sits at is knowing exactly what a solver can promise about it. Placing this site’s games on that scale would be a piece of work with an answer for every one of them.

Two neighbours are worth the trip. It ends, and nothing says when is the hydra taken on its own terms, where the growth of the tree is the subject rather than half of a comparison. And the game that is a number system is Sylver Coinage taken on its, where the termination is a footnote and the open problem is the point.