Combinatorial Game Theory
who wins, and by how much
Depth

Series — page 5

A field says what an essay is about. A series follows one idea essay by essay — from the question that introduces it to the one that assumes all the others.
The context that tells them apart. Two positions put into the same company, one context at a time. Each column is a game X; each cell is the outcome class of that side added to X. Equality means every column agrees, for every X there is — so a single disagreeing column is a disproof, and agreement across a bounded list of contexts is evidence rather than proof. The proof is that the difference is zero.

Equality

  1. 1 Equal in every company
  2. 2 The same parts, different wholes
  3. 3 A universe grows by days, not by sums
3 essays · sums 1 ko point, no ko rule. A ko fight drawn as a position graph and labelled by retrograde analysis: blue edges are Black's captures, red are White's, and each position carries the verdict for whichever side is to move. Positions the propagation never reaches are drawn — neither player can force a win and the game does not end — and they appear only where the rules permit a repetition.

Go

  1. 1 The rule that makes Go a finite game
  2. 2 A ko is won somewhere else
  3. 3 Two ways to count a finished board
3 essays · applied What a corner adds. The replies to a centre opening at noughts and crosses. As played, corners draw and edges lose. In the game where the second player can only block, every reply loses.

Maker–Breaker

  1. 1 Blocking is not enough
  2. 2 Three ways to know a draw
  3. 3 A win priced in stones
3 essays · applied What a component has to carry. Four impartial games, one of which is Nim. In the other three a component cannot say what its own legal moves are without knowing something about the past or about the rest of the board, so the Sprague–Grundy recipe does not apply — and the table says by how much. Every outcome was obtained by solving the sum outright rather than by any formula.

Memory

  1. 1 What a component has to carry
  2. 2 What restores the theorem
  3. 3 Two clauses and a third question
3 essays · limits What each heap is worth. The value of a single heap of each size. Nothing here repeats: the forms grow deeper as the heap grows, which is what stops the impartial theory's periodic table from having an analogue.

Partizan subtraction

  1. 1 Two players, two lists
  2. 2 A sequence with a rule and no period
  3. 3 The condition that survived the wider sweep
3 essays · positions 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.

Remoteness

  1. 1 How long it lasts
  2. 2 The number nobody needs
  3. 3 A compound of two different games
3 essays · sums How many different values a Grundy sequence has used. One curve per octal code: the number of distinct Grundy values among the first n heaps. A periodic game runs out of values and its curve levels off. The codes nobody has settled are still climbing at six thousand heaps.

Sparse space

  1. 1 The values that keep arriving
  2. 2 A rare class exclusive-or respects
  3. 3 The odd values keep coming
3 essays · impartial One of these is a game. Every length that came out of 40 random games from each starting position. Brussels Sprouts always ends after exactly five crosses less two moves, so whoever is to move at that point was decided before the first curve was drawn. Sprouts ends at different lengths depending on how it is played, which is what makes it worth playing.

Sprouts

  1. 1 Sprouts, and the game that is not one
  2. 2 A conjecture from hand play
  3. 3 What computing further has bought
3 essays · positions The same row, cut and toppled. Rows of blue and red drawn once and evaluated twice: as a Hackenbush string, where a player cuts an edge of their own colour and everything above it falls, and as Toppling Dominoes, where a player knocks one over and everything on the chosen side falls. Both values are computed by the same recursion from the two rulesets.

Toppling dominoes

  1. 1 Topple it from either end
  2. 2 How long a row a value needs
  3. 3 A recipe instead of a census
3 essays · positions Col and Snort on a path of four. One graph, two games, and one word of difference between the rules. Col forbids painting next to your own colour, which makes every move a small self-harm and drives the values towards numbers. Snort forbids painting next to your opponent's, which makes every move a land grab and drives them towards fights. Both values are computed from the same recursion.

Colouring

  1. 1 One board, two rules
  2. 2 One rule makes it cold, the other hot
2 essays · positions Cram on 4 by 4: the pairing strategy. Cram is Domineering with the orientations shared: either player may place a domino either way up, so both players have exactly the same moves and the game is impartial. Every position therefore has a Grundy value, and this board's was computed by the mex rule over its own placements.

Cram

  1. 1 Cram
  2. 2 Cram with the last move losing
2 essays · impartial Grundy values for subtraction of 1, 2, 3. The Grundy value of every heap size for a take-away game, computed by the mex rule. A period, if the figure marks one, was found by searching the computed sequence rather than assumed — and where no period is marked, none was found in the range drawn, which is not the same as there being none.

Grundy sequences

  1. 2 Grundy sequences, and where they stop being predictable
  2. 3 Naming a game with a number
2 essays · impartial Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer.

Incentives

  1. 1 What a move is worth to the player making it
  2. 2 Nobody wants to move here
2 essays · values Options handed to Left in 1 | −1. A position, and one candidate option after another added to it. Where the gift is one the player would never take the value does not move at all; where it is one they would, it does. The last column is the value of the enlarged form, computed by the same recursion as the original.

Gift horse

  1. 1 An option nobody would take
1 essay · values Four things a position can be. Every position falls into one of four outcome classes, and only three of them correspond to a comparison with zero. The fourth — first player wins — is a position confused with zero, neither greater, smaller nor equal, and it is where the subject departs from arithmetic.

Outcomes

  1. 1 Who moves last
1 essay · values Shove strips, and what each is worth. A shelf of positions with the value the recursion returns beside each. Every one is a number: Shove has no hot positions at all, which is unusual for a partizan game and is the first of the essay's three claims.

Shove

  1. 1 Nothing worth fighting over
1 essay · positions

All essays