Combinatorial Game Theory
who wins, and by how much
Particular games

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.
16 min read 7 figures Not every game is a numberThe value is computableSmall things decide

Take a graph — dots joined by lines, drawn small enough to look at. Left paints a dot blue, Right paints one red, alternating, and a player who cannot paint loses.

That is not yet a game, because nothing has been said about what makes a painting illegal. There are two obvious rules and they differ by one word.

Col: no dot may be painted next to a dot of the painter’s own colour.

Snort: no dot may be painted next to a dot of the opponent’s colour.

Col and Snort on a path of fourOne graph, two games, and one word of difference between the rules. Col forbids painting next to your own colour, which makes every move a small self-harm and drives the values towards numbers. Snort forbids painting next to your opponent's, which makes every move a land grab and drives them towards fights. Both values are computed from the same recursion.Colnot next to your own colourworth 0a number — nobody is in a hurryoutcome P · Left may paint 4, Right 4Snortnot next to your opponent'sworth {{2 | 1} | {-1 | -2}}not a numberoutcome N · Left may paint 4, Right 4a ringed vertex is one somebody may still paint; a filled one is already painted
Fig. 1 The same four dots under both rules. Col’s value is a number; Snort’s is not. The circled dots are the ones somebody may still paint, and both values were computed from the same recursion over the same board.

What each rule makes a move mean

The two rules give a move opposite meanings, and every difference in the values follows.

Under Col, painting a dot blue makes its neighbours unavailable to Left. Left has restricted Left. A move is self-harm — useful only because the alternative is having no move at all, and it is the shortage of moves rather than the gain from them that decides the game.

Under Snort, painting a dot blue makes its neighbours unavailable to Right. Left has restricted Right. A move is a land grab, and the neighbourhood of every unpainted dot is territory somebody may claim.

So Col is a game about running out and Snort is a game about staking out. That is not a metaphor; it is the whole content of the difference, and it produces two different kinds of number.

The asymmetry has a consequence that is easy to miss. Under Col, a player would rather not move at all — and the reason the game has any content is that passing is not allowed. Under Snort, a player would move twice if permitted, and the reason the game has content is that they cannot. Both games are driven by the same rule of alternation, and it is holding back opposite impulses in each.

That is a general feature of this subject rather than a quirk of these two. The normal-play convention makes “having a move” valuable, and every game is then a contest over move availability — but availability can be scarce because the players are consuming it or because they are denying it to each other, and those two scarcities produce values that behave nothing alike.

Cold and hot

Col values are cold. Every Col position is worth a number, or a number plus a star, and nothing else ever appears. Neither player wants to move — moving costs them options — so nothing is ever at stake, and nobody moves in a number while anything else is available.

Snort values are hot. A Snort position is typically a switch: Left has something to gain by painting first and so does Right, and the value is {a∣b}\{a \mid b\} with aa above bb. The board is worth fighting over precisely because a move takes something from the opponent.

Col and Snort on a triangleOne graph, two games, and one word of difference between the rules. Col forbids painting next to your own colour, which makes every move a small self-harm and drives the values towards numbers. Snort forbids painting next to your opponent's, which makes every move a land grab and drives them towards fights. Both values are computed from the same recursion.Colnot next to your own colourworth 0a number — nobody is in a hurryoutcome P · Left may paint 3, Right 3Snortnot next to your opponent'sworth 2 | -2not a numberoutcome N · Left may paint 3, Right 3a ringed vertex is one somebody may still paint; a filled one is already painted
Fig. 2 A triangle under both rules. Col gives zero — a second-player win, with nothing at stake. Snort gives a switch: whoever paints first takes the whole triangle, because painting any dot forbids the other two to the opponent, and the swing is two moves wide.

The classification is worth being careful about. “Col values are numbers or numbers plus a star” is a theorem about the game, not an observation about the examples drawn here. “Snort values are hot” is not a theorem — some Snort positions are numbers, and a fully painted board is worth zero under both rules — it is a description of what the interesting ones do.

Why an empty board says nothing

There is a trap in comparing the two games and it is worth walking into deliberately.

On a board with nothing painted, Col is symmetric between the players: the rule refers only to the painter’s own colour, so swapping blue and red maps the game to itself. A game equal to its own negative is worth 00 or ∗\ast, and that is what every empty Col board comes out as, whatever it looks like.

The same is true of Snort, for the same reason. So an empty board of either game is worth almost nothing and tells almost nothing, and a figure showing only empty boards would be demonstrating a symmetry rather than a difference.

The interesting positions are partly painted, and that is also the realistic case — a game is played from an empty board and reaches partly painted ones on the second move.

Col and Snort on a bowtieOne graph, two games, and one word of difference between the rules. Col forbids painting next to your own colour, which makes every move a small self-harm and drives the values towards numbers. Snort forbids painting next to your opponent's, which makes every move a land grab and drives them towards fights. Both values are computed from the same recursion.Colnot next to your own colourworth -1a number — nobody is in a hurryoutcome R · Left may paint 2, Right 4Snortnot next to your opponent'sworth 3 | 0not a numberoutcome N · Left may paint 4, Right 2a ringed vertex is one somebody may still paint; a filled one is already painted
Fig. 3 The same board with one dot already blue. The symmetry is gone and the two games separate: Col reports a whole number against Left, because Left has damaged Left, and Snort reports a switch with a positive mean, because Left has taken territory. One painted dot, and the two rules disagree about who it helped.

That figure contains the essay’s sharpest fact. Painting a dot blue is bad for Left under Col and good for Left under Snort, and the values say so with opposite signs.

Reading four values in detail

The claims above are easier to trust with the arithmetic in front of them, so here are four positions on a path of three dots, worked through.

Nothing painted. Col is 00 and Snort is {2∣−2}\{2 \mid -2\}. Col’s zero is the symmetry already noted. Snort’s switch says: whoever paints first takes the board, and by two moves’ worth — painting the middle dot forbids both ends to the opponent, leaving the painter with two spare moves.

The left-hand dot blue. Col is −12-\tfrac12 and Snort is {1∣0}\{1 \mid 0\}. Col has gone negative — against Left — because Left painted a dot and lost access to its neighbour. Snort has gone positive for Left, because Right lost access to that neighbour instead.

The middle dot blue. Col is −2-2. Painting the middle of a path of three under Col forbids both ends to Left and leaves both available to Right, so Right is two moves ahead and the value says exactly that. Snort is 22 — a plain number this time, and positive, because Right has nothing left to paint at all.

Left end blue, right end red. Both games are 00. The middle dot is adjacent to one of each colour, so under Col it is available to nobody and under Snort likewise, and both games are over.

Col: 0,  −12,  −2,  0Snort: {2∣−2},  {1∣0},  2,  0.\text{Col: } 0,\; -\tfrac12,\; -2,\; 0 \qquad \text{Snort: } \{2\mid-2\},\; \{1\mid0\},\; 2,\; 0.

Two things stand out from that list. Every Col value is a plain number and every value that is not zero is negative — a painted blue dot is always bad for Left, whatever the shape. And Snort’s values move around in both sign and kind, which is what a game where a move is worth something looks like.

The fraction is the other thing worth noticing. −12-\tfrac12 is not a count of anything on the board; there is no half a move. It is the simplest number between the values of the two players’ options, arrived at by the same rule that gives a Hackenbush string its numeral, and its being a fraction is what tells a reader the position is genuinely settled rather than merely balanced.

Col and Snort on a path of threeOne graph, two games, and one word of difference between the rules. Col forbids painting next to your own colour, which makes every move a small self-harm and drives the values towards numbers. Snort forbids painting next to your opponent's, which makes every move a land grab and drives them towards fights. Both values are computed from the same recursion.Colnot next to your own colourworth −1/2a number — nobody is in a hurryoutcome R · Left may paint 1, Right 2Snortnot next to your opponent'sworth 1 | 0not a numberoutcome N · Left may paint 2, Right 1a ringed vertex is one somebody may still paint; a filled one is already painted
Fig. 4 The second of those positions, drawn. One dot painted, three dots on a line, and two games that report opposite signs about who it helped. The circled dots are the ones somebody may still paint, and the two games disagree about which of them those are.

What the solver computed, and how

Both games are evaluated by the same function with one line different.

A position is a graph together with a colouring string over .LR, indexed by vertex. The legality test walks the neighbours of a candidate vertex and rejects if any is coloured; which colour causes the rejection is the rule’s only parameter — the painter’s own under Col, the opponent’s under Snort.

From there it is the ordinary recursion. Left’s options are the positions reachable by every legal blue painting, Right’s by every legal red one, and the value is {options | options} handed to lib/cgt.js, which reduces it to canonical form. Nothing about numbers, stars or switches is anticipated anywhere; the classification is read off the answers afterwards.

The site’s gate makes the classification a claim rather than a caption. It evaluates Col on four graphs across thirteen colourings and requires every value to be a number or a number with a star attached — a single hot Col value would fail the build. It separately requires Snort, on the same boards, to produce values that are not of that form, in at least one case. And it requires the two games to differ on at least one specific board, so that a bug making them the same function could not pass.

That pair of requirements pulls in opposite directions, which is the point. A check that only demanded coldness would pass on machinery that had collapsed both games to numbers; a check that only demanded a difference would pass on machinery that had broken Col.

Where the model stops

The boards are tiny. Everything here has at most six vertices. Col and Snort on a large graph are both hard, and Snort in particular has been the subject of considerable computation with no closed form to show for it. Six vertices is the point at which the recursion is still instant; a dozen is where it stops being, which is the ordinary situation for an exact evaluator on any partizan game.

Col’s classification is a theorem; the boards do not prove it. Thirteen colourings that all come out cold are evidence and not a proof, and the essay does not claim otherwise. The proof is an induction showing that the options of a cold position are cold and that the simplicity rule then applies.

A star is not nothing. Col values of the form x∗x{\ast} are common, and the star matters: it is the difference between a position that is settled and one where the move still counts. Reading Col as “just numbers” loses exactly the part that decides close games.

Normal play, and finite boards. Both games terminate because every move paints a dot and dots run out, so the recursion is grounded. That is a stronger guarantee than most games here offer, and it is what a loopy game does not have.

A switch, its mean and its temperaturePositions of the form {a | b} with a above b: both players want to move there, so neither is settled. The bar spans the two options, the marked point is the mean the position is worth once the fighting is over, and the temperature is half the gap — which is exactly what moving first is worth.-404{2 | -2}mean 0t = 2{3 | -3}mean 0t = 3{4 | -4}mean 0t = 4{1 | 0}mean 1/2t = 1/2valuethe mean is the midpoint of the two options, and the temperature is half the distance between thema switch is worth nothing on average and everything to whoever moves in it
Fig. 5 What Snort’s values look like when they are put on a line. Symmetric switches, with the mean at zero and the whole content in the width — a board neither player is ahead on and both want to move in. Col never produces one of these on any board tested.

What the pictures cannot show

The figures draw the graph and mark which dots are still available. Two things they cannot draw are worth naming, because both are where the analysis actually happens.

They cannot show the option tree. A Col value of −12-\tfrac12 is the output of a recursion several levels deep, and the drawing shows only the top of it. Nothing on the page lets a reader trace how the fraction arose; that would need a tree of every reachable colouring, which for six dots runs to hundreds of nodes and is not a picture.

They cannot show what the value means in company. A position worth −12-\tfrac12 is worth that in every sum, which is a statement about infinitely many other positions. The board is one object; the value quantifies over all boards it might be added to. No drawing of the board contains that.

The site’s rule is that a figure showing brace notation also shows the position it describes, and these figures satisfy it in the direction that matters — the position is drawn and the value stated beside it. The reverse direction, showing why the value is what it is, is not available in a picture and is what the prose is for.

The same game, written twiceA position with an option no player would ever take, and the same position with it removed. Left would never move to −1 when 0 is available, so the option is dominated and can go. The two games are equal — verified, not asserted — and the second is the canonical form.as it arises1/201{0 | 1}dominatedoption removedcanonical1/201{0 | 1}both are worth 1/2and every game has exactly one canonical form, which is why values can be compared at all
Fig. 6 The machinery the values pass through on the way out. A position, the same position with an option nobody would take removed, and the value both share. Every Col and Snort value on this page has been through this reduction, which is what makes two values comparable as strings rather than as searches.

The general lesson

The pair is the cleanest demonstration this subject has of a fact that is easy to state and hard to believe: what makes a game hot is a property of the rule, not of the board.

The same graph, the same pieces, the same number of moves — and one rule produces positions nobody wants to move in while the other produces positions both players are desperate to move in. There is nothing about the drawing that predicts which.

The mechanism is the one the two rules make explicit. A game is hot when a move takes something from the opponent, and cold when a move costs the mover. Every hot position in this subject is hot for that reason, and the reason is always locatable in the rule.

That is worth carrying into an unfamiliar game. Before evaluating anything, ask whether a move restricts the mover or the opponent. If it restricts the mover, expect numbers and expect nobody to be in a hurry. If it restricts the opponent, expect switches and expect the temperature to be the interesting quantity.

Small Domineering boards and what they are worthEvery value here was computed from the moves rather than looked up. Even on boards this small the values are switches and infinitesimals rather than numbers, which is the ordinary situation for a partizan game and the reason the theory needs more than arithmetic.1×2-1R2×21 | -1N2×32 | −1/2N3×31 | -1NLeft plays vertically, Right horizontally
Fig. 7 A third game for comparison. Domineering restricts the opponent — a placed domino blocks squares both players wanted — and its small boards produce a mixture of numbers and fights, sitting between the two extremes Col and Snort mark out.

Who found them, and when

Both games are Conway’s, from the late 1960s, and both appear in On Numbers and Games with the pun intact: Col takes its name from the colouring and from the constraint that a player must avoid their own, and Snort is named after Simon Norton, who worked on it, with the pig-farming story about neighbouring pens that will not tolerate each other supplied afterwards.

The pairing was deliberate. Conway introduced them together precisely to make the point this essay makes — that the hot–cold distinction is a fact about rules — and the choice of two games differing by a single word is a piece of expository design rather than an accident of what happened to be lying around.

Snort has resisted analysis considerably better than Col. Col’s classification was settled early; Snort on general graphs has no comparable result, and the values of Snort positions on modest boards have been computed and catalogued rather than characterised.

The ladder from here

This is the base rung of the colouring anchor.

Later rungs: the proof that Col values are cold, by induction on the position, which needs canonical forms to get the inductive step to close. Explosive nodes in Snort — the vertices whose painting closes off a whole region — and the way they dominate the analysis. Col and Snort on the same graph as a sum of independent regions, which is where the values start to earn their place. The relationship to graph colouring proper, which is a different problem that shares a rule. And Snort on large graphs, where the honest answer is a catalogue rather than a theory.

The thing this rung establishes is a diagnostic. Given a new game, the question “does a move restrict the mover or the opponent” predicts the shape of every value it produces, and it is answerable from the rulebook before any computation is done.

Where this goes next

-205{2 | -2}mean 0t = 2{5 | 1}mean 3t = 2{1 | 0}mean 1/2t = 1/2{3 | -1}mean 1t = 2{1/2 | −1/2}mean 0t = 1/2valuethe mean is the midpoint of the two options, and the temperature is half the distance between thema switch is worth nothing on average and everything to whoever moves in it 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. the boardworth 2 | −1/2outcome N{2 | −1/2}Left plays verticallyRight plays horizontally 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. n →m123451234501234-10011-20011-3-1-100-4-1-100the 2×4 cakeis worth 1every entry checkedto be a whole numberblue where Left is ahead, red where Right is, shaded where the cake is worth nothinga value with no fraction and no star in it is a game nobody wants to move in 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.