Combinatorial Game Theory
who wins, and by how much
Concept

Incomparable — where it appears

Two positions where neither is at least as good as the other, written with a fourth symbol beside less, greater and equal. It is the ordinary case rather than the exception, and it is why comparing games is a search over sums rather than a look at two numbers.

Named by 4 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 One board, all the way down. The mobility rule's failure rate on a three by five board at every depth, with the threshold each depth gives.

A heuristic that becomes a theorem

The mobility rule's failure rate had been measured at two depths on each of five boards and found to fall. Swept at every depth it does not merely fall — it accelerates, and it reaches exactly nought before the endgame. From four to eight empty squares onwards the rule has no exceptions at all, which turns a rule of thumb into a guarantee for the last few moves.

values · Dominance Four moves, three arguments. Every first move in the sum, with what answers it and how many cases of each the census holds.

The case that was supposed to be hard

The mex rule for the mirror construction was to be proved by induction, and the step flagged as needing care was the one where an option is incomparable with the nimber. There is no induction: the argument is four lines, and incomparability is what makes two thirds of the cases go through — because a fuzzy sum is a first-player win and the first player is the opponent.

sums · Negation The test, scored. The recognition test run on every deletion the second reduction makes, against what actually happens.

A side about to lose its move

A fifth of the second reduction's work removes the last option a player had on a side, and no rule on the ladder had looked at one — because a deletion with no survivor has no pair in it. The recognisable object is not which option goes but whether the side is one an option can go from, and two comparisons on the parts decide it on all 525.

sums · Reduced form

Named alongside it

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

Dominated optionPartial orderCanonical formEnumerationCounterexampleDisjunctive sumSimplificationValueAntichainApproximationChainComparison

All concepts