The seven were the order

Sylver Coinage is played by naming positive integers in turn. A number that is a sum of numbers already named may not be named, and whoever is forced to name 1 loses. A position is described by its gaps — the numbers still nameable — and a position whose gaps pair off around the largest one is a win for the player to move, a fact the pairing test uses to strike moves that would hand the opponent such a position. A move the test does not strike is a survivor.

A different question at every depth priced a proof over survivors against the search that simply finishes. The finishing search is memoised, skips struck moves and stops at the first winning move; the proof deepens one odd depth at a time and must show that every surviving reply is answered within the remaining depth. Over all 1,766 irreducible positions with up to twenty gaps, even the cheapest possible proof — one told the right depth in advance — was dearer than finishing on all but seven. On all seven, the essay noticed, the winning move came fifth when moves were tried smallest first, which is the order every search there used. It closed on the question that observation raises: whether the order is the whole story.

It is.

Five orders, and what each one costs #

The two searches are run exactly as before, charged a closure for every move they examine, with one change: both try moves in the same order, and the order is varied.

Smallest first is the order already published, and it reproduces the result exactly: the told proof is cheaper on 7 of 1,766 positions and costs 2.47 times the finishing search at the median. Largest first tries the biggest nameable number first. Both of these read only the numbers themselves, so a search using them can examine moves one at a time and stop at the first that wins.

Two further orders read a property of the position a move leaves. A shortlist with nothing at the top scored seven such properties as predictors of the winning move, and the best — prefer the survivor that leaves the smallest largest gap — put a winning move first on 24.9% of positions against 22.3% by chance. That order and its reverse are run here. They carry a cost the lazy orders do not: to sort moves by what they leave, a search has to compute every move’s result first. At every position it expands, it pays for a full scan before it tries anything.

And the fifth order is not an order a program could use. The oracle puts a winning move first at every position, found without charge. It is the floor under every real order: no ordering heuristic can make either search cheaper than this, so whatever gap remains between the two searches under the oracle is not a matter of order at all.

The seven do not survive #

The seven positions where the proof won are a family: six of them have gaps one to five, then every odd number up to some point, then one larger gap — 1, 2, 3, 4, 5, 7, 9, …, 21, 27 is the first. On every one, the winning move is 7, and smallest first tries 2, 3, 4 and 5 before it. That every one of these positions is won at all is every move closes the largest gap: gaps that pair off around the largest never lose for the player to move, by a strategy-stealing argument that names no move — which is exactly why finding the move is the whole of the cost. The finishing search must refute each of those four losing moves completely before it reaches the one that wins, and refuting a losing move in Sylver Coinage means finding the opponent’s winning reply and proving it, a whole search in itself. The proof, told its depth, abandons each losing candidate as soon as one surviving reply escapes the depth, which on these positions is quickly.

The seventh is a twenty-gap position of a different shape, with gaps one to eight and then a scattering up to 38, and under every other order it goes the same way as the six.

Change the order and the seven are gone. Under largest first, under both gap-sorted orders and under the oracle, the proof is dearer than the finishing search on every one of the seven. Not one position of the published exceptions is an exception under any other order. That is the cleanest possible answer to the question the earlier essay left: if the seven had been positions whose structure made proofs cheap, some of them would have survived at least one other order, and above all the oracle, which removes nothing a proof needs. None does. Their structure made smallest first expensive for the finishing search, and nothing else.

A bad order manufactures new ones #

What replaces them is more telling than their disappearance. Under largest first the proof is cheaper on fifty-five positions; under the order that prefers the largest gap left, on forty-eight. The order the shortlist essay found most predictive of the winner gives five.

The totals say why. Largest first is a bad order for both searches: it nearly doubles the finishing search’s total, from 1.54 million closures to 2.96 million, and nearly doubles the proof’s, from 4.94 million to 9.53 million. But the two searches suffer differently on different positions. The finishing search must refute every losing move it tries before the winning one, in full. The proof must refute them only to a depth, and gives up on each candidate at the first surviving reply that escapes. So an order that puts losing moves first costs the finishing search the whole of each refutation and the proof only part of it. On positions where the bad order puts several losing moves ahead of the winner, the finishing search’s cost balloons past the proof’s.

The six positions where largest first gives the proof its widest margin show the pattern directly. On each, largest first makes the finishing search several times dearer than smallest first does, while the proof’s cost moves less. The proof’s win is the finishing search’s loss, not a saving of its own. And with the winning move first, both searches shrink to a fraction of their cost and the proof is dearer on every one of the six.

So the exceptions are an artefact with a mechanism. A position is an exception when the order puts enough losing moves ahead of the winner that refuting them in full costs more than refuting them to a depth. Every order has such positions, and different orders have different ones. None of them is a position where proving is cheap.

Why a losing candidate costs the two searches differently #

The asymmetry deserves spelling out, because it is the whole mechanism and it is not specific to Sylver Coinage.

A search at a won position tries candidate moves until one wins. Every candidate tried before the winner is a losing move, and each has to be rejected. The two searches reject a candidate by different arguments. The finishing search rejects it by proving that the position it leaves is won for the opponent: it must find one of the opponent’s replies and show that reply wins, which means showing that every one of the mover’s answers to it loses, and so on to the end of the game. The rejection is a complete sub-proof, as large as the position it leaves.

The proof rejects a candidate by showing only that the candidate does not win within the remaining depth: it walks the opponent’s surviving replies and stops at the first one that the mover cannot answer within the depth left. It does not need to show that the reply wins, only that it escapes, and escaping a depth is a weaker thing to prove than winning. When the depth is small — and on six of the seven it is five, on the seventh nine — the rejection is short.

So a losing candidate costs the finishing search a full refutation and costs the proof a bounded one. A position where the order tries many losing candidates before the winner is a position where the proof’s bounded rejections add up to less than the finishing search’s complete ones. That is the only way the proof ever wins, under any order, and the oracle — which never tries a losing candidate at a won position — removes it completely. What is left under the oracle is the part of the proof’s cost that has nothing to do with rejected candidates: the depth-indexed questions at the opponent’s positions, asked once per depth instead of once.

The same asymmetry is at work on Domineering in a proof inside a budget, with the roles of cost and depth arranged differently. There a certificate gives up on nothing — every iteration searches every line to its cut — and so it has no cheap rejections to set against its repeated iterations, and it never wins at all. Here the told proof has cheap rejections and one iteration, and it wins exactly when an order hands it enough rejections to be cheap about.

The best predictor is not the cheapest order #

One more comparison falls out of the totals, and it is a caution about what a good order is.

The order that prefers the survivor leaving the smallest largest gap is the one a shortlist with nothing at the top found most likely to put a winning move first — a quarter of the time, against a little over a fifth by chance. As an order for the finishing search it costs 2.20 million closures in total, against 1.54 million for smallest first. The better predictor is the dearer order, by forty-three per cent.

The reason is the scan. Smallest first examines moves one at a time and stops at the first winner, so on a position where the winner comes early it has examined almost nothing. The gap-sorted order must compute every move’s result before it can sort, at every position it expands, so it pays for the whole move list even where the winner would have come first anyway. A predictor that is right a quarter of the time cannot buy back a full scan at every node. Among the orders a program could actually run, smallest first is the cheapest for both searches, and the reason it is cheapest is not that it predicts well — it predicts barely better than chance — but that it costs nothing to follow.

That puts the oracle’s number in proportion. The finishing search with a free winning move first costs 29% of smallest first; every real order tried costs more than smallest first. The distance between what is available and what is possible is a factor of more than three, and nothing measured here closes any of it.

The floor #

The oracle is the measurement the question needed, because it removes order from the comparison entirely.

With a winning move always first, the finishing search’s total falls to 29% of its smallest-first cost and the proof’s to 16%. The perfect order helps the proof more, as it should, since the proof’s losing candidates were its larger expense. And still the proof is cheaper on none of the 1,766 positions. At the median it costs 1.6 times the finishing search; in total, 804,515 closures against 444,803.

What remains is not order. With a winning move first, the finishing search at a won position examines that move and then proves the resulting position lost: every reply the opponent has must be answered, each by the opponent’s position being won for the mover again, recursively, but each answered by finding one winning move, and with the oracle that move is found first. The proof at a won position does the same with one difference: it must show each reply answered within the remaining depth, and a position proved within five moves is a different question from a position proved within seven. The finishing search asks one question of a position, is it won; the proof asks a question indexed by depth, and a position reached at two depths is two questions. The tree and the graph made the corresponding point about routes and positions: a memoised search’s economy is that it asks about each position once, and any scheme that keys its questions by something more than the position gives that economy away. That is the essay before this one’s title, measured now with the confounding factor removed: it costs about sixty per cent more even when every move is chosen perfectly.

The ratio does not fall with the gaps #

Positions with more gaps are dearer for both searches, and it was possible that the proof’s price was a fixed overhead that larger positions would amortise. By the number of gaps, the median ratio stays above one at every size from six to twenty under every order, and it does not trend downward. The oracle’s line is the lowest, as it must be, and it too stays above the line of parity. There is no size at which the proof’s question becomes cheaper to answer than the finishing search’s, within the range where both can be run.

The convention, and what the census counts #

Sylver Coinage under the convention the game that is a number system sets out: naming 1 loses, so 1 is never a move. The census is every irreducible position — gaps pairing off around the largest — with up to twenty gaps, 1,766 of them, enumerated as numerical semigroups by genus and checked against the published counts. Every search is charged one closure per move examined, the unit of the two essays before, so the smallest-first figures reproduce theirs. The gap-sorted orders are charged a closure for every move at every position they expand, because a program sorting by what a move leaves has to compute it; the oracle is charged nothing for its knowledge, because it is a floor rather than a method. The depth the told proof is given is found by an uncharged deepening, as before.

What five orders cannot show #

Five is not all. A better order than any tried here might put the winner first more often than a quarter of the time, and nothing rules out an order that is both cheap to compute and near the oracle. What the oracle does rule out is that any order, however good, makes the told proof cheaper than the finishing search: the floor is above parity everywhere. The costs are closures, not time. A closure on a position with twenty gaps costs more than one on a position with six; a timing would weigh the large positions more heavily, and the ratios could shift. And the two searches are compared, not the best of each. A finishing search with a transposition table shared across positions, or a proof that orders its candidates by the previous depth’s results, is a different pair of searches, and neither is run here.

Still open: an order a program can compute #

The oracle cuts the finishing search to under a third of its smallest-first cost, and every real order tried is worse than smallest first. The order the moves are tried in found, for Domineering, that trying first the move leaving the opponent fewest replies cut a who-wins search twenty-seven-fold against the worst order. The Sylver analogue — prefer the survivor that leaves the opponent fewest survivors — was scored by a move whose every reply is struck as a predictor and found no better ordered than one move at a time. Whether any order a program can afford recovers a meaningful part of the distance between smallest first and the oracle, for the finishing search alone, is the question that is left. The comparison with proofs is settled: with every order, including the perfect one, the finishing search is the cheaper way to know.