The price of asking what the parts are

The licence that weighs nothing finished the anchor’s account of three substitution licences by pricing each of them two ways — by what it saves and by how large a table it needs — and found the order reversing between the two. The third licence, which lets a solver look up a connected region rather than a whole position, saves the least of the three and is the only one whose table does not grow with the sum or with the board.

It closed on the half of the cost it had not counted:

Every number on this page counts table entries and none counts work, and the third licence is the one whose work is not in the table: a solver using it must decompose every position it meets into connected regions before it can look anything up. That is a flood fill over the free squares at every node, and whether it costs more than the lookups it saves is a measurement nobody on this anchor has made.

It costs more. At equal cost per operation it costs about six times more, and nine tenths of that is the fill.

That is the crude answer and the interesting one is underneath it, because six times is not a measurement — it is a measurement plus an exchange rate, and the exchange rate was chosen rather than found.

Two solvers, one board #

The comparison is between two ways of remembering.

The plain solver keys its table on the whole position. It meets a position, probes the table, and if it has not seen that position expands it into its options. Its work is one probe per node and one expansion per novel node, and its table holds every distinct position the search reaches.

The decomposing solver does what the third licence permits. It meets a position, flood-fills the free squares into connected regions, and probes the table once per region. If every region is already known, the position needs no expansion at all — its value is the sum of values already on file, which is exactly what a disjunctive sum licenses. If some region is new, the position is expanded as before.

The saving is not marginal. Between a third and two thirds of the node expansions disappear, the share rising with the board, and the table doing it is smaller than the one the plain solver keeps. That is the rung below’s finding arriving in a solver rather than in a count of entries, and it is the reason the licence looked so attractive.

Why a known region lets a position go unexpanded is worth one sentence, because it is the whole theorem the licence is. A position that has fallen into regions $A + B$ has value $v(A) + v(B)$, and that is not an approximation — it is the definition of the disjunctive sum together with the fact that a move touches one region only. So a solver that already knows $v(A)$ and $v(B)$ knows the position without looking at it. The board falls apart is where that saving is drawn and priced on a single position; the count above is the same saving over an entire search.

The catalogue is also small, and that is the rung below’s point arriving in a solver. On the 3 × 4 the plain solver must remember 550 distinct positions and the decomposing one must remember 199 distinct regions — fewer entries, each of them smaller, and every one of them reusable on a board the solver has never seen. A region catalogue is not a fact about this search at all.

What a fill actually does #

The cost sits in one place and it is worth looking at closely, because the size of it is not what a reader guesses.

A flood fill is not one pass over the board. It is a pass over the board — every square, to find the ones not yet assigned to a region — plus a walk out from each unassigned free square, and the walk examines all four neighbours of everything it reaches. So a nine-square board costs 26 examinations, not 9, and a twelve-square board costs 35.

Nine tenths of the decomposing solver’s work is that fill. Not the probes, not the expansions it still performs — the fill.

Taking the unit out #

Six times is only as good as the claim that a square-examination and a table probe cost the same, and they do not. A probe is a hash and a comparison over a key; a square-examination is an array index and a test. Any real accounting makes the square cheaper, and the question is how much cheaper it would have to be.

That question has an answer that needs no opinion at all.

A square-examination must cost under a tenth of a table probe for the licence to pay. On the boards here the number runs from 0.078 to 0.112, so the requirement is that a square be between nine and thirteen times cheaper.

The number is stable across the five boards, which is the first thing to check about a ratio built from two growing quantities. It runs 0.082, 0.090, 0.078, 0.095, 0.112 on boards of six to twelve squares, with no trend in the board’s size and a mild one in its shape. Two quantities that both grow roughly as the search does would give a stable ratio for an uninteresting reason, and these do — the fill grows with positions visited and so does everything else — but the stability is what licenses quoting one number for the family rather than five.

Whether that is achievable is a fact about an implementation rather than about game theory, and it is genuinely close. A table probe on a hashed key is not obviously ten times a bounds check and an array read — it might be two times, or twenty, depending on the key, the hash and the cache. What the measurement establishes is that the answer is decided in that ratio and nowhere else, and that a solver author who has not measured it has no idea whether the licence helps.

The way out is not to pay it #

The interesting consequence is not the number but what it recommends, and it recommends something the rung below’s framing could not see.

A solver does not have to recompute the decomposition. A move in Domineering covers two adjacent squares. It can split one region into at most two, and it can never join two regions — so a solver that carries its decomposition alongside the position can update it in the neighbourhood of the move rather than rebuilding it from scratch. That is the free fill column, and there the licence is worth about a factor of two.

So the honest recommendation has three parts. The licence saves a real fraction of a search. Recomputing the decomposition at every node costs six times what it saves. And the decomposition is cheap to maintain and expensive to recompute, so the licence is worth having exactly when a solver is written to carry its parts with it.

That is a conclusion about program structure rather than about games, and it is the reason a pricing in table entries could never have reached it. A table entry is a static quantity — it is there or it is not — and the cost this page found is dynamic, paid once per node visited, and removable by an implementation choice that changes no value anywhere.

It is also the reason the licence has probably never been rejected on these grounds by anybody who tried it. A solver written to carry its decomposition pays the maintained cost and finds the licence worth roughly double; a solver written the obvious way pays six times over and finds it worthless. Both authors would report the truth about their own program, and neither would be describing the licence. The measurement that settles it is not a measurement of a theorem at all.

What this says about the other two licences #

The procedure cost is not peculiar to the third licence, and running the same question past the other two is what makes the finding a statement about licences rather than about one of them.

The first licence costs nothing to apply. It permits substituting a component of a sum, and a solver using it is handed the components — a sum of two boards is stored as two boards. There is no analysis to perform, no fill, and no decision about which entry applies: the position’s own representation names the parts. That is why a product against a sum can quote it as a saving with no cost column at all and be right to.

The second licence costs a lookup and no analysis. It permits substituting a subposition, and the subpositions of a board are the board with some squares filled — which the solver has in hand. Half a licence is nearly all of it measures what that buys, and again there is nothing to compute before the table can be consulted.

The third is the only one whose applicability has to be discovered. A region is not part of how a Domineering position is written down; it has to be found. So the three licences differ not only in what they save and in what they store but in whether using one requires solving a problem first, and only the third does.

That is a distinction worth having beyond this anchor. A substitution theorem is usually stated as a permission and evaluated as a saving, and the third quantity — what does it cost to notice that the theorem applies here? — is invisible in both. It is nought for the first two licences and it dominates for the third.

Why the reversal keeps happening #

This anchor has now reversed its ordering of the three licences twice, and the two reversals have the same shape.

One half multiplies, the other adds put them in order by saving: geometric, linear, constant. The rung below put them in order by table size and got unbounded, board-bounded, nearly constant — the exact reverse. This page puts them in order by the work of using one and finds the third dearest of all, at least under the obvious implementation.

A licence is three things and the anchor kept measuring one of them. It is a permission — a theorem saying two positions may be substituted — and that is the part equal in every company establishes and is not in question. It is a catalogue, which costs memory. And it is a procedure for deciding which catalogue entry applies to the position in hand, which costs time at every node. The third is the one nothing on this anchor had counted, and it is the one where the third licence is worst, because deciding which region catalogue entry applies means computing the regions.

The first licence has no such cost at all: deciding that a sum’s components may be substituted needs no analysis of the position, because the components are how the position was given. That asymmetry is the whole account of why the three orderings keep disagreeing, and it is available only once the procedure is counted.

What the solver computed, and how #

Five boards from 2 × 3 to 3 × 4. Each is searched twice from the empty position, over all of Left’s and Right’s moves, with no alpha-beta and no ordering — the point is to count states reached, not to solve quickly.

The plain solver pushes positions onto a stack, probes a set keyed on the whole occupancy, and expands the ones not seen. Its work is counted as one unit per probe and one per expansion.

The decomposing solver pushes the same positions, and on each one that it has not already visited it performs the flood fill: scanning every square of the board, and walking out from each unassigned free square examining all four neighbours of everything reached. Every square looked at counts one, including the neighbours that turn out to be occupied or off the board — a fill that assumed its neighbours were free would be a fill that did not have to look. Each region is then normalised to its own bounding box and probed. A position all of whose regions are already known is not expanded.

The two totals are then compared under two exchange rates: a square-examination costing one probe, and costing nothing. The break-even is the rate at which the two totals are equal, solved directly rather than searched for.

Two things are asserted rather than reported. The licence must save expansions on every board, or there is nothing for the fill to eat and the page has no subject. And the decomposing solver must be dearer at parity on every board, since a break-even below one is what makes the break-even the answer.

Where the model stops #

Five small boards and one ruleset. The largest is twelve squares, and the trend in the break-even is mild and not monotone: the long thin boards do better than the square ones, which is what a reader would expect — a 2 × 5 falls apart more readily than a 3 × 3 — and five boards is not enough to say whether the licence eventually pays on a large board. The saved share of expansions does rise with the board, so the direction is favourable and the sweep cannot follow it.

The exchange rate is the whole finding and it is not measured here. Nothing on this page times anything. A probe and a square-examination are counted, never clocked, and the claim is that the licence pays when their true ratio exceeds ten — not that it does or does not. Measuring that ratio is an experiment about a machine and a data structure rather than about a game, and it does not belong on this site.

And the incremental fill is an argument rather than a measurement. The free fill column charges nothing, which no implementation achieves; a maintained decomposition costs something per move, just far less than a rebuild. So the true answer lies inside the interval this page brackets and closer to its lower end, and where exactly is a question for a solver that has been written that way. None has been, here.

Normal play throughout, and the substitution the whole licence rests on is a normal-play theorem: two positions with equal values are interchangeable in every sum, which is what makes a region’s value usable in isolation.

Where the ladder goes next #

The universes anchor has eight rungs: equality made computable, which restrictions license rewriting a sum, which license rewriting a subposition, what the second licence is worth, what the first is worth on its own, how the two grow, the third and what a licence costs to hold, and now what it costs to use.

The rung above is the maintained decomposition, and it is the one measurement that would replace this page’s interval with a number. A solver carrying its regions and updating them across a move does bounded work per node: a move covers two squares, so at most one region splits and the update is a fill of that region alone rather than of the board. Counting that — squares examined per move rather than per position — turns the free-fill column from a bound into a measurement, and the break-even from a requirement into a verdict. It is the same two searches with one data structure added, and it is the last thing this anchor needs to say what its three licences are actually worth.

Two neighbours are worth the trip. The board falls apart is where a decomposition’s value was first established, and it is the page this one is the bill for. And a position reached eleven ways is one position is the saving that is not a licence at all — the transposition table — and it is the standing comparison, because it costs one probe per node and no analysis whatever, which is exactly the property the third licence lacks.