The question in the middle

Knowing who wins and knowing what it is worth priced two questions against each other on the same positions — the winner, counted in positions expanded, and the canonical form, counted in pairs of positions compared — and found the second the dearer by a growing factor. It closed by naming a third:

Between the winner and the value sits the outcome of a sum — cheaper than a value, more than a winner — and it is what a player actually needs when a board has broken into parts. Pricing it would complete the ladder rather than extending it.

The third question is in the middle on seven sums of eight, and the eighth is the interesting one.

Why it is a third question #

A board that has fallen into pieces presents three questions and they are genuinely different.

Who wins each part? Cheap, and useless: outcomes do not add, so knowing that both components are first-player wins says nothing about the sum.

What is each part worth? Expensive, and reusable: a canonical form settles the question for every sum that part will ever appear in — equal in every company is the theorem that licenses it — which is what makes a catalogue of region values worth building.

Who wins the board? This is what a player needs and it is not either of the others. It can be answered by taking the second route — compute the values, add them, read the outcome — or by searching the sum directly, over tuples of the components’ states.

Searching over tuples is the version priced here, because it is what a program with no theory of values would do — and because the alternative is already priced. The value route’s cost is the third column plus an addition, and an addition of canonical forms is cheap next to producing them, so the third column is the value route to within a rounding error.

That is worth being explicit about, because it means the table is not comparing two methods and a curiosity. It is comparing the two ways of answering one question, with the parts’ outcomes standing beside them as the scale: the cheapest thing a program can do that is about the board at all.

The count, and what is being counted #

Eight sums: five of two Domineering boards, two of two Toads and Frogs strips, and one of each — because a mixed sum is where a value theory earns its keep and a search does not care.

Each is measured three ways and every measure is a count of distinct memo entries, which is the rule the rung below set and the reason the three numbers can go in one table. A position expanded twice is charged once; a comparison made twice is charged once; a tuple reached twice is charged once. Anything else would be measuring the absence of a cache.

The totals over the eight sums: 413 for the winners of the parts, 8,344 for the winners of the sums, 32,089 for the values of the parts.

So the middle question is in the middle, and it is not close: it is twenty times the first and a quarter of the third.

Those totals hide the spread and the spread is the interesting part.

Neither column is a constant, and the second is the one that grows with the board — 7.7 on the largest sum here, 1.1 on the smallest. That is the same shape the rung below found between its two questions, and for the same reason: the value column is the one whose cost grows fastest with the tree.

The exception, and why it is not one #

On seven of the eight sums the search is cheaper than the values. On the eighth — two copies of a 2 × 3 Domineering board — it is dearer: 104 tuples against forty-seven comparison pairs.

The reason is accounting rather than arithmetic. A program taking the value route on two identical components computes one value and looks the second up, so it pays for one; the search has no such shortcut, because the pair of states is what it indexes on and the pair (a, b) is a different entry from (b, a) even when the two components are the same board.

That is the whole of the exception and the table charges it honestly: repeated components are counted once in the value column and the search pays for every tuple it reaches.

It is also the clearest small statement of what a value is for. A value is a summary that can be reused; a search is work that cannot. The moment a component appears twice, the value route halves its work and the search route does not — and a real board is full of repeated regions.

The word exception is the wrong one, and taking more copies shows why.

The value column is flat and the search column is exponential in the number of copies. Four copies of one board cost the values forty-seven and the search 11,460, which is 244 times as much; and the fourth row of that figure is a board of twenty-four squares, which is smaller than the boards a person plays on. So the eighth row of the eight-sum table is not an oddity of a small example — it is the second point of a curve. Two copies put the search at twice the values, three copies at twenty times, four copies at two hundred and forty-four.

Why the product is a bound and not a cost #

The obvious objection to the whole exercise is that a search over tuples ranges over a product where the other two questions range over sums, so it ought to be the most expensive of the three by a wide margin.

It is not, and the table says by how much it is not. The 3 × 3 Domineering board has ninety-eight positions and the Toads and Frogs strip TTT..FFF has 413, so the pairs of states number 40,474. The search reaches 2,546.

Two things keep it down and both are ordinary.

The search stops at the first winning move. Asking whether Left wins means asking whether some option leads to a position Right loses, and the moment one does the rest are not examined. On a position with a winning move that move is often the first one tried, and the whole subtree behind the alternatives is never built.

And the two components shrink together. A tuple deep in the search has both components partly played, and the number of ways to reach such a tuple is large while the number of such tuples is not — which is exactly what a memo exploits.

So the product is the size of the state space and the search is a walk through part of it, and the part is small. The product bounds the cost and does not predict it, which is the general reason worst-case bounds are unhelpful in this subject and is worth having a measurement of rather than an assurance.

The mixed sums, where the difference is widest #

Two of the eight sums put a Domineering board beside a Toads and Frogs strip, and they are where the columns are furthest apart.

Domineering 2 × 3 with TT..FF costs forty for the winners, 157 for the sum and 1,079 for the values — the sum’s outcome is seven times the winners and a seventh of the values. Domineering 3 × 3 with TTT..FFF costs ninety-four, 2,546 and 19,708, and the last of those is nearly eight times the middle.

The mixed sums are the widest because the value column is dominated by whichever component is dearest to evaluate, and evaluating a Toads and Frogs strip is much dearer than evaluating a Domineering board of comparable size. The search column is dominated by the product, which the cut-offs keep down, so the expensive component costs the search far less than it costs the reduction.

That is the case a value theory is usually sold on and it is the case where a search does best. Two games with nothing in common cannot be analysed together by any means but a value — there is no common structure to exploit — and the value is exactly what costs eight times as much as walking the sum.

The reason is not that values are wasteful. It is that the value answers a question about TTT..FFF that this board did not ask: what it is worth against anything, when what was wanted was what it is worth against one 3 × 3 Domineering board.

One component wider, and the ordering goes #

Every sum above is a sum of two, and a real board falls into three or four. A search over triples of states ranges over a triple product where a search over pairs ranges over a square, so the question is whether the cut-offs keep it down as effectively — and the answer is that they do not.

So the middle question does not stay in the middle. Three Domineering boards of six, eight and nine squares cost 57 for the parts’ winners, 9,616 for the search and 1,184 for the values: the search is eight times the values on twenty-three squares of board, and it was a seventh of them on the largest sum of two.

The reason is arithmetic rather than anything about the games. A third component multiplies the search and adds to the values. The value column is a sum over distinct parts, so a third part adds one term; the search column is a walk through a product of state spaces, so a third part multiplies the space it walks. The cut-offs cut a constant fraction of a space that has grown by a factor, and a constant fraction of a much larger thing is a much larger thing.

That is the clean statement the two-component table could not make. Its ordering is not a fact about the three questions; it is a fact about sums of exactly two, and it was already the narrowest case for the search. Everything the ladder above builds — the catalogue, the reach, the frequency ordering — is aimed at boards with many components, which is precisely where the route this page prices stops being the cheap one.

What the ladder now says #

Three questions, three costs, and the ordering is stable across every sum of two here except the repeated one.

Asking who wins each part is nearly free and answers nothing about the board. Asking who wins the board costs twenty times as much and answers the question a player has. Asking what the parts are worth costs four times that again and answers it for every board those parts will ever be in.

The middle question is the one a program should ask if it will see each position once, and the last is the one it should ask if it will see them many times. That is the whole trade and the table is the exchange rate, which for these eight sums sits at about four.

The number is not a constant and the reason is the same as the rung below’s: the value column grows faster. Domineering 3 × 3 against a Toads and Frogs strip is 2,546 against 19,708 — nearly eight times — and it is the largest sum here. A larger one would be further apart still, which is what makes reusable the right word for a value rather than cheap.

One property of the middle question does not show in the numbers and it decides when to ask it.

The winner of a part is a fact about the part. The value of a part is a fact about the part. The winner of a sum is a fact about the sum, and there is no sense in which it can be stored against either component — a program that has learned who wins A + B has learned nothing about A + C.

So the middle column is work that is thrown away, and the outer columns are not. On a single board that costs nothing; on a session of boards over the same regions it costs everything, because the search is repeated in full for every new pairing while the values are computed once.

The table therefore prices a one-off, and it is the right thing to price because the rung below priced two one-offs. What it does not price is the amortisation, and the amortisation is the reason values exist.

What a solver would actually do #

Neither of the two routes is what a serious program does, and it is worth saying what is missing so that the table is not read as advice.

A program facing a board decomposes it, evaluates each region and looks the region up in a catalogue — which is the region catalogue this site builds for Domineering. The catalogue is the value column paid once, in advance, for a whole family of positions, and thereafter every board made of catalogued regions is answered by addition.

That changes the arithmetic completely. The value column above is the cost of computing the parts’ values for this board; against a catalogue it is the cost of a lookup. The search column is unchanged, because a search has nothing to look up.

So the honest statement of the trade is about how many boards will be asked, not about how many components this board has. One board, once: search it. A family of boards over a family of regions: build the catalogue.

The exception is the whole design #

The one sum where the value route wins — the sum whose two parts are the same position — looks like a footnote and is the entire argument for building a catalogue. It is worth promoting.

Computing the outcome of a sum is a search over the sum, and it has to be redone for every sum. Computing a value is expensive once and free thereafter: the value of a part is the same in every board that part appears in, so the cost is amortised over every future appearance. On a sum with a repeated part that amortisation happens immediately, which is why the exception shows up at two components rather than at fifty.

So the two routes are not two ways of answering one question with different prices. They are answers with different shapes: one is per-board and one is per-part, and which is cheaper depends entirely on how many boards a part will appear in.

That is a ratio nothing on this page measures, and it is the ratio that decides. A part appearing once makes the outcome route right; a part appearing a thousand times makes the value route right by three orders of magnitude, whatever the per-computation costs are. The interesting quantity is therefore the reuse rate, not the cost of either computation — and a catalogue is exactly the machine for driving the reuse rate up.

Which is why the ladder above stops pricing computations and starts counting how often each shape turns up in play. The middle question priced here is the right question for one board, and a program never plays one board.

What the sweep does not say #

Four limits.

Eight sums, and small ones. The largest sum here has a component of 413 positions. The cost ordering is stable across all eight of the sums of two, and eight is not many; every count is a count rather than a rate.

Six three-component sums is not many either, and the ordering they break is the whole finding above rather than a detail of it. A fourth component is the same computation one wider again, and it is not run here.

Nothing here is about hardness. Deciding the winner of a Domineering position is PSPACE-complete and so is deciding the winner of a sum of them, and none of the three columns is evidence about a complexity class. They are counts on small positions, and the ordering between them, and where it breaks, is the finding.

And the value column is a cost, not a complexity. Counting distinct comparison pairs is a proxy for the work a reduction does, and it is the proxy the rung below chose and defended. It is not the number of machine operations, and a program with a different comparison strategy would pay a different amount for the same answer.

The convention, named #

Normal play, and both games are the site’s standard ones: Domineering with Left vertical, Toads and Frogs on a strip with the ordinary hop.

Every measurement runs on its own caches, so a cost measured is not a cost measured with something else’s memo already warm. The winner of a part is counted in memo entries of the two win predicates; the value of a part in distinct pairs the comparisons expanded; the winner of a sum in distinct tuples of states the two win predicates reached. A component appearing twice in a sum is charged once in the value column, because a program would look it up, and every tuple is charged in the search column, because a search cannot.

Where the ladder goes next #

The value-cost anchor has two rungs to here: the two currencies priced against each other, and now the question that sits between them.

The four rungs above take the repetition this page notices — that a value computed once serves every board containing that part — and turn it into a program’s design.

When the catalogue starts paying prices the catalogue against the search it replaces: the crossover is between five boards and two hundred depending on how far it reaches, and it falls as the board grows. The whole catalogue of every region to eight squares costs one part in seventy-six of a single undecomposed five-by-five board.

Where to stop building then 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 and the answer is to build to six or seven.

The last two rungs replace reach with frequency and then check the pool. A catalogue that knows what it will meet finds eight shapes answering half the components a played board produces, where a size-ordered catalogue needs fifteen — and three quarters of a size-ordered catalogue never turns up in play at all. The catalogue a strong player needs then re-runs the measurement against a player that reads the board, and finds the head of the distribution unchanged while the tail collapses: 114 entries answer nine tenths of what a strong player meets, against 2,018 for a random one.

So the third question this page prices turns out to have a fourth behind it — which parts, and how often — and that is where the whole saving lives.