Decomposition — where it appears
Named by 93 essays across 9 fields — each of them below, with the objects they name alongside it.
How hard is it
Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves.
The game in every exercise book
Dots and Boxes is played by more people than every game in this collection put together, and everybody is taught the same rule — take every box available. The rule is wrong. Establishing that takes a solver rather than an opinion, and the solver says how wrong, on which boards, and by how many boxes.
Domineering
One player places dominoes vertically, the other horizontally, on a shared grid. The rules take one line, the values are a mess, and that mess is the point — this is what the theory looks like applied to a game nobody designed for it.
The chains decide it before the boxes do
Under every game of Dots and Boxes there is an impartial game with no score in it, and it settles the question the scoring game keeps asking — who ends up having to open. The rule players learn as folklore falls out of it, and so do the exceptions nobody mentions.
The board falls apart, and the arithmetic changes
A 4×5 Domineering board with a wall down the middle has 2,916 positions in it, and that number is exactly 54 × 54 — the product of its two halves. Solving the halves separately costs 108. Decomposition is the one saving in this subject that turns a product into a sum.
The endgame, accounted for
Add up what each region is worth, then add the biggest thing at stake, subtract the next, and so on down. On a board of simple fights the result is exact — and the moment one region has a fight inside it, the account is out by a point.
A winning strategy that is a spanning tree
The Shannon switching game was sold in a box in 1960 and solved in 1964, and the solution is not an assertion that somebody wins. It is a property of the graph anybody can check, and the strategy falls straight out of it — whichever link the opponent cuts, take its partner in the other tree.
Amazons, and when a position becomes a sum
Every technique on this site starts from a position already broken into independent parts. Amazons does not begin that way — the board is one fight until the arrows cut it, and the moment of cutting is something the play produces rather than the analyst assumes.
Three ways to add the same games
A move in exactly one component is a choice, not a law. Move in every component at once and the game is different; move in any set of them and it is different again. The same two positions, added three ways, give three different answers — and only one of the three has values that add.
Squash every loop to a point
Colour every Hackenbush edge green and the game becomes impartial, so the whole picture is worth a single Nim heap. Two principles find which one without playing anything — fuse the cycles, then run one pass up the tree — and a nine-vertex lattice that costs 1,283 positions to solve costs twelve steps to read.
A pawn ending is a sum
In a blocked pawn ending the material is level, the files never speak to each other, and whoever has to move is the one in trouble. Chess calls that mutual zugzwang; this site calls it a P-position; and the two vocabularies were built four decades and one subject apart to say the same thing.
Independence is a claim
Splitting a position into parts and adding the values is the whole method of this subject, and the splitting step is a claim about the position rather than a fact about the drawing. Where it is false the two answers differ — and the failures that matter are the ones that keep the same winner and change the value, because nothing reports those.
The tartan theorem
The nimbers are a field, with a multiplication defined by a mex-style rule that looks like an algebraist's amusement. Lay two coin-turning games on a grid and the Grundy value of each square is the nimber product of its two coordinates — which is the point at which the multiplication stops being a curiosity and starts computing answers.
When a real board falls apart
Amazons is played competitively, and late in a game the arrows have cut the board into regions no piece can cross. From that moment the position is a disjunctive sum — arrived at by the play rather than assumed — and the territory count every program uses can be measured against what the sum is actually worth.
The values of every small board
Thirty Domineering rectangles, every value computed from the moves rather than looked up. The 1×n row obeys a formula and the 2×n row does not: its outcomes run L N N R three times over and then 2×13 comes out worth exactly 0, and its temperatures climb to 19/16 and fall back without settling.
A token on a graph
Geography is an impartial game whose position is a vertex and a history, so a ten-vertex graph has ten thousand states rather than ten. Take the arrows off and the same game is decided by a maximum matching — first player wins exactly when every maximum matching covers the start, verified on 41 vertices across eight graphs. One word in the rules separates a polynomial criterion from a PSPACE-complete problem.
Amazons on one line
A board one square high is small enough to evaluate completely: every strip from two to ten squares with one amazon a side is 37,886 positions taking 81 distinct values, and every one of them is an integer, a switch, a number plus a star, or a bare star. Not one is a fraction — and forcing the arrow onto the square just vacated, which takes a freedom away rather than adding one, produces 1,196 that are.
Finding the parts
Decomposition turns a product into a sum and is the largest saving in the subject. Nobody labels the regions. The pass that finds them costs the same on every board of a size — including the boards where there is nothing to find — and what it buys ranges from four orders of magnitude to nothing at all.
The code names the move
If the lost rows of a coin-turning game are a linear code, then a won row is a codeword with errors in it and the winning move is whatever turns the errors off. Over all 256 rows of Mock Turtles on eight coins: 16 codewords, 240 won rows, none more than two coins from a lost one — and 64 of them whose cheapest winning move has to turn three coins anyway.
When the nested sum only sees the value
The ordinal sum reads the form and not the value: three positions all worth zero, placed under a star, give three different answers. On impartial games it reads the value after all — 72 substitutions of an equal-valued heap from a different game, and every ordinal sum comes back unchanged. That difference is the whole reason a green Hackenbush tree can be collapsed one branch at a time.
What can be struck out
From G + X = H + X it follows that G = H, in one line, by adding −X to both sides. It is the shortest theorem here and the most used: it is what makes comparing two boards region by region legitimate. Over 10,648 triples the hypothesis fires 484 times and the conclusion holds 484 times — and the licence expires in three separate directions, each of which loses the same axiom in a different way.
Every group must keep breathing
NoGo is Go with no captures at all: a stone may be placed only if, afterwards, every group on the board still has a liberty. That makes a move's legality a fact about the whole board rather than about the squares it occupies — and a board therefore almost never breaks into independent parts. Of 117 boards here whose empty points fall into two regions, 24 are the sum of their regions and 93 are not.
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.
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.
When the regions add
The rung below described the NoGo boards whose regions add as the ones with symmetric walls, and said the description was a guess made from six examples. It is wrong: fourteen symmetric boards do not add and sixteen that add are not symmetric. What replaces it is a criterion about liberties — sound on all 117 boards, provable in a line, and complete on only nine of the twenty-four.
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.
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.
The reading that survives too much
Counting the empty squares in front of each coin gets a Push position right half the time, and the rung below said the failures were exactly the positions with two coins of opposite colour side by side. Sixty-six of the 1,072 failures have no such pair, the smallest is five squares long, and the condition that does decide it is not about the board at all — it is about every position the board can reach.
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.
A compound of two different games
Every rule the compound theory has survives mixing exactly — the minimum-remoteness rule is right on all 5,184 mixed pairs and all 7,560 triples — and the reason is not that the rules are strong. It is that each of them reads one number per component, and a number does not remember which ruleset produced it. The thing mixing damages is the shortcut a reader carries instead.
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.
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.
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.
Which option the reduction keeps
Domination deletes an option when another is at least as good, so what survives is the top of an order. On a board that order is made of moves, and two descriptions of the surviving move suggest themselves. Over 1,586 Domineering option lists one of them is right 47% of the time and the other 90%, and the one that wins is not the one a player would guess.
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.
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.
The symmetry one move away
A pairing argument proves the second player wins and names no move to do it with. Asked of every shape of up to eight squares it settles twelve boards. Asked one move later — can the first player reach a position a half-turn pairs? — it settles 288, and which boards those are is decided by parity before anything about their outline is looked at.
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.
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 moves a player can be talked out of
The difference of the two players' largest domino packings is the value of a Domineering region on 141 of the 315 worth numbers. The count is optimistic for its owner and pessimistic for the other, and one number cannot be both — so it becomes an interval, from what a player can be reduced to against what the opponent can achieve. The interval contains the value on 209, is a single point on 505 of the 1,042 regions, and never exceeds two moves wide.
How many moves are worth making
A value answers who wins and by how much, and the anchor below names the quantities it discards. This is the first of them counted. Over 1,034 Domineering regions and 125 values, 63 values have two regions disagreeing about how many placements are worth making and 52 disagree over whether there is any choice at all — and the count of good moves stays near one and a half however large the region gets.
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.
What a game actually produces
Fifty-three per cent of the Domineering regions of at most eight squares are hot. Of the components eleven hundred random games actually produce, sixteen per cent are — and ten per cent once single squares are counted. The figure is the same on three sizes of board, so it is a property of play rather than of the board, and it says that every temperature census this site has taken over a catalogue overstates how hot the game is by a factor of three.
What a strategy has to remember
A value answers who wins and by how much, and it settles neither how many moves achieve it nor whether the best one is unique. Counted over every position reachable inside the catalogue of regions, the gap has a size: 4,269 positions carry 128 values between them, and a player who wants to win rather than to predict has to store 3,308 choices — twenty-six entries for every number the theory supplies.
One fight makes a board a fight
The rung below found 16 per cent of the components a played game produces to be hot, against 53 per cent of the catalogue they are drawn from, and predicted that the share of hot boards would be much larger. Taking the same play-outs and tallying at the board gives 32 per cent — twice the piece figure and not ten times it, because a Domineering board carries only 1.68 pieces and the hot ones cluster on the same boards.
Two errors that cancel
Replacing the packing count with an interval left a doubt that the pessimistic half would add across a board. It adds, for a one-line reason. What is worth measuring is what the reading is then worth: over boards of one to four regions the count decays from exact on 45 per cent to exact on 11, and the interval's containment does not decay at all — it rises from 67 per cent to 74, because the interval's width adds and its error does not.
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.
The size of a cake
Ω gives the sign of a Maundy Cake and says nothing about the size, and the rung below left four values — 7, 10, 13 and 16 — unaccounted for. For a one-row cake they are a formula: write the prime factors largest first and add up their running products. The rule behind it is greedy — cut by the largest prime — and it is exact on every one-row cake to two hundred and wrong on a fifth of the two-sided ones.
A region one player owns
On a strip, a region containing only one player's amazons is worth exactly its free-square count, on all 45,057 positions of the rung below's sweep — and it predicted the exactness would fail in two dimensions, where an amazon can be short of room in one direction and not another. It does not fail. Over 2,412 two-dimensional regions there is no exception, and the reason is one clause: an amazon may shoot back at the square it has just left.
The threshold was a fact about the census
Two rungs failed to account for the seventy-two pairs where a mobility count gets the direction of a comparison wrong, and the third looks at them one at a time. They are not a class of shapes. All seventy-two are on the largest board in the census, at two depths, and sixteen positions up to symmetry — and one board larger the count fails at a margin of three, which the ladder has been quoting as the point at which it never does.
Three rules and a tie-break
An exhaustive table of what a Domineering strategy has to remember is 3,308 lines. Three rules applied in order answer 94.5 per cent of it — leave the opponent fewest replies, then keep the region whole, then take whichever placement comes first — and the fourth and fifth rules answer not one more. The residue is 181 decisions in which every rule scores the candidates the same and one of them is worse.
Half the difference in odd runs
The rung below asked what the regions the packing reading fails on have in common, and whether it is something a player could see. It is: the reading itself. The count has a closed form — half the difference between the region's odd horizontal runs and its odd vertical runs — and it is exact seven times in ten when it claims one move of advantage, on none of the largest regions where it claims two, and it exaggerates four times in five when it is wrong at all.
The cliff a cut invents
The rung below asked for a correction term in the gap between two Push runs. There is none, because the gap's contribution vanishes: widen it and the strip's value converges geometrically, at a rate set by the back run's length alone, to a limit that is not the sum. And Shove — whose reading is exact everywhere — fails at the same cut, which says the broken thing is the cut and not the game.
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 obstacle was the catalogue
The rung below could not measure the early game because its regions were too large for the catalogue, and asked for a bracket rather than a value. No bracket is needed: a twelve-square region evaluates in five milliseconds and an eighteen-square one in under a second. What was expensive was cataloguing every shape rather than sweeping the positions a board actually reaches — and the sweep says a board is hot four times in five three moves in, and cools when it breaks up.
Half a licence is nearly all of it
The rung below priced the substitution licence a restricted universe gives a solver and asked what half of one is worth — the licence to rewrite components but not subpositions. It is worth nearly the whole saving. Rewriting components collapses a million and a half states to three thousand six hundred; rewriting subpositions collapses those to eight hundred and eighty-four, and splitting the pieces takes it to fourteen.
A catalogue that knows what it will meet
The rung below priced a catalogue of regions by its reach and found the coverage saturating, and asked what a catalogue ordered by frequency would cost instead. Eight shapes answer half the components a played Domineering board produces; a catalogue by size needs fifteen for the same, and 1,042 for what 119 chosen by frequency reach. Three quarters of a size-ordered catalogue never turns up in play at all.
Read from the back forwards
The rung below found a two-run Push strip converging at a rate set by the back run and asked what a third run does — whether the rate is still the rearmost run's, or whether the rates compound. It is the rearmost run's, and for every gap: widen the front gap of a three-run strip, two whole runs away, and the value still dies at the last run's rate. Shove, the game one clause away, compounds.
One domino every three cells
The rung below gave the optimistic packing count as a formula in odd runs and asked for the other end of the interval, expecting a formula in the even ones. Parity is the wrong arithmetic: the smallest maximal packing is a sum of ⌈(len−1)/3⌉ over the runs, exact on all 1,042 shapes. That makes the whole interval readable off a drawing — and shows it can never reach the value, because regions with the same runs have different values.
Eight squares, and no hotter
The rung below found no Domineering position hotter than three halves on four boards and asked for the position that attains it. It is a region of eight squares, there are five of them up to symmetry, three are the hot core of an attaining board on every size swept — and the ceiling holds at nine and ten squares too, where the obvious extrapolation predicted seven quarters.
The catalogue a strong player needs
A Domineering catalogue built from random play faces an objection that could overturn it: random play is not play. A player that reads the board produces the same head — eight of the ten commonest shapes — and concentrates far harder: 114 entries answer nine tenths of what it meets, against 2,018. And a catalogue measured on random play over-serves it, while the reverse fails.
One half multiplies, the other adds
The rung below priced the two halves of a substitution licence on sums of two Cram boards and predicted that the first half's saving would grow with the number of components while the second's would not. It is right, and both halves have closed forms: the component licence saves s^(k−1)/k and the subposition licence k·s over a shape count that never moves.
Two strips that end the same way
If a Push strip's sensitivity is governed by its last run, then two strips agreeing at the far end should behave the same however different their fronts. On 78 of 80 tails they do, exactly. On two of them a single empty square in the prefix reaches across a gap that grows without bound and halves the rate — and the run reading turns out to be sound in one direction only.
A heuristic that becomes a theorem
The mobility rule's failure rate had been measured at two depths on each of five boards and found to fall. Swept at every depth it does not merely fall — it accelerates, and it reaches exactly nought before the endgame. From four to eight empty squares onwards the rule has no exceptions at all, which turns a rule of thumb into a guarantee for the last few moves.
The price of taking the maximum
The seventy-two decisions where a Domineering strategy's rules name the wrong placement are never wrong by more than one reply, and a third of them are the second rule's fault rather than the mobility count's. The repair that follows — keep every placement within one reply of the best — retains a best placement every time and costs thirty decisions for every one it saves.
Where the runs meet
A Domineering region's value interval is a function of its run lengths and its value is not — twenty-one groups of shapes share a multiset and disagree. The crossing count separates none of them, and neither do ten other local statistics, fifteen sets of which agree on everything and differ in value. What separates nineteen of the twenty-one is where along its runs each crossing sits.
An effect that changes sign
Which squares two Amazons share turns out to matter about as much as how many — three shared squares in a line run at 0.63 where three scattered run at 2.51. But the effect of clumping is hotter at one distance and colder at the next, so the arrangement predicts well and describes nothing, which is not what the four rungs below it produced.
The licence that weighs nothing
The third substitution licence is constant in the number of components, exactly as predicted, and it saves under two times where the first saves seventy-six million. Priced by its table instead of by its saving it is the only one of the three whose cost does not run away — which reverses the order three rungs of this anchor have put them in.
The ceiling was a plateau
Three halves of a move looked like a ceiling on a Domineering region's temperature: it held at eight squares, at nine and at ten, and the rise that had been a quarter every two sizes stopped. At eleven squares four regions reach seven quarters — and they contain the hottest eight-square shapes and are hotter than them, so the extra material is not cold.
A catalogue that builds itself
A solver that stores every region it has to evaluate builds a catalogue out of its own games. After 650 games it holds 232 of the 1,042 shapes and is still growing — and the order things arrive in is nearly arbitrary while the order they are consulted in reproduces a census of a strong player's games almost exactly.
The table that changes its mind
The advice that ten entries chosen by use serve nine lookups in ten was untested: it describes a table sorted after the fact rather than a solver that only ever held ten. A solver that only ever held ten gets 94.2 per cent — beating the best ten chosen with the whole run in view, because there is no best ten.
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.
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 price of asking what the parts are
The third licence lets a solver look up a region rather than a position, and the rung below priced it by the entries it stores. Priced by the work it costs, it saves between a third and two thirds of the expansions and pays for them with a flood fill at every node — six times the total. A square would have to be ten times cheaper than a table probe before it broke even.
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.
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.
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.
The parts are worth nothing and the sum is not
Every chain and every loop in Nimstring, taken alone, has Grundy value nought. So the Sprague–Grundy theorem predicts that every position built from them is worth nought — and ninety-six of the two hundred and seven positions checked here are not. The theorem is not being misapplied; it does not apply, because a capture keeps the turn. What replaces it is smaller and sharper: count the short chains, and one long component of any kind reverses the parity.
Four hundred and seventy steps
The tartan theorem replaces a search with a multiplication. Measured on every grid a brute-force solve can reach, the two agree on all of them — and the ratio doubles with every square added. On the 8 × 8 grid the theorem is normally drawn at, the search would have to value eighteen quintillion arrangements; the theorem needs twenty-six different nimber products, and computing all of them by the rule that defines them looks at four hundred and seventy pairs.
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 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.
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 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.
The second dimension is not the deep end
The rung below says a row of eight reaches every corner of the vocabulary and goes far into none of them, and that the narrowness is a fact about the board. So the obvious next move is a rectangle — and nine squares in a square hold twenty-five values where nine squares in a line hold fifty-eight. The geometry says why before any stone is placed.
A count that forgets
A Domineering solver with room for ten component values does better evicting whatever it used least recently than evicting whatever it used least often, and the explanation offered was that a use count never forgets. Halve every count at a fixed interval and the count overtakes recency at every table size — by less than half a point, and only with the right interval. The right interval grows with the table: a quarter of a game's worth of lookups at ten entries, five games' worth at forty.
One board, and recency still wins
A Domineering solver's table of component values did best evicting whatever it used least recently, and the explanation was that the run changed board size three times. Take the change away — play all 650 games on one board — and counting wins back its lead only on the smallest board. On 5 × 5, 6 × 6 and 7 × 7 recency still beats both counting and the best fixed table, by the most on the largest. The locality recency exploits is not between boards or between opening and endgame. It is inside a single move.
A wall the pawns cannot cross and the rule can
Two rows of Dawson's diagram separated by a file with no pawn on it: 1,616 moves were examined and not one crosses the gap. With captures optional the rows add on every diagram checked. With captures compulsory they do not, because the compulsion is a rule about the whole board — and the game that is a sum is the one ·137 does not describe.
A difference the rows cannot predict
The diagrams that are not the sum of their rows have been counted and never priced. Priced over 50 diagrams and 63,408,981 positions, the difference takes three values and is a function of nothing a reader can see: seven diagrams whose rows are worth ∗ and ∗ split five to two on it, the third value arrives only at the ninth file, and the one rule that survives is a parity — all twenty-one diagrams of three, five and seven rows add, and every failure carries an even number of rows.
The endgame theory arrives late
Every component the chain-and-loop theory names has coins of degree two, so a position it can read is one where every surviving coin holds exactly two strings. Over a six-box board that is 1,033 of the 28,028 positions with no free box on the table — 3.7 per cent — and more than half of them only after twelve of the board's seventeen strings have been cut.
A thousand positions and no exception
The parity law was fitted to constructed bags of chains and loops inside a string budget. A board's positions are a different population — the sizes are what the geometry allows, the components come correlated, and a six-box board holds exactly one position that is a loop of six. Tested on all 1,032 of them and all 160 of the four-box board's, the law is right every time, against a verdict computed from the strings by a walk that has never heard of a component.
A coin with three strings is worth something
Every chain and every loop is worth nought on its own, whatever its size, and that is exactly what makes their nim-sum useless. A coin with three strings on it is worth nought, one, two or three depending on its arms — 31 of the 35 measured are not nought, and the four that are are the ones whose arms are all long. A coin with four strings is back to nought every time.
Four boxes for every chain after the first
Nimstring answers who is forced to open and says nothing about the score. The margin has a formula: the controller nets the total less four boxes for every long chain after the first — two surrendered and two not taken, each time control is kept. Checked against the solver on 175 endgames it is exact on 172, never too generous, and exact wherever it promises the controller anything at all. The three it misses are the three where it promises nothing.
Two and four are not conventions
Declining costs two boxes on a chain and four on a loop, and those numbers are read off the geometry rather than chosen: one cut completes the last two boxes of a chain and two cuts complete the last four of a loop. Solved again with the fee changed, 418 endgames give a different winner on up to a third of themselves — so the endgame's law is a law about the fee as much as about the shapes, and the fee is not a free parameter.
Named alongside it
The objects these essays reach for when they reach for this one.
EnumerationExhaustive searchDomineeringDisjunctive sumCounterexampleHeuristicRegionValueComponentApproximationInvariantNormal play