Combinatorial Game Theory
who wins, and by how much
Depth

Series — page 3

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.
Folding a 4×4 board by its symmetries. The size of a Domineering solver's table when positions related by a board symmetry are stored once. The saving rises toward the size of the symmetry group and stops there — it is a constant factor by construction, and no board is large enough to make it anything else.

Identification

  1. 1 What counts as the same position, and what that is worth
  2. 2 What it costs to notice a repetition
  3. 3 A key shorter than the position
  4. 4 A check bit halves the average and not the key
  5. 5 A key is a code, and two squares come free
5 essays · complexity Smaller than every positive number, and not zero. Values that sit between zero and every positive number, each compared with zero and with 1/1024. Every relation drawn was computed by playing the difference, and one of them is confusion — neither greater, smaller nor equal. None of these is a number, and in a close game they are the entire margin.

Infinitesimals

  1. 1 Infinitesimals
  2. 2 How many ups
  3. 3 Tiny, miny, and the sizes below every size
  4. 4 The class where nobody runs out first
  5. 6 When the ups add
5 essays · values Classes needed, as the heaps get bigger — Dawson's chess ·137. How many kinds of position there are, against how large a heap the universe allows. Under normal play the answer stops growing as soon as the Grundy values stop growing. Under misère play it does not stop, and every new class is a pair of positions that behave identically under normal play and differently under misère.

Misere cost

  1. 1 The cost is in the closure, not in the positions
  2. 2 A misère sum is searched, not added
  3. 3 Two heaps of testing are enough
  4. 4 Twelve classes, seven questions
  5. 5 A staircase, not a slope
5 essays · complexity Nim with heaps of 3, 5, 7. Heaps of counters; a move takes any number from one heap. The position is a loss for the player to move exactly when the binary digits of the heap sizes cancel in every column — the nim-sum — and that is the whole of the theory of Nim.

Nim

  1. 1 Nim, and the nim-sum
  2. 2 The move that gives counters back
  3. 3 The nimbers multiply
  4. 4 The tartan theorem
  5. 5 Four hundred and seventy steps
5 essays · impartial The reduction that puts options back. How the two reductions change the width of a form. Domination only ever removes an option. Bypassing a reversible option substitutes the answer's whole option list, so it can leave the form wider than it started — and the finished canonical form can be wider than the form it came from.

Reversibility

  1. 1 The reduction that puts options back
  2. 2 How wide a form can get
  3. 3 What a value costs to write down
  4. 4 The same position, written once
  5. 5 A reduction that reads a graph
5 essays · values One node per route, one node per position. For each board, the number of nodes in the recursion tree a solver with no memo table would walk, beside the number of distinct positions that tree contains, beside the longest run of moves in it. The first number is the cost of forgetting; the second is the size of the table that avoids it; the third is the stack, and it stays small however the other two grow.

Search

  1. 1 A position reached eleven ways is one position
  2. 2 The order a solver tries the moves in
  3. 3 A verdict that changes with the depth
  4. 4 Where a search may stop
  5. 5 Search on in pairs of moves
5 essays · complexity What the rule costs. Every sum of three components from a fixed pool, played out twice: once with one side following the rule "move where the stake is largest" and once with both sides evaluating exactly. The rule is not optimal, the gap is bounded, and the bound is the largest temperature on the board.

Strategy

  1. 1 A rule with a guarantee
  2. 2 A rule with no promise at all
  3. 3 A pool built to punish greed
  4. 4 A schedule instead of a number
  5. 5 An environment instead of a stack
5 essays · temperature Hex on 3 × 3, with every winning opening found. A rhombic Hex board with each cell marked according to whether taking it first wins. Left joins the top edge to the bottom and Right joins left to right; a filled board is always a win for exactly one of them, so the search needs no draw test. Strategy stealing proves that a winning opening exists without exhibiting one — these are the ones exhaustive search finds, on a board small enough for exhaustive search to finish.

Strategy stealing

  1. 1 The theorem that names a winner and no move
  2. 2 Where the needle has a sentence
  3. 3 A board one column wider
  4. 4 A potential that names every move
  5. 5 The winning reply is the fourth choice
5 essays · applied Toads and frogs. Toads move right and frogs move left, one square into a gap or hopping over exactly one opponent. A player unable to move loses. It can be played on squared paper by anybody, and its values are immediately stranger than the game looks.

Toads and Frogs

  1. 1 Toads and Frogs
  2. 2 The strip nobody has a formula for
  3. 3 The same strip without the jump
  4. 4 The strip where every number is a whole one
  5. 5 The square that cannot be halved
5 essays · positions A blocked file, and the tempo it holds. Files of a blocked pawn ending: a White pawn below, a Black pawn above, and a gap between them that either side may close one square at a time. Each file carries the value the game recursion gives it. With only single steps available a file is worth a star or nothing, by the parity of the gap, so the whole position is tempo and no material at all — which is what a chess player means by mutual zugzwang.

Chess

  1. 1 A pawn ending is a sum
  2. 2 What has to break before a pawn is worth a number
  3. 3 One king, and two files to be in
  4. 4 A position with no value, and the rule that gives it one
4 essays · applied A board in pieces costs the sum, not the product. A Domineering board with squares blocked out, so that it falls into regions no domino can span. The number of positions in the whole board is exactly the product of the numbers in its regions — which is why evaluating the regions separately, and adding the values, is an exponential saving rather than a tidier way of writing the same search.

Decomposition

  1. 1 The board falls apart, and the arithmetic changes
  2. 2 Finding the parts
  3. 3 How often a board falls apart
  4. 4 A wall an amazon can walk through
4 essays · complexity End-Nim: a player at each end of the row. Rows of heaps in which Left may take from the leftmost heap and Right from the rightmost. The value beside each row was computed by the game recursion and reduced to canonical form; the outcome beside it says who wins. A single heap is a Nim heap, because both players may take from it — and that is the last thing about this game that looks like Nim.

End-Nim

  1. 1 Taking from the ends
  2. 2 Where the nimbers run out
  3. 3 The rows that are their own mirror
  4. 4 A game with nothing at stake
4 essays · positions 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.

Fibonacci nim

  1. 1 The heap is not the position
  2. 2 The family the Fibonacci numbers belong to
  3. 3 What the numerals knew
  4. 4 One proof, and one wrong lemma
4 essays · impartial Three take-and-break games, three kinds of answer. The Grundy sequences of Nim, Lasker's Nim and Kayles over the first heaps. Adding a move that removes nothing takes Nim's sequence from the identity to a four-line formula; bounding how much may be taken instead takes it somewhere with no formula at all.

Lasker

  1. 1 Splitting is a move
  2. 2 The proof is sixteen cells
  3. 3 One split is enough
  4. 4 The formula is a limit
4 essays · impartial The 22 values born by day two, and the order they form. Each value sits above everything it is greater than, joined to what it covers. The order has 36 covering relations and is nine levels deep, and 52 of its 253 pairs are incomparable — and it is still a lattice: every pair has a least upper bound and a greatest lower bound among the same 22 values. Two values are marked, together with their join and their meet.

Lattice

  1. 1 The simplest game above both
  2. 2 Where the order and the sum disagree
  3. 3 Fifty-two errors and seven sizes
  4. 4 One of four questions
4 essays · values 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.

Nogo

  1. 1 Every group must keep breathing
  2. 2 When the regions add
  3. 3 How thick a wall has to be
  4. 4 A wall that bends
4 essays · positions Every impartial position is a Nim heap. A heap in a subtraction game, its Grundy value, and the Nim heap it is equivalent to. The equivalence is exact: the two positions have the same options up to value, so they behave identically in any sum, which is the Sprague–Grundy theorem.

Sprague–Grundy

  1. 1 Every impartial game is a Nim heap
  2. 2 A row of coins is already a sum
  3. 3 Two people, four years apart, one theorem
  4. 4 Where the impartial theory stops
4 essays · impartial 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. The two marks on the base line are the stops — what each player gets by moving first and playing the fight out with no tax charged at all.

Stops

  1. 1 Where the fight stops
  2. 2 The fight never runs backwards
  3. 3 The numbers it is confused with
  4. 4 Which end of the interval is open
4 essays · values a path with every link doubled: the criterion and the game. A Shannon switching graph with the two marked vertices in gold. Short secures links and Cut deletes them; Short wins by joining the two marks. Lehman's criterion says Short wins moving second exactly when some subgraph holding both marks splits into two edge-disjoint spanning trees — drawn here in blue and red where one exists. The verdicts beside the graph come from playing the game out, and the criterion is computed without looking at the game at all.

Switching

  1. 1 A winning strategy that is a spanning tree
  2. 2 The first move is a link that is not there
  3. 3 Cut is Short on another graph
  4. 4 A point with three neighbours
4 essays · applied Poker Nim from 3, 5, 7, with reserves of 4 and 4. Nim with one extra kind of move: a player may put any number of counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. They cannot, and the winner is decided by exactly the same nim-sum as ordinary Nim — checked here over every position within a stated range rather than argued.

Termination

  1. 1 The condition the recursion rests on
  2. 2 It ends, and nothing says when
  3. 3 Two ways to end with no bound
  4. 4 Which games end at which level
4 essays · limits

All essays