A move whose every reply is struck

A shortlist with nothing at the top scored seven quantities a single pass could compute about the moves the Sylver Coinage pairing test leaves standing, and found no order among them. The best put a winning move first on 24.9% of 583 positions, against 22.3% for an order that knew nothing, and every one of the seven placed the first winner deeper in its list than chance does. It ended by naming the obvious thing a one-move scan cannot do, which is to look at the reply.

A move that survives the test hands the opponent a position whose gaps do not pair off around its largest gap. The opponent then faces a shortlist of their own. So each survivor carries a number the one-move scan never read: how many of the opponent’s replies survive the same test. A move leaving the opponent few surviving replies ought to be a move that leaves the opponent little to work with. This essay scores that, and then reads the same number a second way, which turns out to be the one that matters.

The number under each move #

The position drawn is the semigroup whose gaps are 1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 17, 18, 23 and 28. Its gaps pair off around 28, so the player to move is known to win, by the stealing argument every move closes the largest gap sets out, and the argument names no move. Of the fourteen legal moves — every gap except 1, which loses at once — the pairing test strikes two, 2 and 3, because each leaves a position whose own gaps pair off and which the opponent therefore wins.

Twelve survive, and under each is the new number. Naming 28 leaves the opponent eleven surviving replies. Naming 17 or 18 leaves nine. Naming 6, 7 or 9 leaves three. Naming 4 leaves none. Every move the opponent could make after 4 is a move the test strikes: each hands back a position whose gaps pair off, so each hands back a win.

That is not a heuristic observation about 4. It is a proof that 4 wins, and it is two scans long: one over the moves from the position, one over the replies to 4. The other winning move, 6, leaves three surviving replies, exactly as many as the losing moves 7 and 9 do, so as a number the count does not separate it from them. As a proof it does not have to.

One move down, and the order is no better #

The first reading is the one the earlier essay asked for: order the survivors by the number of surviving replies they leave, fewest first, and score the order exactly as the seven one-move orders were scored.

It puts a winner first on 24.7% of positions, 144 of 583. Chance does 22.3%, and the best one-move reading, the survivor leaving the smallest largest gap, did 24.9% — one position more. On the second score it is worse than chance: the first winner sits at place 4.86 on average, against 4.28 for an order that knows nothing and 4.34 for the best of the one-move orders. And on 123 positions several survivors tie for the fewest replies, so the order has to fall back on something else to choose among them.

Reading one level down, then, buys nothing as an order, and the earlier essay’s conclusion survives a test it could not make itself. The reason has to be something the count shares with the one-move quantities, because they all fail the same way.

A lean, and winners everywhere #

The count is not unrelated to winning. Winning survivors leave 6.62 surviving replies on average and losing survivors 7.37, and 30.9% of winning survivors fall in the fifth of their shortlist that leaves the fewest, against 25.8% of losing ones. A move that leaves the opponent less to work with is, a little more often, a move that wins.

The lean is small and the spread is wide. 13.3% of winning survivors fall in the fifth that leaves the most replies — the place an order reading replies puts last — against 13.5% of losing ones. And because most positions have one winning move among nine or ten survivors, an order is judged on where it puts that one move, not on how the population leans. A lean of five points in the first fifth moves the share first by two and a half.

The mechanism is not mysterious. A move that closes many gaps leaves the opponent few moves of any kind, surviving or struck, so the count is partly a count of what the move removed; and the one-move scan already read how many gaps a move closes, and found winners and losers closing almost exactly the same number, 3.11 and 3.10 here. A second quantity that mostly re-reads the first cannot order what the first could not.

Read as a proof #

The order throws the count’s one exact value away. A survivor whose count is nought is not merely a promising move; it is a winning one, because the test never strikes a move that wins, and if it strikes every reply then every reply loses.

That turns the question from ranking into certification, and certification has a natural continuation. A survivor wins within three moves if every surviving reply to it leaves a position in which some survivor has no surviving reply; within five if every surviving reply leaves a position won within three; and so on. At each step the only moves examined are survivors, and a struck move is treated as settled, because the test’s verdict on it is a theorem. It is the pairing test used as the leaves of a search rather than as a filter in front of one.

At one move it proves 57 positions: a tenth of the census has a winning move whose every reply the test strikes. At three moves it proves 24 more, at five 83, at seven 111 and at nine 177, the largest single depth. By eleven moves 543 are proved, and every one of the 583 is proved by thirteen. Each proof names its winning move, and every move named was compared with the answer of the full search, and all were winning moves.

The 57 include every position the earlier essay found the test finishing outright. On 22 positions only one move survives, and a position known to be won with one move left is won by that move; all 22 are among the positions proved at one move, because a lone survivor turns out, every time, to leave the opponent nothing but struck replies. The other 35 are new. Their shortlists run to three moves at the median and to twelve at the longest, as in the position drawn at the top, and on none of them does elimination alone name the move. The count names it, by settling a different list — the opponent’s.

That distinction is worth holding onto, because the two certificates are of different kinds. Elimination proves a move wins by showing every other move loses, which needs the test on every sibling. The count proves a move wins by showing every reply loses, which needs the test on every child of that one move and says nothing about the siblings. How much a list can lose measured the first kind in another game; the second kind is the one a search is built from, and the rest of this essay follows it down.

The contrast with the earlier essay’s closing claim is exact. It argued that a winning move cannot be recognised from the position it reaches, because what makes a position lost is a statement about every move from it, and that a certificate of a win is a strategy. On 57 positions the strategy is one move deep and the statement about every move from the child is supplied by the test itself. A strategy is not a certificate priced strategies as objects far larger than the answers they certify; here, for a tenth of the positions, the certificate is a move and a list of struck replies.

A step deeper every two gaps #

The depths are not scattered. Sorted by the number of gaps, the proofs deepen steadily, and the deepest proof at each size follows a rule with no exception in the census. Up to five gaps every position is proved at one move. From six gaps on, the deepest proof is the largest odd number at most three below the number of gaps: three moves at six and seven gaps, five at eight and nine, and so on to thirteen at sixteen. The mean rises more smoothly, from 2.1 moves at six gaps to 9.9 at sixteen, a little over half a move for every gap added.

Two things in that shape are worth separating. The first is the ceiling it sits under. Every move closes at least one gap, so no line of play from a position is longer than its number of gaps, and a proof that has to look further than that has nothing left to look at. The deepest proofs stop three or four moves short of that ceiling, which says that some part of every long line is settled by the test before the line runs out.

The second is the odd step. The proofs are measured at odd depths only, because a proof ends on a move whose replies are all struck, so the deepest proof can only climb in steps of two. That it climbs by exactly one step for every two gaps is the observation, and nothing here explains it. The obvious guess is that the hardest position of each size is the one whose shortest winning line closes one gap a move — naming the largest gap, as in the position drawn below — so that every extra pair of gaps adds one exchange that the test cannot shortcut. Whether that holds past sixteen gaps, or whether a position turns up whose proof is deeper still, the census cannot say.

For a search, the rule is the bad news behind the cost figure. The proof deepens with the size of the position, and a deeper proof is dearer; the positions that most need help are the ones the proof reaches last.

The winning move with the most replies #

The small position drawn is the order’s failure and the proof’s success in one strip. Its gaps are 1 to 7 and 14, which pair off around 14, so the mover wins. Six moves survive the test. Naming 3 leaves the opponent two surviving replies, the fewest, and 3 loses. The only winning move is 14, and it leaves five surviving replies, the most of any survivor, so the order by replies puts the one winner last.

The reason is plain once the position is read as numbers rather than counts. Naming the largest gap closes nothing else, because every other gap is smaller and no sum involving 14 can reach them. So 14 leaves the opponent every other move — the gaps 2 to 7, less the one the test strikes — and each of those replies loses. The count is high precisely because the move is quiet, and a quiet move that leaves the opponent many losing options is exactly what a count of options cannot see. The proof sees it, at a depth of five, because it does not count the replies; it settles each one.

What a proof costs #

A proof that settles every position is a search, and the question that matters to anybody writing one is its price against the searches it could replace.

The cost is counted in closures: one computation of the semigroup a move reaches, which is what the test, the proof and the search all pay per move examined. Two searches that simply finish are set against the proof: the plain memoised search, which stops at the first winning move it finds, and the same search told to skip every move the test strikes.

The proof is cheaper than the plain search on 26 positions, all proved within three moves, and cheaper than the search that skips struck moves on none. Its median cost is the plain search’s at one move, one and a half times it at three, nearly three times at five, and thirteen and a half times at thirteen. Against the pruned search it is never cheaper at any depth, and sixteen times dearer at thirteen.

The pruned search is the real finding in this figure, and it is the earlier essays’ finding again in a sharper form. Skipping struck moves makes the finishing search cheaper on 548 of 583 positions. The test pays when it removes work from a search that will finish anyway. It does not pay when it is asked to certify, because a certificate built from it has to be rebuilt at every depth, and every rebuilding examines the struck moves again to know they are struck.

Search on in pairs of moves found the same ordering in Domineering, with a different proof and a different game: a certificate by deepening got cheaper only by becoming the search that finishes, and never beat it on any board small enough to check. The two are the same fact, and where a search may stop is where it was first measured. On a game small enough to solve, a search that remembers what it has seen and goes to the end has already paid for every proof, and proving something shallower than the end is a way of paying for part of it twice.

What the count is good for #

Put together, the two readings give the number under each move an honest job description.

As an order it is worthless, and no better than the seven one-move quantities it was meant to improve on. The lean toward fewer replies is real and too small to move a winning move to the front of a list of ten.

As a proof it is exact where it applies. A survivor with no surviving reply wins, on 57 positions of 583, and that certificate costs about what the search it would replace costs. The pairing removes moves it cannot name turned a theorem about positions into a test on moves; applied one level down it names a move, but only where the opponent is left nothing the test does not already settle.

As a search it is complete and expensive: every position proved by thirteen moves, and at no depth cheaper than simply searching with the struck moves skipped. The same test is worth most as pruning, and the order a solver tries the moves in explains why pruning and proof price differently: a search that finishes needs one winning move at each won position and every move at each lost one, and the test removes exactly the moves it would otherwise have had to refute.

What 583 positions cannot show #

The census stops at sixteen gaps. The 583 are every irreducible position in that range, and a lean too small to matter here could grow with the number of gaps, or a depth at which proof becomes cheaper than search could appear on positions large enough that the plain search is expensive. Nothing here reaches those positions.

The proof deepens without keeping anything. Each depth is searched with a fresh table, which is the price of a proof whose verdicts at one depth are not reusable at another. A proof search that kept the positions it had already settled, and asked only about the ones it had not, would cost less, and it is not measured.

The count reads replies, not their values. A rule comparing what two survivors leave — the pairing test’s own quantity for each reply, or the size of each reply’s shortlist — reads more than a count, and nothing here scores it. The negative result is about counting.

The rules the counts assume #

Sylver Coinage under the convention the game that is a number system sets out: the players name positive integers in turn, a number may not be named if it is a sum of numbers already named, and the player who names 1 loses — so 1 is left out of every move list, as a resignation rather than a move. A position is the numerical semigroup generated by the numbers named, its gaps are the numbers still available, and a position is irreducible when its gaps pair off around the largest one, which makes it a win for the player to move. The pairing test strikes a move exactly when the position it reaches is irreducible with a largest gap above 1. The winning moves in every figure are those of the full memoised search, computed independently of the test.

Still open: a search that keeps its proofs #

Every proof here is rebuilt from nothing at each depth, and every one costs more than a search that skips struck moves and finishes. The obvious repair is a search that does both: deepens over survivors, keeps the positions it has proved or refuted at any depth, and never examines them again. Whether such a search is ever cheaper than the pruned finishing search — and whether it becomes so on positions with more than sixteen gaps, where the finishing search is dearer and the share of positions proved at one or three moves might grow — is the measurement this leaves.