Combinatorial Game Theory
who wins, and by how much
Generator

One node per route, one node per position

One node per route, one node per position
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.

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.

14 essays call search-cost. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

Where it is called

Changing this generator changes every one of these figures.

A golden ratio in a table that never mentions it. Grundy values for Wythoff's game, computed by the mex rule alone — a queen moving left, down or diagonally toward the corner, and whoever cannot move loses. The circles are Wythoff's 1907 description of the losing positions, which came thirty years before any of this machinery: the pairs formed from the golden ratio. They land on the zeros exactly. Nothing in the computation knows about φ and nothing in Wythoff's argument knows about Grundy values. How it was found

A golden ratio thirty years early

Wythoff described the losing positions of his game in 1907 with an argument about partitions of the integers, and no Grundy value anywhere in it. The theory that arrived thirty years later computes the same positions — and has never produced a closed form for the values, which the older argument had for the zeros from the start.

 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. What it costs

A position reached eleven ways is one position

A 4×4 Domineering board has 5,700 positions in it and 6,257,129 routes through them. Three heaps of 7, 11 and 13 have 480 positions and 7.6 × 10¹⁶ routes. The gap between those two numbers is not an optimisation — it is the difference between a search that finishes and one that does not.

 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. What it costs

The board falls apart, and the arithmetic changes

A 4×5 Domineering board with a wall down the middle has 2,916 positions in it, and that number is exactly 54 × 54 — the product of its two halves. Solving the halves separately costs 108. Decomposition is the one saving in this subject that turns a product into a sum.

 One Sprouts game from 3 spots, counted. One randomly played Sprouts game, with the map counted after every move. A move spends two lives and the new spot brings one, so the lives fall by exactly one every time — and unlike the arms of a Brussels cross they are not replaced. Every move either cuts a face in two or joins two separate pieces of the drawing, and how many of each a game contains is up to the players, which is why the length is not fixed. How it was found

A conjecture from hand play

Sprouts was invented over tea and its outcome pattern was guessed from games played with a pencil. Computers have checked it far past where a person could go, and this site's own solver gives out at three spots — so the honest figure states the frontier it reaches rather than the number somebody else published.

 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. What it costs

The class is named after memory, and that is not an accident

A 4×4 Domineering board has 6,257,129 routes through it, 5,700 distinct positions, and a deepest line eight moves long. Those three numbers are three different resources, and the smallest of them is the one that gives games their complexity class.

 Small Domineering boards and what they are worth. Every value here was computed from the moves rather than looked up. Even on boards this small the values are switches and infinitesimals rather than numbers, which is the ordinary situation for a partizan game and the reason the theory needs more than arithmetic. Particular games

The values of every small board

Thirty Domineering rectangles, every value computed from the moves rather than looked up. The 1×n row obeys a formula and the 2×n row does not: its outcomes run L N N R three times over and then 2×13 comes out worth exactly 0, and its temperatures climb to 19/16 and fall back without settling.

 What a value costs to write down. Every one of the 1,474 values born by day three, grouped by the width of its canonical form, with the number of symbols the form takes when it is written out. Each count was obtained by walking the canonical form and counting its nodes, so a subposition appearing twice is counted twice — which is what writing it out does. The widest values of the day are not the longest to write. Values

What a value costs to write down

The canonical form is the smallest form of its value, and it is smallest in the one currency the reduction happens to spend: options. Counted in symbols it is nothing of the kind — the widest value born by day three is not the longest, the longest has six options rather than seven, and every canonical form on the day except the seven integers writes some position out twice.

 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.

 Three questions about the same board. For each sum of two positions: the cost of deciding who wins each part alone, of deciding who wins the whole sum by search, and of computing what each part is worth. The middle question is in the middle on seven of the eight, and the exception is the sum whose two parts are identical. What it costs

The question in the middle

Between knowing who wins each part and knowing what each part is worth sits the question a player actually has: who wins the board. Priced on sums of two it lands between the other two on seven of eight, cheaper than the values by up to eight times. On sums of three, with nothing repeated, it is dearer than the values on five of six — because a component multiplies a search and only adds to a value.

 Where in a game a board falls apart. Every position reachable from an empty Domineering board, grouped by how many dominoes have been placed, with the share that have fallen into two or more live pieces. The share is nought at both ends of the game and around three fifths in the middle. What it costs

How often a board falls apart

A decomposition turns a product into a sum, so a solver wants to know how often one arrives. Over every position of a 4 × 4 Domineering board the answer is 47 per cent — nought for the first two moves, three fifths in the middle, and nought again at the end. What one decomposition is worth is the other half of the answer and it is a factor of 1.8.

 How much of the board a who-wins search walks. Positions a memoised who-wins search of 4 × 5 Domineering expands under six move orderings, drawn to scale against the 48,670 positions the board has. Leaving the opponent fewest replies expands 1,125; trying losing moves first expands 30,202; all six find the same winner. What it costs

The order a solver tries the moves in

A memoised search asking who wins 4 × 5 Domineering expands 1,125 positions when it tries first the move that leaves the opponent fewest replies, and 30,202 when it tries losing moves first — the same answer at twenty-seven times the price. The ordering that already knows which moves win is not the cheapest. A win needs one move and a loss needs all of them, so the price of an order is paid one level down, in the replies it leaves.

 Right, wrong, and right again. A 4 × 5 Domineering position with Right to move, which Right loses, beside what a search cut at each depth from 0 to 9 says about it when it guesses that the player with more placements wins. The guess alone is right, a search one move deeper is wrong, and every deeper search is right. What it costs

A verdict that changes with the depth

A who-wins search of 4 × 5 Domineering cut at a fixed depth, guessing that the player with more placements wins where it stops, is right about 72.5 per cent of positions at depth 0 and about every one of them by depth 7. On the way, 4,697 positions are right at one depth and wrong at a deeper one. With a guess that knows nothing, going one move deeper makes the search worse — and its errors alternate in kind with the parity of the depth, so that half its verdicts are proofs.

 Two depths that agree. A 4 × 5 Domineering position with Right to move, which Right wins, beside what a search to each depth from 0 to 6 says under the guess that any mover wins. The verdicts alternate until depths 2 and 3 agree, which certifies the answer 3 moves before the longest line. What it costs

Where a search may stop

A search deepened until two consecutive depths agree carries a proof of its verdict, and on 4 × 5 Domineering it stops before the longest line on 17,589 of 48,670 positions. It also costs three times what the search that simply finishes costs. The rule that pays is the other one. Search on wherever the two players' counts of placements are within one, and at depth 2 the wrong verdicts fall from 2,140 to 86 for about a quarter more work per search.

 Two ways to search on, one position. A 4 × 5 Domineering position with Right to move, which Right wins, beside what deepening says at each depth when it declines to guess where the counts of placements are close. Searching on one move at a time, depths 0 and 1 agree on the wrong verdict; searching on two moves at a time, the search stops at depth 3 with the right one. What it costs

Search on in pairs of moves

Deepening until two depths agree gives a proved verdict, and searching on where the counts are close gives a better one; put together the obvious way, they stop on a wrong verdict at 3,231 positions of 4 × 5 Domineering. A guess one move past the cut has the other player to move and flatters the wrong side. Searching on two moves at a time keeps the proof, and the window that suits it is one-sided — but however it is widened, the certificate gets cheaper only by turning into the search that finishes, and on four boards it never gets below it.

The whole library · The position index · The figures that play back