Combinatorial Game Theory
who wins, and by how much
Series

Approximation — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. the temperature that bounds the loss. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.

    A rule that is never right and cannot be far wrong

    Playing the hottest component is not optimal — over 440 measured lines it costs something on 17 of them. What makes it worth having is that the cost is bounded by the temperature, provably, and that the same test run with the ordering reversed breaks the bound on 54.

    part 1 · complexity
  2. The bound, and the cost, on four pools. Hottest-first play against optimal play on boards of two, three and four components drawn from four pools, 4,240 lines in all. The bound on the cost is the largest temperature on the board, which reaches 3; the worst cost measured anywhere is 1, and 100 lines meet the bound exactly.

    The bound names the hottest part and the cost does not

    Moving in the hottest component costs at most the largest temperature on the board, and that bound is attained: 100 lines of 4,240 pay exactly it. It is still the wrong quantity. Across four pools and boards of two, three and four parts the cost is nothing on 90.8% of lines and otherwise takes one of two values — half a point or one — on boards whose largest temperature runs to three, and it exceeds the coolest component on 13 lines and twice it on none.

    part 2 · complexity
  3. The more cheap fights there are, the cheaper the rule is. Hottest-first play against optimal play over 10,410 lines, grouped by how many components share the lowest temperature on the board. Lines costing more than that temperature occur only where one or two components share it; over the 3,230 lines with three or more, none does.

    The cheap fights make the rule cheaper

    A conjecture stands that playing the hottest part costs at most the coolest temperature times the number of parts sharing it — proposed on a range where that number never exceeds two. Swept to five-part boards over 10,410 lines it is false, and false the other way round: every line costing more than the coolest part has one or two parts at that temperature, and over the 3,230 lines with three or more, not one does.

    part 3 · complexity
  4. 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.

    part 4 · complexity
  5. 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.

    part 5 · complexity
  6. 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.

    part 6 · complexity

All series