Combinatorial Game Theory
who wins, and by how much
Concept

Confused — where it appears

The relation between two positions when neither is at least as good as the other, so that whoever moves first in their difference wins. It is a computed verdict rather than an absence of one, and it is the fourth relation a total order has no room for.

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

One option list, as the order it is. The four options above, with an arrow from each option to every option it is at least as good as. Deleting keeps the one nothing points at and removes the rest, so the reduction takes three of them — a number read off the shape and not off the values.

How much a list of options can lose

Deleting a dominated option is the reduction with no surprises, and how many options it takes is decided by the shape of the order rather than by the values in it: the survivors are the maximal elements, and the count is the length of the list less the number of them. The essay separating the two reductions closed by predicting that the longest chain would give the number. It is a lower bound, exact on 3,859 of the 7,315 four-option lists and wrong on the rest.

values · Dominance The numbers each position is confused with. Each row is a position. The bar runs from its right stop to its left stop; the filled part is the set of numbers the position is genuinely confused with, computed one comparison at a time. The two coincide except at the ends, and a position whose stops meet is confused with nothing at all even when it is not a number.

The numbers it is confused with

A position is confused with a number when neither is at least as good as the other, and the set of such numbers is an interval. It is exactly the open interval between the two stops: over 36,850 comparisons the rule is wrong nowhere it speaks, and the 2,596 comparisons it declines are precisely the ones at an endpoint, where the position and the number differ by an infinitesimal.

values · Stops What an approximation is worth. Every pair of Clobber rows up to six squares, judged twice: by their up-brackets and by the comparison itself. The bracket is never wrong where it speaks, and most of what it declines to answer has no answer.

When the bracket decides

A Clobber row's value is an all-small game nobody can hold in their head, so the practical answer is the up-bracket: a pair of integers between which its atomic weight must lie. As an approximation it is worth exactly what it settles — 1,585 of 7,875 pairs of rows are ordered by it, every one of those orders is right, and of the 6,290 it declines, 4,222 have no answer either.

positions · Clobber Which end of the interval is open. Every value born by day 3 compared with each of its own two stops — 2,948 comparisons, each one a search over the difference. The two rows are mirror images because the day is closed under negation, and the small number in each row is the exception class: the 352 values whose two stops coincide, for which the left stop is the right stop and the law has nothing to bite on.

Which end of the interval is open

The confusion interval is open at both ends, and the two ends are not the same kind of open. At its own left stop a position can be below the number, confused with it or equal to it, and — over 2,948 comparisons — above it exactly thirty-three times, every one of them a value whose two stops are the same number and whose left end is therefore also its right one.

values · Stops The identity that would join the order to the addition. Every pair of the twenty-two values born by day two, asked whether the join plus the meet equals the sum. It holds on all 201 comparable pairs, where the join is the larger and the meet the smaller and it cannot do otherwise, and on none of the 52 incomparable ones.

Where the order and the sum disagree

Day two is a lattice, and day two is a group, and it is not a lattice-ordered group. The one identity that would join the two structures — the join plus the meet equals the pair — holds on exactly the 201 pairs where it cannot fail and on none of the other 52, and the errors split thirteen high, thirteen low and twenty-six confused.

values · Lattice Fifty-two errors, put to four instruments. The fifty-two discrepancies the lattice identity leaves on day two, counted by what distinguishes them. As values no two are the same; as pairs of stops there are seven; as means three and as temperatures three. Not one of them is a number, and only three are values born by day two.

Fifty-two errors and seven sizes

Day two is a lattice and a group and not a lattice-ordered group, and the fifty-two incomparable pairs it fails on leave fifty-two different error terms. Measured rather than listed, the fifty-two collapse: seven pairs of stops, three means, three temperatures, and a rule that predicts the temperature from the pair on forty-four of them.

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

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.

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

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.

values · Dominance The order one day out. Whether the values born by day three still form a lattice. Twice as many pairs are incomparable as at day two, and every incomparable pair still has a least upper bound and a greatest lower bound — so the order becomes more tangled without becoming ragged.

One of four questions

Three rungs of this ladder rest on sweeps of day two — 22 values, 253 pairs. Day three is 1,474 values and over a million pairs, and only one of the four questions can be asked of it. The order can: twice as many pairs are incomparable and every one of 1,606 sampled still has a least upper bound and a greatest lower bound, none of them a value day two already had. The other three compare sums of day-three values, which are born on day six, and sixty of those exhausted an eight-gigabyte heap.

values · Lattice

Named alongside it

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

ComparisonCanonical formPartial orderCounterexampleInfinitesimalStar (∗)Day twoEnumerationExhaustive searchValueApproximationBound

All concepts