Combinatorial Game Theory
who wins, and by how much
Depth

Series

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.
Domineering on 2 by 3. Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses. The two players see different games on the same board, which is what partizan means — and the value that results is not a number.

Domineering

  1. 1 Domineering
  2. 2 The values of every small board
  3. 3 A board that is a sum of its regions
  4. 4 Which shapes are worth fighting over
  5. 5 Counting the moves each side has
  6. +6 more
11 essays · positions {5 | {4 | 0}} beside one other fight. A local position and a single switch, played out together at each of several ambient temperatures. The middle columns are what optimal play does: whether it opens the local fight, and whether it answers when the opponent opens it. The answer stops being forced at a temperature the local position alone does not name.

Sente

  1. 1 Sente is a fact about the rest of the board
  2. 2 Double sente is not a property of the position
  3. 3 What a move nobody makes is worth
  4. 4 The answer that starts another fight
  5. 5 What the halving is a function of
  6. +6 more
11 essays · temperature Every position has an exact opposite. A position beside its negative, which is the same game with the players exchanged, and the sum of the two. The sum is worth zero every time — a second-player win — because the second player can answer each move with its mirror image. It is the fact that makes values a group, and it is what lets one position be subtracted from another.

Negation

  1. 1 Turn the board through a right angle
  2. 2 The values that are their own negatives
  3. 3 What can be struck out
  4. 4 The thirty that cancel themselves
  5. 5 A self-negative value costs a day
  6. +5 more
10 essays · sums A switch, its mean and its temperature. Positions of the form {a | b} with a above b: both players want to move there, so neither is settled. The bar spans the two options, the marked point is the mean the position is worth once the fighting is over, and the temperature is half the gap — which is exactly what moving first is worth.

Switches

  1. 1 Worth nothing, and worth fighting for
  2. 2 The switch a player is imagining
  3. 3 When a switch is not a switch
  4. 4 A fight with no midpoint
  5. 5 The bend is the condition
  6. +5 more
10 essays · values Knowing who wins, and knowing what it is worth. Nine positions, each evaluated twice by an instrumented evaluator that starts with an empty cache. The third column counts what deciding the winner costs and the fourth counts what the canonical form costs, in the currency each question is actually paid in.

Value cost

  1. 1 Knowing who wins, and knowing what it is worth
  2. 2 The question in the middle
  3. 3 When the catalogue starts paying
  4. 4 Where to stop building
  5. 5 A catalogue that knows what it will meet
  6. +5 more
10 essays · complexity Where 1,474 values sit on the scale. The temperature of every value in the pool, counted. The floor is −1 and only numbers are on it; the next rung up is 0, and everything there is a number with an infinitesimal added. Above that the scale is continuous and the counts thin out.

Cold

  1. 1 Below zero
  2. 2 How hot a day gets
  3. 3 How hot a real position is
  4. 4 What a game actually produces
  5. 5 One fight makes a board a fight
  6. +4 more
9 essays · temperature {4 | 0} played out in a stack of 5 coupons. An idealised environment: coupons worth a fixed step less each, which either player may take instead of moving in the game. The rows are the line optimal play takes over the whole board, in order. What the game turned out to be worth is set beside its mean value, and the coupon the players stopped at beside its temperature — two quantities measured from the play, and two computed from the thermograph.

Coupons

  1. 1 An environment made of coupons
  2. 2 Two games in one environment
  3. 3 When to leave the environment
  4. 4 How big the answer is
  5. 5 The quantity that does not order a board
  6. +4 more
9 essays · temperature What deleting is worth on its own. The reduction split into its two halves and each measured. Deleting a dominated option removes exactly one option and can do nothing else; bypassing a reversible one substitutes an option list and can widen the form. The counts say how much of the reduction the monotone half accounts for.

Dominance

  1. 1 The reduction that always shrinks
  2. 2 How much a list of options can lose
  3. 3 Which option the reduction keeps
  4. 4 The margin a count needs
  5. 5 The weight that blunts the count
  6. +4 more
9 essays · values One position, three ways of writing it, and only one of them adds. The same positions as a sentence about who wins, as a description of the position itself, and in the notation Winning Ways introduced. The first two columns carry identical information and support no operation whatever. The third column can be added — and the sums below it are values that no manipulation of the first two columns could reach, because two of these pairs start from the same two outcomes and finish differently.

Notation

  1. 1 The notation was the argument
  2. 2 Where the braces stop
  3. 3 Two names that add to nothing nameable
  4. 4 What two numbers cannot tell apart
  5. 5 A board is written as a sum
  6. +4 more
9 essays · history Amazons, after the arrows have cut the board in 2. An amazon moves like a queen and then shoots an arrow, also like a queen, which burns the square it lands on. Late in a game the burnt squares cut the board into regions no amazon can cross — and from that moment the position is a sum of independent games, which is the shape the whole theory was built for, arrived at by the play rather than assumed.

Amazons

  1. 1 Amazons, and when a position becomes a sum
  2. 2 When a real board falls apart
  3. 3 Amazons on one line
  4. 4 A region one player owns
  5. 5 The fractions that were not there
  6. +3 more
8 essays · positions Backward induction on a game that ends, one round at a time. Zermelo's argument as it actually runs. Round zero is the positions where the player to move has no move at all, which is the only thing the procedure knows without being told; each later round is what those settle. Anything still unlabelled when nothing more can be deduced has no label and never will — and on a game with a cycle in it, that leftover is exactly the set of drawn positions. The theorem is a statement about this procedure terminating, and it names the winner of nothing.

Determinacy

  1. 1 The first theorem, and the winner it declines to name
  2. 2 The paper was about how long
  3. 3 The gap between two answers
  4. 4 Every play ends and no round settles
  5. 5 What the play keeps coming back to
  6. +3 more
8 essays · history A 2 × 3 board of boxes, 6 still on the table. A Dots and Boxes position drawn as dots and lines, and — where the figure asks for it — the same position as a strings-and-coins graph: one coin per box, one string per line, and the border lines running to the ground. Lines already played are solid, lines still available are dashed, and a box with no strings left has been pocketed. The footer carries the exact net score the solver computes from here and the normal-play verdict on the same position.

Dots and Boxes

  1. 1 The game in every exercise book
  2. 2 The chains decide it before the boxes do
  3. 3 The parts are worth nothing and the sum is not
  4. 4 The endgame theory arrives late
  5. 5 A thousand positions and no exception
  6. +3 more
8 essays · applied Moore's Nim with k = 2: the columns, divided by 3. The heap sizes in binary, with each column added as an ordinary sum rather than exclusive-or. In Moore's Nim a move may take from as many as k heaps at once, and the position is lost for the player to move exactly when every column sum is divisible by k + 1. Ordinary Nim is k = 1, where divisible by two means an even number of ones — the same picture with a different divisor.

Moores-nim

  1. 1 Taking from several heaps at once
  2. 2 The patch that generalised
  3. 3 The rule a smaller move breaks
  4. 4 The wider move is the easier game
  5. 5 The count of odd heaps
  6. +3 more
8 essays · impartial The simplest number in between. A game whose options are numbers is worth the simplest number strictly between them — and simplest means born earliest, so integers come before halves and halves before quarters. It is not the midpoint, and the difference is the whole content of the rule.

Numbers

  1. 1 The simplicity rule
  2. 2 The day a number is born
  3. 3 Numbers avoid numbers
  4. 4 The numbers came out of the game
  5. 5 The recursion this site cannot run
  6. +3 more
8 essays · values 7 symmetries, and the one that is a strategy. 4 games and 7 candidate symmetries, each tested by playing the strategy out against every opponent line rather than by argument. A pairing strategy needs a map that fixes the start, is an involution, and carries one player's moves to the other's — and the last condition is where most of these fail.

Pairing

  1. 1 The strategy that is a symmetry
  2. 2 Looking for the symmetry
  3. 3 The symmetry one move away
  4. 4 A check in front of a search
  5. 5 The check that was not a check
  6. +3 more
8 essays · impartial Push and Shove over every strip up to 6 squares. The same strips under both rules. A cliff lets coins fall off and a wall does not, and the census says what that one clause is worth: both games are entirely made of numbers, they never agree on a value, and the obvious board-reading is right far more often under the wall than under the cliff.

Push

  1. 1 The other way to move a row
  2. 2 The reading that survives too much
  3. 3 The criterion that cannot exist
  4. 4 A numeral in the empty squares
  5. 5 The cliff a cut invents
  6. +3 more
8 essays · positions The values the construction hands down, and the values games produce. The two lists counted against each other. The construction produces 1,474 values by day three; the eleven thousand positions swept here produce 1,193, and only 116 of those are on the construction's list. A value's birthday and a value's reachability have nothing to do with each other.

Realisability

  1. 1 The values nobody's game produces
  2. 2 The cheapest way to show a value
  3. 3 The birthday is a floor
  4. 4 Wider costs less
  5. 5 The entry fee was the cap
  6. +3 more
8 essays · values A game where the last move decides nothing. Rows of coins taken from either end, with the exact score for each side moving first. Under the normal-play convention this family is settled entirely by the parity of the row — nobody is ever without a move until the coins run out — so normal-play theory returns the same answer for every row and it is not the answer anybody wants. The scoring answer depends on nothing but the numbers.

Scoring

  1. 1 Counting at the end changes everything
  2. 2 What a pass is worth to a theory
  3. 3 A hypothesis has to hold all the way down
  4. 4 Nothing to subtract with
  5. 5 The restriction that buys the most
  6. +3 more
8 essays · applied The thermograph of {5 | 1}. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.

Temperature

  1. 1 What is at stake
  2. 2 Cooling
  3. 3 Playing the hottest
  4. 4 The same fight, eight times over
  5. 5 The first time it told somebody something
  6. +3 more
8 essays · temperature The thermograph of {5 | 1}. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.

Thermograph

  1. 1 Reading a thermograph
  2. 2 The endgame, accounted for
  3. 3 Two hot fights that add to a cold number
  4. 4 A thermograph is built from its options'
  5. 5 A thermograph with two bends
  6. +3 more
8 essays · temperature

All essays