A rule that is never right and cannot be far wrong

Every essay in this field so far has been about the exact answer and what it costs. Here is what the theory says when the exact answer is not available at all.

It does not say guess. It gives a rule that is never optimal and cannot lose by more than a stated amount — and the amount is computed from the position rather than hoped for.

The rule, and the claim about it #

A board of independent components, each a game worth fighting over. The rule is one line: move in the component with the highest temperature, and inside that component take the best option available.

That is a local decision. It looks at each component’s own temperature and nothing else — not at what the other components will become, not at the total, not at how many moves are left. Which is exactly why it is affordable: temperatures of small components are cheap to compute, and the alternative is a minimax over the whole sum.

The claim attached to it is not that it plays well. It is that it cannot lose by more than the largest temperature on the board. A statement of that shape is worth quite a lot more than an observation that a rule usually does well, and it is worth being precise about which part of it is proved and which part is measured here.

What was actually measured #

The experiment is fixed in advance and it is small enough to describe completely.

Every board of three components drawn from that pool, which is 220 boards, played twice — once with Left to move first and once with Right — giving 440 lines.

Each line is played out three times: once by minimax over the whole sum, which is optimal by construction; once by the hottest-first rule; once by the same machinery with the ordering reversed, taking the coolest component each turn.

The three totals are compared. “Worse” carries a sign, since Left wants the total large and Right wants it small, and the loss recorded is always the loss to the player who moved first.

The results, and the two that matter #

Hottest-first exceeds the bound on 0 of 440 lines. The worst it ever does is 1, against bounds running up to 3.

Hottest-first is strictly worse than optimal on 17 of 440. This is the second half of the claim and it is the half people forget to check. A rule that were always optimal would make the bound true and vacuous — a bound is only a bound if the thing bounded can move.

Coolest-first exceeds the bound on 54 of 440, with a worst loss of 5.

That third number is the one that makes the first two mean anything. The same code, the same boards, the same comparison, with one ordering reversed — and it fails. So the test is capable of rejecting a rule, and hottest-first passing it is information rather than a property of the harness.

The scatter clamps a negative margin to zero, because a bound is a claim in one direction only, and clamping hides a number worth having.

Fourteen lines on which a rule that is never optimal beats optimal play is not a paradox, and the reason is the second caveat below: both players follow the rule being tested, so the greedy attacker is meeting a greedy defender. Against a defender playing perfectly the fourteen would not exist. What they do show is how flat the hottest-first distribution is — 409 lines of the 440 land exactly on optimal, and the whole of the rest is one point either way.

All three numbers are assertions rather than reports. The scatter at the top of this page refuses to draw if hottest-first ever exceeds the bound, if hottest-first is optimal on every line — which would make the bound true and empty — or if the reversed rule never breaks it, which would mean the experiment has no failing case at all. So the picture and the check are the same object, and one implementation serves both readings.

What the bound is, exactly #

The proved statement is about temperature, which is a measurement of how much is at stake in a position — how much a player gains by moving in it rather than elsewhere.

Roughly: playing greedily in the hottest component can leave a player behind by at most the temperature of the hottest component, because whatever advantage the opponent takes elsewhere is worth at most that much per exchange, and the accounting closes. The reason the largest temperature is the right quantity, rather than the sum of them, is that temperatures do not add — a sum is no hotter than its hottest part, so one number covers a board of any width.

There are sharper versions in the literature with better constants and more conditions, and this essay is not going to overstate what it has established. What is measured here is exactly the loose form: over 440 lines the loss never exceeded the largest temperature on the board.

Two features of the measurement should be stated because they narrow it.

Both players follow the rule being tested. The comparison is between two whole regimes — everyone greedy against everyone optimal — rather than one player deviating from perfect play. That is why some lines show the greedy player doing better than the optimal-versus-optimal total: their opponent is greedy too, and greedy defence is imperfect defence.

Every component here is a switch or nearly one. Boards of infinitesimals would test something else entirely, since temperature is silent about positions whose values are smaller than every number, and the accounting the rule rests on has nothing to weigh there.

The seventeen lines where it costs something #

The lines where the rule is strictly worse are the interesting ones, and they have a common shape.

A plain switch — $\{6 \mid 0\}$, say — has nothing inside it. Whoever moves in it takes the whole stake, and there is no second decision to get wrong. Boards made only of those are played optimally by the greedy rule, and the loss is zero on every line.

The components with a fight nested inside them are different. $\{4 \mid \{2 \mid 0\}\}$ is hot at the top and hot again underneath, so moving into it hands the opponent a position that is still worth something. A rule that ranks components by their current temperature does not see that the position it is about to create is nearly as hot as the one it is leaving — and on some boards taking the second hottest first, and coming back, is worth a point.

One row of that table is worth more than the pattern it confirms. $\{3 \mid \{2 \mid \{1 \mid 0\}\}\}$ is the deepest component in the pool — a fight inside a fight inside a fight — and it appears on none of the seventeen. So depth is not what costs the point, and nor is the follow-up being large relative to its own component: that ratio is highest for the deep one, whose temperature is seven eighths and whose follow-up is three quarters.

What costs the point is the follow-up being hot compared with the rest of the board. The deep component’s follow-up sits at three quarters, cooler than every plain switch in the pool but one, so after it is played the rule would have gone elsewhere anyway and there is nothing to get wrong. Compare $\{5 \mid \{4 \mid 0\}\}$, which appears on nine of the seventeen: its own temperature is 1, so hottest-first plays it late — and moving in it opens a fight at temperature 2, hotter than the component was and hotter than most of what is left. A rule that ranks by current temperature cannot see a move that raises the temperature of the board.

That is why the pool was built with four such components in it, and the claim is checkable rather than plausible: run the experiment on the six plain switches alone.

Coolest-first breaking the bound on none of those 112 lines is what makes the point. The reversed rule is the experiment’s rejection test, and on plain switches it has nothing to reject: an experiment run there would report a bound respected on every line, zero lines strictly worse, and a control that passes too. Three clean numbers, and nothing whatever established.

What optimal play costs, for comparison #

It is worth pricing the thing the rule is standing in for, because the whole argument is that it is unaffordable.

Optimal play over a sum is a minimax across every component at once: at each turn, every option in every component is tried, and the recursion continues from each. That search is over positions of the whole board, so its size is the product of the components’ position counts rather than the sum.

For the three-component boards here that is small — the components are tiny and the whole experiment runs in seconds, which is why the comparison is possible at all. Add a fourth component and it multiplies again; a Go endgame with a dozen fights is far past anything a minimax reaches.

The greedy rule, by contrast, costs one thermograph per component per turn, and a thermograph is computed from the component alone. It is linear in the number of components where the exact method is exponential — and that difference, not the quality of the play, is why the rule exists.

So the honest summary of the trade: an exponential saving, in exchange for a loss bounded by the hottest temperature on the board and measured here at 17 lines in 440.

Why an approximation with a proof is a different object #

The distinction this rung exists for is between two things that both get called heuristics.

A heuristic is a rule that works well in practice. Its evidence is a track record, its failures are discovered by being beaten, and its guarantee is nothing.

A bounded approximation is a rule with a theorem attached. It may still be beaten — hottest-first is beaten on 17 of 440 lines here — and the size of the beating is known in advance, from the position, before the game starts.

The second is what a person actually wants when the exact answer is out of reach. It converts nobody knows how much this costs into this costs at most three points, which is a claim that can be planned around. And the number is computed from the position rather than assumed: the largest temperature on a board is available for the price of a thermograph per component, which is far cheaper than solving the sum.

Where this sits among the answers #

Set the possibilities in order and the field’s shape is visible.

A closed form. The exact answer, cheaply, at any size: the nim-sum, fusion, the value of a Cutcake. Rare, and worth everything where it exists.

An exact search. The exact answer, expensively, up to the size where the table stops fitting. This is what the rest of the site does.

A bounded approximation. Not the answer, with a proved distance from it. Available on positions far past what any search can reach, because it needs only local measurements.

A heuristic. Something that has worked before.

Combinatorial game theory is unusual in having so much of the third. The temperature apparatus is not a fallback bolted on for hard positions — it is a theory of how much is at stake, developed for its own sake, that happens to yield bounds on greedy play as a consequence.

It is also worth saying which of the four this site’s own figures are, since the distinction is exactly the one the previous rung asks people to make: every played-back position here is an exact search, complete, on a position small enough for that to be affordable. Nothing here plays by temperature, because nothing here needs to.

That is also why the theory got used on real Go endgames. A Go endgame is far past exact solution as a whole board, its components are small enough to measure, and a rule with a proved bound is exactly what a player can act on.

Reading the picture #

The scatter at the top of this page repays a minute, because it carries four claims at once and none of them is the usual “look how well the rule does”.

The horizontal axis is not time or size. It is the bound itself — the largest temperature on that board — and the six positions along it are the six values that the pool of components can produce. The vertical axis is the loss. So the diagonal is the line $\text{loss} = \text{bound}$, and the entire claim is a statement about which side of it the points fall on.

The gold points all sit on or below the diagonal, in two rows: a large blob at zero, where the rule was exactly optimal, and a scattering at one, which is the seventeen lines. The magenta points climb well above it — as high as five, on boards whose bound was three.

Note also what the area of each point means: how many of the 440 lines landed there. The single largest blob is gold at loss zero, which is the rule being right most of the time — true, and the least interesting thing on the figure.

The figure is drawn by the same code the gate asserts on, so a reader who doubts the numbers is doubting the thing that would fail the build.

Why no rule of this kind can bound the winner #

The caveat above — that a bound in points is not a bound on the outcome — is worth turning into a statement about what is available in principle, because it explains why this whole apparatus belongs to Go rather than to the games this site mostly draws.

A guarantee of the outcome would have to say: play this way and the win arrives whenever perfect play wins. Under normal play, winning is decided by the sign of the final total, and the totals that decide games are routinely infinitesimal — a board of ups and stars whose value is smaller than every positive number and is nonetheless a win for somebody. A rule that can lose a whole point on some board cannot promise anything about a board whose whole margin is an up.

So the two guarantees are not the same guarantee weakened. They are denominated in different currencies, and there is no exchange rate: any bound of the form at most $t$ points is silent on every position where the margin is below every number, and those are exactly the positions the atomic weight was built for.

That is why the temperature apparatus is a scoring theory that happens to live inside a normal-play one. In Go the score is the answer, so a bound on the score is a bound on the answer, and Berlekamp’s endgame work is directly actionable. In Domineering or Clobber the score is a bookkeeping device and the answer is a sign, so the same bound tells a player how much they are giving away and never whether they have given away the game.

A reader wanting the second kind of promise has to change instruments rather than sharpen this one. What bounds an outcome is a comparison, and a comparison is a search — which is precisely the expensive thing the bound was standing in for.

What the experiment cannot settle #

Three limits, and the first is the one that keeps this honest.

440 lines is not a proof. The bound is a theorem in the literature; what is here is a measurement consistent with it on a fixed, small pool. If the pool were changed the numbers would change — and the gate would still require the bound to hold, which is the useful property.

The pool is deliberately favourable in one respect. The components were chosen to include some with a fight inside them, precisely so that hottest-first would not be trivially optimal. A pool of plain switches would show 0 lines strictly worse, and the bound would be true and empty.

A bound in points is not a bound on the outcome. Losing by at most the temperature is a statement about the total score at the end. On a board where the margin is smaller than the temperature, a rule that respects the bound perfectly can still hand over the win — which is where infinitesimals decide everything and temperature has stopped being the relevant measurement.

Nothing here says how to choose within a component. The rule as tested takes the option with the best mean inside the chosen component. That is a second decision, made greedily too, and a different tie-break would produce different numbers. The claim measured is about the whole procedure, not about the choice of component alone.

Who built the apparatus #

Temperature, cooling and thermographs are Conway’s, in On Numbers and Games, and the motivation there is structural rather than computational — a way of saying how much a position is worth fighting over, and of separating the part of a value that is a number from the part that is a fight.

The computational reading is largely Berlekamp’s, and it arrived through Go. Berlekamp’s endgame work is the standing demonstration that a theory built for its own reasons can be the practical tool for positions nobody can solve: measure each fight, play the hottest, and know the size of what that costs.

Which is a fair statement of what this whole field has been circling. The exact answer is expensive and often impossible. What replaces it, at its best, is not a guess — it is a smaller computation with a theorem attached, and the theorem is what makes the smaller computation worth trusting.

The last rung of this field goes back to the case where the theory itself is the expensive part. Misère play changes one line of the rules, keeps every position exactly as it was, and makes the cost of an answer grow with the universe it is asked about rather than with the position.