Combinatorial Game Theory
who wins, and by how much
Theme

The thread: Not every game is a number — page 2

Some positions are worth a half or a quarter. Others are worth something no number can express, and the ones that are not numbers are where the subject becomes interesting.
How often one value is above another. The partial order counted on two successive days. The proportion of pairs that can be compared at all falls sharply, and so does the proportion of values that can be compared with zero — which is the proportion of positions whose winner does not depend on who moves. Sums and comparison

How rare it is to be bigger

Values are partially ordered, and 'partially' does most of the work. On day two, 179 of 231 pairs can be compared and 13 of the 22 values can be compared with zero. One day later the shares are 60% and 29%, and the largest set of mutually incomparable values found rises from four to at least twenty-three. Comparison is the exception; confusion is what values normally do to one another.

 Clobber: every value smaller than every number. Blue and red stones on a small board. A move takes one of your own stones onto an orthogonally adjacent enemy stone, which is removed. Because adjacency is symmetric, a player has a move exactly when the opponent does — so no position can ever be worth a whole move to anybody, and every value that comes out is an infinitesimal. Particular games

One row of Clobber

Every string of blue, red and empty squares up to eight long — 9,840 rows — carries one of only 111 values, and every one of them is infinitesimal. A third of the rows are worth exactly zero. Six alternating stones are worth zero and eight are worth a form that takes four lines to print, so the values do not simplify as the row grows: they explode, while the row stays trivial to describe.

 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. Values

The simplest game above both

Values sit in a partial order, and a partial order is entitled to be ragged: two things with no least thing above them. The 22 values born by day two are not ragged at all. Every one of their 253 pairs has a least upper bound and a greatest lower bound among the same 22, and the order is distributive on all 10,648 triples — so it is a lattice, and the join of zero and star is one half.

 Trees, and what each is worth. A row of blue-red Hackenbush trees with the value the recursion returns under each. Every one is a number, and none of them is the binary reading of anything a reader can see in the picture. Particular games

A tree is still a number

A Hackenbush string spells its own value in binary. Put a fork in it and the numeral has nothing to read — there is no leftmost anything. The value is still a number, in all 10,066 forests up to six edges; it is still computable, by the ordinal sum, in all 3,238 single-trunk trees; and the reading is right on 762 of them, of which 126 are the strings it was written for.

 What each move is worth to the player making it. For each position: every incentive, whether they are all strictly negative, whether the position is a number, and its temperature. The middle two columns are two different computations of the same fact. Values

Nobody wants to move here

A position is a number exactly when every move loses ground for the player making it. The test never mentions numbers, it disagrees with the ordinary one on none of the 1,474 values born by day three — and the reason a position fails it is not that somebody wants to move. It is that somebody cannot afford to wait.

 The same row, cut and toppled. Rows of blue and red drawn once and evaluated twice: as a Hackenbush string, where a player cuts an edge of their own colour and everything above it falls, and as Toppling Dominoes, where a player knocks one over and everything on the chosen side falls. Both values are computed by the same recursion from the two rulesets. Particular games

Topple it from either end

A row of blue and red is the picture this site opens with, and under Hackenbush's rules it is always a number. Knock the pieces over instead of cutting them — everything on the chosen side falls — and 480 of the 510 rows up to eight pieces stop being numbers. The two games agree on sixteen rows, every one of a single colour, and the temperature of the hottest row climbs by exactly a half for each domino added.

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

The other way to move a row

Shove has a cliff and Push has a wall, and that is the whole of the difference. Both games make every one of the 728 strips up to six squares a number, so neither ever has anything worth fighting over — and the two rules do not agree on the value of a single position. The obvious board-reading is exact on 446 strips under the wall and on 140 under the cliff, and 486 strips contain a coin its owner cannot move at all.

 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. Values

The values nobody's game produces

The construction hands down 1,474 values by day three. Seventeen rulesets on this site, swept to eleven thousand positions, produce 1,193 — and only 116 of those are on the construction's list. Two of the twenty-two values born by day two are produced by no position of any game here, and 1,077 of the values that are produced are born later than day three. A value's birthday and a value's reachability have almost nothing to do with each other.

 Every Domineering shape up to four squares. The pieces a partly played board falls into, each with the value the recursion gives it. Left plays vertically and Right horizontally, so a tall shape is worth something positive and a wide one something negative, and the quarter turn is not a symmetry of the game. Particular games

A board that is a sum of its regions

A table of rectangles is a table about the openings. A partly played Domineering board is not a rectangle, and evaluating one means splitting it into pieces no domino can straddle, looking each piece up and adding. The catalogue of 104 shapes does it correctly on every one of the 3,227 positions of a 3×4 board it covers — and among the shapes are two worth an up and a down, which no rectangle ever is.

 How hot a day gets. The hottest value born by each of the first three days, with every temperature that occurs on it. Day one tops out at nought, day two at one, day three at two — a day buys exactly one degree — and the value attaining the maximum is unique each time. Each temperature was computed as the height at which that value's two thermograph walls meet. The temperatures of day three are exactly the half-gaps between the numbers born by day two, which is what puts a hole in the scale at 7/4. Temperature

How hot a day gets

A day of construction buys exactly one degree of temperature — nought, then one, then two — and the value attaining the maximum is unique on every day: ∗, then {1 | −1}, then {2 | −2}. The distribution underneath is not tidy at all: it peaks at a half, leans to the right of the peak, and has a hole in it at one and three quarters where nothing is born.

 What the third colour reaches. Every row of Toppling Dominoes up to 7 long, over two colours and over three, with the number of distinct values each set of rows carries. Each value was computed by the recursion; the last column is the count of values three colours reach that two do not, cumulatively. Particular games

How long a row a value needs

Add a third colour that either player may topple and a row of seven dominoes reaches 1,047 distinct values where two colours reach 149. That makes the length of the shortest row worth a value into a measure of the value's complexity — one a reader can hold in their hand — and it is not the birthday: 1↑ is born on day three and needs seven dominoes.

 A sequence with a rule and no period. The values of the subtraction game with Left taking 1 or 2 and Right taking 1 or 3, from heap 5 up. Each is the game whose only Left option is nought and whose only Right option is the value three heaps below — checked at every heap rather than asserted, and the two heaps where it fails are the two below the seeds. Particular games

A sequence with a rule and no period

The values of the subtraction game where Left takes one or two and Right takes one or three never repeat — thirty-one heaps, thirty-one different values. They are nonetheless completely described: three seeds and the rule v(k + 3) = {0 | v(k)} generate every one of them, which is what a pattern without a period looks like.

 What a Domineering region is worth, by size. Every connected shape of at most six free squares, sorted by whether its value is a number, an infinitesimal distance from a number, or hot. Hot shapes do not appear at all until four squares, and the hottest shape of six is the two-by-three rectangle. Particular games

Which shapes are worth fighting over

Forty-four of the 104 Domineering regions of at most six squares are worth numbers and the rest are not, and the rung below said no visible property of a shape predicts which. Half of that is wrong: a region only one orientation fits in is a whole number, on all eleven of them, for a reason a reader can supply in a sentence. The other half stands, and thirty-three shapes are what makes it stand.

 How much of End-Nim is a Nim heap. Rows of End-Nim by length, with the share worth a nimber beside the share that are palindromes and the number of distinct values. The impartial share falls from all of the one-heap rows to a fifteenth of the six-heap rows, while the values multiply. Particular games

Where the nimbers run out

A single End-Nim heap is a Nim heap and every palindromic row is worth a nimber, so the impartial theory looks as though it might get a long way into a partizan game. It gets one row in thirteen. Five nimbers occur in five and a half thousand rows, the palindromes account for two fifths of them, and the rows worth something else run to 2,693 distinct values.

 The bend decides it. Whether the stop reading gives the mean and temperature, against whether either wall bends below the meeting point. Both off-diagonal cells are empty on all 138 values. Values

The bend is the condition

The rung below offered a description of the class its stop reading is exact on — neither wall bends below the meeting point — and a route to proving it: that a bend happens precisely when some option is neither a number nor an infinitesimal. The first is exact on all 138 values, both directions, no exception. The second is half right: every bent value has such an option and 49 unbent ones do too. And the eight apparent exceptions to the first turn out to be a bookkeeping convention.

 Almost none of them is a number. Every three by three Amazons region holding one amazon of each colour, sorted by what kind of value it carries. Fifty-six of the two thousand are fractions and the great majority are hot positions. Particular games

The fractions that were not there

The rung below counted 1,452 fractions among the shared Amazons regions and asked which fractions they are. Fifty-six of them are fractions. The other 1,396 are hot positions with a fraction somewhere inside their options, counted by a regular expression looking for a slash — and the quantity the separation of the two amazons actually sets is not a denominator but a temperature.

 The collapse happens twice. How many subsets, antichains and values there are. Domination takes 1,793 subsets to 96 antichains and the rest of the reduction takes those to 30 values. Sums and comparison

What identifies two subsets

Every subset of a day gives a self-negative value by mirroring it, and 1,793 subsets of day two give thirty values. The collapse happens in two stages with different characters: domination takes the 1,793 to 96 antichains and is a theorem, and the rest of the reduction takes 96 to 30 and is concentrated almost entirely on two values — nought, which has an exact description, and star, which has none.

 The yield, four sizes further. Toppling Dominoes rows to twelve, with the count of values not seen at any smaller size and the share of rows that is. Values

The mirror was the floor

Toppling Dominoes' share of genuinely new values had fallen from one to a half over eight sizes, and the rung below could not tell a floor from a slow fall. Four more sizes settle it: the distance above a half halves every two sizes. And the half is not a shortage of values but a symmetry — a row played from the other end is the same game, and the ruleset is as injective as that allows.

 Four moves, three arguments. Every first move in the sum, with what answers it and how many cases of each the census holds. Sums and comparison

The case that was supposed to be hard

The mex rule for the mirror construction was to be proved by induction, and the step flagged as needing care was the one where an option is incomparable with the nimber. There is no induction: the argument is four lines, and incomparability is what makes two thirds of the cases go through — because a fuzzy sum is a first-player win and the first player is the opponent.

 The value predicts on one residue only. Value-indexed rule selection on the silent decisions and on the seventy-two. Values

Close calls nothing resolves

The same value panel that settles 118 of the 202 silent decisions settles four of the seventy-two the rules get wrong. Every rule that helps at all must replace connectivity rather than follow it, and the cheapest one breaks twenty-six decisions for every one it saves.

 Same group, three different yields. The rulesets with a trivial symmetry group, which the conjecture predicts must all have a yield of one. Values

Three groups, and three yields

The conjecture was that each ruleset's yield tends to the reciprocal of its symmetry group's order. Three rulesets have a trivial group and predicted yields of one; they measure 1.000, 0.531 and 0.204. And every colliding value in Push and Shove — all 175 of them — has two rows no symmetry relates.

 Which clause of the rules produces which kind of value. Every combination of pawn-file clause in range, sorted by the kind of value it produces. Files where both pawns can advance are all-small and their values are nimbers and infinitesimals. A file where one pawn is stuck behind a friendly piece gives the other side free moves and is worth an integer. A file whose middle square can be held stops the other pawn the moment somebody reaches it, and is worth a switch — a position both players want to move in. The dictionary is read off the evaluation rather than asserted. Out in the world

What has to break before a pawn is worth a number

Every value the blocked-file model can hold is an infinitesimal, and the reason is one sentence about the move rule rather than anything about pawns. Break that sentence — a pawn stuck behind a friend, a square only one side can hold — and integers, switches and positions worth fighting over arrive at once.

 What the flip is worth, and what is at stake. Left's chances if Left moves and if Right moves, with the gap between them beside the position's temperature. The two are answers to the same question computed by different routes, and they do not order the positions the same way. Where it stops

The coldest position has the biggest swing

How much a flip is worth is the gap between the coin's two branches, and it is a rival to the temperature — both answer how much is at stake. They disagree at once: the empty position has the lowest temperature there is and a swing of one, twice the hottest thing born on day two. On the small pool the two quantities look like a perfect three-way correspondence, and 255 of day three's values break it.

All themes