Combinatorial Game Theory
who wins, and by how much
Theme

The thread: The theory runs out — page 2

Misère play, scoring, three players and computational hardness each break something essential. Knowing which of them is biting is most of knowing where a game stands.
The same population counted twice. The temperature scale over the positions this site has enumerated, once with every position counted and once with every distinct value counted. The two disagree about how much of the subject is hot, about what the commonest hot temperature is, and about whether a number is the usual thing for a position to be worth. Temperature

How hot a real position is

Counted one value at a time, a tenth of the subject is hot. Counted one position at a time — every board this site has enumerated, all 11,397 of them — it is a twentieth, two thirds of the positions are worth numbers outright, and ten of the seventeen rulesets never produce a hot position at all.

 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.

 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.

 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.

 How old a value is, against how big a board it takes to show it. For each birthday, the range of sizes of the smallest position exhibiting a value of that age. The bars do not march rightwards: values born on the last day of the sweep are shown by six-piece positions, and values born on the fourth need up to fifteen. Values

The cheapest way to show a value

Eleven thousand positions from fifteen rulesets reach 1,193 values, and for each of them there is a smallest board that shows it. Set against the birthday the two measures agree hardly at all — until the numbers are taken out, at which point they agree rather well, and the whole apparent independence turns out to be a fact about integers.

 Every saltus in the two-digit family. The constant added each time round, over all 255 two-digit hexadecimal codes. Forty-eight codes add one, thirteen add two, six add four and three add sixteen — and one code adds three. Impartial games

A code that climbs by three

Five hexadecimal codes were known to repeat with a constant added, and every one of the five constants was a power of two — either a fact about exclusive-or or a coincidence over five cases. Sweeping all 255 two-digit codes settles it: seventy-one climb, seventy of them by 1, 2, 4 or 16, and one by three. The exception is ·3f, whose values are 3⌊n/6⌋ + (n mod 3) on every heap to twelve hundred.

 Two conditions, one of which survives. Two candidate conditions on a pair of subtraction lists, scored over all 961 pairs drawn from one to five. Translation holds on 83 pairs and every one of them repeats; all-odd holds on 49 and four of them do not. Particular games

The condition that survived the wider sweep

Which pairs of subtraction lists have a value sequence that repeats? Over the 49 pairs drawn from one, two and three, two conditions answer it identically — a translation and all-odd — and both are exactly right. Over the 961 pairs drawn from one to five, all 83 translations still repeat with no exception and four all-odd pairs do not, at heap ninety with a period as long as forty-two. Neither condition is necessary: 104 pairs repeat that satisfy neither.

 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.

 Four second parts, and none of them enough. The residues paired with each of four further counts, at three caps, with a move taking from two heaps. Every pairing leaves classes containing both a win and a loss. Impartial games

The wider move is the easier game

An earlier essay ruled out every rule that reduces the heaps and reads the residues, and asked for a two-part statistic: the residues plus one more count. Four second parts are tested here and none of them decides. What turns up instead contradicts the premise the request was made under — a move that may reach three heaps is more predictable than one that may reach two, on every cap, every candidate rule, and after the change in the base rate is taken out.

 Climbing is the ordinary case. The two-digit and three-digit hexadecimal families, each swept for exact and arithmetic periodicity. Seven in ten of the settled three-digit codes repeat with a constant added. Impartial games

The third digit

The rung below found 71 of the 255 two-digit hexadecimal codes repeating with a constant added rather than exactly, and asked whether the same share holds one digit wider. It rises. Of the 4,095 three-digit codes, 1,433 climb and 617 repeat exactly — seven in ten of the settled ones — so a saltus is the ordinary way a hexadecimal game settles and the exact repetition the octal survey was built to find is the special case.

 What each reach answers. Catalogues of four to ten squares against the regions four sizes of board actually produce. The coverage rises from about 54 per cent to about 74 while the catalogue grows from 15 shapes to 12,871. What it costs

Where to stop building

The rung below priced a catalogue of small regions against the search it replaces and found the crossover. What it could not say is how far to build, and the coverage answers that: going from four squares of reach to ten multiplies the catalogue by 860 and lifts the share of regions it answers from 54 per cent to 74. The price of a point of coverage runs from five shapes to five thousand.

 A function on the wild side too. Every pair of heaps filed by the pair of genus symbols it is made from. No file holds two different sums, including the sixteen with a wild symbol in them. Where it stops

A function with no formula

The rung below's composition rule is exact on tame pairs and wrong on all fourteen wild ones, which looked like an exact boundary. Two heaps further it is wrong on 34 of 35 and right on one — Kayles' five and nine — so the boundary was a boundary of the pool. What survives is stronger and stranger: the pair of symbols still determines the sum on the wild side, and no rule of that shape describes it.

 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.

 Two orders of magnitude. The share of positions of a size whose value is one no smaller position exhibits. Every Hackenbush string is a new value and fewer than one Clobber row in a hundred is. Values

The rate was the alphabet

The rung below asked for a quantity a size cap cannot censor and proposed the rate: how many new values a ruleset produces per extra square. The rate is honest and it measures the notation — every ruleset grows at close to the number of symbols its positions are written in, and the seven span less than a factor of two. What separates them is the yield, which spans a hundred and nineteen.

 Thirteen sweeps, four thresholds. The mobility rule's failures on every board and depth the sweep can afford, with the threshold each one gives. The thresholds take four different values and no ordering of the boards produces them. Values

A threshold is a detection limit

The rung below had two points — a margin of three at fifteen squares, four at eighteen — and asked whether the mobility rule's threshold grows with the board. Eleven more sweeps say no property of a board orders the thresholds, that the same board at two depths gives two of them, and that a tenth of the sweep which produced the four reports three instead. What does move, on every board measured twice, is the depth.

 One-sided, all three. The three option tests with their disagreements split by direction. None ever refuses a comparison that holds. Where it stops

Wrong in one direction only

The rung below asked for the simplified comparison test the dead-ending hypothesis is supposed to license, and predicted it would agree with the quantifier on the dead-ending rulesets and not on Toads and Frogs. Written three ways and scored on 492 pairs, it agrees best on the ruleset that is not dead-ending — and never once refuses a comparison that holds, which makes it a sound filter and not a test.

 Who gains, and how much. How much each test improves when dead-endedness is turned on, with the class-specific test beside the others. Where it stops

The clause that turns the class off

Three rungs failed to find the dead-ending class doing measurable work, and each time the population was blamed. Toads and Frogs with and without the jump is the matched pair the anchor wanted — the same board with the class switched on and off — and on it the test the class licenses gains less from the class than a control that has never heard of it.

 Five of six. The six predictions made for seven heaps by the difference reading, each scored against the sweep that was declined at the time. Impartial games

The family with two witnesses

Six predictions about seven heaps were written down and deliberately not run. Five of them held. The one that broke is the condition that had been checked against two cases when it was proposed — the fewest of the four — and at seven heaps it does not merely give the wrong answer, it asks a question the parity word has stopped being able to answer.

 A pairing no motion of the square gives. The smallest Cram shape carrying a pairing that is not a rigid motion, with its three pairs drawn as lines between the squares they join. Impartial games

A pairing that is not a symmetry

Every pairing strategy this ladder has found is a rigid motion of the square, and the requirement mentions no geometry at all. Searching all 8.8 million fixed-point-free involutions instead of the eight maps more than doubles what a pairing explains — and the smallest new one turns out to be a reflection with its two fixed squares swapped.

 One of the two quantities is inert. The candidate predictors of a pre-period's length, each scored by correlation against the measured length. Impartial games

The quantity that carried nothing

The rung below proposed predicting a pre-period's length from the saltus and the period. The saltus correlates with it at −0.03, which is nothing; the period correlates at 0.77 with a coefficient of one, so a pre-period is about one period long. The digit that predicts whether there is one predicts nothing at all about how long.

 The counts, beside what happened next. The hottest Domineering region of each size with the number of shapes attaining it, and whether the next size was hotter. Temperature

A description, and not a detector

The rung below noticed that the count of shapes attaining the hottest temperature grew across a plateau and collapsed at the step, and proposed it as a way to read a plateau off a single size. The growth is exact — five plateaus, no exception — and the rule is impossible: five orbits precede a rise at seven squares and no rise at eight.

 Neither quotient identifies anything. The number of misère-equivalence classes on each side of the matched pair, against the number of distinct positions. Where it stops

A quotient that identifies nothing

The dead-ending class is famous for quotients rather than comparisons, so the matched pair was asked the question its own subject is about. Neither quotient identifies a single pair of positions, and both are separated by exactly five addends — because a quotient is small when its universe is poor, which is a choice of company and not a property of a class.

 One set, described three ways that share no arithmetic. Wythoff's cold positions can be stated as the Beatty pairs of the golden ratio, as a greedy construction over the integers that mentions no constant, and as a condition on Fibonacci numerals. None of the three consults the game. The fourth column is the game — a mex table over the moves — and all four name the same set of cold pairs over the whole square, which is what the figure counts. Out in the world

A set with three descriptions, and a function with none

Wythoff's cold positions can be written three ways that share no arithmetic — an irrational constant, a greedy rule, a condition on Fibonacci digits — and all three are exact. The same game's Grundy values have no closed form at all. Both facts are about one table, and the gap between them is the subject.

 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

Where the numeral stops

A Hackenbush string is a numeral and a tree is a trunk with a forest on it, so the obvious next question is a graph with a cycle in it. Green Hackenbush answers that by fusing the cycle to a point. In blue and red the fusion is right on every three-edge cycle, on fewer than half of the six-edge ones, and the smallest thing it gets wrong has four edges.

All themes