Domineering — where it appears
Named by 78 essays across 8 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 sum is the object
Real positions come apart into independent regions, and a move happens in exactly one of them. That operation — the disjunctive sum — is what the whole theory is built to survive, and it is the reason values exist at all.
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 game with the shortest rule is the hard one
Deciding a generalised board game is PSPACE-complete, which is a statement about families and encodings rather than about size. Nim in the same subject is settled by one pass over the input at any size, and green Hackenbush by one pass over the edges — while Domineering, whose rules take a single line, has no shortcut anybody has found.
Toads and Frogs
Toads shuffle right, frogs shuffle left, and either may jump over one of the other. A strip six cells long is worth exactly up. Another six-cell strip is worth exactly down. Nobody has a formula for which.
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.
Turn the board through a right angle
A two-by-four Domineering board is worth something no number can express, and Right is ahead on it. Turn a second board through a right angle, put the two side by side, and the total is exactly zero. Every position has an exact opposite, and that single fact is what makes subtraction — and therefore comparison — possible at all.
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.
Worth nothing, and worth fighting for
A switch is a position both players want to move in. Its average value can be zero while the difference between getting there first and second is enormous, and that gap is a second number every position carries.
"Left wins" has no short proof
A complete solution of Nim on heaps of 7, 11 and 13 is 480 table entries. A winning strategy for the same position — one move of the winner's at each of their turns, and an answer to every reply — has 56,167,022 nodes in it. The answer is smaller than the proof by a factor of a hundred thousand.
A game where nobody can be ahead in moves
A blue stone beside a red one is a move for both players at once. So neither player can run out while the other still has something to do — and every value the game produces is smaller than every positive number, by the shape of the rule rather than by inspection.
Tiny, miny, and the sizes below every size
An empty two-by-four Domineering board is worth less than nothing and more than every negative number. It is not up, not down and not a fraction — it is a miny, and the minies come in sizes, strictly ordered among themselves below a floor no number reaches.
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 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.
Three different claims are all called solved
Hex is solved in the sense that the first player provably wins, by an argument that names no move whatever. Nim is solved in the sense that a formula gives the right move from any position at any size. Between them sit strategies for one opening, and databases of a few billion positions. The word covers all four.
Cooling by exactly one
Cooling is usually met as a way of reading a thermograph: a tax, and two numbers at the height of the tax. Applied as an operator it returns a position instead — and then the obvious question is whether heating gives the position back. Over the 1,474 values born by day three, 27 survive the round trip and 15 of those are numbers that never moved. Cooling throws away almost everything it touches.
Cram
Domineering with one word of the rule changed: both players may place a domino either way up. That makes the game impartial, and the entire partizan apparatus collapses into a single Grundy value — on the 4 × 4 board, Domineering's canonical form runs to 114 characters of nested braces and Cram's answer is the one character 0.
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.
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.
The operator chosen for one game
Chilling is cooling by exactly one, and the one is not derived from anything. It is chosen because Domineering mostly runs at that temperature — and measured against this site's whole Domineering catalogue it turns thirteen of fifteen boards into numbers or numbers plus a star, and warms thirteen of the fifteen back exactly. They are not the same thirteen: eleven boards do both, two freeze too far to be recovered, and two stay hot and come back on the nose.
The operator that puts the star back
Chilling is not invertible: it freezes, and 400 values born by day three collapse onto 29. Both heating and Norton's warming operator are exact right inverses of it — each lands back where it started, on all 400 — and they pick different preimages, differing on 396 of them and differing by exactly a star on 335. The clause that separates them is one line long and it is about the integers.
The values nobody's game produces
The construction hands down 1,474 values by day three. Seventeen rulesets on this site, swept to eleven thousand positions, produce 1,193 — and only 116 of those are on the construction's list. Two of the twenty-two values born by day two are produced by no position of any game here, and 1,077 of the values that are produced are born later than day three. A value's birthday and a value's reachability have almost nothing to do with each other.
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.
Nobody comes back
There is a class of games in which running out of moves is permanent, and it is the setting almost every modern misère result is stated in. Nine of this site's eleven rulesets belong to it across 5,334 positions; the two that do not are Toads and Frogs and Amazons, and Toads and Frogs loses the property to a single clause — delete the hop and it joins the list.
The strategy that is a symmetry
A pairing strategy is a symmetry of the board that turns one player's moves into the other's, and it wins without computing anything. Tested by playing it out rather than argued, it wins one of seven candidate symmetries across four games — exactly the Cram boards with both sides even, which is exactly where no domino is its own image.
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.
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 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.
The margin a count needs
Leaving the opponent fewest replies names only surviving options nine times in ten, which leaves the question of what a bound stated in that count would have to be weakened to. It is a margin. Over 57,879 pairs of Domineering options, the one leaving the opponent fewer replies is the worse of the two 1,052 times at a margin of one and 72 times at a margin of two — and at a margin of three, never.
The weight that blunts the count
The rung below found that counting the opponent's replies gets the direction of a comparison right once the gap reaches three, and proposed a repair: weigh each reply by whether it leaves the opponent anything. Weighing it makes the count worse. The threshold goes from three to four, the failures from 1,124 to 1,320, and all seventy-two of the pairs the repair was written for come through it unchanged.
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 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 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.
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.
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.
Seventy-two of them were not silence
The rung below said its 181 unanswered decisions were all the rules falling silent and asked whether the position's value picks the placement once the geometry cannot. Seventy-two of the 181 are the rules speaking and being wrong, which is a different failure. On the 109 that really are silence, a rule chosen per value answers more than half — and the star class the rung below singled out is settled outright by leaving the younger position.
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.
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.
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.
Three distances too many
The junction descriptor records how far a crossing sits from four ends, and the rung below asked what the value does when one crossing slides along its run. It reads one bit — the offset's parity — and only when the run has odd length. The other three distances reach the value not at all.
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.
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 board is written as a sum
Every measurement of the brace notation so far has been of a single position, and nobody writes a single position. A board is several parts, and it can be written as the parts joined by plus signs or as the one value they add up to. Over every sum of up to four games born by day two, the one value is usually the shorter — and the share of boards that need a brace climbs with every part added, until the longest value is four times its sum.
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 verdict that changes with the depth
A who-wins search of 4 × 5 Domineering cut at a fixed depth, guessing that the player with more placements wins where it stops, is right about 72.5 per cent of positions at depth 0 and about every one of them by depth 7. On the way, 4,697 positions are right at one depth and wrong at a deeper one. With a guess that knows nothing, going one move deeper makes the search worse — and its errors alternate in kind with the parity of the depth, so that half its verdicts are proofs.
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.
Where a search may stop
A search deepened until two consecutive depths agree carries a proof of its verdict, and on 4 × 5 Domineering it stops before the longest line on 17,589 of 48,670 positions. It also costs three times what the search that simply finishes costs. The rule that pays is the other one. Search on wherever the two players' counts of placements are within one, and at depth 2 the wrong verdicts fall from 2,140 to 86 for about a quarter more work per search.
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 key is a code, and two squares come free
The families of positions a Zobrist key confuses are the words of a binary linear code — the sets of squares whose words cancel — so choosing a key is choosing a code. On 4 × 5 Domineering the textbook choice, a code with the largest minimum distance, confuses more stored positions than a random key at fourteen, sixteen and nineteen bits. The choice that reads the board confuses none at eighteen: two squares of one shade, in rows of different parity, are decided by the other eighteen, and no seventeen-bit key is exact.
Search on in pairs of moves
Deepening until two depths agree gives a proved verdict, and searching on where the counts are close gives a better one; put together the obvious way, they stop on a wrong verdict at 3,231 positions of 4 × 5 Domineering. A guess one move past the cut has the other player to move and flatters the wrong side. Searching on two moves at a time keeps the proof, and the window that suits it is one-sided — but however it is widened, the certificate gets cheaper only by turning into the search that finishes, and on four boards it never gets below it.
Eleven moves and one decision
A prefix has one quantifier a turn, so a game of eleven moves is eleven alternations. Counted on the boards themselves, a Toads and Frogs strip of eleven moves has twenty-six turns with exactly one move available and one turn anywhere at which the choice changes the answer; a Clobber board has a hundred and fourteen turns and none. Nim, the game everybody calls solved, decides at four turns in five.
The opponent stops choosing
Replace one player by a rule with no search in it and the question has one chooser left, which is a puzzle rather than a game. Nim recovers five of its six lost positions that way, and six of seven on three heaps of five. Domineering recovers six of a hundred and twenty-two while the fixed rule throws away a winning move eighty-eight times, and one Clobber board recovers none at all — because on that board no rule can misplay.
Named alongside it
The objects these essays reach for when they reach for this one.
DecompositionEnumerationExhaustive searchHeuristicCanonical formApproximationRegionValueMemoisationTemperatureDisjunctive sumComplexity