A rule with a guarantee

Every route to the right move on this site so far has been an evaluation. Build the sum, reduce it to canonical form, read off the answer. That is exact, and it is unavailable the moment the board has a dozen fights on it: the canonical form of a sum of twelve small positions is an object nobody can write down, and the cost of building it grows faster than the board does.

The alternative is a strategy. Not a value — a rule for choosing a move that looks only at the parts, one at a time, and never assembles the whole. A rule like that cannot be exact; what makes one worth having is that it comes with a bound on how much it can lose.

The rule #

Move in a component of greatest temperature, and inside it take the option that leaves the best stop.

The first half is playing the hottest and is what strong players do without being told. The second half is the tie-break, and it is needed: a component may have two options at the same temperature, and a rule that did not say which to take would not be a rule.

Neither half looks at the sum. To follow it a player needs one number per component — its temperature — and one comparison inside the chosen component. Nothing is added up, nothing is canonicalised, and the work is linear in the number of fights on the board.

What the guarantee says #

The bound the sweep checks is this: a player following the rule never ends more than $t$ below the mean of the board, where $t$ is the largest temperature anywhere on it.

$$\text{score} \;\geq\; \sum_i \mu(G_i) \;-\; t$$

It held in all 220 sums. That is the shape a strategy result takes and it is worth reading carefully, because it is not the shape a reader expects.

It is not a bound against optimal play. Optimal play is also somewhere in the interval — over the same 220 sums the exact score sat within $t$ of the mean every time — and the two bounds are separate statements. The rule could be exactly on the bound and optimal play could be exactly on the bound and they would agree; or optimal could be above and the rule at the bottom, and the gap would be $2t$.

It is also not a bound in points a player can bank. The mean is what the components are worth between them — what many copies of a position settle at — and it is a number the player never sees during the game: it is computed from the thermographs afterwards. What the guarantee buys is the knowledge, before playing, that following the rule cannot be catastrophic — bounded by the largest single stake, whatever the rest of the board does.

What it costs, measured #

Over the 220 sums the rule is exact in 196 and loses something in 24. The largest loss anywhere is one point, and the sum that produces it is small enough to look at.

Two copies of $\{2 \mid 0\}$ and one copy of $\{10 \mid \{9 \mid 1\}\}$. The means are $1$, $1$ and $9$, so the board is worth $11$. Perfect play by Left scores $12$. The rule scores $11$.

The rule’s mistake is that $\{10 \mid \{9 \mid 1\}\}$ has temperature $1$ and so do both copies of $\{2 \mid 0\}$, so the three components are equally hot and the tie-break sends Left into one of the switches. Perfect play goes into the big component first, because its Right option carries a follow-up worth eight points and leaving it standing is expensive in a way the temperature does not see.

Why the error is one temperature and not many #

A bound of $t$ on a board with a dozen fights on it should look suspicious. Every move is an opportunity to be wrong, so an error term that does not grow with the number of components is the part of the result that needs explaining.

The explanation is that the errors cancel, and they cancel because both players are following the same ordering. Imagine the board as a list of stakes sorted downwards, $t_1 \geq t_2 \geq t_3 \geq \cdots$, with the players alternating: Left takes $t_1$, Right takes $t_2$, Left takes $t_3$. What Left gains over the whole game, relative to a split down the middle, is the alternating sum

$$t_1 - t_2 + t_3 - t_4 + \cdots$$

and an alternating sum of a decreasing sequence is at most its first term. Every stake after the first is cancelled by the one that follows it — the opponent’s answer is worth nearly as much as the move that provoked it, because the list is sorted and consecutive entries are close. Only the head of the list survives, and the head of the list is $t$.

That is the whole of the intuition, and three of its features are worth naming because they explain everything the sweep found.

It is why the error does not accumulate. Twelve components do not give twelve chances to lose a point; they give one uncancelled term. This is the same asymmetry the thermograph figure above records — means add and temperatures do not — seen from the strategic side rather than the arithmetic one.

It is why the rule has to take the hottest. A player who plays out of order has broken the sortedness the cancellation depends on, and the terms stop pairing off. Taking a two-point fight while a nine-point fight stands does not lose two points; it loses whatever the opponent takes from the nine.

And it is why the bound is stated against the mean rather than against optimal play. The argument above never mentions the opponent’s best play at all — it works against any opponent, and the mean is the reference point that makes it work. Comparing to optimal would require knowing what optimal does, which is the computation the whole exercise exists to avoid.

Where the rule is blind, and it is exactly at a tie #

The sum the rule mishandles has all three of its components at temperature $1$, and that is not a coincidence about that row.

A rule that reads one number off each component can distinguish two components only when their numbers differ. When the numbers agree it has no information left and falls back on a tie-break, and a tie-break is by construction the part of a rule that is not justified by anything. So the crude strategy is blind on precisely the set of positions where its measurement fails to separate — which is to say, where several fights are equally urgent and the reason to prefer one of them is something other than urgency.

That is exactly the situation the finer strategy was built for. Comparing wall widths at the current ambient temperature rather than comparing temperatures gives a real number where the crude rule has a tie, and the ties are where the crude rule’s twenty-four losses come from. The measurement here does not check that claim — the fine strategy is not implemented — but it does establish the shape of the target, which is a narrower thing to test than “is the fine rule better”.

One more reading of that row is worth having. The board’s mean is $11$, the largest temperature is $1$, so the guarantee permits a score of $10$; perfect play gets $12$ and the rule gets $11$. The rule therefore lands a full point above its own guarantee in the worst case anybody found, and the same holds wherever the losses were inspected. Across all 220 sums the bound was satisfied and never met.

That gap is the ordinary condition of a strategy result and is worth being unromantic about. The guarantee is proved by an argument that assumes the worst at every step — every stake exactly as large as it could be, every cancellation as unhelpful as it could be — and real boards are not adversarial in all those ways at once. A bound that is never tight is still the only thing here that survives changing the pool.

The second strategy, which turned out to be the first #

Berlekamp’s pair of strategies is usually presented as two ideas. Thermostrat plays where the stake is largest. Sentestrat answers a threat: if the opponent has just moved in a component that is still hot, move there, and otherwise fall back on Thermostrat.

Both were implemented, both were run against an evaluating opponent over the same 220 sums, and they never once chose differently.

The reason is not that Sentestrat is a bad idea. It is that the opponent in this sweep evaluates exactly, and an opponent who evaluates exactly answers threats because answering them is right — so the component they have just moved in is almost always a hottest one anyway, and the fall-back clause fires on every move.

That is a real finding about what sente is for. A threat is a precaution against an opponent who might not answer, or who might not notice. Against perfect defence there is nothing to protect: the threat is already priced into the position, which is exactly what sente being a fact about the rest of the board says, and it is why double sente is not a property of a position either. The measurement here is the same statement in the negative, and it is a sharper way of putting it than the essay one rung over could manage.

Who found it, and what they were replacing #

The bounds come from two directions and forty years apart.

Hanner in 1959 and Milnor in 1953 were both looking at games with scores rather than winners — Go endgames, in Milnor’s case explicitly — and both arrived at the same shape of result: the value of a sum is within a computable distance of the sum of the parts’ mean values, and the distance is a temperature. Milnor’s version is a theorem about positional games with a non-negative incentive condition; Hanner’s is about the same bound reached by exhibiting play.

Berlekamp’s contribution, in the 1980s and 1990s, was to turn the bounds into procedures. Thermostrat and Sentestrat are not analyses of a position; they are instructions, and the theorem attached to each says what following the instruction guarantees. That is the move this essay is about: from “the value of the sum lies here” to “here is what to play, and here is what it costs”.

The context was Go. A Go endgame is a board that has broken into a dozen independent regions, every one of them small enough to evaluate and the whole of them not, which is precisely the situation a strategy exists for. The coupon stack — an environment of known stakes placed beside the board — came out of the same programme, as a way of turning the theory into something two people could sit down and test.

The coupon stack — an environment of known stakes placed beside the board — came out of the same programme, as a way of turning the theory into something two people could sit down and test: a player may always take the top coupon instead of moving, so the coupon they stop at measures the temperature of the position rather than computing it. The rule above is what a player does when the whole board is coupons of unknown value.

Why a bound is worth more than a good average #

The rule is exact 89% of the time and it would be easy to present that as the headline. It is the less useful number.

An average is a statement about the pool. Change the pool — add components with deep follow-ups, add a dozen more of them — and the 89% moves, and there is no way to predict where. The guarantee does not move: it is $t$, whatever the pool, and $t$ is a quantity the player can read off the board before starting.

That is the difference between a heuristic and a strategy, and it is the reason the subject bothers with these constructions at all. “Play where the stake is largest” as folk advice is a heuristic; the same rule with $\sum \mu - t$ attached is a theorem about a procedure, and the theorem is what survives contact with a board nobody has seen before.

The pool, and why it has follow-ups in it #

A sweep of this kind is only as honest as the positions it runs on, and a pool of plain switches would have made the rule look perfect.

On a board where every component is a switch $\{a \mid b\}$ with $a > b$ and no deeper structure, playing the hottest is optimal, and the orthodox account settles the score exactly. That is the classical case and it is the one a reader is most likely to have seen; it is also the case in which the strategy has nothing to prove.

So half the pool is built to break it. $\{10 \mid \{9 \mid 1\}\}$ has temperature $1$ and a Right option worth eight points less than its Left option — a threat sitting under a small stake. $\{\,\{8 \mid 0\} \mid 0\}$ has temperature zero and a Left option that is a four-point fight, so it looks like nothing and is not. $\{3 \mid \{2 \mid -8\}\}$ is the same shape with the threat on Right’s side.

A plain switch and one with a follow-up differ in the shape of their thermograph walls rather than in any single number: the switch’s run straight, the follow-up’s bend where the deeper option takes over. A rule that reads only the height at which the walls meet sees the same figure for a component with a bend and one without, and the bend is where the point is lost.

Twenty-four of the 220 sums lose something and every one of them has at least one follow-up component in it. That is not proved here, but it is what the rows show, and it is what the design of the pool was for.

What the solver computed, and how #

The pool is ten positions built by hand: plain switches, two switches with a follow-up on one side, and two positions whose only move leads into a fight. Every unordered triple gives 220 sums.

For each sum three scores are produced. The optimal score comes from an exact search over the sum, which at three small components is affordable and is memoised on the tuple of component identities. The rule’s score comes from playing the sum out move by move with one side choosing by the rule and the other by the same exact search — so the strategy is measured against best defence rather than against another heuristic, which would report a number about neither.

The reference quantities are read off the thermographs: each component’s mean, summed, and the largest temperature on the board. The guarantee is checked on every row rather than asserted once, and the rows where the rule loses are kept so the worst case can be printed rather than described.

The check that could have failed and did not is the bound. A row scoring below $\sum \mu - t$ would have meant either that the bound is false or that the strategy was implemented as something other than what it claims to be, and either would have been worth more than the 89%.

Where the model stops #

Three components. The bound is about sums of any size and the sweep is about sums of three, because the exact opponent has to evaluate the whole sum and that is what limits the size. A sum of eight components from this pool would be a better test of a rule designed for boards nobody can evaluate, and it is exactly the case where the reference score cannot be computed.

The strategies implemented here are the site’s versions of Berlekamp’s and are simpler than his. Thermostrat proper does not compare temperatures; it compares the widths of the components’ thermograph walls at the current ambient temperature, which is a finer measurement and gives a better bound on positions where several components are equally hot — the case that produces the one-point loss above. What is measured here is the crude version, and the crude version is what the folk advice actually says.

And the pool is a pool. Ten positions chosen to include follow-ups is not a random sample of anything, and the 89% is a number about them. The guarantee is the part that does not depend on the choice.

Where the ladder goes next #

This rung establishes that a rule looking at one component at a time comes with a bound, and measures what the bound costs. The rung above is the finer version: the strategy that compares walls rather than temperatures, and whether the sums where the crude rule loses are exactly the ones the fine rule saves.

Two neighbours are worth the trip. An environment made of coupons is the other way to make a strategy measurable — put a stack of known stakes beside the game and watch where the players stop taking them. And playing the hottest is the rung below, which asks whether the rule is optimal and finds that it is not; this one asks how far from optimal it can get, and answers with a number.