Combinatorial Game Theory
who wins, and by how much
Concept

Hotstrat — where it appears

The rule of playing in the component with the highest temperature. It is not optimal and it comes with a guarantee — a player following it ends no more than the largest temperature below the board's mean — which is why every better rule here is measured against it.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

How far down the stack the guarantee reaches. The temperatures of a sum's components, sorted largest first, with each position asked whether playing in the hottest component can lose more than the temperature sitting there. The first two never fail; the third fails on 681 sums.

A schedule instead of a number

Playing in the hottest component loses at most the largest temperature on the board — the classical guarantee, stated against one number. Sorting the temperatures and reading the guarantee one step further down gives a promise 47 per cent smaller that is never breached over 1,734 sums. Two steps down it fails 120 times, so the schedule has exactly one step of slack in it.

temperature · Strategy Thirteen cells, thirteen scores. The rule scored in every cell of the unit interval on the designed pool, at three components.

A pool built to have an answer

The coefficient in the rule score a component by t − λa scored identically for every λ in the unit interval, because the rule reads an ordering and that pool's orderings changed at three places. A pool designed to have twelve crossings turns the interval into thirteen different rules, and all three board sizes agree on one cell: between a quarter and a third.

temperature · Coupons The cost falls as the cool part warms. Cost of hottest-first play against the temperature t of the coolest part, on one three-part board with Right to move. For a plain switch the cost is 1 − 2t and vanishes at a half; for a cool part with a follow-up it is 1 − t. Twice the coolest temperature, drawn dashed, lies below both curves for small t.

The cheapest fight is not the yardstick

Hottest-first play was found to cost at most twice the coolest temperature on the board, on pools whose coolest parts sat at a quarter or a half. Put a fight worth an eighth on the board and the rule costs seven times it. On one board the cost falls as the cool part warms, which is the opposite of a bound in the coolest. The number that holds on all 14,946 lines of seven pools is the second-largest temperature.

complexity · Approximation The second temperature, with the threat on top. Hottest-first play against the best reply on four pools whose hottest component is a threat of the form {10 | {8 | 0}}, with a switch just below it and a smaller threat below that. Over 2,254 lines the cost never exceeds the second-largest temperature on the board and meets it exactly on 97.

The price of a tie

The second-largest temperature bounded hottest-first play on 14,946 lines, and the pool that should have broken it puts a threat on top. It does not break: over 2,254 more lines the cost never passes the second temperature and meets it on 97. What the pool finds instead is where the rule goes wrong — one move into the game about as often as at its start — and why. Almost every line that meets the bound is a tie: two parts equally hot and the rule taking the first on the board. Break ties well and the lines meeting it fall from 636 to 51 on the earlier pools, and to none on any board with the threat on top.

complexity · Approximation Answering locally wins back half. Six cheap tie-breaks for hottest-first play and the searched one, scored over 17,200 lines of eleven pools by the share of board order's excess cost over the search each recovers: first on the board 0%, prefer to deny the opponent one -28%, prefer a follow-up of one's own 21%, answer where the opponent just played 50%, answer locally, else deny 32%, answer locally, else a follow-up 71%, locally, a follow-up, then an urgent denial 52%, the best, by search 100%.

Answer where the opponent played

Most of what hottest-first play costs is the choice between parts equally hot, and a search could make that choice well. Six choices a player could make without searching were scored on all 17,200 lines of eleven pools. Answering where the opponent has just played wins back half of what board order loses, and 95 per cent of it on the pools with a threat on top; preferring a part with a follow-up of one's own wins back a fifth; the two together, 71 per cent. Preferring to deny the opponent a follow-up is worse than taking the first part on the board, and denying only an urgent one takes the combination back down to 52. What is left is mostly at the opening move, where there is nothing yet to answer.

complexity · Approximation

Named alongside it

The objects these essays reach for when they reach for this one.

ApproximationDisjunctive sumTemperatureCounterexampleHeuristicSenteBoundConventionExhaustive searchFollow-upEnumerationMean value

All concepts