The order a solver tries the moves in

A position reached eleven ways is one position counted two sizes for every board: the routes a solver with no table walks, and the positions a solver with a table stores. On 4 × 4 Domineering the second is 5,700 against 6,257,129, and the essay’s argument was that the gap between them is the difference between a search that finishes and one that does not.

The position count reads naturally as the cost of a solver with a table, and it is — for a solver that wants every position’s value. A solver that wants only to know who wins does not have to visit all of them. How many it does visit is decided by something the position graph does not contain at all: the order in which it tries each position’s moves.

One answer at six prices #

A 4 × 5 board, with Left placing vertical dominoes and Right horizontal ones, has 48,670 positions with a player to move that play can reach. The search measured here is the plainest possible. At a position, try the moves one at a time; if some move leads to a position the opponent loses, this one is won and the search stops looking; if none does, it is lost. Every answer is stored, so no position is expanded twice.

Run that search under six rules for which move to try first. Trying first the move that leaves the opponent fewest replies expands 1,125 positions. Trying first the move that leaves the widest margin of placements expands 1,136. Trying winning moves first — an ordering available only to something that already knows the answers — expands 1,781. The order in which the moves happen to be generated, a scan of the board row by row, expands 5,988. A fresh random shuffle at every position expands a median of 8,313 over twenty runs. Trying losing moves first expands 30,202.

All six conclude that Left wins moving first and that Right loses moving first, so Left wins this board whoever starts. The verdict is fixed by the game. The price of reaching it varies by a factor of 26.8, and the cheapest search looks at 2.3 per cent of the board’s positions.

Two things in that list need explaining. The first is why an ordering that knows which moves win should lose to one that merely counts replies. The second is why the order a program happens to generate moves in should beat a random one. The first has an exact answer, and it is the centre of this essay.

A win needs one move and a loss needs all of them #

The asymmetry is in the definition of winning, the one who moves last sets out. A position is won if some move leads to a lost position, and lost if every move leads to a won one. To establish the first, a search needs to find one move and show that one child lost. To establish the second it has to show every child won, and no ordering can shorten a list that has to be finished.

The table makes the asymmetry measurable. Under fewest replies, 578 of the 580 won positions are settled by the first move tried. The ordering is not told which moves win; it almost always picks one anyway. Under winning moves first, every won position is settled on the first try by construction. Under the generation order only 57 per cent are.

At lost positions nothing like this is possible, and the count says so exactly: the moves refuted at a lost position always equal its number of moves. What differs between orderings is which lost positions a search is led into. Fewest replies reaches 545 of them, with 1.68 moves each to refute. Losing moves first reaches 10,102.

So the cost of an ordering is mostly decided one level below the choice. A move chosen at a won position creates a lost position for the opponent, and that lost position will cost exactly as many refutations as it has moves. Choosing the move that leaves the fewest replies is choosing the cheapest refutation. Winning moves first chooses a winning move without looking at what refuting its replies will cost: its lost positions average 2.49 moves each against 1.68, and there are more of them, 694 against 545.

That disposes of the first oddity. Knowing which moves win answers only half of what an ordering is for. The other half is how much proof lies beneath the winning move, and the number of replies it leaves is a cheap and very good proxy for that.

Two cheap orderings reading the same thing #

The widest-margin rule differs from fewest replies in counting the mover’s own placements as well as the opponent’s: it prefers a move after which the mover has many places left and the opponent few. On 4 × 5 the two cost nearly the same, 1,136 against 1,125, and on 3 × 4 exactly the same.

Both read the board the way the margin a count needs and counting the moves each side has read it: a Domineering player with more room than the opponent is usually ahead. As a verdict that is a rough guide. Here it is doing something more forgiving. It does not replace the search; it decides where the search looks first. A wrong guess costs a few extra positions rather than a wrong answer, which is why a heuristic too crude to trust as a judgement can still be excellent as an ordering — the same division of labour as a check in front of a search, with the check steering instead of settling.

The proof a cheap order leaves behind #

The positions a who-wins search expands are more than a cost; taken together they are a proof. For every won position in the set, the search found one move to a lost position that is also in the set. For every lost position, it tried every move and found that each leads to a won position in the set. Anyone handed the 1,125 positions fewest replies expanded, with the chosen move marked at each won one, could confirm that Left wins 4 × 5 whoever starts without searching anything — by checking one move at each of 580 won positions and all 914 moves at 545 lost ones.

So the six orderings are also producing certificates for the same fact, and the smallest certificate there is can be no larger than the cheapest measured here. Winning moves first produces a larger one, all 1,781 of the positions it expands, even though every move it marks wins: the proof beneath a winning move can be large or small, and it did not choose. Losing moves first expands 30,202 positions, but its certificate is much smaller than that, because most of what it expanded lay under moves it tried and abandoned, which a proof does not need.

That distinction — the work of finding a proof against the size of the proof found — is where the orderings differ. A perfect ordering would do no more work than its proof requires. Fewest replies very nearly does on 4 × 5: its 1,497 probes are three more than the 1,494 checks its own certificate needs.

Where in the game the orderings part company #

The empty board is expanded twice, once for each player to move, and after one domino every ordering but the dearest expands 17 positions. That number has a reading. Right moving first loses, so all 16 of Right’s opening placements have to be refuted, and each refutation starts from a position with one domino on the board; Left moving first wins, so one of Left’s 15 placements is enough. Losing moves first expands 19 at that depth, because it tries Left’s losing openings before a winning one — and there are only two of them. Thirteen of Left’s fifteen opening placements on 4 × 5 win.

The orderings separate where the graph is widest. Six dominoes down, the board has 15,624 positions with a player to move. Losing moves first expands 10,885 of them, the generation order 1,969, winning moves first 423 and fewest replies 263. At the last depths the counts close up again, because few positions survive that long and every ordering must finish the ones it reaches.

That shape is why ordering matters as much as it does. A search spends its time where the positions are, positions are in the middle of the game, and any factor an ordering saves is multiplied by the widest part of the graph. How often a board falls apart found the same middle heavy with decompositions, and noted that a solver’s move ordering decides which of those positions it ever sees; this is that ordering, measured.

The scan is not a neutral order #

A random order is the obvious baseline for an ordering that knows nothing, and it is worse than the scan. Twenty shuffled searches expand between 6,700 and 10,348 positions, with a median of 8,313. The scan expands 5,988, fewer than every one of them.

The scan tries placements from the top-left corner in reading order, so its first candidates lie along an edge. Why that should help is not something these counts identify. A plausible reading is that a domino against an edge removes fewer of the mover’s own future placements than one in the middle, which would make edge moves good for the reason the reply count captures directly, but the runs do not test it. What they do establish is that “the order the moves happen to come out in” is a choice with a price, and that on this board a random order would have cost two fifths more.

There is one exact fact about the scan that the counts do check. Reversing it — trying placements from the bottom-right corner backwards — costs precisely what the scan costs, 5,988 positions and 10,607 probes. The reversed reading order is the scan of the board turned through a half turn; a half turn takes vertical dominoes to vertical dominoes and horizontal to horizontal; so the reversed search is the same search on a board that is the same game. Two orderings that look unrelated are one ordering seen from opposite corners, which is the symmetry what counts as the same position folds tables by, turning up here in the price of a search instead.

Five boards, and where the knowing order wins #

The spread grows with the board: 6.7 times on 3 × 3, 26.8 times on 4 × 5, and nothing in the five boards suggests it stops. That is the shape of every search cost measured in these essays — a factor that is small on the boards anyone can draw and large on the boards that matter.

The ranking is less tidy. Fewest replies is cheapest on 3 × 4, 3 × 6 and 4 × 5, and on 3 × 6 it beats winning moves first by a factor of two. But on 4 × 4 winning moves first expands 199 positions against fewest replies’ 218, and the widest-margin rule costs 339. A heuristic is a bet about the board, and on the square board the bet loses. The reply count is the better ordering on most boards measured here; it is not a theorem about all of them.

The saving, set against the first two #

The two columns of the routes-and-positions count were the routes a solver with no table walks and the positions a solver with a table stores. Ordering is a third saving and it applies to the second column. On 4 × 4 the board has 4,886 positions with a player to move, and a who-wins search in a good order expands 199 of them. The table removes the redundancy among routes; the ordering removes most of the positions the table would otherwise have had to hold.

The two savings do not simply multiply. Without a table a good ordering still helps, and helps more in absolute terms, since each position it avoids would have been walked once per route. With a table, a position expanded to no purpose is at least never expanded twice, so a bad ordering is less ruinous. Every count here is with a table. Space is the resource describes the solver that cannot afford one, and for that solver ordering is the lever that is left.

Names for the two kinds of position #

The distinction this essay turns on has names from chess programming. Knuth and Moore’s 1975 analysis of alpha–beta pruning described the tree that a perfectly ordered search examines and sorted its nodes into types; the later and more descriptive names are cut nodes, where one good move is enough, and all nodes, where every move must be examined. A who-wins search is the simplest instance: a won position is a cut node and a lost one is an all node, and the whole art of ordering is making the cut come at the first move.

The idea of ordering by how cheap the remaining proof will be has its own name. Proof-number search, introduced by Victor Allis and colleagues in the early 1990s, keeps for each position an estimate of how many positions still have to be settled to prove it won and how many to prove it lost, and always expands where the proof looks cheapest. A position with few moves has a small disproof number, because there are few children to refute — which is what fewest replies prefers, without keeping any numbers at all. The programs that solved 8 × 8 and then 10 × 10 Domineering around the turn of the century used alpha–beta with move ordering and a transposition table, and nim is easy notes that the published solutions combine alpha–beta, transposition tables and symmetry reduction.

What the counts leave out #

The cost of ordering is not counted. Sorting a position’s moves by the replies each leaves means generating the moves of every child before searching any of them, where the scan generates a child’s moves only when it expands that child. So the positions-expanded count flatters the two board-reading orderings by a move generation for every option of every position they expand. The probes column in the second table is a closer measure and it still omits the sort.

The search is for a verdict, not a value. Knowing who wins and knowing what it is worth prices the difference between those two questions. A value is determined by all of a position’s options, so a search for values examines every option at every position and an ordering buys it far less. Everything measured here concerns the cheaper question.

One family, small boards. Domineering is a game in which counting placements is a good guide to who is ahead, which is why the orderings that count do so well. In a game where the number of moves says little about the outcome, a reply count would order much worse, and nothing here measures how much worse.

The convention, named #

Normal play: a player who cannot move loses. Left places vertical dominoes and Right horizontal ones, as in Domineering. A position is a set of covered squares together with the player to move, reached by alternating play from the empty board with either player starting — which is why 4 × 4 has 4,886 positions here against the 5,700 boards the routes-and-positions count reported, since that count took every board either player’s moves could produce, in any order. The search stores its answer for every position it expands and asks only whether the player to move wins.

Still open: when the search cannot reach the end #

Every ordering here is followed all the way to the last move. The saving is large, but it is a saving on a search that still finishes, and on a board of any real size a search that finishes is unaffordable in any order. The next question is what such a search does instead — stop at a fixed depth and guess — and what the guessing costs in verdicts rather than positions. The count that makes a good ordering is also the obvious guess, and whether a guide good enough to steer a search is good enough to judge a position where the search stops is a separate measurement.