Combinatorial Game Theory
who wins, and by how much
Concept

Packing — where it appears

How many dominoes fit into a region, counted either at best or at worst. The gap between the two bounds the region's value, which is why a question about a game turns into a question about fitting shapes together.

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

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.

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.

positions · Domineering Same runs, different values. Three groups of Domineering regions sharing a run-length multiset, with the value of each member.

Where the runs meet

A Domineering region's value interval is a function of its run lengths and its value is not — twenty-one groups of shapes share a multiset and disagree. The crossing count separates none of them, and neither do ten other local statistics, fifteen sets of which agree on everything and differ in value. What separates nineteen of the twenty-one is where along its runs each crossing sits.

positions · Domineering One size further. The hottest Domineering region of each size, one size beyond what the rung below could reach.

The ceiling was a plateau

Three halves of a move looked like a ceiling on a Domineering region's temperature: it held at eight squares, at nine and at ten, and the rise that had been a quarter every two sizes stopped. At eleven squares four regions reach seven quarters — and they contain the hottest eight-square shapes and are hotter than them, so the extra material is not cold.

temperature · Cold

Named alongside it

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

ApproximationCounterexampleDecompositionDomineeringEnumerationInvariantValueNumberRegionSymmetryBoundHeuristic

All concepts