Combinatorial Game Theory
who wins, and by how much
Concept

Sampling — where it appears

Measuring a population by drawing from it rather than by enumerating it, used here wherever a sweep is out of reach. A sample can find an exception and cannot prove there is none, so every share reported from one is stated with the population it was drawn from.

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

A game is colder than its catalogue. The share of hot positions in the Domineering region catalogue against the share among the components a real game produces. Fifty-three per cent against sixteen.

What a game actually produces

Fifty-three per cent of the Domineering regions of at most eight squares are hot. Of the components eleven hundred random games actually produce, sixteen per cent are — and ten per cent once single squares are counted. The figure is the same on three sizes of board, so it is a property of play rather than of the board, and it says that every temperature census this site has taken over a catalogue overstates how hot the game is by a factor of three.

temperature · Cold Three populations, three answers. How often something is worth fighting over, measured on the catalogue of shapes, on the pieces a played game produces, and on the whole board those pieces make up.

One fight makes a board a fight

The rung below found 16 per cent of the components a played game produces to be hot, against 53 per cent of the catalogue they are drawn from, and predicted that the share of hot boards would be much larger. Taking the same play-outs and tallying at the board gives 32 per cent — twice the piece figure and not ten times it, because a Domineering board carries only 1.68 pieces and the hot ones cluster on the same boards.

temperature · Cold 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.

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.

positions · Domineering What each reach answers. Catalogues of four to ten squares against the regions four sizes of board actually produce. The coverage rises from about 54 per cent to about 74 while the catalogue grows from 15 shapes to 12,871.

Where to stop building

The rung below priced a catalogue of small regions against the search it replaces and found the crossover. What it could not say is how far to build, and the coverage answers that: going from four squares of reach to ten multiplies the catalogue by 860 and lifts the share of regions it answers from 54 per cent to 74. The price of a point of coverage runs from five shapes to five thousand.

complexity · Value cost Still a count of squares. One-sided Amazons regions on two-dimensional boards, swept exhaustively. Every one is worth exactly the number of free squares in it.

A region one player owns

On a strip, a region containing only one player's amazons is worth exactly its free-square count, on all 45,057 positions of the rung below's sweep — and it predicted the exactness would fail in two dimensions, where an amazon can be short of room in one direction and not another. It does not fail. Over 2,412 two-dimensional regions there is no exception, and the reason is one clause: an amazon may shoot back at the square it has just left.

positions · Amazons 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.

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.

values · Dominance 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.

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.

complexity · Value cost A count that forgets, at six rates of forgetting. The hit rate of a component table limited to 10, 20 and 40 entries under recency, under a use count halved every 25 to 5,000 lookups, under a use count never forgotten, and against the best fixed table chosen with the whole run in view. At every size some half-life beats recency, and the longest half-lives fall back toward the rule that never forgets.

A count that forgets

A Domineering solver with room for ten component values does better evicting whatever it used least recently than evicting whatever it used least often, and the explanation offered was that a use count never forgets. Halve every count at a fixed interval and the count overtakes recency at every table size — by less than half a point, and only with the right interval. The right interval grows with the table: a quarter of a game's worth of lookups at ten entries, five games' worth at forty.

complexity · Value cost The board held fixed, and recency still wins. Each of the four board sizes played on its own for 650 games, with a component table of ten entries under recency, a use count never forgotten and the best of three half-lives, against the best fixed ten shapes chosen with the whole run in view. Counting beats recency only on the 4 × 5 board; on 5 × 5, 6 × 6 and 7 × 7 recency beats both counting and the fixed table, by the widest margin on 7 × 7.

One board, and recency still wins

A Domineering solver's table of component values did best evicting whatever it used least recently, and the explanation was that the run changed board size three times. Take the change away — play all 650 games on one board — and counting wins back its lead only on the smallest board. On 5 × 5, 6 × 6 and 7 × 7 recency still beats both counting and the best fixed table, by the most on the largest. The locality recency exploits is not between boards or between opening and endgame. It is inside a single move.

complexity · Value cost The day-four figure, twenty draws at a time. Corrected day-four comparability from twenty seeds of each of two constructions, as dots on a percentage axis, with the range of day three's four slices shaded and the single figure the earlier essay reported marked. The seeds spread over about twelve points and the two constructions agree.

Twenty draws and a second recipe

Day four's comparability was reported as 60.6 per cent against day three's 59.7, from one built sample and one calibration. Built twenty times with each of two recipes whose biases differ by six points, and calibrated against all 1,474 day-three values rather than a quarter of them, the corrected figure spreads over twelve points from seed to seed and the two recipes agree within one standard error. The floor survives; the decimal was one draw.

sums · Comparison Four positions, sampled. Three samples of three thousand loopy regions on four positions, drawn with each possible move present at a chance of one half, about a third and a quarter. For each: how many regions have both sides named by the thirty-five names two-position regions use, by those together with the thirteen invented for three positions, and how many need a new name.

Four positions, sampled

Ten names write both sides of every loopy region of two positions, and forty-eight every region of three. Four positions are over four billion graphs and cannot be counted, but they can be drawn. Three thousand regions at each of three densities: the forty-eight names cover between 95.9 and 99.5 per cent, the thirteen names invented for three positions come back at four almost all of them, and the sparsest sample meets thirty-five sides nothing earlier reproduces — a floor of eighty-three names, and a curve that grows by accretion rather than collapse.

history · Notation Half the new sides are sums. The 50 sides of four-position loopy regions that no earlier name reproduces, tested against every sum of two games from the day-two values, the stoppers and the thirteen three-position names. 23 are such sums, 15 of them using a three-position name; 27 are not.

Each size is built from the last

At three positions the sides that needed new names were sums of nothing older: no pair of stoppers, and no two-position stopper with a small game beside it, wrote any of them. At four positions the thirteen names three positions forced are available as parts, and they change the answer. Of the fifty sides the samples met that nothing earlier names, twenty-three are sums of two earlier games — fifteen of them using a three-position name — and twenty-seven are not.

history · Notation Three parts close most of the gap. The fifty sides four-position regions needed new names for, split by the smallest sum of earlier games that writes them: 23 by a sum of two, 16 only by a sum of three, and 11 by neither, with how often each group turned up in the samples.

Composition at every size

Twenty-seven of the fifty new four-position sides were written by no sum of two earlier games. Sums of three write sixteen of them — seven plain finite games born after day two, nine built on the names three positions forced — and leave eleven, met seventeen times in nine thousand regions. Run the same test one size down and the story the counts told falls apart: eight of the thirteen names three positions were thought to invent are sums of up to three older parts, two of them just two finite values. Every size composes. What each invents is a residue — five, then eleven.

history · Notation The pairs level and the order does not. Corrected day-four figures under two recipes beside the honest day-three figures, for samples of 120. The share of comparable pairs is unchanged within its error; chains of three fall, wholly confused triples rise from 12.2% to about 14.8%, and the width rises from 19.7 to 29.4 and 30.3.

The pairs stand still and the order spreads

The share of pairs of game values the order can compare falls from 77.5 per cent on day two to 60 on day three and then stops: built twenty times under two recipes and calibrated, day four sits within two standard errors of day three. That looked like a floor under the order. Measured beyond pairs it is not. Chains of three keep falling, triples with no comparable pair keep rising, and the largest set of mutually confused values in a sample of 120 grows from about 20 to about 30 — every one of forty seeds wider than day three's mean. The floor belongs to one statistic, not to the order it summarises.

sums · Comparison

Named alongside it

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

EnumerationDecompositionDomineeringHeuristicDisjunctive sumExhaustive searchValueApproximationComponentCounterexampleMemoisationRegion

All concepts