Combinatorial Game Theory
who wins, and by how much
Generator

Comparing two positions means playing a third — the difference game generator

Comparing two positions means playing a third
Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer.

Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer.

9 essays call difference-game. 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

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

PositionWorth OutcomeDrawn in
{{2|1}|{0|−1}} − {{2|1}|{0|−1}} 0 P Comparing two positions means playing a third
{{4|2}|0} − 0 {{4 | 2} | 0} N What a move is worth to the player making it
{{6|2}|{1|-3}} − {4|-1} 2 | −2 N The switch a player is imagining
{0,−1|1} − {0|1} 0 P Comparing two positions means playing a third
{0,−1|1} − 1/2 0 P Comparing two positions means playing a third
{1 | 0} − {1/2 | 0} {{1 | 1/2} | {0 | −1/2}} L The same strip without the jump
{1|0} − {1|0} 0 P Comparing two positions means playing a third
{10|{9|1}} − {9|1} {8, {9 | 1} | 0} N What a move is worth to the player making it
{2 | 0} − {1 | 0} {{2 | 1} | {0 | −1}} L Equal in every company
{2 | 0} − 1 1 | −1 N The same strip without the jump
{2|0} − {1|0} {{2 | 1} | {0 | −1}} L Comparing two positions means playing a third
{2|0} − {2|0} 0 P Comparing two positions means playing a third
{2|0} − 1 1 | −1 N Comparing two positions means playing a third · Knowing who wins, and knowing what it is worth · What a move is worth to the player making it
{3|-1} − {3|-1} 0 P The switch a player is imagining
{3|0} − 0 3 | 0 N What a move is worth to the player making it
{4|0} − 0 4 | 0 N What a move is worth to the player making it
{4|2} − {{4|2}|0} {2, {4 | 2} | 0} N What a move is worth to the player making it
{5|{4|0}} − {4|0} {4, {5 | 1} | 0} N The answer that starts another fight · What a move is worth to the player making it
{5|1} − {5|1} 0 P The switch a player is imagining
{5|1} − 1 4 | 0 N The answer that starts another fight · What a move is worth to the player making it
{6|0} − 0 6 | 0 N What a move is worth to the player making it
↑ − ↑ 0 P Comparing two positions means playing a third
↑ − ∗ ↑∗ N Comparing two positions means playing a third · The fight never runs backwards · What a move is worth to the player making it
↑ − ∗2 {0 | ∗3} L The simplest game above both
↑ − 0 ↑ L Knowing who wins, and knowing what it is worth · The fight never runs backwards
↑ − 1/2 −1/2↑ R Equal in every company
↑∗ − ↑∗ 0 P Comparing two positions means playing a third
⇑ − ∗ 2·↑∗ L The fight never runs backwards
∗ − ∗ 0 P Comparing two positions means playing a third
∗ − ∗2 ∗3 N Equal in every company · The simplest game above both
∗ − 0 ∗ N Comparing two positions means playing a third · The fight never runs backwards · What a move is worth to the player making it
∗ − 1/2 −1/2∗ R The same strip without the jump
0 − −1 1 L Comparing two positions means playing a third
0 − ∗ ∗ N The same strip without the jump · The simplest game above both
0 − 1 −1 R What a move is worth to the player making it
0 − 1/2 −1/2 R What a move is worth to the player making it
1 − {1|0} 1 | 0 N What a move is worth to the player making it
1 − 0 1 L The same strip without the jump
1 − 2 −1 R What a move is worth to the player making it
1/2 − {0 | 1} 0 P Equal in every company
1/2 − ∗ 1/2∗ L The simplest game above both
1/2 − 0 1/2 L The simplest game above both
1/2 − 1/4 1/4 L Comparing two positions means playing a third
1/2 − 3/4 −1/4 R Comparing two positions means playing a third · What a move is worth to the player making it
1/8 − 1/16 1/16 L Comparing two positions means playing a third
10 − {10|{9|1}} {{9 | 1} | 0} N What a move is worth to the player making it
2 − {2|0} 2 | 0 N What a move is worth to the player making it
2 − 1 1 L Comparing two positions means playing a third
3 − {3|0} 3 | 0 N What a move is worth to the player making it
3/4 − 1/2 1/4 L Comparing two positions means playing a third
4 − {4|0} 4 | 0 N What a move is worth to the player making it
5 − {5|{4|0}} {{5 | 1} | 0} N The answer that starts another fight · What a move is worth to the player making it
5 − {5|1} 4 | 0 N The answer that starts another fight · What a move is worth to the player making it
6 − {6|0} 6 | 0 N What a move is worth to the player making it

Where it is called

Changing this generator changes every one of these figures.

Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer. Sums and comparison

Comparing two positions means playing a third

There is no way to look at two games and see which is better. The question "is G at least H?" is answered by building G − H and asking who wins it — so the most basic operation in the theory is a decision problem, and every canonical form is built out of them.

 The context that tells them apart. Two positions put into the same company, one context at a time. Each column is a game X; each cell is the outcome class of that side added to X. Equality means every column agrees, for every X there is — so a single disagreeing column is a disproof, and agreement across a bounded list of contexts is evidence rather than proof. The proof is that the difference is zero. Sums and comparison

Equal in every company

Two games are equal when no third game can tell them apart — a quantifier over every position there is, discharged by one finite test. A search over 184 contexts separates all 5,790 unequal pairs it is handed and still calls two different games the same, which is exactly why G − H = 0 is a theorem and an exhaustive search is not.

 Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer. Values

What a move is worth to the player making it

The gain from a move is the option minus the position it was played from — and that is a game rather than a number, so two moves can be incomparable instead of one of them being best. Temperature is what happens when the largest of those games is asked for a single number.

 What a deeper position does to the shape. Thermographs side by side, two of them, with temperature running up each panel and value across it: {{6 | 2} | {1 | −3}}, with a bend where an option's own fight cools out; {4 | −1}, straight-walled. A wall that runs straight has nothing changing hands below the meeting point; a bend is an option's own fight cooling out at a lower temperature than this position's, and it is where a decision passes from one player to the other. The two marks on each base line are the stops — what each player gets by moving first with no tax charged. Values

The switch a player is imagining

Every account of a hot position ends up as "worth about m, and worth t to move in", which is the switch {m+t | m−t}. For a plain fight that summary is the position exactly. For a fight with anything behind it the leftover is not a rounding error — on one position here it is a whole second fight of temperature two.

 Knowing who wins, and knowing what it is worth. Nine positions, each evaluated twice by an instrumented evaluator that starts with an empty cache. The third column counts what deciding the winner costs and the fourth counts what the canonical form costs, in the currency each question is actually paid in. What it costs

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 same strips, with no jumping. Elephants and Rhinos: toads move right and frogs move left, one square into an empty one, and nothing may hop over anything. The pieces keep their order for ever, and the values are computed by the same recursion as the game with the jump in it. Particular games

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.

 The fight never runs backwards. Each of the 22 values born by day two, drawn from its right stop to its left stop — what Right gets moving first, and what Left gets moving first, once the fight has been played out to a number. Every bar runs the same way. The left stop is never below the right one, which is what "both players are trying to improve their own position" amounts to, and the cold rows, where the two coincide, are drawn as a single point. Values

The fight never runs backwards

Left's stop is never below Right's — in every one of 1,780 distinct values, computed twice by two independently written routes, with nothing that disagreed anywhere. The inequality is what makes a mean value well defined and a fight a fight; and where it collapses to equality, 433 of the 460 cold positions turn out not to be numbers at all.

 The 22 values born by day two, and the order they form. Each value sits above everything it is greater than, joined to what it covers. The order has 36 covering relations and is nine levels deep, and 52 of its 253 pairs are incomparable — and it is still a lattice: every pair has a least upper bound and a greatest lower bound among the same 22 values. Two values are marked, together with their join and their meet. Values

The simplest game above both

Values sit in a partial order, and a partial order is entitled to be ragged: two things with no least thing above them. The 22 values born by day two are not ragged at all. Every one of their 253 pairs has a least upper bound and a greatest lower bound among the same 22, and the order is distributive on all 10,648 triples — so it is a lattice, and the join of zero and star is one half.

 Where sente stops, by what the answer costs. The largest ambient temperature at which a local move is still answered, sorted by how deep the fight below the answer runs. When the answer ends the fight the crossover is the follow-up's temperature; when the answer starts another fight it is exactly half of it, and a third level does not halve it again. Temperature

The answer that starts another fight

A local move is answered while the ambient temperature stays below the follow-up's — and that rule, which this site has carried since the anchor opened, is exact only when the answer ends the fight. When the answer starts another one the crossover is exactly half the follow-up's temperature, on every position tested, and a third level of fight does not halve it again.

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