Combinatorial Game Theory
who wins, and by how much
Theme

The thread: A theorem that names no move — page 3

Knowing who wins and knowing what to play are different achievements, and the subject is full of results that supply the first and refuse the second. A bound is sometimes all there is.
The value does not count the good moves. How many of a Domineering region's placements are best ones, against what the region is worth. Half the values have two regions that disagree about the count, and 52 disagree over whether there is a choice at all. Values

How many moves are worth making

A value answers who wins and by how much, and the anchor below names the quantities it discards. This is the first of them counted. Over 1,034 Domineering regions and 125 values, 63 values have two regions disagreeing about how many placements are worth making and 52 disagree over whether there is any choice at all — and the count of good moves stays near one and a half however large the region gets.

 The same temperature, and four different departures. Positions with a temperature of one whose follow-ups are worth different amounts, with the coupon at which the players leave the environment. The departure tracks the follow-up. Temperature

How big the answer is

The rung below found every early departure from a coupon stack caused by a position with a follow-up, and could not say more: its follow-ups were all of a similar size, so the class it measured was one bit. A pool graded by follow-up size answers it. With the position's own temperature held at one, the departure runs from coupon 1 to coupon 3.5 as the follow-up's temperature runs from 1 to 4 — and over the whole grid the players leave at the larger of the two temperatures.

 The margin the count needs. Every pair of Left options sorted by how many more replies one leaves the opponent than the other. At a margin of three the option leaving fewer replies is never the worse one. Values

The margin a count needs

Leaving the opponent fewest replies names only surviving options nine times in ten, which leaves the question of what a bound stated in that count would have to be weakened to. It is a margin. Over 57,879 pairs of Domineering options, the one leaving the opponent fewer replies is the worse of the two 1,052 times at a margin of one and 72 times at a margin of two — and at a margin of three, never.

 The crossover by depth. How far the ambient temperature can rise with the move still answered, by how deep the fight goes. Where the answer settles the fight it is the follow-up's temperature; deeper it is that less a half. Temperature

A subtraction, not a factor

The crossover factor was a half on fights whose answer starts another fight, measured on a pool with two three-deep positions in it. A pool built to be deep gives twenty, and the factor does not survive them: the crossover is the follow-up's temperature less a half on eighteen of the twenty, and a factor of a half agrees with that only where the temperature is one — which nearly every position in the earlier pool had.

 Four ways to count a reply. The plain count of the opponent's replies against three weightings of it, each scored on the same pairs of Domineering options. Every weighting has a larger threshold than the plain count and gets more pairs wrong. Values

The weight that blunts the count

The rung below found that counting the opponent's replies gets the direction of a comparison right once the gap reaches three, and proposed a repair: weigh each reply by whether it leaves the opponent anything. Weighing it makes the count worse. The threshold goes from three to four, the failures from 1,124 to 1,320, and all seventy-two of the pairs the repair was written for come through it unchanged.

 Two clauses, one formula. The law split by which of the two temperatures is the smaller. When the answer is colder the correction is half of it; when it is hotter the correction saturates at half the fight's own temperature. Temperature

Half of the smaller temperature

The correction to the sente crossover has been priced twice — first as a factor of a half, then as a subtraction of a half — each time on a pool whose answers were all about the same size. Over 128 fights with answers from a number up to a temperature of six, the correction is half the answer's temperature, saturating at half the fight's own. Both earlier readings are regions of that one law.

 What a value costs a player. The number of positions a winning strategy has to tell apart, against the number of values among them. The value compresses 4,269 positions into 128 numbers and leaves 3,308 choices to be remembered. Values

What a strategy has to remember

A value answers who wins and by how much, and it settles neither how many moves achieve it nor whether the best one is unique. Counted over every position reachable inside the catalogue of regions, the gap has a size: 4,269 positions carry 128 values between them, and a player who wants to win rather than to predict has to store 3,308 choices — twenty-six entries for every number the theory supplies.

 What survives being added. The packing count and the packing interval on boards of one to four regions. The count is exact on 45 per cent of single regions and 11 per cent of four-region boards; the interval contains the value 67 per cent and 74 per cent of the time. Particular games

Two errors that cancel

Replacing the packing count with an interval left a doubt that the pessimistic half would add across a board. It adds, for a one-line reason. What is worth measuring is what the reading is then worth: over boards of one to four regions the count decays from exact on 45 per cent to exact on 11, and the interval's containment does not decay at all — it rises from 67 per cent to 74, because the interval's width adds and its error does not.

 One test in front of a search. Five Cram boards solved with and without a check for a reachable pairing. A 4 × 5 board takes 17,348 node expansions without it and one with it. Impartial games

A check in front of a search

The rung below found a pairing one move away on 288 of the 767 even first-player shapes, and asked what a solver that tested for one before recursing would save on a real game. On an even Cram board it saves nearly the whole search — a 4 × 5 board takes 17,348 node expansions without the check and one with it — and the depth profile shows why that number flatters: the check settles every winning position at the opening and at the last two moves, and about one in ten in between.

 The ordering that does not order. Playing in the hottest component against playing by the larger of a component's two temperatures, over 220 boards. The proposed rule is exact far less often and its worst case is nine times as bad. Temperature

The quantity that does not order a board

The rung below found the players leaving an environment at the larger of a position's two temperatures, and proposed that a board should therefore be played in the order of that quantity. Over 220 boards of three components it plays exactly on 124 against playing-in-the-hottest's 196, loses 85 of the 97 disagreements, breaks Hotstrat's guarantee on six boards, and costs nine points on its worst one.

 Every failure is on one board. The eight Domineering boards of the mobility census with the number of failing pairs on each. Seven of them contribute none; every failure at a margin of two is on the largest board, at two depths, and sixteen positions up to symmetry. Values

The threshold was a fact about the census

Two rungs failed to account for the seventy-two pairs where a mobility count gets the direction of a comparison wrong, and the third looks at them one at a time. They are not a class of shapes. All seventy-two are on the largest board in the census, at two depths, and sixteen positions up to symmetry — and one board larger the count fails at a margin of three, which the ladder has been quoting as the point at which it never does.

 The list saturates at three. Rules added greedily, each chosen to answer the most decisions given the ones already on the list. Three rules answer 94.5 per cent, and the fourth and fifth answer not one more. Values

Three rules and a tie-break

An exhaustive table of what a Domineering strategy has to remember is 3,308 lines. Three rules applied in order answer 94.5 per cent of it — leave the opponent fewest replies, then keep the region whole, then take whichever placement comes first — and the fourth and fifth rules answer not one more. The residue is 181 decisions in which every rule scores the candidates the same and one of them is worse.

 The count is a count of odd runs. The largest packing of dominoes a player can hope for in a region, written as a formula in the region's own lines. Every run of odd length wastes one cell, so the packing is half of what is left, and the count is half the difference between the two directions' odd runs. Particular games

Half the difference in odd runs

The rung below asked what the regions the packing reading fails on have in common, and whether it is something a player could see. It is: the reading itself. The count has a closed form — half the difference between the region's odd horizontal runs and its odd vertical runs — and it is exact seven times in ten when it claims one move of advantage, on none of the largest regions where it claims two, and it exaggerates four times in five when it is wrong at all.

 Cut small unless you are behind. The complete rule for the best cut in a Maundy Cake, in three cases decided by the two sides' counts of prime factors. It is exact on every cake in a sixty by sixty grid. Particular games

Cut small unless you are behind

The rung below found the greedy rule — cut at the largest prime — wrong on 104 of 552 Maundy Cakes and asked for a description of them. On all 104 the best cut is at the smallest prime, the exact opposite. A middle divisor is never needed on any cake in a sixty by sixty grid, and which of the two extremes wins is decided by Ω alone: cut small when Ω(m) + 1 ≥ Ω(n), large otherwise, and that is exact on all 3,540.

 The rule that was supposed to lose. Five ordering rules on the same 220 boards. Playing where the temperature less the answer's is largest is exact more often than playing in the hottest component, which is what the rung below predicted it would not do. Temperature

A rule that beats the hottest

The rung below proposed the reverse of the rule that had just failed — discount a component by its answer's temperature rather than promoting it — and predicted, before the sweep, that it would not beat playing in the hottest component. It does. It plays exactly on 201 of 220 three-component boards against 196, wins two thirds of the boards where the two disagree, keeps inside a guarantee proved for the other rule, and the gap widens as the board grows.

 Sorted by how many heaps are odd. The 2,002 positions of the census grouped by how many of their heaps hold an odd number of counters. Four of the six groups are entirely lost or entirely won. Impartial games

The count of odd heaps

The rung below refused a family of two-part rules for bounded Moore's Nim and asked what the 364 losing positions have in common as a set. They have an invariant, and it is a statistic of the whole position rather than of a heap: how many heaps hold an odd number. Every all-even position is lost, at every width of move, by a restoring strategy — and the count settles every position at one heap a move and at four, and a little over half at two.

 The third temperature is not consulted. Positions grouped by their two top temperatures, with the third temperatures they hold between them. The crossover is the same for every position in a group however far apart their third temperatures are. Temperature

The two numbers at the top

The rung below found the crossover of a sente fight to be its temperature less half its answer's, and said a proof would settle the depth question with it. The depth question is settled without the proof, by construction: group the positions by their two top temperatures and the crossover is single-valued on every group, however far apart the third temperature is — and the formula survives a fourth level of fight, which the rung below never reached.

 The check fires on positions that lose. How often the pairing check accepts a position, and how often the position is a loss. On every even board in the sweep it is wrong between an eighth and a fifth of the time. Impartial games

The check that was not a check

The rung below asked for a depth-conditioned solver and named the board to measure it on. Building it found two things first. The pairing check is unsound at interior positions — on a four by five Cram board it fires on 8,613 positions and 1,026 of them are losses — and the board it named has twenty-five squares, so the check can never fire there at all. Repaired, the check is right everywhere, and the policy that pays is the root alone.

 The same coverage, an eighth of the shapes. Catalogues ordered by size against catalogues ordered by frequency, at the same coverage. The frequency order wins at every reach and by more at each one. What it costs

A catalogue that knows what it will meet

The rung below priced a catalogue of regions by its reach and found the coverage saturating, and asked what a catalogue ordered by frequency would cost instead. Eight shapes answer half the components a played Domineering board produces; a catalogue by size needs fifteen for the same, and 1,042 for what 119 chosen by frequency reach. Three quarters of a size-ordered catalogue never turns up in play at all.

 Thirteen sweeps, four thresholds. The mobility rule's failures on every board and depth the sweep can afford, with the threshold each one gives. The thresholds take four different values and no ordering of the boards produces them. Values

A threshold is a detection limit

The rung below had two points — a margin of three at fifteen squares, four at eighteen — and asked whether the mobility rule's threshold grows with the board. Eleven more sweeps say no property of a board orders the thresholds, that the same board at two depths gives two of them, and that a tenth of the sweep which produced the four reports three instead. What does move, on every board measured twice, is the depth.

 Two failures, not one. The decisions a Domineering strategy has to store, split by what the two content rules do: answer them, name a worse placement, or leave two candidates standing. Values

Seventy-two of them were not silence

The rung below said its 181 unanswered decisions were all the rules falling silent and asked whether the position's value picks the placement once the geometry cannot. Seventy-two of the 181 are the rules speaking and being wrong, which is a different failure. On the 109 that really are silence, a rule chosen per value answers more than half — and the star class the rung below singled out is settled outright by leaving the younger position.

 Four counts and an interval. One Domineering region with its run lengths in each direction and both packing counts written as sums over the runs. Particular games

One domino every three cells

The rung below gave the optimistic packing count as a formula in odd runs and asked for the other end of the interval, expecting a formula in the even ones. Parity is the wrong arithmetic: the smallest maximal packing is a sum of ⌈(len−1)/3⌉ over the runs, exact on all 1,042 shapes. That makes the whole interval readable off a drawing — and shows it can never reach the value, because regions with the same runs have different values.

 Two symmetries, the same two clauses. The half-turn pairing and the reflection pairing written side by side, with the fixed squares and self-paired dominoes each has to exclude. Impartial games

A pairing, and the pairing

The rung below repaired the half-turn check and asked whether a reflection would fire where it does not. It does — forty positions of 58,830 on the largest board — and it is sound, and it is worth one node in a thousand to a solver. It can never fire on an empty rectangle at all, which is why the ladder's whole subject is the half turn.

 Which catalogue is safe. Catalogues built from one style of play and used against another. A catalogue measured on random play over-serves a strong player and not the reverse. What it costs

The catalogue a strong player needs

A Domineering catalogue built from random play faces an objection that could overturn it: random play is not play. A player that reads the board produces the same head — eight of the ten commonest shapes — and concentrates far harder: 114 entries answer nine tenths of what it meets, against 2,018. And a catalogue measured on random play over-serves it, while the reverse fails.

All themes