Partizan — where it appears
Named by 66 essays across 7 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.
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.
Every impartial game is a Nim heap
Sprague and Grundy proved, independently and four years apart, that any position in any impartial game is equivalent to a single heap of counters. Not similar to one — equal to one, interchangeable with it inside any larger game.
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 game older than the theory
Kōnane was played on carved lava boards in Hawai‘i long before anybody wrote a brace notation, and its rule for losing is the normal-play convention arrived at some centuries early. Evaluate a row of it and the answers are halves, quarters, stars and infinitesimals — the theory's whole vocabulary, out of a game that was not built to display any of it.
Which part to move in
The value of a sum is the sum of the values. The move in a sum is not the move in any part, and there is no rule that reads it off the values — in the smallest interesting example, the only winning move is in the component worth nothing.
One board, two rules
Col forbids painting next to your own colour. Snort forbids painting next to your opponent's. One word differs, the boards are identical, and the values that come out are not the same kind of object.
Cutcake, where every value is a whole number
A partizan game in which no position is ever worth a fraction, a star or a fight. Every value is an integer, the integer is a count of spare moves, and the pattern it follows is decided by binary digits.
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.
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.
Where the impartial theory stops
Sprague–Grundy gives every impartial position one number, and the number is complete. The moment the two players have different moves no number works at all — not a harder one to compute, none — and three positions here are compared against every nimber to show it.
A green edge on a blue one
Blue over green and green over blue are the same two edges in the other order. One is worth 1∗ and the other ↑∗ — a number with a star on it against something smaller than every positive number — so a stalk with all three colours in it stops being a numeral and starts being a position whose value depends on what is underneath.
The class where nobody runs out first
Three stones in a row — blue, blue, red — and the position is worth exactly up. Clobber cannot produce anything else, because adjacency is symmetric — a player has a move precisely when the opponent does, and a game with that shape can never be worth a whole move to anybody.
The strip nobody has a formula for
Some toads, a gap, some frogs. Two counts and a spacing is the whole description, and the values that come out of it are integers, stars, switches with eighth-point options and a down — four classes inside one two-parameter family, which is why nobody has written the formula.
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.
One rule makes it cold, the other hot
Col forbids painting next to your own colour and Snort forbids painting next to your opponent's. Over all 540 colourings of six graphs, not one Col position has anything at stake and 61 Snort positions do — the difference between a game that is a count and a game that is a series of fights, produced by one word.
Maundy Cake
Cutcake with one word added: a cut must divide the piece into equal parts. The values are still whole numbers, and the rule this site has been repeating about them is false — over all 1,296 cakes to 36×36 the largest-odd-divisor account has 946 counterexamples. What survives is a count of prime factors, and it says who wins without saying by how much.
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.
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.
The same strip without the jump
Delete one clause from Toads and Frogs — the hop over an opponent — and the game is Elephants and Rhinos. Over the same 3,279 strips the values do not become simpler in the way a reader would guess: every value that is a number becomes an integer, against 172 fractions with the jump in, and the count of positions worth fighting over nearly doubles. Removing a move made the game hotter.
Taking from the ends
End-Nim is Nim's board with a player at each end, and it takes one sentence to state. Not one of its 5,460 small positions is worth a non-zero number — the game is all-small, so zero is the only number any of them can reach — and there are 2,693 distinct values between them. The outcome says a great deal more: 4,738 of those positions are won by the same player whoever moves, and on two heaps the rule is that the larger end wins.
One row of Clobber
Every string of blue, red and empty squares up to eight long — 9,840 rows — carries one of only 111 values, and every one of them is infinitesimal. A third of the rows are worth exactly zero. Six alternating stones are worth zero and eight are worth a form that takes four lines to print, so the values do not simplify as the row grows: they explode, while the row stays trivial to describe.
Nothing worth fighting over
Shove is a strip of coins beside a cliff, and both players have completely different moves. Every one of its 728 positions is worth a number, so nobody ever wants to move; the winner is the owner of the coin furthest from the cliff, in all 728; and the number the board is worth is not the sum of its coins — that reading is exact on 126 strips and wrong on 588 of the other 602.
Two players, two lists
Give each player their own list of how many counters they may take and the impartial theory stops applying. What survives is the outcome: it settles into a repeat, for every pair of lists, and that is a theorem. What does not survive is the value — on four of six pairs swept it has no repeat inside sixty heaps, and the birthdays are still climbing at the edge of the window.
A tree is still a number
A Hackenbush string spells its own value in binary. Put a fork in it and the numeral has nothing to read — there is no leftmost anything. The value is still a number, in all 10,066 forests up to six edges; it is still computable, by the ordinal sum, in all 3,238 single-trunk trees; and the reading is right on 762 of them, of which 126 are the strings it was written for.
Topple it from either end
A row of blue and red is the picture this site opens with, and under Hackenbush's rules it is always a number. Knock the pieces over instead of cutting them — everything on the chosen side falls — and 480 of the 510 rows up to eight pieces stop being numbers. The two games agree on sixteen rows, every one of a single colour, and the temperature of the hottest row climbs by exactly a half for each domino added.
The other way to move a row
Shove has a cliff and Push has a wall, and that is the whole of the difference. Both games make every one of the 728 strips up to six squares a number, so neither ever has anything worth fighting over — and the two rules do not agree on the value of a single position. The obvious board-reading is exact on 446 strips under the wall and on 140 under the cliff, and 486 strips contain a coin its owner cannot move at all.
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.
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.
The strip where every number is a whole one
Delete the hop from Toads and Frogs and the halves, quarters and ups vanish completely: over 9,801 strips, every value that is a number is an integer, without a single exception. The guess that the hopless game therefore has a formula reading the gaps is half right and exactly wrong — 1,460 strips of eight squares are switches, and three strips with the same counts of toads, frogs and empty squares are worth 1, {2 | 1} and 2.
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.
A sequence with a rule and no period
The values of the subtraction game where Left takes one or two and Right takes one or three never repeat — thirty-one heaps, thirty-one different values. They are nonetheless completely described: three seeds and the rule v(k + 3) = {0 | v(k)} generate every one of them, which is what a pattern without a period looks like.
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.
The rows that are their own mirror
Four hundred and ten End-Nim rows are worth nimbers and 168 of them are palindromes, so a condition covering the other 242 was outstanding. It is that the row is equal to its own negative — and on this game that condition is not merely sufficient but exact, which is more than the group law promises and is a fact about End-Nim rather than about games.
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.
A game with nothing at stake
The rung below explained a coincidence with a claim it did not compute: that End-Nim carries no hot self-negative values. The census says something stronger. Not one of 10,919 rows across three shapes of board is hot, every one of them is worth an infinitesimal, and the 361 rows the earlier census called numbers are 361 rows worth nought. The reason is one line of the rule, and 2,693 distinct values sit underneath it.
The condition that survived the wider sweep
Which pairs of subtraction lists have a value sequence that repeats? Over the 49 pairs drawn from one, two and three, two conditions answer it identically — a translation and all-odd — and both are exactly right. Over the 961 pairs drawn from one to five, all 83 translations still repeat with no exception and four all-odd pairs do not, at heap ninety with a period as long as forty-two. Neither condition is necessary: 104 pairs repeat that satisfy neither.
The criterion that cannot exist
The rung below asked for a quantitative version of its condition — turn 'the reading survives mixing three quarters of the time' into a statement about the strip. Three strips of four squares settle it. `.LLR`, `.LRL` and `.RLL` have the same length, the same reading, the same coins and the same single run, and their readings are wrong by 1¼, ¼ and ½. The error is a fact about the order of the colours, and 207 of 805 statistical classes carry more than one of them.
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.
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 numeral in the empty squares
The rung below ruled out a quantitative criterion for Push and asked for a numeral over the coins combined with a count over the gaps. The two ingredients are the right way round: the colours pick a fraction — −1, −1/3, −1/7, −1/15 — and the empty squares give the binary precision, so a run of k coins before one of the other colour with g gaps is worth exactly (1 − 2^(−kg)) ÷ (2^k − 1). And it does not compose: a strip of two runs is not the sum of them, on any pair tried.
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.
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.
Cut small unless you are behind
The rung below found the greedy rule — cut at the largest prime — wrong on 104 of 552 Maundy Cakes and asked for a description of them. On all 104 the best cut is at the smallest prime, the exact opposite. A middle divisor is never needed on any cake in a sixty by sixty grid, and which of the two extremes wins is decided by Ω alone: cut small when Ω(m) + 1 ≥ Ω(n), large otherwise, and that is exact on all 3,540.
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 short side only says how many
The rung below settled which cut to make in a Maundy Cake and left the value open. With the cut settled the recursion is a walk, the walk unrolls, and what it unrolls into is the running products of the long side's prime factors, largest first. The short side never enters the products at all — it decides how many of them there are and nothing else, so sixty-two different short sides give one value.
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.
The short side is not in the lemma
The closed form for a two-sided Maundy Cake rested on one unproved statement: that no divisor beats the largest prime. Written out, that statement never mentions the short side — it is an inequality between a multiset of primes and a term count — and once it is stated that way it has a two-line proof, term by term. The ladder ends in a theorem rather than a grid.
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.
The mirror was the floor
Toppling Dominoes' share of genuinely new values had fallen from one to a half over eight sizes, and the rung below could not tell a floor from a slow fall. Four more sizes settle it: the distance above a half halves every two sizes. And the half is not a shortage of values but a symmetry — a row played from the other end is the same game, and the ruleset is as injective as that allows.
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 obvious cut is the wrong one
Maundy Cake's rule was proved by restating its lemma so the short side vanished. Cutcake's collapses the same way — into a binary length instead of a multiset of primes — but the cut the argument needs is not the one the ladder predicted. Halving is wrong on a third of all cakes, and the smallest counterexample is six squares by two.
A fraction does not reach
Two Push tails read their prefix when every other tail ignores it, and the previous rung guessed the deciding bit was a shape — whether the prefix's last coin stands alone. The full census says it is a number. The rate changes exactly when the prefix is worth a whole move, and three quarters of a move is not enough.
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.
The square that cannot be halved
Every number in hopless Toads and Frogs is a whole number, which the rung below measured on seven thousand strips and could not explain. The reason is that every empty square is either one player's alone or split evenly between them — except one, and that one is where the numbers stop.
Where the numeral stops
A Hackenbush string is a numeral and a tree is a trunk with a forest on it, so the obvious next question is a graph with a cycle in it. Green Hackenbush answers that by fusing the cycle to a point. In blue and red the fusion is right on every three-edge cycle, on fewer than half of the six-edge ones, and the smallest thing it gets wrong has four edges.
A recipe instead of a census
Counting a thousand values in seven dominoes suggests Toppling Dominoes reaches every short game, and a count is not a construction. The obvious construction — lay the two options either side of a Left domino and a Right one — is exact on day one, right on a third of day three, and cannot be applied to nine in ten values at all.
What has to break before a pawn is worth a number
Every value the blocked-file model can hold is an infinitesimal, and the reason is one sentence about the move rule rather than anything about pawns. Break that sentence — a pawn stuck behind a friend, a square only one side can hold — and integers, switches and positions worth fighting over arrive at once.
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.
The two moves that are not captures
Kōnane begins from a full board and the first two moves lift stones rather than take them, which is the only time in the whole game anybody does. Nothing on this site applies to them, and the choice is not free — on a 3 × 5 board two of Black's eight openings leave a position a whole move worse than the other six, and on a 3 × 3 board none of the five does.
The first move is a link that is not there
Lehman's criterion answers one question about a switching game — who wins when Short moves second. The other question has the same answer asked of a different graph: add one link from A to B, and Cut is forced to spend its first move deleting it. The trees of that larger graph then name Short's opening, and on every subgraph of seven graphs they name a winner.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
EnumerationExhaustive searchValueCanonical formInvariantOutcome classCounterexampleDecompositionStar (∗)Normal playDisjunctive sumSwitch