A rule with no promise at all

A rule with a guarantee measured what playing in a hottest component costs. Over 220 sums of three hot components, the rule scores exactly what perfect play scores on 196 of them, is never more than a point behind, and never ends more than the largest single temperature on the board below the board’s mean. The last of those is the promise the rule comes with, and it held every time.

A bound that has never been violated is a bound nobody has tested. This essay runs two more rules over the same 220 sums: one that has no theorem behind it at all, and one that is deliberately bad.

The results are not what the ordering of those two sentences suggests.

The four rules #

Move in a hottest component. Find the component with the largest temperature and play there, taking the option that leaves the best stop. This is the site’s Thermostrat: play where the stake is largest.

Answer the opponent, else the hottest. If the opponent has just moved in a component that is still hot, move there; otherwise fall back to the first rule. This is the site’s Sentestrat: never leave a threat standing.

Take the biggest immediate gain anywhere. Look at every option in every component and take the one that moves the mover’s stop furthest in the mover’s direction, ignoring temperature entirely. This is how a strong human player is often described, and it is not the same rule as the first.

Move in a coldest component. The control. There is no argument for it and it is included because a promise the pool cannot break is a promise about the pool.

What the guarantee says #

The claim behind the first two rules is a bound on the score:

$$\text{score} \ \ge\ \mu - t$$

where $\mu$ is the sum of the components’ mean values — what the board is worth between the players, once the fighting is over — and $t$ is the largest single temperature on it.

It is a statement about worst cases and it is deliberately weak. A rule that guarantees only $\mu - t$ is admitting it may give away one whole fight’s worth of advantage, and the reason it can promise no better is that the opponent moves too: after the rule’s move, the opponent takes the best thing left, and the accounting has to allow for that all the way down.

The two rules with the theorem #

Both hold. On all 220 sums, both rules end at or above $\mu - t$, and neither ever loses more than a single point against perfect play.

They also never differ from each other — the 220 sums produce identical scores under both, which the earlier essay reported and which has a plain explanation: an opponent playing optimally answers a threat because answering it is right, so the component they have just moved in is nearly always a hottest one and the fall-back never fires. Sente is a precaution against an opponent who might not answer, and an exact evaluator always does.

So on this pool the theorem’s two rules are one rule, and the interesting comparison has to come from outside.

The rule with no theorem beats them #

Two hundred and five of 220 exactly optimal, against 196.

The greedy rule — take the biggest immediate gain anywhere on the board — is strictly better on this pool than the rule with the bound, by nine sums, and its worst loss against perfect play is the same single point.

It also satisfies the bound, on all 220. Nothing about the rule mentions temperature, means or stops of the board, and it lands inside the promise every time anyway.

That is the finding, and it should be read carefully, because it is easy to over-read.

It does not say greedy play is better. It says that on 220 sums of three components drawn from a pool of ten hot positions, greedy play happened to be better. There is no bound behind the rule, so there is nothing to stop a family of positions on which it is catastrophic, and constructing one is not hard: a component whose biggest immediate gain is followed by an enormous reply is exactly the shape a greedy rule walks into, and it is what sente is a word for.

It does say the bound is not a ranking. Being inside $\mu - t$ is a property a great many rules have, including rules with nothing to recommend them, so satisfying it is not evidence that a rule is good. The bound is a floor and the interesting question is how far above the floor a rule sits, which the bound does not address.

The nine-sum gap is a net figure and the raw counts are worth having: the two rules part company on thirteen of the 220 sums, greed winning eleven of them and the hottest rule two. One of the eleven is small enough to read.

The control does the work #

Playing in a coldest component is exactly optimal on 75 of the 220 — a third, which is what a rule with no idea gets on a pool where a third of the sums are easy — and it violates the guarantee on 74 of 220.

It also loses up to eleven points, against the other rules’ maximum of one.

That is what makes the guarantee a real constraint rather than a description of the pool. Something in the space of rules breaks it, on a third of the sums, badly. The 220 sums are not so easy that any rule stays inside; the rules that stay inside are staying inside because of what they do.

The bound is never tight here #

The last column of the census is the one that closes the argument, and it is a zero.

On no sum in the pool does the hottest rule end exactly on $\mu - t$. The closest it comes is one full point above, on the sum in the figure above. So the bound is satisfied everywhere, comfortably, with slack to spare on every single position.

A bound with permanent slack is a bound that has not been shown to be the right bound. It might be that the true guarantee is $\mu - t + 1$ on pools of this shape, or that $\mu - t$ is exactly right and the pool is not adversarial enough to reach it. The census cannot distinguish those, and the honest report is the slack.

What is known from outside the census is that the bound is tight in general: Berlekamp’s analysis constructs sums on which Thermostrat’s guarantee is met exactly, and the construction needs components whose thermographs have particular widths. Nothing in the ten-position pool has that shape, which is a fact about the pool.

What “greedy” actually means here #

The rule needs stating precisely, because greedy is doing a lot of work in the paragraph above and there are several rules that could be called that.

The one measured takes, over every option of every live component, the one that moves the mover’s own stop furthest in the mover’s direction. For Left that is the option $A$ maximising

$$\text{RS}(A) - \text{RS}(G_i)$$

— the right stop of the option minus the right stop of the component it came from. That is the incentive of the move to Left read as a number rather than as a game: the incentive proper is $G^L - G$, a whole game, and this is what it is worth once the fighting stops. The reduction to a number is what makes the rule cheap and is also the only thing it throws away.

So the greedy rule is play the move with the largest incentive, and that is not the same as playing in the hottest component. A component’s temperature is a property of the whole component; an incentive is a property of one move. A hot component can offer a small move and a cool one can offer a large one, and the two rules diverge whenever it does.

There is a version of this rule that is in the literature, and the difference is one word: play the move of largest incentive rather than the move in the component of largest temperature. Nothing here says which is better in general, and on this pool the census says the first is exact nine times more often — winning eleven of the thirteen sums on which the two disagree, and losing two.

What the measurement cannot say #

The opponent is exact. Every rule here plays against an evaluator, not against another rule. That is the right choice — a heuristic against a heuristic reports a number about neither — and it is also the friendliest possible opponent for a rule with a bound, because an exact opponent never does anything unexpected. Sentestrat exists for opponents who do.

The pool is ten positions, and they are switches and switches-with-follow-ups rather than positions from a game. A pool drawn from the values a real ruleset produces would be shaped differently and mostly colder.

The counts scale. Four-component sums from the same ten is 715, on which the picture is the same: greedy exact on 641, hottest on 606, coldest violating the bound on 339. Both counts move together, which is reassuring and is not a wider pool.

The components are hot. Every position in the pool has a positive temperature, so there is never a moment when a rule has to choose between a fight and a number. A real endgame is mostly numbers with a few fights in it, and which part to move in is a different question when most of the parts are settled.

Only the score is measured. Nothing here measures how long a rule takes to decide, and the difference is real: the hottest rule needs a thermograph per component, which is a recursive computation, and the greedy rule needs one stop per option. A rule that is nine sums better and considerably cheaper is a strange thing for the theory to have no name for.

The rule that answers, and the opponent it is for #

Sentestrat’s failure to differ from the hottest rule on any of the 220 sums deserves one more look, because it is a measurement about the opponent rather than about the rule.

Sente is a move the opponent must answer. A rule that always answers is a rule that never leaves a threat standing, and the reason to want one is that an unanswered threat can be cashed later at a profit. Against an exact evaluator there are no unanswered threats, because an exact evaluator answers whatever is worth answering, so the rule’s distinguishing clause never fires.

So the honest report on Sentestrat here is that the pool cannot see it. It would take an opponent following a rule of its own — a heuristic against a heuristic, which measures neither — or a pool of positions with large hidden follow-ups, to make the two rules come apart.

What “no promise” actually means #

The phrase in the title is doing precise work and it is worth spelling out, because a rule with no guarantee is not the same as a rule that is unreliable.

The greedy rule has no theorem. There is no proof that its loss against perfect play is bounded by anything at all, so its worst case over all boards is unknown, and could be arbitrarily bad on some board nobody has tried. That is the whole of the deficiency, and it is a statement about the literature rather than about the rule.

What the sweep measures is quite different: how the rule performs on a stated pool. On those 220 sums it is not merely bounded, it is better than the rule with the theorem. Those two facts are compatible and neither weakens the other, because a guarantee is a claim about the worst case and a census is a claim about a sample.

The uncomfortable part is that a reader cannot use the second to get the first. No number of boards on which the greedy rule behaves well is evidence that it is bounded, because the bound is a universally quantified statement and every sweep is finite. A guarantee cannot be measured into existence.

So the honest position after this page is a pair of statements a reader has to hold at once: on everything measured the unguaranteed rule is better, and on the boards nobody has measured only the guaranteed one is safe. Which of those matters depends entirely on whether an adversary chooses the board — and in a real game, an adversary does.

Why the theory prefers the bounded rule anyway #

Because the numbers above are the wrong kind of evidence for the question the theory is asking.

A guarantee is a statement about every position, including the ones nobody has enumerated, and its value is precisely that it does not depend on a pool. When a Go endgame has forty regions in it, no census is available and no comparison of rules can be run; what is available is the sentence this rule cannot end more than the hottest region below the count, and that sentence is what an endgame analysis is built out of.

The greedy rule’s 205 is a measurement, and a measurement of a heuristic is a description of the sample. A rule that is never right and cannot be far wrong is the essay about exactly this trade, in the setting of an approximation algorithm, and the trade is the same here: the guaranteed rule is worse on average and is the one that can be reasoned with.

So the ranking the census produces and the ranking the theory produces are answers to different questions, and both are right. On this pool, greed wins. In general, only the provable sentence survives contact with a board nobody has enumerated.

Four rules on one sum, move by move #

The census is 220 rows and the mechanism is easier to see in one.

Take the sum $\{2 \mid 0\} + \{2 \mid 0\} + \{10 \mid \{9 \mid 1\}\}$. Two small identical fights and one large one with a follow-up inside it. Perfect play scores $12$ for Left.

All three components have temperature $1$, which is the first thing to notice: nothing about a temperature separates them, so the rule with the theorem is choosing on its tie-break alone. It opens in a copy of $\{2 \mid 0\}$ and scores $11$. Perfect play opens in the large component instead, because its Right option carries a follow-up worth eight points and leaving it standing is expensive in a way no temperature records.

The greedy rule opens in the same switch and scores $11$ as well, which is the usual case: with the temperatures tied, the largest immediate gain here happens to sit where the tie-break was already going.

The coldest rule opens in a small fight too, and the opponent takes the large one. It scores $5$: the seven-point difference from perfect play is one component, taken by the wrong player, because the rule declined to look at it.

Where the two serious rules part company is where the incentives break a tie the temperatures do not, and thirteen sums in the pool are like that — eleven of them won by greed and two by the rule with the theorem.

Where the ladder goes next #

The strategy anchor has two rungs to here: a rule with a guarantee, and a rule with none that outscores it. The two above take the obvious next steps and neither goes as planned.

A pool built to punish greed builds the adversarial pool this page proposes — components with a large immediate gain and a larger follow-up for the opponent — and the prediction fails. The traps miss, because the rule called greedy scores a move by the stop it leaves, and a stop already contains every follow-up inside that component. What the traps do catch had to be written afterwards: a rule that scores a move by the territory it takes, which loses sixteen points where the guaranteed rule loses five.

That is a finding about this site’s own vocabulary rather than about game theory. The word greedy was carrying more short-sightedness than the rule has, and an adversarial example has to be adversarial to a stated quantity rather than to a name.

A schedule instead of a number takes the other direction and finds the guarantee’s slack to have a size. Sort the board’s temperatures and read the guarantee one step down the list rather than at the top: the promise is 47 per cent smaller and is never breached over 1,734 sums. Two steps down it fails 120 times.

So the classical bound is not loose by an unknown margin that a finer theory might close. It is loose by exactly one entry of the sorted temperature list — which is a far more useful thing to hand a player, and which explains why the rule with the theorem and the rule without one stay within a point of each other on nearly every board.