When the catalogue starts paying

The question in the middle prices two things a program might be asked. Who wins this board is a search over its position tree. What is this board worth is that search plus the comparisons the canonical form costs, and the second is a different complexity from the first.

Neither is what a real program does. It closed by naming the third question:

Everything on this page compares computing values for one board against searching one board, and the answer a real program gives is neither: it pays for a family of regions once and answers every board over them by addition. Measuring the crossover — how many boards a catalogue has to serve before it is cheaper than searching each — is a measurement this site’s machinery could make and would need a family of boards rather than eight sums.

The family of boards is generated rather than chosen, and the crossover turns out to be a small number that gets smaller.

What is being counted #

Everything is in distinct positions expanded, which is the unit the rung below prices the other two questions in and the only one that does not depend on the machine.

The catalogue’s cost is the number of distinct positions reachable from all its shapes at once. Shared, because two shapes with a common sub-shape pay for it once, which is exactly how a program would build it.

A board’s cost is the number of distinct positions reachable from that board.

Looking a board up in the catalogue is a flood fill to find its pieces, a lookup each, and some additions. That is not counted at all, so the crossover reported here is an upper bound rather than an estimate: the catalogue is at least this good.

The boards #

A crossover measured on boards somebody chose would be a statement about the chooser. So the family is generated: random legal play from an empty board, keeping every position that has fallen into two or more pieces with none of them larger than the catalogue reaches.

That is the population a solver actually meets. It is also the population how often a board falls apart measured — a board in play decomposes early and often, and the catalogue’s whole value is that it answers those positions.

Three hundred positions are sampled at each combination of board size and catalogue reach, deduplicated, and each is searched directly to find what it would have cost.

The answer #

A catalogue of every region up to four squares is fifteen shapes and costs 54 positions to build. A decomposed 4×5 board costs 11 on average to search directly. The crossover is five boards.

A catalogue reaching eight squares is 1,042 shapes and costs 14,706. Decomposed 4×5 boards cost 71 on average. The crossover is 206 boards.

Between those it runs 12, 25, 59 — the catalogue costs more and answers more, and the number of boards it has to serve rises with it.

The spread inside each row is worth a note, because a mean over a sample is where a crossover can quietly go wrong. The cheapest decomposed positions in the 4×5 sample cost six positions to search and the dearest nearly a thousand, so the mean of 71 is not a typical value — the median is lower and the tail is long. A crossover computed against the median would be larger and a crossover computed against the dearest positions would be smaller, and the mean is the right one because it is what a program’s total bill is made of.

Two hundred boards is not a lot. A single game of Domineering on a 4×5 board passes through a dozen decomposed positions, and a solver examining the game tree passes through thousands. On any use that resembles playing rather than answering one question, the catalogue has repaid itself long before it is finished being useful.

And it falls with the board #

The more interesting column is the one that changes sign against intuition.

On a 5×5 board, the same catalogues have crossovers of 5, 10, 18, 33 and 100 — every one of them lower than on 4×5.

The reason is that the catalogue’s cost does not depend on the board at all, and the thing it is being compared against does. A decomposed 5×5 position costs 147 positions to search where a 4×5 one costs 71, because the pieces are bigger and there are more of them, so each board the catalogue answers saves twice as much.

So the catalogue is worth more the larger the position, which is the opposite of what pricing it against one small board suggests, and it is the reason a real program builds one. The census asserts the direction: a crossover that rose with the board size would mean the saving is fixed rather than scaling, and the finding would be the other way round.

What a decomposed board looks like #

The positions being priced are worth seeing, because the whole argument turns on how ordinary they are.

A few dominoes down the middle of a board and it is two regions. Each of them is in the catalogue; the board’s value is their sum; and the search that would have been needed to evaluate the board as one object never happens.

That is not a special position. It is what happens after four or five moves on a board of this size, and the sampled family here is nothing but positions of that kind — reached by random legal play rather than constructed.

The one thing the sample excludes is positions with a piece too big for the catalogue, and those are exactly the positions early in the game. So the catalogue answers the late game and the search answers the opening, which is the division of labour a real program has and the reason its cost is dominated by the part the catalogue covers.

The comparison that is not a comparison #

There is a second reading of the same numbers, and it is the one that matters most.

Searching a 5×5 Domineering board from empty expands 1,125,703 distinct positions. The whole catalogue of every region up to eight squares expands 14,706 — one part in seventy-six of it.

But the catalogue cannot answer the empty 5×5 board at all, because that board is one component of twenty-five squares and the catalogue reaches eight. What it can answer is every position that board falls into once a few dominoes are down, which is nearly all of the tree by count.

So the honest statement is not that the catalogue beats the search; it is that the two answer different questions and the catalogue answers the one a program spends its time on. A solver’s cost is dominated by the enormous number of small positions it revisits, not by the handful of large ones near the root, and that is exactly what a decomposition buys.

What one more square costs #

The catalogue’s own growth is worth a figure, because it is what decides where to stop.

Fifteen shapes, then 36, 104, 312, 1,042 — a factor of about three a square. The positions they expand grow faster: 54, 193, 787, 3,250, 14,706, which is a factor of four and a half.

That is a growth rate a program can live with for a while and not for ever, and it is why a catalogue has a reach rather than being built as far as anybody likes. Nine squares would be roughly 3,500 shapes and 70,000 positions, and the boards it newly answers are the ones that decompose least often.

Where to stop is therefore a question about the board rather than about the catalogue: build to the largest piece the board reliably falls into, and no further.

What this says about the three questions #

The rung below’s finding was that computing a value is a different complexity from deciding a winner, and that the ratio between them grows with the board. This page adds the third column and it changes the picture.

Per board answered, the catalogue is cheaper than either — a lookup and an addition against a search. What it costs is paid once, and the whole question is how many boards there will be.

That is a different shape of cost from the ones the rung below priced, and it is the shape every practical solver has. Knowing who wins and knowing what it is worth prices two questions asked afresh each time; the catalogue prices one question asked once and then never again, which is why the crossover is the right measurement and the per-board ratio is not.

The number to carry #

If one number is to be carried off this page it is not the crossover; it is the ratio between the catalogue and the board.

Fourteen thousand seven hundred and six against one million one hundred and twenty-five thousand seven hundred and three. The catalogue that answers every region of eight squares or fewer costs 1.3 per cent of one search of an empty 5×5 board.

And it is reusable in a way the search is not. The search answers one board; the catalogue answers every 5×5 position that has decomposed, every 4×5 one, every 6×6 one, and every position of any board whatsoever whose pieces are small enough. Its cost is paid against the whole subject rather than against one question.

That is what makes the crossover the wrong headline and the right measurement. The crossover says the catalogue pays for itself quickly; the ratio says it was never really competing.

What the census does not say #

Four limits.

The catalogue is built to a reach, not to a budget. Every measurement here fixes the reach and asks what it costs; a program with a fixed budget would ask the reverse, and the two are not the same optimisation. Building every shape to eight squares is not the cheapest way to spend 14,706 positions, and what the cheapest way is has not been asked.

Domineering only. The catalogue idea needs a game whose positions decompose into independent pieces of a shape that recurs, and Domineering is the cleanest example on the site. A game with fewer distinct small regions would have a cheaper catalogue and a smaller crossover; one with more would have neither.

The lookup is free. The flood fill and the additions are not counted, so the crossover is an upper bound. The flood fill is linear in the board and the additions are a handful of canonical-form sums, so the true crossover is higher by some small factor — and the direction of the error is the one that makes the finding weaker rather than stronger, which is the safe way round.

Two board sizes. Four by five and five by five, which is enough to establish the direction and not the rate. Whether the crossover keeps falling or flattens is what a 6×6 sample would say, and a 6×6 board’s undecomposed search is beyond what this evaluator can afford.

And a sample of three hundred. The boards are random play-outs rather than an exhaustive enumeration of decomposed positions, so the mean direct cost is a sample mean. The spread is wide — the cheapest positions in the sample cost six positions and the dearest nearly a thousand — so the mean is doing real work and a different sample would move the crossover by some tens of per cent.

Why the crossover falls as the board grows #

The crossover moving the wrong way is the most useful thing on this page and it is worth deriving, because it is the reverse of what a reader expects from a fixed cost.

A catalogue costs a fixed amount to build: evaluate every shape up to the reach, once. That cost does not depend on the boards it will serve. What it saves per board is whatever those boards’ regions would have cost to search — and that grows with the board, because a larger board’s regions are larger and a region’s search cost grows steeply with its size.

So the crossover is a fixed cost divided by a growing saving, and a quotient of that shape falls. A catalogue that needs two hundred boards to pay for itself on a small board needs five on a large one, and the direction is guaranteed rather than measured.

That is an unusual and pleasant situation. Most precomputation gets harder to justify as problems grow, because the table has to grow too; here the table is fixed by the reach and the problems it serves get dearer.

The catch is on the other side of the same fact, and it is what the rung above measures. A larger board has larger regions, and larger regions are the ones outside the catalogue — so the same growth that makes the catalogue cheaper to justify makes it able to answer less. The two effects run in opposite directions, and the honest figure for a program is their product rather than either.

What a program would actually do #

The measurement suggests a shape for a solver, and it is worth writing down because it is not the shape a first attempt has.

Build the catalogue first, to the largest region the board reliably falls into. For a 5×5 board that is around eight squares, which costs 14,706 positions and is paid before the first move is examined.

Then search only until the board decomposes. Every position from that point on is a lookup and an addition. The search’s job is the opening, where the board is one piece and the catalogue has nothing to say.

And keep the catalogue between boards. It does not depend on the board it was built for, so a program answering questions about several sizes pays for it once. That is the part the crossover measurement makes concrete: two hundred boards sounds like a threshold and is a single afternoon’s use.

The one thing this ordering assumes is that the board decomposes early, and that assumption is measured rather than hoped — it is what the rung below’s neighbour counts, and the answer there is that it decomposes more often than a reader expects and sooner.

The convention, named #

Normal play. A board is a rectangle of squares, Left placing vertical dominoes and Right horizontal. A region is a connected set of empty squares, taken up to the reflections, and a board decomposes when its empty squares fall into two or more of them.

Positions expanded counts distinct positions, keyed on the board and its occupied squares. The same position reached by two orders of play is one position, which is the memoisation every solver here does and is priced on its own elsewhere.

The catalogue of reach $n$ is every region of at most $n$ squares with its value computed. Its cost is measured by expanding all of them together, which shares work between shapes exactly as building it would.

The crossover is the catalogue’s cost divided by the mean cost of searching one decomposed board directly: the number of boards after which the catalogue has cost less than the searches it replaced.

Where the ladder goes next #

The value-cost anchor has three rungs to here, and the three above answer the question this one leaves: not whether a catalogue pays, but how far to build it and what to put in it.

Where to stop building finds the coverage saturating. Going from four squares of reach to ten multiplies the catalogue by 860 and lifts the share of regions it answers from 54 per cent to 74 — so the tenth square costs five thousand shapes for a single point of coverage, and the answer is to build to six or seven.

A catalogue that knows what it will meet then changes the ordering and does far better than any reach can. Eight shapes answer half the components a played board produces, where a size-ordered catalogue needs fifteen for the same half and 1,042 for what 119 chosen by frequency reach. Three quarters of a size-ordered catalogue never turns up in play at all.

The catalogue a strong player needs checks the pool those frequencies came from, since random play is not play. The head survives — eight of the ten commonest shapes are the same — and the tail collapses: 114 entries answer nine tenths of what a strong player meets, against 2,018. And the direction of the error is the safe one: a catalogue built on random play over-serves a strong player, while the reverse fails.

So the crossover this page computes is the right question asked of the wrong catalogue. Built by frequency rather than by size, the same coverage costs an order of magnitude less, and the crossover falls with it.