Combinatorial Game Theory
who wins, and by how much
Concept

Company — where it appears

A finite set of values that two positions are compared against, in place of every game there is. Restricting it makes equality computable and makes the answer depend on the restriction, which is the trade every result stated over a universe makes.

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

What a finite closed company is made of. The finite closed companies found by the search, counted by the properties they share. Every one of them consists of games equal to their own negatives and has a size that is a power of two, and not all of them are made of nimbers.

The company that is closed

Restricted equality licenses substitution only inside a company closed under addition, and none of the five companies this site computes in is closed — day two keeps a quarter of its own sums. Searching for companies that are closed finds seven, at one, two, four and eight members, and every member of every one of them is its own negative.

limits · Universes The second closure picks out the nimbers. The seven finite companies closed under addition, tested for closure under forming options. The four that are groups of nimbers keep every option; the three containing plus-or-minus one lose theirs.

The closure that picks the nimbers

Closure under addition lets a sum be rewritten and turned out to admit companies that are not nimbers at all. Closure under forming options lets a subposition be rewritten, and it pulls the other way: every company this site computes in has it and none has the first, and among the seven finite addition-closed companies, keeping every option is exactly being a group of nimbers — four of seven, both directions, no exception. Demand both at once and nineteen of twenty-two day-two values generate nothing finite.

limits · Universes How often one position beats another. Misère comparison inside each ruleset's own universe. A quarter to a half of ordered pairs compare, and the ruleset that is not dead-ending is in the middle of the range.

What the class does not buy

Dead-ending is the hypothesis several modern misère results are stated under, and the rung below sorted this site's games into it without running the comparison those results are about. Running it: a quarter to a half of ordered pairs compare inside a ruleset's own universe, which is a great deal — and the ruleset that is not dead-ending sits in the middle of that range. Ten comparisons are lost when a universe is enlarged, and every one is lost to a dead-ending company.

limits · Dead-ending Four solvers on one sum. The states each solver has to distinguish on a three by four board plus a three by five, with one more substitution allowed at each step. A million and a half becomes fourteen.

Half a licence is nearly all of it

The rung below priced the substitution licence a restricted universe gives a solver and asked what half of one is worth — the licence to rewrite components but not subpositions. It is worth nearly the whole saving. Rewriting components collapses a million and a half states to three thousand six hundred; rewriting subpositions collapses those to eight hundred and eighty-four, and splitting the pieces takes it to fourteen.

limits · Universes A gap that widens without bound. Both savings as the number of components grows, enumerated where possible and given by the closed forms beyond.

One half multiplies, the other adds

The rung below priced the two halves of a substitution licence on sums of two Cram boards and predicted that the first half's saving would grow with the number of components while the second's would not. It is right, and both halves have closed forms: the component licence saves s^(k−1)/k and the subposition licence k·s over a shape count that never moves.

limits · Universes One-sided, all three. The three option tests with their disagreements split by direction. None ever refuses a comparison that holds.

Wrong in one direction only

The rung below asked for the simplified comparison test the dead-ending hypothesis is supposed to license, and predicted it would agree with the quantifier on the dead-ending rulesets and not on Toads and Frogs. Written three ways and scored on 492 pairs, it agrees best on the ruleset that is not dead-ending — and never once refuses a comparison that holds, which makes it a sound filter and not a test.

limits · Dead-ending

Named alongside it

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

EnumerationEqualitySubstitutionUniverseCounterexampleDisjunctive sumClosureComparisonCramDead-endingDecompositionGroup

All concepts