Combinatorial Game Theory
who wins, and by how much
Theme

The thread: The theory runs out — page 4

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.
One misère outcome, searched. The number of positions a misère search visits to decide the outcome of a sum of k heaps of Dawson's chess, each heap at most 9, on a logarithmic scale: the average over the sums and the worst single sum, for k from one to eight. Normal play decides the same sums from 20 stored values. What it costs

A misère sum is searched, not added

Under normal play the outcome of a sum of heaps is a nim-sum of numbers already known: twenty stored values decide every sum of Dawson's chess with heaps up to nine, however many heaps it has. Under misère play each sum is a new position to search. One outcome costs six positions for a single heap, two hundred for four heaps and over five thousand for eight, and a table of every eight-heap outcome costs a hundred thousand. The misère quotient is the only thing that brings the price back down.

 A staircase, not a slope. The number of misère classes of Dawson's chess positions as the largest heap allowed rises from three to 16, computed with positions of at most three heaps and tests of at most two. The count stays flat for several heaps at a time and then jumps. What it costs

A staircase, not a slope

With the misère closure cut forty-fold, Dawson's chess can be classified at heaps far beyond nine. The count of classes is a staircase: six from heap three to eight, twelve from nine to twelve, seventeen from thirteen to sixteen. Normal play steps once in that range, from four to eight at heap thirteen, where a Grundy value of four first appears. Misère play steps there too, and once more at heap nine, where normal play does not move at all — the first wild heap. Heaps eleven, fifteen and sixteen are also wild and move nothing.

 Four positions, sampled. Three samples of three thousand loopy regions on four positions, drawn with each possible move present at a chance of one half, about a third and a quarter. For each: how many regions have both sides named by the thirty-five names two-position regions use, by those together with the thirteen invented for three positions, and how many need a new name. How it was found

Four positions, sampled

Ten names write both sides of every loopy region of two positions, and forty-eight every region of three. Four positions are over four billion graphs and cannot be counted, but they can be drawn. Three thousand regions at each of three densities: the forty-eight names cover between 95.9 and 99.5 per cent, the thirteen names invented for three positions come back at four almost all of them, and the sparsest sample meets thirty-five sides nothing earlier reproduces — a floor of eighty-three names, and a curve that grows by accretion rather than collapse.

All themes