Memoisation — where it appears
Named by 33 essays across 5 fields — each of them below, with the objects they name alongside it.
A position reached eleven ways is one position
A 4×4 Domineering board has 5,700 positions in it and 6,257,129 routes through them. Three heaps of 7, 11 and 13 have 480 positions and 7.6 × 10¹⁶ routes. The gap between those two numbers is not an optimisation — it is the difference between a search that finishes and one that does not.
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.
What counts as the same position, and what that is worth
Folding a 4×4 Domineering board by its symmetries takes the table from 5,700 entries to 1,522 — a saving of 3.75, against a ceiling of exactly 4. An orbit cannot be larger than the group acting on it, so this is the one saving in the subject that can never change an exponent.
The class is named after memory, and that is not an accident
A 4×4 Domineering board has 6,257,129 routes through it, 5,700 distinct positions, and a deepest line eight moves long. Those three numbers are three different resources, and the smallest of them is the one that gives games their complexity class.
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.
Knowing who wins, and knowing what it is worth
Deciding a winner expands positions. Computing a canonical form expands pairs of positions, because a comparison unfolds as a recursion over one subposition of each and the reduction makes many comparisons. Measured on the same nine positions by an evaluator that starts empty every time, the second costs between 1.3 and 279 times the first, and the ratio grows with the tree.
What a value costs to write down
The canonical form is the smallest form of its value, and it is smallest in the one currency the reduction happens to spend: options. Counted in symbols it is nothing of the kind — the widest value born by day three is not the longest, the longest has six options rather than seven, and every canonical form on the day except the seven integers writes some position out twice.
The same position, written once
Writing out the canonical forms of day three takes 24,940 nodes. Naming each distinct subposition once inside each form takes 10,102, and naming each distinct subposition once across the whole day takes exactly 1,474 — one per value, because nothing appears inside a canonical form that is not itself a value of the day.
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.
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.
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 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.
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 check in front of a search
The rung below found a pairing one move away on 288 of the 767 even first-player shapes, and asked what a solver that tested for one before recursing would save on a real game. On an even Cram board it saves nearly the whole search — a 4 × 5 board takes 17,348 node expansions without the check and one with it — and the depth profile shows why that number flatters: the check settles every winning position at the opening and at the last two moves, and about one in ten in between.
A product against a sum
A company closed under both addition and options licenses a solver to rewrite any subposition, and the rung below found that exactly the nimber groups have both closures. Priced on Cram boards, that licence is the difference between walking a product of position sets and walking their sum — four to twenty-five times on two components, twenty-four to a hundred and sixty-one on three — and it is available to impartial games because their class representative is a heap rather than a form.
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.
The check that was not a check
The rung below asked for a depth-conditioned solver and named the board to measure it on. Building it found two things first. The pairing check is unsound at interior positions — on a four by five Cram board it fires on 8,613 positions and 1,026 of them are losses — and the board it named has twenty-five squares, so the check can never fire there at all. Repaired, the check is right everywhere, and the policy that pays is the root alone.
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.
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.
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.
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.
Two measures bounded, and one not
A sum is born no later than its parts' birthdays together, and it has no more options than they have between them — a bound nobody had checked, and it is attained. What runs away is the length of the written form: 27 pairs of 231 exceed it, the worst by 29 characters, on a sum with exactly as many options as it was entitled to.
A factor, and not an overhead
Deciding who wins a form searches the form's own tree. Reducing it to canonical form searches a difference game for every comparison, and a difference game is a sum. Over 256 forms the reduction expands 5.46 times as many positions — and the ratio runs from 0.58 at one option to 9.80 at eight.
What it costs to notice a repetition
Folding a 4 × 4 Domineering board by its symmetries takes the table from 5,700 entries to 1,522. It also spends 559,424 square-mappings to work out where each entry goes — seventeen and a half times the entire cost of not folding. The saving has a ceiling of four and the price has no ceiling at all, and knowing which currency each is paid in is the difference between an optimisation and a habit.
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.
The order a solver tries the moves in
A memoised search asking who wins 4 × 5 Domineering expands 1,125 positions when it tries first the move that leaves the opponent fewest replies, and 30,202 when it tries losing moves first — the same answer at twenty-seven times the price. The ordering that already knows which moves win is not the cheapest. A win needs one move and a loss needs all of them, so the price of an order is paid one level down, in the replies it leaves.
A key shorter than the position
A who-wins table for 4 × 5 Domineering addressed by a 16-bit Zobrist key stores a wrong verdict in 59 runs of 60 and names the wrong winner of the empty board in 19. The pairs of positions sharing a key follow the birthday count exactly while addresses are scarce, and fall away to nothing once the key has more bits than the board has squares, because a Zobrist key is linear. Symmetry and value identify positions that really are the same; a short key identifies positions that differ, at a rate set by arithmetic.
A check bit halves the average and not the key
Real transposition tables keep a few of a key's bits beside each verdict and trust an entry only when they match. On 4 × 5 Domineering each such check bit halves the average number of wrong verdicts, exactly as the birthday count says. It does not halve any one key's. A Zobrist key confuses positions in families — every pair that differs on one set of squares whose words cancel — and a bit removes a family whole or not at all, so from eighteen bits to nineteen thirty of fifty-eight keys lose every confusion and fourteen keep every one.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
DomineeringExhaustive searchEnumerationDecompositionComplexityHeuristicDisjunctive sumCanonical formSearch costIdentificationPosition graphApproximation