Combinatorial Game Theory
who wins, and by how much
Theme

The thread: What a search costs — page 3

A value is worth what it costs to find. These essays price the search rather than quoting the answer: positions visited, states stored, and the size of the board where the counting stops.
The same plays, a different chooser. Two trees with a ringed starting vertex. From each start edge geography can end after 2 moves or after 3, so the multiset of maximal trail lengths is the same, but on the first the player to move chooses the long play and wins, and on the second the first move is forced and the opponent chooses the short one. What it costs

The plays do not say who chose them

Every way a game of edge geography can go is a maximal trail, and the parity of each trail says who moved last. So the list of their lengths ought to decide the game, and over every connected graph to six vertices it nearly does — 780 of 810 starts, 108 of 114 on one cycle, where no rule on the matching and the cycle reached 91. It still fails, and the smallest failure is two trees: the same two plays from each start, and a different player choosing between them. Keep that choice one move at a time and the ambiguity falls from eighteen profiles to seven, one and none. The list costs sixteen times the search.

 The second temperature, with the threat on top. Hottest-first play against the best reply on four pools whose hottest component is a threat of the form {10 | {8 | 0}}, with a switch just below it and a smaller threat below that. Over 2,254 lines the cost never exceeds the second-largest temperature on the board and meets it exactly on 97. What it costs

The price of a tie

The second-largest temperature bounded hottest-first play on 14,946 lines, and the pool that should have broken it puts a threat on top. It does not break: over 2,254 more lines the cost never passes the second temperature and meets it on 97. What the pool finds instead is where the rule goes wrong — one move into the game about as often as at its start — and why. Almost every line that meets the bound is a tie: two parts equally hot and the rule taking the first on the board. Break ties well and the lines meeting it fall from 636 to 51 on the earlier pools, and to none on any board with the threat on top.

 The odd values do not stop. The odd Grundy values of the octal game ·354 counted in blocks of ten thousand heaps to 100,000. The first block holds 314; every later block holds between three and eleven, and the last odd value in range is at heap 99,600. Impartial games

The odd values keep coming

·354 is the one growing octal code of up to three digits whose values have a class that thins: 288 odd values in the first two thousand heaps, seven between ten and twenty thousand, the last of those at 18,908. A sparse-space argument needs that class to stop. Taken to a hundred thousand heaps it does not: 48 more odd values arrive after twenty thousand, every block of ten thousand holds some, and the last in range is at 99,600. They keep no schedule a remainder can see, their gaps are spread like arrivals, and most of them are one number, 37 — each one a heap where every split that could have reached 37 misses it.

 The pairs level and the order does not. Corrected day-four figures under two recipes beside the honest day-three figures, for samples of 120. The share of comparable pairs is unchanged within its error; chains of three fall, wholly confused triples rise from 12.2% to about 14.8%, and the width rises from 19.7 to 29.4 and 30.3. Sums and comparison

The pairs stand still and the order spreads

The share of pairs of game values the order can compare falls from 77.5 per cent on day two to 60 on day three and then stops: built twenty times under two recipes and calibrated, day four sits within two standard errors of day three. That looked like a floor under the order. Measured beyond pairs it is not. Chains of three keep falling, triples with no comparable pair keep rising, and the largest set of mutually confused values in a sample of 120 grows from about 20 to about 30 — every one of forty seeds wider than day three's mean. The floor belongs to one statistic, not to the order it summarises.

All themes