Knowing who wins, and knowing what it is worth

Many forms, one value counted what the reductions do to a population of forms and closed by naming what its census could not reach:

What does the canonical form cost to compute? Both reductions call comparison, comparison is subtraction followed by a search, and the search is over the sum of two game trees. The complexity of that is not the complexity of deciding who wins, and the difference between the two is a rung of its own.

The two currencies #

Deciding a winner expands positions. The recursion visits each position of the game tree and asks whether any option leaves the opponent losing, which settles the position’s outcome class and nothing else. With memoisation each position is visited once, so the cost is the number of distinct positions — the size of the tree after transpositions have been merged.

Computing a canonical form expands pairs. The reduction has to know which options dominate which, and

$$G \ge H \iff \text{no Right option of } G \text{ is} \le H \text{, and no Left option of } H \text{ is} \ge G$$

which is a recursion over one subposition of $G$ and one of $H$ at a time. So the state being memoised is a pair, the tree is walked against itself, and the reduction makes many such walks.

That is the whole of the answer, and everything below is the size of it.

It is worth noticing that neither currency is time. Positions and pairs are counts of distinct states expanded, which is the quantity a memoising evaluator’s table holds and the quantity that decides whether a computation finishes at all. Wall-clock timings would measure the machine as much as the question; these counts measure the question.

The numbers #

The nine positions were chosen to span two games and a range of sizes, and to be small enough that the expensive computation finishes — which is a real constraint, since the pair count grows fast enough to exhaust memory a couple of squares past the largest board here.

A $2 \times 2$ Domineering board has six distinct positions. Deciding the winner expands four of them; computing the value expands five pairs. The ratio is 1.3, and at that size the two questions cost the same.

A $3 \times 4$ board has 550 positions. Deciding the winner expands 145; computing the value expands 18,763 pairs. The ratio is 129.

Toads and Frogs on $\texttt{TTT..FFF}$ has 413 positions. Deciding the winner expands 68; computing the value expands 18,970 pairs. The ratio is 279.

The ratios across the nine positions run 1.3, 5.3, 5.9, 17, 28, 32, 66, 129 and 279, and they climb with the size of the tree. That is what a different complexity means: not a constant factor, but a gap that widens.

Why the winner is so cheap #

The win-loss recursion has a shortcut the value computation does not: it can stop early.

To show a position is a win for Left, one option leaving Right losing is enough — the other options need never be looked at. To show it is a loss, all of them must be checked, but the check on each stops as soon as its own answer is known. On a $3 \times 4$ board that pruning takes the count from 550 positions to 145 expansions, so nearly three quarters of the tree is never visited at all.

The same pruning is why a solver can answer who wins for boards whose values nobody has: the two questions are asked of the same tree and only one of them can skip most of it.

Nothing of the kind is available for a value. A canonical form has to know the whole option list, has to compare every option with every other, and has to know the reasons — an option that is not dominated has to be shown not dominated, which means the comparison must run to completion rather than stopping at the first good sign.

The comparisons are few and expensive #

The count of comparisons is small — between two and forty-seven across the nine positions — and the count of pairs is in the thousands. So the cost is not that the reduction compares a great deal; it is that each comparison is expensive.

A comparison between two positions of a $3 \times 4$ board is a search over pairs, and there are 550 positions on each side, so the pair space has up to 302,500 members. The 18,763 actually expanded is a small fraction of that, which is memoisation and pruning doing their work — but it is still 129 times the whole win-loss computation, from forty-seven comparisons.

That is the shape of the cost. Few questions, each of them quadratic in the tree, against many questions each of them linear.

Reading the table across the two games #

Domineering and Toads and Frogs behave differently in a way the comparison counts make visible.

The Domineering boards climb steadily in ratio: 1.3, 5.9, 17, 28, 129 as the board grows from four squares to twelve. The comparisons do not climb with them. In board order they are two, seven, twenty-six, twenty and forty-seven — the $2 \times 4$ board makes twenty-six of them and the larger $3 \times 3$ board makes twenty, while the $3 \times 3$ board’s ratio is the higher of the two. So the growth is not more questions; it is dearer ones.

Toads and Frogs does something else. $\texttt{TTT..FFF}$ makes eight comparisons and expands 18,970 pairs, which is 2,371 pairs per comparison; the $3 \times 4$ Domineering board makes forty-seven comparisons and expands 18,763, which is 399 apiece. Nearly the same total from a sixth as many questions.

The reason is the shape of the option lists. A Domineering board has many options — every place a domino fits — and most of them are quickly seen to be dominated, so there are many cheap comparisons. A Toads and Frogs strip has few options and they are all incomparable, so every comparison must run to the bottom of two deep trees before returning neither.

That is worth carrying as a rule of thumb. A comparison that comes back confused is the expensive kind, because there is no early exit from it: showing that neither of two positions is at least as good as the other means exhausting both possibilities. So a game with wide, flat option lists is cheap to reduce and a game with narrow, incomparable ones is not, whatever the trees look like.

The evaluator is not the site’s #

This measurement needed its own evaluator, and the reason is worth stating because it is a trap that would have made every number above meaningless.

The site’s evaluator memoises across the whole collection. By the time any figure asks what a $3 \times 4$ board costs, a dozen earlier figures have already computed pieces of it, and the answer would be whatever was left over. A cost measured with a warm cache is a measurement of the cache.

So the instrumented evaluator here starts empty for every measurement, builds the position tree itself, and counts what it does. Which raises the obvious problem: a second implementation is a second chance to be wrong.

The check is the one this site uses whenever a quantity is computed twice. Every position in the sweep has its canonical form’s width compared with the width the site’s own evaluator gives, and the two agree on all nine. That does not prove the new evaluator is correct in general; it proves it agrees with the site’s own on exactly the positions whose cost is being reported, which is what the claim needs.

Where the second evaluator was wrong #

It was wrong twice, and both faults are worth recording because both were found by the check rather than by reading the code.

The first was a missing half of the reduction. Only Left’s reversible options were being bypassed, not Right’s, so a $2 \times 4$ board came out with a form one option wider than the site’s — width three against width two. A reduction that stops early understates the cost, so the bug’s effect was to make the answer look cheaper than it is.

The second was subtler. The working form was carrying the key of the position it started as, so the comparison cache was answering questions about a form that no longer existed once the first option had been deleted. The fix is a fresh key on every change, and its effect on the numbers was small — but a poisoned cache produces wrong answers, not merely wrong costs, and it would have shown up as a width disagreement rather than as anything visible in the timings.

Both were caught by comparing widths with the site’s evaluator, which is exactly the job that check exists to do.

Notice what the check does not establish. Two evaluators agreeing on nine positions is not a proof that either is right; it is a proof that a fault in one of them would have to be a fault the other shares. What makes it worth running is that the faults it actually caught were not shared: a missing half of a reduction and a stale cache key are both mistakes one implementation makes and the other does not.

What a solver author would do with this #

The measurement has a practical edge, and it is not the one a reader expects.

The obvious reading is do not compute values unless they are needed, which is true and is not news. The useful reading is about when a value pays for itself.

A value is worth computing exactly when the position will be added to something. One board, one question, one winner: the win-loss search is 129 times cheaper and gives the whole answer. A board that has broken into five regions: computing five values and adding them is enormously cheaper than searching the product of five trees, and the difference is the exponential saving decomposition buys.

So the two costs are not in competition. They price two different strategies, and which is cheaper depends on whether the position is going to be a component. That is why a Domineering solver computes region values and a Hex solver does not: one game decomposes and the other never does.

The second practical point is about caching. Every number in the table above assumes a memo table with no evictions, and the pair counts are the sizes those tables reach — 18,970 entries for one eight-square Toads and Frogs strip. A solver that computes many values shares the comparison cache between them, which is where the real saving lives and which no single measurement can show.

What this says about the two questions #

Deciding a winner and computing a value are usually presented as the same activity at different depths — as though the value were what the search produces when it is run further. They are not.

The winner is a fact about one position. It needs one tree and it can be pruned.

The value is a statement about every sum the position could appear in. That is what equality quantifies over, and a claim about every possible companion cannot be established by looking at the position alone. The comparisons are where that quantifier is discharged, and the pairs are what discharging it costs.

So the gap between the two costs is not an inefficiency waiting to be optimised away. It is the price of a stronger statement, and a reader who wants only to know who wins should not be paying it.

There is a converse worth stating too. The value, once computed, answers infinitely many questions — who wins this position in company with any other position whatsoever — while the winner answers one. Priced per question the value is free, and priced per position it is 279 times the winner. Which of the two prices is the real one depends entirely on how many questions are going to be asked.

Where the ratio comes from #

The ratio grows because the two quantities grow at different rates, and it is possible to say roughly how.

The win-loss cost grows with the number of distinct positions, call it $N$. The comparison cost grows with the number of distinct pairs the comparisons reach, which is bounded by $N^2$ and is in practice much less, because a comparison only ever pairs subpositions at compatible depths.

Measured, the pair counts run well below $N^2$, and by a wide margin on every position.

The two boards at the bottom of that column are the two largest, which is the shape to notice: the share falls as the tree grows, so the pair count is not becoming quadratic. It is growing faster than $N$ and slower than $N^2$, and that is enough for the ratio: a quantity growing faster than another has an unbounded ratio, and the nine positions here show it passing 1, 10, 100 and heading upward.

Four positions the sweep did not choose #

A ratio that grows across the positions it was measured on is a claim about those positions. The nine were picked to be small enough that both computations finish, and a reader is entitled to ask whether the growth is a fact about the question or about the choice.

Four more were run afterwards, none of them in the nine, and none of them chosen to be flattering: a Domineering board one column wider than the widest in the sweep, and three Toads and Frogs strips of eight, nine and ten squares.

The last row is the essay’s rule of thumb at full stretch. $\texttt{TTTT..FFFF}$ has 1,775 positions and the win-loss search expands 126 of them — seven per cent, because a winning move is found early and almost the whole tree goes unvisited. The reduction makes fourteen comparisons and expands 227,138 pairs, which is 16,224 apiece. Few questions, each of them ruinous, on a position the winner search barely looks at.

That is also the clearest statement of why the ratio has no ceiling in sight. The pruning that makes the winner cheap gets better as the tree grows, and the comparisons that make the value dear get worse, so the two quantities are moving apart for two independent reasons at once.

Why the ratio is the wrong number to remember #

The table reports a ratio between the two costs, and the ratio is the least durable thing on the page. It is worth saying what to carry instead.

A ratio between two computations on the same positions depends on three things that have nothing to do with the question: which positions were chosen, how good each implementation is, and where the memo tables happen to hit. Change any of them and the ratio moves, and none of the three is a fact about knowing who wins against knowing what it is worth.

What is durable is the shape of each cost. The winner is decided by one search over one position, so its cost is the size of that position’s graph. The value is decided by a recursion that reduces every option, and reducing an option means comparing it with its siblings, and each comparison is a search of its own over a difference game. So the value’s cost is not a larger constant times the winner’s: it is a different function, with the comparisons multiplying down the tree while the difference games multiply across each sum.

That is why the gap widens with the position and why no ratio survives being quoted. A reader who remembers “eight times” will be wrong on a board twice the size, and wrong in the direction that matters, because the two costs are not proportional at all.

The number worth remembering is the qualitative one and it is decision-relevant on its own: if the answer wanted is who wins one board, computing the value is the expensive way to get it. That statement holds at every size, needs no pool, and is what a solver author would actually act on.

What the sweep cannot say #

Nine positions, in two games, all small enough that both computations finish. That is the only regime in which the comparison can be made at all, and it is the regime where the ratio is smallest — so the numbers here are a lower bound on the gap rather than a description of it.

Nothing here is a complexity result. How hard is it is about families and encodings and asks what happens as the input grows without bound; this is nine measurements with a memoising evaluator, and the honest statement is that the ratio grows over these nine, not that it grows in general.

And the cost of a canonical form depends on the reduction used. The one here deletes dominated options greedily and bypasses reversible ones when nothing else applies; a cleverer order would make fewer comparisons, and a much cleverer one might reuse work between them. What the sweep prices is a straightforward implementation, which is what most implementations are.

Where the ladder goes next #

value-cost opens here with the two currencies separated and priced against each other, and the five rungs above follow the third question this page names until it becomes an engineering answer.

The question in the middle prices that third question — who wins the board, given parts — and it lands where the name suggests, between the other two on seven sums of eight and cheaper than the values by up to eight times. The exception is instructive: on a sum whose two parts are the same position, computing one value serves both, so the value route wins exactly where the parts repeat.

When the catalogue starts paying then takes the repetition seriously and turns it into a program’s design. A catalogue of small regions is paid for once and answers every board over them by addition; the crossover is between five boards and two hundred depending on reach, 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.

The last three rungs are about how far to build it, and each corrects the one below. Where to stop building finds the coverage saturating — the tenth square of reach costs five thousand shapes for one point — so the answer is six or seven squares. A catalogue that knows what it will meet orders by frequency instead of by size and does far better: eight shapes answer half the components a played board produces, and three quarters of a size-ordered catalogue never turns up in play at all. And the catalogue a strong player needs tests the objection that random play is not play, and finds strong play concentrates the same distribution — 114 entries for nine tenths of what it meets, against 2,018.

The other direction this page names is the order of the two reductions, and nothing above takes it: deleting before bypassing and bypassing before deleting make different numbers of comparisons and the same answer either way, and how much the order costs is still unmeasured.

Two neighbours are worth the trip. What counts as the same position is where the merging both numbers rest on is defined. And a position reached eleven ways is one position is the transposition merging without which neither computation would finish at all.