Equality — where it appears
Named by 42 essays across 6 fields — each of them below, with the objects they name alongside it.
Comparing positions
One position is worth at least another when the second player wins their difference. That is the only definition there is, it is a computation rather than a judgement, and it produces an order in which some pairs are simply not comparable.
Canonical form
Two positions are worth the same when neither player can tell them apart inside any larger game. Deciding that could be an infinite search. Instead there is a normal form — delete what nobody would play, bypass what backfires — and equality becomes a comparison of two small trees.
What counts as the same position, and what that is worth
Folding a 4×4 Domineering board by its symmetries takes the table from 5,700 entries to 1,522 — a saving of 3.75, against a ceiling of exactly 4. An orbit cannot be larger than the group acting on it, so this is the one saving in the subject that can never change an exponent.
Comparing two positions means playing a third
There is no way to look at two games and see which is better. The question "is G at least H?" is answered by building G − H and asking who wins it — so the most basic operation in the theory is a decision problem, and every canonical form is built out of them.
Two hundred and fifty-six ways to write twenty-two things
Every game whose options come from the four born on day one — there are 256 of them, and between them they carry 22 values. The reduction that collapses one to the other has choices in it at every step, and uniqueness is the claim that none of the choices matters.
Independence is a claim
Splitting a position into parts and adding the values is the whole method of this subject, and the splitting step is a claim about the position rather than a fact about the drawing. Where it is false the two answers differ — and the failures that matter are the ones that keep the same winner and change the value, because nothing reports those.
Confused is not the same as unknown
Two positions can be neither greater, nor smaller, nor equal. That is a fourth relation with its own symbol, it is a fact about the pair rather than a limit of the method, and it is what makes a game worth playing — a position is a first-player win exactly when it is confused with zero.
The other sum, the one that nests
A move in one part wipes the other out entirely. That is the ordinal sum, it is what a Hackenbush stalk actually is — 1 : (−1) is a half, and 1 : (−1) : 1 is three quarters — and it is not an operation on values at all: three positions all worth zero give three different answers under it.
Equal in every company
Two games are equal when no third game can tell them apart — a quantifier over every position there is, discharged by one finite test. A search over 184 contexts separates all 5,790 unequal pairs it is handed and still calls two different games the same, which is exactly why G − H = 0 is a theorem and an exhaustive search is not.
The cost is in the closure, not in the positions
Under normal play, Dawson's chess needs four classes for every heap up to twelve, because its Grundy values stay at three or below there. Under misère play the same game needs six, then twelve, and the number rises with the universe rather than with the position — which is a different kind of expense entirely.
The values that are their own negatives
Every game satisfies G + (−G) = 0, so a game equal to its own negative satisfies G + G = 0 — it has order two in a group whose elements otherwise have infinite order. The nimbers do. So does ±1, on sight. Over the 1,474 values born by day three there are 30 of them and only four are nimbers, every one of the 900 sums of two is another, and the equality test and a symmetry of the written form agree 1,474 times out of 1,474.
A pass is not a move
Put a single pass token on a Nim board and one clause decides everything. If it may be taken at any time — including as the move that ends the game — the value of the whole is the nim-sum with a one added, in all 120 positions swept: the pass is a heap of one. Forbid it as the final move and the value stops being a function of the nim-sum at all, and 3 and 1 + 2 come apart.
How rare it is to be bigger
Values are partially ordered, and 'partially' does most of the work. On day two, 179 of 231 pairs can be compared and 13 of the 22 values can be compared with zero. One day later the shares are 60% and 29%, and the largest set of mutually incomparable values found rises from four to at least twenty-three. Comparison is the exception; confusion is what values normally do to one another.
An option nobody would take
Every reduction of a form deletes. The gift horse principle adds: a move may be handed to a player for nothing, provided it is one they would never choose. Over all 484 additions to the values born by day two, 283 leave the value exactly where it was and the 201 that move it are precisely the ones the condition forbids — with the boundary at *not better*, which is a weaker demand than *worse*.
Equal in this company
Equality quantifies over every game there is, and the quantifier can be made smaller. Restricted to a company of nine numbers, the twenty-two values born by day two collapse to seventeen; restricted to four games — nought, one, minus one and star — they stay twenty-two, and no three of the four will do. The company that decides equality is tiny, and it has to contain a star.
The simplest game above both
Values sit in a partial order, and a partial order is entitled to be ragged: two things with no least thing above them. The 22 values born by day two are not ragged at all. Every one of their 253 pairs has a least upper bound and a greatest lower bound among the same 22, and the order is distributive on all 10,648 triples — so it is a lattice, and the join of zero and star is one half.
What can be struck out
From G + X = H + X it follows that G = H, in one line, by adding −X to both sides. It is the shortest theorem here and the most used: it is what makes comparing two boards region by region legitimate. Over 10,648 triples the hypothesis fires 484 times and the conclusion holds 484 times — and the licence expires in three separate directions, each of which loses the same axiom in a different way.
The reduction that puts options back
Canonical form is presented as simplification, and half of it is. Deleting a dominated option takes one away. Bypassing a reversible one substitutes the answer's whole option list, so it can leave the form wider than it started — and 60 of 32,428 forms end up with a canonical form wider than they are.
How hot a background has to be
The reduced canonical form throws away infinitesimals, and the rung below asked for a bound: how hot must the rest of the board be for the discarded part not to matter? There is no such bound. Safety is not monotone in the background's temperature — an eighth is safe, a quarter is not, two is safe again — and the quantity that does decide it is not a temperature but a stop.
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.
What the colon respects
The ordinal sum reads the form of its base rather than its value, which is why the colon principle is stated for positions and not for values. Built over 9,604 forms it turns out to read the value on 636 of the 640 values that have more than one form, and the four it can tell apart are zero, one, minus one and star — the values born by day one, and no others.
How many moves are worth making
A value answers who wins and by how much, and the anchor below names the quantities it discards. This is the first of them counted. Over 1,034 Domineering regions and 125 values, 63 values have two regions disagreeing about how many placements are worth making and 52 disagree over whether there is any choice at all — and the count of good moves stays near one and a half however large the region gets.
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.
No fifth value
The colon reads a form rather than a value, and the rung below found the forms of a value disagreeing at exactly four of them — the values born by day one. It could only check forms whose options came from day two. Built one day deeper, by adding day-three gift horses to day-three values, eighteen thousand forms give no disagreement at all, while the same treatment still splits nought four ways. The class is about the width of the base's form and not the depth of its options.
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.
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.
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.
The licence that weighs nothing
The third substitution licence is constant in the number of components, exactly as predicted, and it saves under two times where the first saves seventy-six million. Priced by its table instead of by its saving it is the only one of the three whose cost does not run away — which reverses the order three rungs of this anchor have put them in.
The price of asking what the parts are
The third licence lets a solver look up a region rather than a position, and the rung below priced it by the entries it stores. Priced by the work it costs, it saves between a third and two thirds of the expansions and pays for them with a flood fill at every node — six times the total. A square would have to be ten times cheaper than a table probe before it broke even.
The proof needs both reductions
The gift-horse theorem was to be proved by showing the added option dominated. It is, on 97.8 per cent — and the other 232 are reversible instead, with nothing left over. The case the proposal missed is almost entirely one follower: none under a positive number, 190 under a negative one.
A floor, and not a decline
Comparability fell eighteen points from day two to day three and the next day cannot be enumerated. It can be built — and the construction's bias measured one day lower, where the truth is known. Corrected, day four comes to 60.6 per cent against day three's 59.7: the fall was a one-day event.
Three groups, and three yields
The conjecture was that each ruleset's yield tends to the reciprocal of its symmetry group's order. Three rulesets have a trivial group and predicted yields of one; they measure 1.000, 0.531 and 0.204. And every colliding value in Push and Shove — all 175 of them — has two rows no symmetry relates.
A reduction that reads a graph
The two reductions are defined as deletions from an option list, and the shared form has no option lists — a node is reached from several parents at once. Both restate as rewritings at a node, the rewriting is confluent, and its fixed point is the canonical form. What does not carry over is the sharing: four fifths of the shared nodes need a different answer under different parents.
Twenty-six other values
The mex rule accounts for sixty-six of the ninety-six antichains and is silent on the other thirty. Every one of those thirty is worth a self-negative value born by day three — and the same mex, run over that family instead of over the nimbers, is exact on all ninety-six. The nimber rule is this one cut short after its fourth member.
A stopper and how to find one
The class a value theory for loopy games would need is the ones with no infinite alternating run, and the qualifier does the work: seventy-nine of the two hundred and fifty-six two-node loopy games qualify and seventy-two of them have a cycle. Every one has a decided outcome, and under eight tests the seventy-nine collapse to six.
What it costs to notice a repetition
Folding a 4 × 4 Domineering board by its symmetries takes the table from 5,700 entries to 1,522. It also spends 559,424 square-mappings to work out where each entry goes — seventeen and a half times the entire cost of not folding. The saving has a ceiling of four and the price has no ceiling at all, and knowing which currency each is paid in is the difference between an optimisation and a habit.
Nothing to subtract with
Comparison is defined by contexts and computed by subtraction, and the equivalence between the two is a theorem about groups. A scoring game is not one — sixty-six of eighty-one coin rows do not cancel against their own negatives — and the difference test then fails on a row compared with itself, which every context accepts and nothing certifies.
What two numbers cannot tell apart
A thermograph summarises a position in a mean and a temperature — nine characters against the brace form's twenty-two, and readable in a way the expression is not. It is also not exact: 1,454 of the 1,474 games born by day three share a pair with some other game, 291 of them share one pair, and adding a star to two of those gives different winners.
What a component would have to carry
For a held pass to be decided by a summary of each component, the summary must separate every pair of components some company tells apart. The Grundy value does not — Nim 1 and Kayles 8 are equal games that a held pass separates beside a single Nim heap of two. Nor does the Grundy value with the component's own held-pass value: Kayles 3 and Kayles 6 agree on both and are split by a company of two Nim heaps. Over twenty-four components, fifteen classes against fourteen pairs, and the gap widens as the pool grows.
The follower does the reversing
The gift-horse theorem for the ordinal sum needs two cases, and the second — the added option is reversible — was counted and not described. Recorded move by move, the reversing answer is always Right's move inside the follower: on all 410 escapes under five followers, and on every one of the 2,628 gift horses under every follower that gives Right a move at all. The case split is by follower, not by horse.
A cancelling pair is a zero
Two cancelling coin rows side by side cancel against their two negatives — all 190 pairs from rows of two, four and five coins, the odd row that cancels without pairing off included. And a cancelling row beside its negative is invisible next to any other row: in 741 tests against every row of one to three coins, neither score of the context moves. A non-cancelling pair moves a score in 452 of 780. Scoring games have no inverses in general; this class has them, and they behave as inverses must.
Two heaps of testing are enough
A misère quotient is computed by testing positions against positions, and the universe used to find twelve classes of Dawson's chess was every position of up to four heaps tested against every other — 511,225 outcomes. Varied one size at a time, the count stops growing at tests of two heaps and positions of three: 12,100 outcomes find the same twelve classes. The narrower universe the earlier essay drew did not merge anything; it held fewer positions. And the corner that is enough moves: for Kayles at heap twelve, two-heap tests miss a class.
Named alongside it
The objects these essays reach for when they reach for this one.
Canonical formExhaustive searchEnumerationComparisonDisjunctive sumSubstitutionStar (∗)CounterexampleOutcome classNegationNormal playGroup