Combinatorial Game Theory
who wins, and by how much
Theme

The thread: It depends on the company

Sente, independence, equality, the size of a move and even the winner turn out to be facts about the rest of the board rather than about the position in front of the reader.
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.

 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. Particular games

Amazons, and when a position becomes a sum

Every technique on this site starts from a position already broken into independent parts. Amazons does not begin that way — the board is one fight until the arrows cut it, and the moment of cutting is something the play produces rather than the analyst assumes.

 How much changes hands, against how much is at stake. Two ways of choosing where to move, run against optimal play over every board from a pool of three components. Biggest-first takes the component where the most changes hands, which is the count in every endgame book; hottest-first takes the one with the highest temperature. They disagree on most of these boards, the count costs points more often, and — the difference that matters — the count sometimes loses more than the largest temperature on the board, which is the bound the theory's rule is guaranteed to keep. Temperature

Big is not the same as hot

A player sizes a move by how much changes hands when it is played, which is the number in every endgame book. The theory sizes it by temperature. On a plain switch the two agree exactly, so nothing shows; on a move with a follow-up they come apart, and the count gives up more than the guarantee the theory's rule carries.

 {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. Temperature

Sente is a fact about the rest of the board

A move that must be answered is called sente, and the word is used as though it described the local position. It does not. The same fight is answered while the rest of the board is quiet and ignored once it is busy, and the crossover — measured by solving the whole board at every temperature — sits at the follow-up's own temperature.

 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.

 Is {{5 | 3} | {2 | −4}} double sente?. One local fight with a follow-up on each side, played out inside a sum with a switch whose temperature rises. The two middle columns are what optimal play does when each player opens the fight. Whether the opponent has to answer is settled by the ambient temperature and not by the shape, so the same position is double sente, sente for one player, and gote for both, at three different ambients. Temperature

Double sente is not a property of the position

A fight with a threat on each side is called double sente, as though the phrase named a shape. Swept against a rising ambient temperature, one such fight — { {5 | 3} | {2 | −4}} — is double sente up to an ambient of 1, sente for one player only from 3/2 to 3, and gote for both from 7/2, and the two band edges are the temperatures of the two follow-ups.

 The endgame, accounted for. Several independent regions, each a fight with a settled value and a size. The account plays them hottest first: add up what each is worth on average, then add the largest amount at stake, subtract the next, and so on down. The exact value of the whole position is computed beside it, and the figure prints both. How it was found

The first time it told somebody something

A theory earns its keep when it produces an answer nobody had. Temperature did that for Go endgames — the orthodox account gives a move order that is provably right and is not the one experience offers, and the position it is right about is small enough to check here completely.

 Where the count and the value part company. Amazons endgames whose arrows have already cut the board into regions, with the territory count beside the computed value. Territory gives every empty square to whichever amazon can reach it in fewer moves, which is what Amazons programs compute. The positions drawn are the ones where that number gets the outcome wrong, and they have something in common: each is worth a switch, so there is no number for the count to have been right about. Out in the world

When a real board falls apart

Amazons is played competitively, and late in a game the arrows have cut the board into regions no piece can cross. From that moment the position is a disjunctive sum — arrived at by the play rather than assumed — and the territory count every program uses can be measured against what the sum is actually worth.

 {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. Temperature

An environment made of coupons

Beside the game sits a stack of coupons worth 4, 3, 2, 1, 0, and a player may always take the top one instead of moving. Play the whole thing out and two quantities the theory computes are measured instead: {4 | 0} comes out worth exactly 2, its mean value, and the coupons stop at 2, its temperature. For {10 | {9 | 1}}, whose temperature is 1, they stop at 7/2 — because what the stopping coupon measures is the hottest temperature anywhere in the tree.

 7 positions of the same value, and how long each of them lasts. Nim positions whose heap sizes all nim-sum to zero. As games they are the same object: each is worth zero, each is a loss for the player to move, and each may be substituted for any other inside any sum without changing a single outcome. The bars are how many moves each one takes, from the shortest legal play to the longest. The value determines everything about who wins and nothing at all about when. Values

What a value leaves out

A value settles who wins, by how much, and what happens in every sum the position appears in. It says nothing about when. Seven positions here are worth exactly zero and interchangeable everywhere, and they run from two moves long to eighteen.

 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. Sums and comparison

Equal in every company

Two games are equal when no third game can tell them apart — a quantifier over every position there is, discharged by one finite test. A search over 184 contexts separates all 5,790 unequal pairs it is handed and still calls two different games the same, which is exactly why G − H = 0 is a theorem and an exhaustive search is not.

 Finding the parts costs the same whether there are any or not. Domineering boards of 4 squares by 5 with different squares blocked out, and what the decomposition is worth on each. The pass that finds the regions is a flood fill and visits every square once, so it costs the same on all of them. What it buys ranges from nothing — on the boards that do not decompose — to a saving of 2,808 positions, and it cannot tell which case it is in until it has run. What it costs

Finding the parts

Decomposition turns a product into a sum and is the largest saving in the subject. Nobody labels the regions. The pass that finds them costs the same on every board of a size — including the boards where there is nothing to find — and what it buys ranges from four orders of magnitude to nothing at all.

 What a deeper position does to the shape. Thermographs side by side, two of them, with temperature running up each panel and value across it: {{6 | 2} | {1 | −3}}, with a bend where an option's own fight cools out; {4 | −1}, straight-walled. A wall that runs straight has nothing changing hands below the meeting point; a bend is an option's own fight cooling out at a lower temperature than this position's, and it is where a decision passes from one player to the other. The two marks on each base line are the stops — what each player gets by moving first with no tax charged. Values

The switch a player is imagining

Every account of a hot position ends up as "worth about m, and worth t to move in", which is the switch {m+t | m−t}. For a plain fight that summary is the position exactly. For a fight with anything behind it the leftover is not a rounding error — on one position here it is a whole second fight of temperature two.

 The same position, two conventions, two winners. Three-player Nim with the last counter winning. The two columns differ only in what a player does when they cannot win themselves, which is a question the rules do not answer — and the answer decides who wins. Where it stops

Three players and no answer

Every theorem here is about two players, and the reason is not convenience. With two players the game is zero-sum, so 'play well' needs no further explanation. Add a third and the winner of a Nim position becomes a fact about the convention: two reasonable ones disagree on 56 of the 71 positions swept. The one question no convention touches — can a player force a win against the other two together — is answered 'nobody' in 65 of the 71.

 4 | 0 and {2 | {1 | 0}} in the same environment. Two positions and one coupon stack, solved as a single board. The rows are the line optimal play takes; the coupon on top when each position is first entered is compared with the coupon it was entered at when it had the environment to itself. The mean contributions still add and the entry coupons need not agree. Temperature

Two games in one environment

A coupon stack measures a position: play the whole board out and the coupon the players stop at is the temperature, the score is the mean. Put a second position beside the first and one of the two measurements stops working. Over 36 ordered pairs the contributions still add to the means every time, and the coupon a fight is entered at moves on 13 of them — without either position changing.

 How much company equality needs. Each row restricts the quantifier in the definition of equality to the games named, and counts how many of the 22 values born by day two survive as distinct. The bar is the same number drawn; the jump from nine numbers to four games is the whole argument. Where it stops

Equal in this company

Equality quantifies over every game there is, and the quantifier can be made smaller. Restricted to a company of nine numbers, the twenty-two values born by day two collapse to seventeen; restricted to four games — nought, one, minus one and star — they stay twenty-two, and no three of the four will do. The company that decides equality is tiny, and it has to contain a star.

 What the reduction collapses. Each reduced form with the values that reduce to it. The largest class is the one that reduces to zero and it holds every infinitesimal on the list, which is exactly what the reduction is for — against a hot background, none of them is distinguishable from nothing. Sums and comparison

What is left when the small change is thrown away

Canonical form answers a demanding question: which positions are interchangeable inside every sum whatever. A player with a hot board does not have every sum — an infinitesimal difference cannot decide anything against a genuine fight — so there is a coarser question with an exact answer. The reduced canonical form takes the 1,474 values born by day three to 61, with 292 of them collapsing to zero, and it is a homomorphism on all 8,100 pairs tested only when a second pass is made.

 The move that stops the other one. Six local fights, each placed beside an environment of known temperature. The last two columns are the band over which taking the local move beats spending the move outside, and the band over which the opponent's move in the same fight has to be answered. They are not the same band. Temperature

What a move nobody makes is worth

If Right's move in a fight has to be answered, then Left's move in the same fight prevents an exchange Right was going to get for nothing. That is a reverse sente, and pricing it is the awkward case: over sixty measurements the gain matches the local temperature once and the follow-up's swing twice, and the band over which the move is worth taking is not the band over which the move it reverses is sente.

 When the regions add. Every board in the independence census — 117 positions whose empty points fall into two or more regions — tested against a stated criterion and against the guess it replaces. The criterion is that no stone group has liberties in two different regions, which makes a move in one region unable to change what is legal in another. It holds on 9 boards and the regions add on every one of them. Particular games

When the regions add

The rung below described the NoGo boards whose regions add as the ones with symmetric walls, and said the description was a guess made from six examples. It is wrong: fourteen symmetric boards do not add and sixteen that add are not symmetric. What replaces it is a criterion about liberties — sound on all 117 boards, provable in a line, and complete on only nine of the twenty-four.

 How hot a background has to be. Every pair of values born by day two that share a reduced canonical form, added to backgrounds of seven temperatures and three means — 609 comparisons in all — with the count of pairs whose outcome the swap changes. Safety is not monotone in the background's temperature, so the threshold the question asks for does not exist; every one of the 48 changes is at a position with a stop exactly on nought. Sums and comparison

How hot a background has to be

The reduced canonical form throws away infinitesimals, and the rung below asked for a bound: how hot must the rest of the board be for the discarded part not to matter? There is no such bound. Safety is not monotone in the background's temperature — an eighth is safe, a quarter is not, two is safe again — and the quantity that does decide it is not a temperature but a stop.

 What a finite closed company is made of. The finite closed companies found by the search, counted by the properties they share. Every one of them consists of games equal to their own negatives and has a size that is a power of two, and not all of them are made of nimbers. Where it stops

The company that is closed

Restricted equality licenses substitution only inside a company closed under addition, and none of the five companies this site computes in is closed — day two keeps a quarter of its own sums. Searching for companies that are closed finds seven, at one, two, four and eight members, and every member of every one of them is its own negative.

 When the players stop taking coupons. Every pair of fights from a pool of nine, played beside a coupon stack, with the coupon standing when somebody first plays on the board. Sixty of the eighty-one leave exactly when the coupon falls to the board's temperature. Temperature

When to leave the environment

A Go player's question is not which fight to take but when to stop taking the small stuff. Put two fights beside a stack of coupons and the orthodox answer — leave when the coupon falls to the hottest temperature on the board — is exact on sixty of eighty-one pairs. All twenty-one departures have a fight with a follow-up in them, and every pair of plain switches leaves on time.

 The second closure picks out the nimbers. The seven finite companies closed under addition, tested for closure under forming options. The four that are groups of nimbers keep every option; the three containing plus-or-minus one lose theirs. Where it stops

The closure that picks the nimbers

Closure under addition lets a sum be rewritten and turned out to admit companies that are not nimbers at all. Closure under forming options lets a subposition be rewritten, and it pulls the other way: every company this site computes in has it and none has the first, and among the seven finite addition-closed companies, keeping every option is exactly being a group of nimbers — four of seven, both directions, no exception. Demand both at once and nineteen of twenty-two day-two values generate nothing finite.

 How often one position beats another. Misère comparison inside each ruleset's own universe. A quarter to a half of ordered pairs compare, and the ruleset that is not dead-ending is in the middle of the range. Where it stops

What the class does not buy

Dead-ending is the hypothesis several modern misère results are stated under, and the rung below sorted this site's games into it without running the comparison those results are about. Running it: a quarter to a half of ordered pairs compare inside a ruleset's own universe, which is a great deal — and the ruleset that is not dead-ending sits in the middle of that range. Ten comparisons are lost when a universe is enlarged, and every one is lost to a dead-ending company.

All themes