Combinatorial Game Theory
who wins, and by how much
Theme

The thread: The parts do not decide the whole — page 2

Outcomes do not add. Neither do temperatures, atomic weights, misère outcomes or the value of an auction. Which quantities survive being added is the question every method here turns on.
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. Where it stops

What a component has to carry

Three impartial games on this site break the sum, and they break it for the same reason: a component cannot say what its own legal moves are. Measured with one instrument — one number per part, exclusive-ored — the failure rate runs from a quarter to nearly half, against a control where the same recipe is a theorem and is never wrong.

 The number nobody needs. The shortened selective compound — move in any non-empty set of components, and the game stops as soon as any one component stops — solved directly on 1,176 three-heap positions across four subtraction sets, with four predictions beside it. The suspense number was introduced for this compound and it is right; so are three cheaper things, and the shortening leaves the winner unchanged. Sums and comparison

The number nobody needs

The compound theory carries a third quantity — the suspense number — computed by the remoteness recursion with both preferences reversed, for the compound that stops as soon as any component stops. It governs that compound correctly. So does remoteness, so does the plain Grundy value, and the shortening does not change the winner on any of 1,176 positions.

 The identity that would join the order to the addition. Every pair of the twenty-two values born by day two, asked whether the join plus the meet equals the sum. It holds on all 201 comparable pairs, where the join is the larger and the meet the smaller and it cannot do otherwise, and on none of the 52 incomparable ones. Values

Where the order and the sum disagree

Day two is a lattice, and day two is a group, and it is not a lattice-ordered group. The one identity that would join the two structures — the join plus the meet equals the pair — holds on exactly the 201 pairs where it cannot fail and on none of the other 52, and the errors split thirteen high, thirteen low and twenty-six confused.

 One number per heap, and one number per state. Sums of Fibonacci Nim components solved in full, against two predictions. Giving each component the number its heap size suggests gets a quarter of the pairs wrong; giving it the Grundy value of its state — the pair of heap size and cap — gets every pair and every triple right. Where it stops

What restores the theorem

Fibonacci Nim breaks the recipe every impartial game is supposed to obey: one number per heap, exclusive-ored, gets a quarter of two-heap sums wrong. Index the recursion on the pair of heap size and cap instead and the recipe is exact on every pair and every triple — and the number a heap of nine carries turns out to be five rather than one.

 Fifty-two errors, put to four instruments. The fifty-two discrepancies the lattice identity leaves on day two, counted by what distinguishes them. As values no two are the same; as pairs of stops there are seven; as means three and as temperatures three. Not one of them is a number, and only three are values born by day two. Values

Fifty-two errors and seven sizes

Day two is a lattice and a group and not a lattice-ordered group, and the fifty-two incomparable pairs it fails on leave fifty-two different error terms. Measured rather than listed, the fifty-two collapse: seven pairs of stops, three means, three temperatures, and a rule that predicts the temperature from the pair on forty-four of them.

 How much a domino count knows about a region. The difference between the two players' largest domino packings, set against the value of the region. On the regions worth numbers the count is the value under half the time; on the rest it lands somewhere between the two stops on 85 per cent of them. Particular games

Counting the moves each side has

How many dominoes could each player still place? Subtract, and there is a whole number computable from the drawing with no game theory in it. Over 1,042 regions it is the value on 141 of the 315 worth numbers, lands between the stops on 619 of the other 727, and its failures are two different kinds — one of which was inevitable and one of which is a fact about the game.

 Thickness is not the variable; the wall's own groups are. The same strips split by whether the wall is all one colour. A wall of one colour is a single group with liberties on both sides and it never separates them, at any thickness. A wall of two colours is two groups breathing in opposite directions and it nearly always does. Particular games

How thick a wall has to be

A single stone between two empty stretches of a NoGo board couples them, and the obvious repair is a thicker wall. Over 590 walled strips a thicker wall does help — and splitting the same 590 by the colour of the stones shows that thickness was never the variable. A wall of four one colour couples the sides exactly as one stone does.

 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.

 Four candidate bounds, and the one that holds. Each candidate bound tested against every failing cut. One domino and the height of the cut both fail on six; twice the height holds on all twenty-two; the whole board's temperature fails on eighteen. Sums and comparison

How wrong a nearly-independent split is

Treating a connected board as a sum of two halves is a claim, and the rung below counted how often it fails. This one prices it: over every vertical cut of every small Domineering rectangle the error is a game rather than a number, it is never in Right's favour, and it is bounded below by twice the height of the cut — a bound the height alone does not supply.

 The repair, and where it stops working. Reducing each heap modulo one more than the cap and then applying Moore's column condition, checked against the search. It is exact at every cap when a move touches one heap and wrong at every cap when a move touches two or three. Impartial games

The rule a smaller move breaks

Moore's Nim lets a player take from at most k heaps, and its winning condition is the binary columns summed modulo k + 1. Cap the amount as well and the obvious repair — reduce each heap modulo the cap plus one, then read the columns — is exact at every cap when k is one and wrong at every cap when k is two or three. The reason is stronger than a broken rule: at k ≥ 2 the residues do not determine the outcome at all, so nothing of that shape can work.

 When a catalogue starts paying. How many decomposed boards a catalogue of regions has to answer before building it costs less than searching each board directly. Five boards for regions of four squares, two hundred for regions of eight. What it costs

When the catalogue starts paying

The rung below priced two questions — who wins one board, and what it is worth — and named the third: a program pays for a family of regions once and answers every board over them by addition. The crossover is between five boards and two hundred, depending on how far the catalogue reaches, and it falls as the board grows. The whole catalogue of every region to eight squares costs one part in seventy-six of one undecomposed five-by-five board.

 The bound that needed no third number. The rung below's bound and the conjectured replacement, scored over 1,440 sums whose addend has a follow-up. The two-number bound holds everywhere and is attained; the three-number one fails. Sums and comparison

A bound with one number too many

The rung below bounded how far a hot addend can drag a stop — twice the smaller of the two temperatures — over sums whose addends were all plain switches, and conjectured that an addend with a follow-up would need twice the smaller of three numbers. Over 1,440 sums with bent addends the two-number bound holds everywhere and is attained 358 times, and the three-number version fails on 66.

 Not closed, and not nearly. Where the table's answers live. None is a symbol a wild heap carries; some are symbols tame heaps carry; the rest are symbols nothing in the sweep carries. Where it stops

The wild side does not close

The rung below asked for the wild composition table and for two things about it: whether the wild genus symbols form a small closed set, and whether that set is a misère quotient in disguise. Building the table needed a wider sweep — nine counters a heap gives a diagonal rather than a table — and both answers are no. Not one of the twelve entries is a symbol any wild heap carries, and two wild heaps added together are tame two thirds of the time.

 The theorem a proof would have needed. The mobility rule's failures on decomposed positions against connected ones, across every board in the depth sweep. Values

The easy case was not the reason

The rung below found the mobility rule reaching a failure rate of exactly nought near the endgame and named what a proof would need: that a decomposed board's comparable options are ordered by reply count. That statement is false on all five boards, at margins up to two — and split positions go exact two squares of depth before whole ones, so decomposition is the easy case rather than the cause.

 The bound survives and the rule does not. The census against the widened sweep, with the bound and the two-line rule scored separately on each. Sums and comparison

One expression proved, and one withdrawn

The census closed with three expressions exact on 1,440 pairs, and the rung above asked for derivations. The cold one has a four-line proof. The straight one has a threshold the census cannot determine — any constant between 4/3 and 3/2 fits it — and eight more addends of the same family break it on 38 pairs while leaving the bound above it untouched.

 One number, two statements. The smallest true bound on the cost of splitting a board, in both of the currencies it can be stated in. Sums and comparison

One number, stated two ways

Twice the height of the cut held and was loose; the height alone failed. The smallest true constant is three halves — exact and attained as a bound on how far the value can fall, and an infimum attained nowhere as a bound on the value. The gap between the two is one move.

 The threshold is one whole move. The prefixes grouped by their own value, against the rate they produce behind LRRL. No value class splits, and the boundary falls exactly at one move: three quarters of a move is not enough and one move is, with nothing between them. A fractional advantage does not reach across a gap that grows without bound and a whole move does. Particular games

A fraction does not reach

Two Push tails read their prefix when every other tail ignores it, and the previous rung guessed the deciding bit was a shape — whether the prefix's last coin stands alone. The full census says it is a number. The rate changes exactly when the prefix is worth a whole move, and three quarters of a move is not enough.

 The offsets, and what they separate. The junction descriptor of each member of two split groups, beside the value each holds. Particular games

Three distances too many

The junction descriptor records how far a crossing sits from four ends, and the rung below asked what the value does when one crossing slides along its run. It reads one bit — the offset's parity — and only when the run has odd length. The other three distances reach the value not at all.

 One board, two answers to how many pieces it is in. Every position reachable from a small Amazons opening, counted by depth, under two ways of deciding whether two squares are in the same region. Counting only edge neighbours, a third of all positions are in pieces; counting corners too, an eighth are. What it costs

A wall an amazon can walk through

An arrow burns a square for good, so an Amazons board that has fallen into pieces should stay in pieces. Over 127,583 positions it does not: fifty-one thousand moves put two regions back together. Every one of them is a single diagonal step, and what is wrong is not the game but the rule used to find the regions — which was borrowed from a game whose pieces lie along the board's own lines.

 Two clauses, and what each is about. Four rulesets against the two clauses of the condition. A ruleset passes both or the one-number-per-component recipe fails on it, and the two clauses fail for different reasons: locality is about the state proposed, isolation is about the rule. Where it stops

Two clauses and a third question

A component can carry its own rule when two things hold: its moves are a function of what it carries, and a move in it leaves every other component alone. Two rulesets built to fail one clause each are both caught on a named witness. The four real games sort exactly — every one the recipe gets right fails no clause, every one it gets wrong fails one — and the two clauses still miss something, because Fibonacci Nim and a held pass fail the same clause and only one of them can be repaired.

 A criterion that does not lift. The NoGo separation criterion run on strips and on three-row boards. On strips it holds on nine boards and explains all nine independent ones. On 227 three-row boards it holds on none at all. Particular games

A wall that bends

On a NoGo strip, two empty stretches add when no group breathes into both — a wall of two stones of different colours does it, and the criterion explains nine of ninety-three boards and all nine that it covers. On a three-row board it explains none of 227, and not because it is less accurate. A wall across a board has to bend, a stone at the bend sees empty squares on both sides by itself, and every one of the 227 has a group breathing into both regions. The condition is unsatisfiable.

 Where the two diagrams part. Pairs of hot day-two values with the true thermograph of their sum against the one made by adding the components' walls. Every pair parts, and every pair parts at the lower of the two temperatures. Temperature

The second bend is the boundary

Adding two thermographs wall by wall gives a diagram that is right at the mast and wrong below it. Over every pair of hot values born by day two, the added walls sit outside the true ones at every height — an outer envelope with the truth somewhere inside — and the two pictures separate at exactly the lower of the two temperatures, on all twenty-eight pairs. Above that height both components are still fights and the addition is exact; one sixteenth below it, every pair has parted.

 What one king costs a decomposition. Two pawn files and one king a side, solved as a joint position and again as the sum of its files. With the kings unable to move the two answers agree on every configuration, because a king that cannot choose between files is not a shared resource. Give each king a waiting move and the answers come apart, and on some configurations the sum of the parts names the wrong winner rather than merely the wrong value. Independence is a hypothesis about the position and this is the price of assuming it wrongly. Out in the world

One king, and two files to be in

The whole apparatus needs the files to be independent, and a king is what makes them not. With the kings unable to move the sum of the parts is exact on every configuration; give each king a single waiting move and the sum names the wrong winner on one configuration in six, and on a hundred and twenty-six of two hundred and forty-three with three files.

 A ko fight decided somewhere else on the board. A ko fight against the number of ko threats each side holds. A threat is a play elsewhere that the opponent must answer, and it lifts the prohibition on recapturing, so a player short of threats runs out of ways to come back. Every cell is a full retrograde labelling and the pattern in them is read off afterwards: the fight goes to whoever is ahead on a quantity that is not on this part of the board at all. Where the labelling never settles, the fight is a no-result whatever anybody holds. Out in the world

A ko is won somewhere else

The rung below shows the ko rule buying finiteness by deleting one edge. What it buys with the same edge is a fight nobody can settle by looking at it — the prohibition forces a player to spend a threat, threats are counted on the rest of the board, and every decided cell of the sweep goes to whoever is ahead on a quantity that is not in the picture.

All themes