Combinatorial Game Theory
who wins, and by how much
Generator

Cutcake: every value an integer

Cutcake: every value an integer
Cutcake: every value an integer. The value of an m by n cake, for every small m and n. Left cuts down, Right cuts across, and neither player ever gains by moving — so nothing is ever at stake, every value is a whole number, and the number says exactly how many spare moves one player has.

The value of an m by n cake, for every small m and n. Left cuts down, Right cuts across, and neither player ever gains by moving — so nothing is ever at stake, every value is a whole number, and the number says exactly how many spare moves one player has.

8 essays call cutcake-grid. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

208 distinct positions, harvested by running this generator again at the options each essay passed it.

PositionWorth OutcomeDrawn in
1×1 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
1×2 1 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
1×3 2 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
1×4 3 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
1×5 4 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
1×6 5 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
1×7 6 L Maundy Cake
1×8 7 L Maundy Cake
2×1 −1 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
2×2 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
2×3 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
2×4 1 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
2×5 1 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
2×6 2 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
2×7 2 L Maundy Cake
2×8 3 L Maundy Cake
3×1 −2 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
3×2 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
3×3 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
3×4 1 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
3×5 1 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
3×6 2 L Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
3×7 2 L Maundy Cake
3×8 3 L Maundy Cake
4×1 −3 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
4×2 −1 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
4×3 −1 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
4×4 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
4×5 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
4×6 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
4×7 0 P Maundy Cake
4×8 1 L Maundy Cake
5×1 −4 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
5×2 −1 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
5×3 −1 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
5×4 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
5×5 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
5×6 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
5×7 0 P Maundy Cake
5×8 1 L Maundy Cake
6×1 −5 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
6×2 −2 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
6×3 −2 R Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
6×4 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
6×5 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
6×6 0 P Cutcake, where every value is a whole number · Maundy Cake · The game with the shortest rule is the hard one · The obvious cut is the wrong one
6×7 0 P Maundy Cake
6×8 1 L Maundy Cake
7×1 −6 R Maundy Cake
7×2 −2 R Maundy Cake
7×3 −2 R Maundy Cake
7×4 0 P Maundy Cake
7×5 0 P Maundy Cake
7×6 0 P Maundy Cake
7×7 0 P Maundy Cake
7×8 1 L Maundy Cake
8×1 −7 R Maundy Cake
8×2 −3 R Maundy Cake
8×3 −3 R Maundy Cake
8×4 −1 R Maundy Cake
8×5 −1 R Maundy Cake
8×6 −1 R Maundy Cake
8×7 −1 R Maundy Cake
8×8 0 P Maundy Cake
1×1 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
1×10 6 L Maundy Cake · The size of a cake
1×11 1 L Maundy Cake · The size of a cake
1×12 10 L Maundy Cake · The size of a cake
1×2 1 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
1×3 1 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
1×4 3 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
1×5 1 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
1×6 4 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
1×7 1 L Maundy Cake · The size of a cake
1×8 7 L Maundy Cake · The size of a cake
1×9 4 L Maundy Cake · The size of a cake
10×1 −6 R Maundy Cake · The size of a cake
10×10 0 P Maundy Cake · The size of a cake
10×11 −1 R Maundy Cake · The size of a cake
10×12 1 L Maundy Cake · The size of a cake
10×2 −1 R Maundy Cake · The size of a cake
10×3 −1 R Maundy Cake · The size of a cake
10×4 0 P Maundy Cake · The size of a cake
10×5 −1 R Maundy Cake · The size of a cake
10×6 0 P Maundy Cake · The size of a cake
10×7 −1 R Maundy Cake · The size of a cake
10×8 1 L Maundy Cake · The size of a cake
10×9 0 P Maundy Cake · The size of a cake
11×1 −1 R Maundy Cake · The size of a cake
11×10 1 L Maundy Cake · The size of a cake
11×11 0 P Maundy Cake · The size of a cake
11×12 4 L Maundy Cake · The size of a cake
11×2 0 P Maundy Cake · The size of a cake
11×3 0 P Maundy Cake · The size of a cake
11×4 1 L Maundy Cake · The size of a cake
11×5 0 P Maundy Cake · The size of a cake
11×6 1 L Maundy Cake · The size of a cake
11×7 0 P Maundy Cake · The size of a cake
11×8 3 L Maundy Cake · The size of a cake
11×9 1 L Maundy Cake · The size of a cake
12×1 −10 R Maundy Cake · The size of a cake
12×10 −1 R Maundy Cake · The size of a cake
12×11 −4 R Maundy Cake · The size of a cake
12×12 0 P Maundy Cake · The size of a cake
12×2 −4 R Maundy Cake · The size of a cake
12×3 −4 R Maundy Cake · The size of a cake
12×4 −1 R Maundy Cake · The size of a cake
12×5 −4 R Maundy Cake · The size of a cake
12×6 −1 R Maundy Cake · The size of a cake
12×7 −4 R Maundy Cake · The size of a cake
12×8 0 P Maundy Cake · The size of a cake
12×9 −1 R Maundy Cake · The size of a cake
2×1 −1 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
2×10 1 L Maundy Cake · The size of a cake
2×11 0 P Maundy Cake · The size of a cake
2×12 4 L Maundy Cake · The size of a cake
2×2 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
2×3 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
2×4 1 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
2×5 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
2×6 1 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
2×7 0 P Maundy Cake · The size of a cake
2×8 3 L Maundy Cake · The size of a cake
2×9 1 L Maundy Cake · The size of a cake
3×1 −1 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
3×10 1 L Maundy Cake · The size of a cake
3×11 0 P Maundy Cake · The size of a cake
3×12 4 L Maundy Cake · The size of a cake
3×2 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
3×3 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
3×4 1 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
3×5 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
3×6 1 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
3×7 0 P Maundy Cake · The size of a cake
3×8 3 L Maundy Cake · The size of a cake
3×9 1 L Maundy Cake · The size of a cake
4×1 −3 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
4×10 0 P Maundy Cake · The size of a cake
4×11 −1 R Maundy Cake · The size of a cake
4×12 1 L Maundy Cake · The size of a cake
4×2 −1 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
4×3 −1 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
4×4 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
4×5 −1 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
4×6 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
4×7 −1 R Maundy Cake · The size of a cake
4×8 1 L Maundy Cake · The size of a cake
4×9 0 P Maundy Cake · The size of a cake
5×1 −1 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
5×10 1 L Maundy Cake · The size of a cake
5×11 0 P Maundy Cake · The size of a cake
5×12 4 L Maundy Cake · The size of a cake
5×2 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
5×3 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
5×4 1 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
5×5 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
5×6 1 L Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
5×7 0 P Maundy Cake · The size of a cake
5×8 3 L Maundy Cake · The size of a cake
5×9 1 L Maundy Cake · The size of a cake
6×1 −4 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
6×10 0 P Maundy Cake · The size of a cake
6×11 −1 R Maundy Cake · The size of a cake
6×12 1 L Maundy Cake · The size of a cake
6×2 −1 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
6×3 −1 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
6×4 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
6×5 −1 R Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
6×6 0 P Cutcake, where every value is a whole number · Maundy Cake · The obvious cut is the wrong one · The size of a cake
6×7 −1 R Maundy Cake · The size of a cake
6×8 1 L Maundy Cake · The size of a cake
6×9 0 P Maundy Cake · The size of a cake
7×1 −1 R Maundy Cake · The size of a cake
7×10 1 L Maundy Cake · The size of a cake
7×11 0 P Maundy Cake · The size of a cake
7×12 4 L Maundy Cake · The size of a cake
7×2 0 P Maundy Cake · The size of a cake
7×3 0 P Maundy Cake · The size of a cake
7×4 1 L Maundy Cake · The size of a cake
7×5 0 P Maundy Cake · The size of a cake
7×6 1 L Maundy Cake · The size of a cake
7×7 0 P Maundy Cake · The size of a cake
7×8 3 L Maundy Cake · The size of a cake
7×9 1 L Maundy Cake · The size of a cake
8×1 −7 R Maundy Cake · The size of a cake
8×10 −1 R Maundy Cake · The size of a cake
8×11 −3 R Maundy Cake · The size of a cake
8×12 0 P Maundy Cake · The size of a cake
8×2 −3 R Maundy Cake · The size of a cake
8×3 −3 R Maundy Cake · The size of a cake
8×4 −1 R Maundy Cake · The size of a cake
8×5 −3 R Maundy Cake · The size of a cake
8×6 −1 R Maundy Cake · The size of a cake
8×7 −3 R Maundy Cake · The size of a cake
8×8 0 P Maundy Cake · The size of a cake
8×9 −1 R Maundy Cake · The size of a cake
9×1 −4 R Maundy Cake · The size of a cake
9×10 0 P Maundy Cake · The size of a cake
9×11 −1 R Maundy Cake · The size of a cake
9×12 1 L Maundy Cake · The size of a cake
9×2 −1 R Maundy Cake · The size of a cake
9×3 −1 R Maundy Cake · The size of a cake
9×4 0 P Maundy Cake · The size of a cake
9×5 −1 R Maundy Cake · The size of a cake
9×6 0 P Maundy Cake · The size of a cake
9×7 −1 R Maundy Cake · The size of a cake
9×8 1 L Maundy Cake · The size of a cake
9×9 0 P Maundy Cake · The size of a cake

Where it is called

Changing this generator changes every one of these figures.

What it costs to decide the winner. Three families of game, each at several sizes, with the number of distinct positions an exhaustive solver must evaluate beside the work its closed form does. The bars are logarithmic. Hardness is not about the size of the board or the length of the rules — Domineering has the shortest rule here — it is about whether anybody has found the shortcut. What it costs

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.

 Cutcake: every value an integer. The value of an m by n cake, for every small m and n. Left cuts down, Right cuts across, and neither player ever gains by moving — so nothing is ever at stake, every value is a whole number, and the number says exactly how many spare moves one player has. Particular games

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.

 Maundy Cake: the pieces must be equal. The same cake as Cutcake, cut by the same two players, with one extra rule: a cut must divide the cake into equal pieces, and every piece stays in play. The values are still whole numbers, but the arithmetic that decides them is not Cutcake's — it counts prime factors rather than binary digits. Particular games

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.

 Seven, ten, thirteen and sixteen. The four values the rung below named, each read off the prime factorisation: one plus the largest prime plus the product of the two largest. Particular games

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.

 Cut small unless you are behind. The complete rule for the best cut in a Maundy Cake, in three cases decided by the two sides' counts of prime factors. It is exact on every cake in a sixty by sixty grid. Particular games

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.

 Running products, and where to stop. Six Maundy Cakes with the prime factors of the longer side, the running products those primes make, and the value the sum of them gives. Particular games

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.

 Term by term. Every cut of one long side, with its value written as running products beside the terms of the largest-prime cut. Particular games

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.

 The two proofs, beside each other. Maundy Cake's rule was proved by restating its lemma so the short side vanished into a multiset of primes and a term count. Cutcake's rule takes the same five steps, with the multiset replaced by a binary length — one integer instead of a multiset — and the closing argument correspondingly shorter. The one line where they differ is which cut a reader would guess. Particular games

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.

The whole library · The position index · The figures that play back