The price of a tie

Hottest-first is the simplest rule a player of a sum can follow: find the component with the largest temperature, and move in it. A rule with a guarantee proves that it never costs more than the largest temperature on the board, and the cheapest fight is not the yardstick found a much tighter number in the data. Over 14,946 lines of seven pools, with the opponent replying as well as it can, the cost never exceeded the second-largest temperature — and it met that number exactly often enough that nothing smaller could replace it.

That essay also said which board would test the claim, because its worst line had a particular shape. The line that cost most had a plain switch on top and a threat second: the rule took the switch, and the threat, left standing, was worth more to the opponent than the switch had been to the mover. The reverse shape had not been tried. Put the threat on top, a switch just below it and a smaller threat below that, and the rule takes the right part first and may take the wrong part second. A cost past the second temperature would then have to come from an error made one move into the game, which is where a bound read off the board’s opening temperatures has least to say.

Four pools with the threat on top #

The pools are built from one shape scaled. $\{10 \mid \{8 \mid 0\}\}$ is a threat: Left’s move takes ten, and Right’s move makes $\{8 \mid 0\}$, a switch at temperature four, twice as hot as the threat itself at two. So the threat is the hottest part while it stands, and the move into it hands the opponent something hotter still.

The four pools vary the gaps. The first sets a switch at fifteen eighths directly under the threat at two, with $\{5 \mid \{4 \mid 0\}\}$ below and two fights at an eighth at the bottom. The second steps down by switches at seven quarters and three quarters. The third stacks three threats, each twice the size of the next, with switches between. The fourth puts the threats a hair apart, at two and one with switches at fifteen eighths and seven eighths. Every board is played twice, once with each player moving first, and the rule-follower’s opponent replies with the move that minimises what the rule-follower goes on to get — the convention under which a cost cannot be negative.

The second-largest temperature survives every line. Of 2,254 lines, 647 cost the rule-follower something, and on none does the cost exceed the second temperature on its board. It is met exactly on 97. The worst costs are two, two, four and seven quarters; the first three equal the second temperature of their own boards, and the fourth falls a quarter short of its board’s two. Twice the coolest, which the cheap fights make the rule cheaper had proposed and the eighths pools had already broken, fails again on 231 lines.

So the bound passes the test it was waiting for. That is not the interesting part of the sweep; the interesting part is what the replayed lines show about why.

The error one move in was never rare #

The hypothesis the pool was built on was a hypothesis about timing: with the threat on top the rule starts correctly, so any damage would be done later. The sweep can check that directly, because every costly line can be replayed move by move with the minimax value of the position computed before and after each of the rule-follower’s moves.

An error is a move that lowers the minimax value of the position; the opponent’s replies can only give value back, so the errors along a line add up to at least its cost. On the four threat pools the first error comes at the rule-follower’s opening move on 336 lines and later on 311 — 179 at the second turn, 101 at the third and 31 at the fourth. The pool with the threats a hair apart errs early two times in three; the pool with a switch just under the threat errs late more often than not.

The comparison row is the one that corrects the hypothesis. On the seven earlier pools, the ones whose worst lines suggested that errors come at the start, the first error is later than the opening move on 1,484 of 2,212 costly lines, two in three. The witness that motivated the new pools was an opening error, and it was the exception in its own data. A bound read off the opening temperatures was never protected by errors being early. It survives late errors on seven pools and on four more.

That leaves the question the timing was supposed to answer: what, at a later turn, goes wrong?

A switch the threat makes, as hot as the threat #

The largest cost in the sweep is on the third pool, and it is a board of three parts.

Two copies of $\{20 \mid \{16 \mid 0\}\}$ stand beside one $\{10 \mid \{8 \mid 0\}\}$, and Left moves first. The rule takes a big threat — correctly — and Right replies by playing in the small one, making $\{8 \mid 0\}$. Now the board holds a threat at temperature four and a switch at temperature four. The rule says to move in the hottest part, and there are two. It takes the one that comes first on the board, which is the remaining threat, for twenty. Right then takes the switch for nought, and the line ends at forty.

Taking the switch instead is worth eight at once and leaves Right a threat that Left can answer: Right’s move in it makes $\{16 \mid 0\}$ and Left takes sixteen. Optimal play finishes at forty-four. The difference is four, the second-largest temperature on the board, and all of it is the tie. The rule’s temperatures were right at every turn; what it did not know was which of two equally hot parts to take, and a threat’s follow-up is exactly the kind of part that ties with the switch its opponent has just made.

That is a mechanism, not an accident of one pool. A threat hands the opponent a hotter switch when the opponent plays in it — that is what makes it a threat — and the opponent of a threat-holder plays in the other threats on the board to make switches of their own. On boards built of scaled threats the switches so made come out at exactly the temperatures of the threats still standing, and the rule meets a tie.

The same mistake one fight down #

The line that meets the bound on a board whose hottest part stands alone is smaller, and it is the same mistake.

On $\{10 \mid \{8 \mid 0\}\} + \pm\frac18 + \{\frac12 \mid \{\frac38 \mid \frac18\}\}$ with Right to move, the threat is hottest at two and the other two parts sit at an eighth. The rule plays the threat, Left answers the switch it creates, and Right is left choosing between a plain switch at an eighth and a fight at an eighth with a follow-up. Both have the same temperature. The rule takes the plain switch because it comes first, Left takes the fight for a half, and the line ends at 8⅜. Optimal play takes the fight first, turning it into $\{\frac38 \mid \frac18\}$, and finishes at 8¼.

The cost is an eighth — the second-largest temperature on the board, exactly — and it is a tie again. The threat on top was handled perfectly. What was not handled was two cool parts at the same temperature with different shapes, which is the choice a rule that beats the hottest addresses by looking past temperature at what each part leaves behind.

Separating the rule from its tie-break #

Two witnesses make a pattern and not a count. The count is a second sweep of every line, with one change to the rule.

The change is to the one choice the rule leaves open. When several parts share the hottest temperature, the rule-follower takes whichever of them is best — the one minimax would choose — instead of the first on the board; every other move is the rule’s as before. That is not a rule anybody could follow without searching, and it is not proposed as one. It is a way of dividing the cost into the part that comes from choosing a temperature and the part that comes from choosing among parts the temperature cannot tell apart.

The tie-break turns out to be most of the cost. On the seven earlier pools the costly lines fall from 2,212 to 465, and the lines that cost exactly the second temperature fall from 636 to 51. On the pool built of parts at a half, three eighths and a quarter, every one of its 116 costly lines was a tie, and with ties broken well the rule is exact on all 1,512 lines of it. That pool was the one where the cheapest fight is not the yardstick found the bound met on every costly line, and now the reason is visible. Its seven parts sit at only three temperatures, a half, three eighths and a quarter, and four of them share the top one, so the rule meets a tie at nearly every turn — and every loss it makes on that pool is made at one. On the threat pools the costly lines fall less, from 647 to 501, but the lines meeting the bound fall from 97 to 13.

So the number that bounds the rule’s cost has a reading it did not have before. A tie between two parts at the hottest temperature is a moment at which the board’s largest and second-largest temperatures are the same number, and what the wrong choice gives up is what the right part was worth over it. Over all eleven pools the rule makes 3,290 value-losing moves, 2,266 of them tie-breaks, and not one tie-break gives up more than the temperature the tied parts share; the other 1,024 each stay within the second temperature at the moment they are made. That is an observation, not a lemma, but it turns most of the lines meeting the bound into lines meeting it at a moment when the second temperature and the first coincide.

The bound, met with no tie #

Thirteen lines on the threat pools still meet the bound with ties broken well, and they say which part of the conjecture is not about ties at all.

The board is $\pm\frac{15}{8} + \{6 \mid \{5 \mid 0\}\} + \{6 \mid \{5 \mid 0\}\}$ with Right to move. The switch is alone at the top, so there is nothing to break; the rule takes it. Left then takes one threat for six, and Right plays the other, which Left must answer for five. Optimal play goes into a threat first: Left must answer the $\{5 \mid 0\}$ it makes, which returns the move to Right, who does the same with the second threat and only then takes the switch. Each threat is played in sente — the answer is forced and the move comes back — and together they are worth one point more to Right than the switch was. The cost is one, the second temperature exactly, and it belongs to the rule itself.

That is the witness of the earlier essay again, a switch on top and a threat second, found this time on pools built for the opposite shape because every pool contains switches as well as threats. And all thirteen are of that shape. On the 1,126 lines whose hottest part is the pool’s threat, not one meets the second temperature once ties are broken well, and the worst of them costs 93 per cent of it. With the threat on top the rule’s own error, as distinct from its tie-break’s, stays strictly under the bound on every board here.

Sente is a fact about the rest of the board is the account of why a threat can be worth playing before a hotter switch: whether a move keeps the initiative depends on what else is on the board to take, and temperature is a property of one component alone. The thirteen lines are that fact priced, and they price it at the second temperature exactly.

What four pools cannot show #

The bound is still a conjecture. It has now held on 17,200 lines across eleven pools, four of them built to break it, and nothing on this page proves it. What has changed is the case a proof would have to handle. With ties broken well, the only lines that reach it are a switch above a threat, and a proof that begins with the tie-break separated from the rule has one shape to explain rather than two.

Every component is a switch or a threat with one follow-up. A threat whose follow-up is itself a threat, or a fight whose follow-up branches, would give the opponent a sequence of forcing moves rather than one, and nothing here says what such a sequence costs a rule that sees only the current temperatures. Five parts is also not many.

And “ties broken well” is an instrument, not a rule. Choosing among tied parts by minimax needs the search the rule exists to avoid. The measurement says how much of the cost a tie-break could recover at best; a tie-break that reads the board without searching — preferring the part with a follow-up, or the part the opponent has just moved in — would recover less, and how much less is not measured.

The convention the lines are played under #

Normal play, and the cost is in points. A board is played to the end twice, once with each player moving first. Optimal play is minimax over the whole sum. The rule is hottest-first as it is usually stated: move in a component of largest temperature and, inside it, choose the option of best mean, with ties between components broken by position on the board. The rule-follower’s opponent chooses every reply by minimax against a mover who follows the rule, which is the convention under which a cost is never negative. The cost is optimal play’s score less the rule’s, signed so that a positive number means the rule did worse.

The four earlier pools, played with both sides following the rule, still reproduce the counts the cheap fights make the rule cheaper reported under that convention — 10,410 lines, 761 costing something — which is the check that the rule here is the rule the earlier measurements used.

The surprise: hottest-first was never one rule #

The bound was proposed as a property of hottest-first play, and every account of hottest-first states it in one clause: move in the hottest component. What this sweep shows is that the clause does not name a move on a large share of the boards where the rule goes wrong, and the choice it leaves open is where most of the cost lives.

That is worth being plain about, because it inverts the reading of the earlier tables. A pool on which most parts share the top temperature looked like the best evidence for the second-temperature bound, since every costly line on it met the bound exactly. It is in fact a pool on which every loss hottest-first makes is a tie-break, so what it measured was the cost of taking equally hot parts in board order. The bound was being met, line after line, by the part of the rule nobody had specified.

The largest single cost in the whole sweep, four points on a board of three parts, is the same thing in its purest form. Every temperature on that line was read correctly, the rule was followed exactly, and the whole of the loss was a choice between a threat and the switch the opponent’s threat had just made — two parts the rule treats as the same because it looks at one number each.

Still open: a tie-break that reads the board #

The instrument above breaks ties by searching, which says how much there is to recover and not how to recover it. The next measurement is a tie-break a player could actually use, scored against it. Two are natural. Prefer the part the opponent has just moved in, which is the reflex of answering locally, and which would have taken the switch on the four-point line. And prefer the part with a follow-up, which would have taken the fight on the eighth-point line and which a rule that beats the hottest already uses in a different form. If either recovers most of the gap between board order and the search, hottest-first has a complete statement that is still cheap, and its cost on these boards is the thirteen lines of a switch above threats. If neither does, the tie-break is a search in disguise, and a schedule instead of a number is the other place in these essays where a rule’s cheapness turned out to depend on a decision it did not state.