Start at four

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 has only 1 left to name loses. A position is described by its gaps, the numbers still nameable, and every move closes the largest gap proved that a position whose gaps pair off around the largest — a symmetric one — is never lost for the player to move. The search this essay is about uses that fact at every step: a move that would leave the opponent a symmetric position is struck by a one-pass test and not searched, and among the moves that survive, the search stops at the first that wins.

The order the survivors are tried in decides what that search costs. The seven were the order ran it under five orders over all 1,766 irreducible positions with up to twenty gaps — every one a win for the player to move — and counted closures, one for every move examined. An oracle that puts a winning move first, for free, cut the cost to 29 per cent of trying the smallest move first. Every order a program could compute — largest first, or sorting moves by the largest gap they leave — did worse than smallest first, and the essay closed: the distance between what is available and what is possible is a factor of more than three, and nothing measured closes any of it.

Some of it closes, and the part that closes turns out to be a fact about the rules rather than a trick of search.

The orders a game program uses #

Two kinds of order had not been tried, and both are standard in game-playing programs.

A history table keeps a count, for each number, of how often it has been the winning move anywhere in the search so far, and tries the most successful numbers first. It knows nothing about the position; it only remembers. It costs no closure to consult, so it is lazy in the sense that matters here: the search still examines one move at a time and stops at the first winner. The table here is reset for each position searched, so each search learns only from itself.

A fixed learned order is the same idea done once, in advance, by the program’s author. Count which numbers win in the searches of small positions, sort them, and ship the sorted list. Here it is taught on the positions with at most fourteen gaps and tested on the 1,448 with fifteen to twenty, so that what it learned is not the answer it is scored on. And as a control there is the order that knows nothing at all: each position’s moves in a fixed random order, as cheap to follow as smallest first.

And there is a reading the census already offers. A parity with a first exception found that a position with an odd number of gaps is lost for the player to move far more often than one with an even number, so a move that leaves an odd number of gaps is the better first guess. That order has to compute every move’s result before it can sort them, and it is eager: at every position it expands it pays for the whole move list.

The random control loses badly, for a reason that turns out to be the key to the rest, and it is taken up below. The history table wins back 27.5 per cent of the gap between smallest first and the oracle. It is the first order a program could compute that beats smallest first at all, and it beats it on 1,489 of the 1,766 positions. The learned order does the same on the positions it never saw — 27.3 per cent — so what the table learns in a search is not specific to that search. And the table and the learned order agree about what to try first.

The table learns to skip two and three #

The most frequent winning moves are 4, 9, 6, 5, 8 and 7. The learned order begins 4, 6, 5, 7, 8, 9. What both have discovered is not a ranking among the middle numbers, which they disagree about, but that 2 and 3 almost never win — and smallest first tries them first, at every position of every search.

That suggests an order that needs no learning at all: smallest first, but starting at four, with 2 and 3 tried last. It is as lazy as smallest first — it reads nothing but the numbers — and it is the cheapest order in the census. It wins back 31 per cent of the gap, beats smallest first on 1,695 of 1,766 positions and loses on 67, and does slightly better than either kind of learning. Everything a program learns about the order, on this census, is one fact about two numbers.

Why two and three almost never win #

The fact has a count and, for 2, a proof.

Over the 1,099 won positions reached in those searches, naming 2 is legal at 1,086. It is struck at 1,053 of them — it would leave the opponent a symmetric position — and it wins at the other 33. It never loses in any other way. Naming 3 is legal at 1,066 and wins at 13. Every move from 4 upward, taken together, wins about one time in five. A search that tries 2 and 3 first is paying two closures at nearly every node for moves that win about once in eighty.

The 2 has a reason, and it is short.

Name 2 and every even number becomes reachable. Every odd number the position could already reach is the smallest reachable odd number, call it o, plus some even number, so it is reachable from 2 and o too. So naming 2 leaves exactly the semigroup generated by 2 and o. A semigroup with two generators is always symmetric — its gaps are the odd numbers below o, and they pair off around the largest — and a symmetric position is never lost for the player to move. The opponent moves next. Naming 2 therefore loses, unless the opponent has nothing to move to: that is the case o = 3, where the only gap left is 1 and the opponent is forced to name it. Those are the 33 wins in the census, every one.

The argument is the middle-game version of a fact about openings. The game that is a number system lists 2 among the losing first moves, and the reason is the same two lines run from nothing: after 2 the opponent names 3, the only gap left is 1, and the player who opened must name it. Once the game is under way the opponent cannot always name 3 — it may already be reachable, or the position may make it a mistake — but the opponent does not need to. Whatever odd number the position already reaches, naming 2 hands over a symmetric position, and the pairing removes moves it cannot name is where that fact became the one-pass test the search uses to strike such moves — the test that, applied to 2, strikes it at almost every node.

For 3 there is no such proof, and the count says why the order does not need one. Naming 3 is struck about half the time and loses the other half, and the positions where it wins are rare enough that trying it last costs almost nothing.

So the order that works is not a heuristic in the sense of a guess about positions. It is the consequence of a theorem about one move, which smallest first — by trying the smallest number first — reliably runs into at every node.

A good guess that costs more than it saves #

The parity reading shows the other side of the same lesson.

As a guess, the parity is good. With its sorting done for free — every move’s result computed without charge, only the moves the search then examines counted — it wins back 18.8 per cent of the gap, which is most of what the history table wins. Charged for its sorting, it is the dearest order in the census: 2.56 million closures against smallest first’s 1.54 million, 94 per cent of the gap the wrong way. Put after the history table, sorting only the moves the table has not promoted, it gives back most of what the table won.

That is the finding of the seven were the order again, with a sharper instrument. There the best predictor among the eager orders was dearer than smallest first; here the free version of an eager order separates the two things an order does. It guesses, and it pays to guess. On Sylver Coinage the guessing is worth about a fifth of the gap and the paying is worth more than the whole of it, so no eager order can win. Every order that wins anything back is lazy.

The order the moves are tried in found the opposite on Domineering, where trying first the move that leaves the opponent fewest replies cut a who-wins search twenty-seven-fold against the worst order. The difference is the price of the reading. A Domineering reply count is a scan of a small board; a Sylver Coinage reading is a closure, which is the unit the search is charged in. When reading a position costs as much as searching it, the only affordable orders are the ones that read nothing.

Why smallest first was hard to beat #

Starting at four is a small change to smallest first, and it is fair to ask why nothing larger works — why every order that reads the position loses, and why a program cannot simply do better by looking harder.

At the root, starting at four moves the first winner from an average of 8.65 moves in to 6.93: the two places are the two moves it skips. That is still no better than chance. A position has sixteen moves on average and fewer than two winning ones, and 906 of the 1,766 have exactly one; a winner drawn at random from sixteen would sit about as deep. So at the level of which move to try first, neither order knows much.

A fixed random order — each position’s moves shuffled by a hash of the position, as lazy as smallest first and costing nothing to compute — makes the point from the other side. It is the dearest lazy order in the census: 2.53 million closures, 91 per cent of the gap the wrong way, dearer on 1,227 positions than smallest first. If where the winner sits at the root were what mattered, a random order would cost about what smallest first does. It costs two thirds as much again.

What smallest first has, and a random order lacks, is a property of the moves it examines before it finds the winner. Naming a small number makes many other numbers reachable — every multiple of it, and every sum with what is already there — so the position it leaves has few gaps, and refuting it, or striking it, is cheap. A search that tries small numbers first spends its failures on small subtrees. A random order spends them on large ones. The winner’s place at the root is almost irrelevant beside that, and it is the reason a closure-counting search is so hard to improve with an order that reads positions: the cheapest failures are the ones smallest first already makes, and the only improvement available is to stop making the two that are not cheap but certain — 2, which a theorem strikes, and 3, which almost never wins.

A fixed saving against a growing gap #

The saving is not the same at every size, and the shape of it says what kind of saving it is. From about ten gaps upward, starting at four costs about 78 per cent of smallest first, and the history table about 80, at every size. The oracle’s share falls steadily, from 57 per cent at eight gaps to 27 at twenty. So the cheap orders save a fixed fraction of each search — roughly the two closures at every node that 2 and 3 used to cost — while the value of knowing the winning move grows with the position. The share of the gap won back is 31 per cent over the whole census, and it would shrink on larger positions.

That is the honest size of the result. The factor of more than three between smallest first and the oracle is not closing; a constant is being taken off it. A constant is still worth having in a search whose cost grows as fast as this one’s does — at twenty gaps a fifth of the work is a fifth of a large number — but it is a different kind of result from an order that knew where the winners were, and it should not be mistaken for one.

The convention, and what the census counts #

The positions are the 1,766 irreducible numerical semigroups with at most twenty gaps and Frobenius number above 1, each a win for the player to move. Each is searched from nothing, with a memo that lasts for that search only. A closure is one move examined — the semigroup generated by the position and the named number — and is charged whenever a move is examined, whether or not the search then descends into it. Struck moves are examined and charged, and then skipped. These are the conventions a different question at every depth set for pricing Sylver Coinage searches, kept unchanged so that every total here can be set beside the totals there. The history table is reset for each position; the learned order is built from the winning moves at every won position reached in the searches of the positions with at most fourteen gaps, uncharged.

What the census cannot show #

The positions are one family. Irreducible positions to twenty gaps are the positions earlier essays chose because every one is a win; a search from an arbitrary position, or from a real opening, would meet 2 and 3 in different proportions.

The orders are the ones tried. A history table that persisted across positions, or one keyed on the position’s shape as well as the number, might do better; a learned order sensitive to the largest gap might too. And each cheap order falls back on smallest first, so part of every figure is smallest first’s own luck.

Only 2 is proved. The 3 is a count, and so is the one time in five that later moves win.

Still open: what the oracle knows #

Starting at four removes a cost that a theorem says was wasted, and what remains between it and the oracle — about two thirds of the gap, and a share that grows with the position — is not wasted in any way a count of closures can see. The oracle’s winning moves are spread over the middle numbers, and the history table’s failure to separate 4 from 9 in any stable way suggests there is no fixed order among them to find. The next measurement is the one that would settle it: for each position, the rank of the first winning move under smallest from four, and whether that rank is predicted by anything the one-pass pairing test already computes — the struck moves come free with the search, and a move whose neighbours are struck might be telling the order something. If nothing predicts it, the Sylver Coinage search has reached the point a move whose every reply is struck and a shortlist with nothing at the top kept arriving at from the other side: the winning move is where it is for reasons only the search can see.