Combinatorial Game Theory
who wins, and by how much
Theme

The thread: The parts do not decide the whole

Outcomes do not add. Neither do temperatures, atomic weights, misère outcomes or the value of an auction. Which quantities survive being added is the question every method here turns on.
Knowing who wins is not enough. Three pairs of positions, every one of which is in outcome class N on its own. Their sums are not all the same, and not all in the same outcome class — so the outcome of a sum cannot be worked out from the outcomes of its parts, and that is why the theory needs values. Sums and comparison

Outcomes do not add

Knowing who wins each part of a position tells almost nothing about who wins the whole. Counted over every sum of two values born by day two, six of the outcome table's ten entries are settled and four are not — and every settled one is settled by the order rather than by anything about outcomes. Two first-player wins reach all four classes between them.

 Which part to move in. A sum, and every move one player has in it. Each row is a component, the option taken in it, and what the whole position becomes. The values of the parts say who wins; they do not say where to play, and the winning move here is in the component worth the least. Sums and comparison

Which part to move in

The value of a sum is the sum of the values. The move in a sum is not the move in any part, and there is no rule that reads it off the values — in the smallest interesting example, the only winning move is in the component worth nothing.

 {2 | 0} + {2 | 0} — where the temperature goes. Three thermographs on one frame: two positions and their sum. The mean of the sum is the sum of the means, every time. The temperature is not: it is bounded by the hottest of the parts and is often far below it, so the number that says how much is at stake in a whole board cannot be got by adding up the parts. Temperature

Two hot fights that add to a cold number

The mean of a sum is the sum of the means, every time. The temperature is not — it is bounded by the hottest part and is often far below it. Two positions each worth fighting over can add to a plain number that neither player wants to touch.

 The mirror strategy, and the ending that punishes it. A position beside its negative and the sum of the two, with the outcome under both endings. Under normal play the sum is worth zero every time, because the second player answers every move with its mirror image. Under misère the same answers are available and the same player runs out last, so every one of these sums is a first-player win — there is no zero, and no subtraction. Where it stops

Misère play has no negatives

Put a position beside its own mirror image and answer every move with the mirror move. Under normal play the answerer wins and the sum is worth zero. Under misère the answerer still has every reply and loses because of it — so there is no zero, no subtraction, and no comparison, which is why the misère theory had to be rebuilt rather than adjusted.

 Three partizan positions against every nimber, and not one match. Sprague and Grundy give every impartial position a single number that is complete: two positions with the same value are interchangeable everywhere. The three positions here are partizan — the two players have different moves — and each is compared against every nimber up to eight. Nothing is equal to anything. The magenta cells are worse than inequality: a position confused with a nimber is not above it or below it either, so no ordering could rescue the substitution. Sums and comparison

Where the impartial theory stops

Sprague–Grundy gives every impartial position one number, and the number is complete. The moment the two players have different moves no number works at all — not a harder one to compute, none — and three positions here are compared against every nimber to show it.

 A boundary drawn, and a boundary there. One Domineering board split two ways. Above, a line imagined down the middle: the two halves are evaluated separately and their sum is not the value of the board, because every horizontal domino that would have crossed the line has been thrown away. Below, the same column blocked out: the halves are then genuinely independent and the sum is exact. Every value is computed from its own board. Sums and comparison

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.

 What the two outcome classes of the parts settle. For each pair of outcome classes, the set of outcomes the sums actually took. A cell with one letter is a pair of classes that decided the answer; a shaded cell with several is a pair that did not. Both conventions have ambiguous cells — the difference is that normal play repairs them with values and misère play has nothing to repair them with. Where it stops

Two misère outcomes are not enough

Knowing who wins each part does not say who wins the sum. Over 676 sums built from a pool of twenty-six positions, nine of the sixteen pairs of outcome classes settle the answer under normal play and not one of the sixteen settles it under misère — and the nine that work are theorems about a value being zero, which is exactly the thing misère play does not have.

 Top Entails, one heap at a time. Each heap with the outcome of playing it alone, the Grundy value an ordinary solver would give it, and the moves that win from it. Taking the top coin of a heap forces the opponent to answer in that heap, which is a kind of move no other game on this site has. Where it stops

A move that must be answered

Every argument on this site about sums assumes the parts are independent: a move in one leaves the others alone, and the reply may go anywhere. Top Entails denies it — take the top coin of a heap and the opponent must answer in that heap. The nim-sum then misreads 9 of 36 two-heap positions, and two heaps of two coins are a first-player win, which no impartial game the theory covers can be.

 What the outcome of a loopy sum can be. One row and one column per loopy outcome class, and each cell lists every outcome a sum of two such positions was found to have. Most cells hold several. The cell where both parts are drawn holds one. Where it stops

The one outcome that adds

Finite outcomes do not add: two first-player wins can sum to anything. Loopy play has seven outcome classes instead of four and adds even less — of the 28 cells in the table, eleven hold several answers. Two do not, and they are the two worth having: a second-player win added to anything leaves the outcome alone, and a draw added to a draw is a draw. A draw added to anything else is not.

 The bracket of a sum, against the sum of the brackets. Two all-small positions, the interval of multiples of ↑ each lies between, those two intervals added coordinatewise, and the interval the sum actually lies between. The added one always contains the computed one — greater-than survives addition — so the bracket never widens under a sum. Where it narrows, the parts were each too vague to pin down and the sum is not. Sums and comparison

When the ups add

Atomic weight brackets do not add over a sum — they bound it. Over all 120 pairs from a fifteen-game family the sum's bracket came out exactly the sum of the parts' brackets 56 times, strictly narrower 64 times, and wider never; and the rule separating the two is one line long, because every one of the 54 pairs with a pinned part is exact and only 2 of the other 66 are.

 A pass that may not end the game is not a component at all. The same grouping with the pass forbidden as the final move. Each group now holds several values, and a group with several values is a proof that the parts do not determine the whole. Where it stops

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.

 Swapping a branch for another of the same value. The ordinal sum of a base with a branch, and the same sum with the branch replaced by a heap of a different game carrying the same Grundy value. The two are compared by playing their difference, not by inspection — and they agree every time, which is what the colon principle claims and what the partizan case denies. Sums and comparison

When the nested sum only sees the value

The ordinal sum reads the form and not the value: three positions all worth zero, placed under a star, give three different answers. On impartial games it reads the value after all — 72 substitutions of an equal-valued heap from a different game, and every ordinal sum comes back unchanged. That difference is the whole reason a green Hackenbush tree can be collapsed one branch at a time.

 Welter positions and what they are worth. Coins on a strip, with the Grundy value the recursion returns and the nim-sum the squares would have if they were independent heaps. The two columns are the essay: they hardly ever agree. Impartial games

No two heaps alike

Welter's game is Nim with one extra clause — no two heaps may be the same size — and the clause is fatal to the nim-sum, which gives the right answer in none of the 120 three-coin positions. What replaces it is a function of pairs: ⟨a | b⟩ = (a ⊕ b) − 1, exact on all 55 two-coin positions, and nim-added over every pair it is exact on the whole board provided the number of coins is even.

 What the auction can and cannot see. Values under both conventions. The Richman value is the share of the money the second player needs; a half means the position itself decides nothing and whoever has more money wins. Every infinitesimal on the list, and zero with them, comes out at a half. Where it stops

Nobody has to move

Every convention here rests on one sentence nobody examines — the players move alternately. Replace it with an auction and a position stops having an outcome class and starts having a number: the share of the money the second player needs. The 22 values born by day two collapse to seven of those numbers, eight of them landing on exactly a half; the new number respects the game order on all 179 comparable pairs, and is not determined by the parts under addition on 14 of 49.

 Which of the two operators distributes over a sum. Cooling and heating, each asked whether applying it to a sum is the same as applying it to the parts and adding. The pools are the values born by day two and a set of deliberately hot positions; the counts are of ordered pairs. Temperature

Cooling adds and heating does not

The two operators are presented as a pair, and they are not one. Cooling a sum is the same as cooling the parts and adding, on every one of the 1,768 pairs tried, at two taxes and on two pools. Heating fails on 263 — and not for the obvious reason: in every failure neither part and not the sum is a number, so the clause exempting numbers never fires at the top. It fires two levels down, where an option of a sum is one part's option plus the whole of the other.

 Every heap up to 40, won or lost. Heap sizes with the outcome for the player who moves first. The lost ones are shaded; they are exactly the Fibonacci numbers, which is a fact about a game with one heap, no board and no geometry in it anywhere. Impartial games

The heap is not the position

Fibonacci Nim bounds a move by twice the previous move, which puts the state outside the board: a heap of six with a cap of two and a heap of six with a cap of five are different games. So there is nothing to add and no Grundy value to compute — and the game is completely solved anyway. The opener loses on exactly the nine Fibonacci numbers up to 120, and the smallest term of the Zeckendorf numeral is a winning move in all 110 winnable heaps.

 Two numbers from the same tree. Four subtraction games, each with its Grundy sequence and its remoteness sequence. The Grundy value decides a disjunctive sum and the remoteness decides a conjunctive one; the only thing they always agree about is which heaps are losses for the player to move. Sums and comparison

How long it lasts

Move in every component at once and the game ends the moment any one of them does. Grundy values say nothing about that game; what decides it is the remoteness, a second number computed from the same tree that measures how long a component can be made to last. Over 2,268 positions the rule is right every time, and the two numbers determine each other in neither direction.

 The genus of a sum. Every pair of heaps up to 9 counters, from nine impartial games, filed by the genus symbols of its two parts. The claim under test is that the file determines the answer; it does, and neither half of the symbol determines it alone. Where it stops

The genus of a sum

A genus symbol is meant to be carried one per heap, so that a solver never has to look at the heap again. That is a claim that the pair of symbols determines the sum's, and across nine games and 405 pairs it holds without exception — while the bases alone determine it in only 38 of 50 cases and the superscripts alone in 70 of 74. Both halves of the symbol are load-bearing, and two wild heaps can add to a tame sum.

 Where a sum's temperature actually lands. Every pair drawn from 45 hot positions, with the temperature of the sum set against the larger of the two temperatures. The bound is never broken and it is almost never used: 864 of the 1035 sums sit exactly at the maximum and 160 are frozen. Temperature

How cold a sum of hot games can be

The temperature of a sum is at most the largest temperature in it, and the bound leaves the whole interval below it open. Over 1,035 pairs the sums do not use that interval: 864 sit exactly at the maximum, 160 are frozen outright, and eleven land anywhere in between — every one of them with a component whose wall bends.

 Every empty NoGo board a build can solve. The empty boards, with the value the recursion returns and the outcome that follows from it. The one-row boards run 0, star, switch and repeat, which is a pattern with no reason behind it that survives past six squares. Particular games

Every group must keep breathing

NoGo is Go with no captures at all: a stone may be placed only if, afterwards, every group on the board still has a liberty. That makes a move's legality a fact about the whole board rather than about the squares it occupies — and a board therefore almost never breaks into independent parts. Of 117 boards here whose empty points fall into two regions, 24 are the sum of their regions and 93 are not.

 What is left when the copies pair off. For each position, the difference between n copies and n times the mean, reduced to canonical form. The first two are drawn and the last column says what the sequence does after them: half of these settle into a short cycle and the rest produce a new leftover every time, all of them the same bounded size. Temperature

What is left when the copies pair off

A pile of n copies stays within a bounded distance of n times the mean, and the distance never grows. The difference is a game rather than a number, and what it actually is has a much better answer: for a plain switch it alternates between one fight and nothing at all, and for a fight with a follow-up it is different every time — bounded in size and unbounded in complexity.

 How old a sum is. Every unordered pair of the twenty-two values born by day two, with nought dropped because adding it settles nothing — 231 sums. The birthday of each sum was read off its own canonical form and compared with the sum of the two parts' birthdays, which is the bound. The bound holds everywhere and is attained 163 times. Values

The birthday of a sum

Two values born by days m and n have a sum born by day m + n at the latest, which is the bound that stops a board made of many small parts from being unboundedly complicated. Over 231 pairs of day-two values the bound holds every time and is exact 163 times — and every pair it misses by three days or more has a sum that is a number or a nimber, so the slack is not noise but a measure of how much cancelled.

 Adding two thermographs. Every pair drawn from the 15 values born by day two that are not numbers — 120 sums — with the two walls added pointwise and compared against the true diagram of the sum. The added walls are always an outer bound and the means always add; the whole diagram is right for 92 of the 120, and the 28 it is wrong for are exactly the pairs in which both components are hot. Temperature

When two thermographs can be added

The temperature of a sum is not the sum of the temperatures, and the natural repair is to add the whole diagrams instead. Over every pair of hot values born by day two the added walls always bound the true ones and the mast always comes out right — and the whole diagram is right exactly when at most one of the two components is hot, which is precisely the case a reader has no use for.

 What a wider pool rescues. The misère outcome table built four times over, on pools of 10, 22, 100, 113 positions. A cell holds the set of outcomes that sums of its row class and column class actually took. Fifteen of the sixteen cells are short of all four outcomes on the smallest pool and none is on the largest, so every near-miss in the original table was a statement about the pool rather than about misère play. Where it stops

What a wider pool rescues

The misère outcome table has sixteen cells, and over a pool of ten positions fifteen of them hold fewer than four outcomes — which looks like structure and might be a shortage of positions. Thirteen values further on there is nothing left: every pair of outcome classes takes every outcome, so the near-misses were the pool, and the prediction the rung below made was right.

All themes