II.7: Adding Numbers to Other Games

Weak Number Avoidance

As someone suggested, future details of verification will be simplified if we have something called the “(Weak) Number Avoidance Theorem”, whose statement I first encountered in Winning Ways, although the name may have first appeared in Lessons in Play. It will allow us to bypass silly cases like “If Right moves from x+* to y+*, then…” in our arguments. The idea is that Numbers are extra benefits for Left or Right, and they’re not really where the action of a game is happening. This theorem will apply equally well to Numbers (and other positions) that aren’t short, like ω={0,1,2…|}.

1. If x is equal to a Number, and G is not equal to a Number, then if a player has a winning move in x+G this turn, they can win by moving in G.
WLOG, assume that Left has a winning move in x+G, so that x+Gı⊲0. We want to show that Left can win by moving in G: i.e. there is an option Gℓ1 of G such that x+Gℓ1≥0. Note that we may also assume x is a Number, for if x′ is a Number equal to x, then x′+G=x+Gı⊲0, and if x′+Gℓ1≥0, certainly x+Gℓ1≥0.

Now, assume for sake a contradiction, that we have a Number x of lowest birthday where x+G is a counterexample: x+Gı⊲0 but x+Gℓ⊳ı0 for all options Gℓ of G. Since Left can win x+G but not by moving in G, some xℓ1+G≥0. Note that we can’t have xℓ1+G=0 since then G=-xℓ1, but G is not equal to a Number. Thus, xℓ1+G>0.

Since we assumed x had least birthday among counterexamples, xℓ1+G must be a situation where the theorem applies: Left has a move in the G component to win xℓ1+G, i.e. There is a Gℓ1 such that xℓ1+Gℓ1≥0. Since x is a number, x>xℓ, and we have x+Gℓ1> xℓ1+Gℓ1≥0. But this contradicts our assumption x+Gℓ⊳ı0 for all Gℓ! ✓

Since you can ignore a Number until there’s nowhere else to move, the Number components of a position are kind of like score, although Fraser Stewart has written multiple papers on a theory of combinatorial games that would explicitly include score as we usually think of it.

Incidentally, you might think (as claimed in Winning Ways, although it may have been one of the many intentional errors) that repeated application of this result would yield “if you have a sum of a Number and a bunch of non-Numbers, and you can win, then you can win by moving in one of the non-Numbers”, but that’s false for non-short games (and harder to prove for short games). The following example essentially comes from a counterexample of “the translation property” (“strong number avoidance”) for non-short games introduced in ONAG:

Let ℤ denote the set of integer Numbers, and ±ℤ denote {ℤ|ℤ}. Then certainly Left can win 1+±ℤ+±ℤ by moving in the 1 component to get to ±ℤ+±ℤ=0. But if Left tries to win by avoiding the Number 1, and moves to 1+n+±ℤ, then Right can respond by moving in ±ℤ to get to 1+n+-(1+n)=0, regardless of what integer Number n is.

Hackenstrings and Nim piles

With this tool in hand, we can try to understand, once and for all, how *={0|0} (a Nim pile of size one) compares to various Numbers. Suppose that x is a positive Number (e.g. 5 or 1/ω), then to see how it compares with *, we need to see who wins x-*=x+*. If Left goes first, they can move in * to make the whole position equal x>0 so they win. If Right could win going first, 1. says they’d move in *, but that would make the whole position x>0 and Left would still win. Therefore, *<x for any positive Number x, no matter how infinitesimally small. Similarly, z<* for any negative Number z. Incidentally, an inductive argument shows that any Nim pile *n={0,*,*2,…,*(n-1)|0,*,*2,…,*(n-1)} (or an infinite Nim pile) also lies between all positive and all negative Numbers.

This information essentially tells us who wins a game of “Hackenstrings and Nim piles” (and by extension, yields a strategy). Use Surreal arithmetic to combine all of the Hackenstrings into a single string, and use Sprague-Grundy to combine all of the Nim piles into a single pile. If the Hackenstring is the empty string “”, then the winner is the winner of the Nim pile (the next player to move or not, depending on whether or not the Nim pile is empty). If the Hackenstring isn’t empty, then the player who can take the first letter of the string (remember: that determines the sign of the value) can win. (In the simplified game, they’d win by taking the Nim pile if they get a chance, and taking the Hackenstring pile after that if they get a chance, but in the more complex game you’d have to make a table of who wins the various reachable positions, as with Nim.)

We can understand x+* even better, by finding its canonical form. By definition, x+*={xℓ+*,x|xr+*,x} where xℓ and xr range over the corresponding options of x. Now let’s check for dominated options. x-(xℓ+*)=(x-xℓ)-*=(x-xℓ)+*>0 since x is a Number a positive Numbers are still positive after you add *. Thus, we can delete all of the “xℓ+*” options. Similarly, xr+*>x so we can delete all of the “xr+*” options. This leaves us with x+*={x|x}.
Exercise: Verify that neither of these “x” options could be reversible. By a very similar argument, the canonical form of x+*2 is {x+*,x|x+*,x}, etc.


II.6: Simplifying Conway Positions

Let’s review what we were doing with the Sprague-Grundy theorem: An impartial game is one in which Left and Right have the same options, and all of those options are themselves impartial. This gives us that 0={|} is an impartial game, and then *={0|0}, and the next ones we get are *2={0,*|0,*} and {*|*}. Then Sprague Grundy says we can throw out these stars because mex({1})=0, so {*|*}={|}=0. By induction, every impartial game is equivalent to “a star” (a Nim pile), and the mex rule tells us we can throw out higher stars if one is skipped. Vaguely similarly, the simplicity rule for numbers lets us do things like throw out the 0 in {0,1|2}={1|2}=1+1/2. In this post, I want to cover some more general ways of simplifying games by presenting material primarily from ONAG.

Inequality Identities

As I’ve alluded to before, all of the familiar facts about inequalities hold true for Conway positions: e.g. “F<G≤H implies F<H”. However, sometimes we have positions that are incomparable/confused: G‖H. This ends up giving us a whole collection of unfamiliar facts about inequalities. Just like “G≤H” makes writing “G<H or G=H” tidier, we’ll use “G⊳ıH” to make writing “G<H or G‖H” tidier. Note that “G⊳ıH” really just means “Left can win H-G if they go first”, or equivalently, “Right can win G-H if they go first”.

1. If Gℓ is a left option of G and Gr is a right option, then Gℓ⊳ıG⊳ıGr.
Why? We need to show Left can win G-Gℓ if they get to go first. Gℓ is a left option of G, so Left can move to Gℓ-Gℓ=0 on their first move and win. The right option part is analogous. ✓ (This is similar to the proof of II.5.4.)

2. If F<G‖H or F‖G<H then F⊳ıH.
Why? Assume F<G‖H. We need to show that Left can win H-F, going first. But H-F=(H-G)+(G-F), and N+L=NL†, so F⊳ıH. The F‖G<H case is very analogous. ✓
(† If you don’t want to recreate/click back to read the argument I cited: Left can win H-G if they go first since G‖H and Left can win G-F even if Right gets to go first since F<G. Therefore, in the sum (H-G)+(G-F) Left simply has to start by making the right move in H-G and then responding in the same component to all of Left’s moves.)

3. If F≤G⊳ıH or F⊳ıG≤H, then F⊳ıH
Why? Assume F≤G⊳ıH. If F=G, we’re done automatically. If F<G<H then F<H so certainly F⊳ıH. In the remaining case F<G‖H, the result follows from 2.. The F⊳ıG≤H case is very similar. ✓

Dominated Options

The first main idea is based on the intuition that if a position is worse for Left (or Right) than another, no matter who’s going first, then there’s no reason for Left to make that move in any perfect play; it shouldn’t affect who wins in any combination of games. Suppose a position G has two left options Gℓ1≤Gℓ2. Then we say that Gℓ1 is “dominated” by Gℓ2; the left option Gℓ2 is not worse for Left no matter what. Similarly, if Gr1≤Gr2 then Gr2 is “dominated” by Gr1 (remember that lower positions are better for Right).

4. If F⊳ıG, then introducing F as a left option gives you an equivalent position (and analogously for Right).
Why? By symmetry, I’ll only prove the Left case. We need to show that {F,Gℓ|Gr}={Gℓ|Gr} (here Gℓ and Gr range over the relevant options). In other words, we have to show that {F,Gℓ|Gr}-{Gℓ|Gr}={F,Gℓ|Gr}+{-Gr|Gℓ} is a P-position. If the first player moves in a component to ±Gℓ or ±Gr, then the second player can respond to make the whole game 0 (e.g. Gℓ-Gℓ). The only chance the first player has is if they’re Left and move to F-G, but Right can win that (on their turn) since F⊳ıG, so even in this case the first player to move loses. ✓

In Winning Ways Vol.1, theorem 4. is called “The Gift Horse Principle”.

5. If you delete a dominated option, you get an equivalent position.
Why? By symmetry, I’ll only look at the Left option case. Suppose Gℓ1≤Gℓ2. For tidiness, let H denote “G with Gℓ1 deleted”. Note that by 1., Gℓ2⊳ıH. Combining that with Gℓ1≤Gℓ2 and using 3. tells us that Gℓ1⊳ıH. From that inequality and 4., “H with Gℓ1 added”=H, so G=H. ✓.

This fact has some implications we already knew: In that {0,1|2} example, 0 is dominated by 1, so we may delete it, leaving {1|2}=1+1/2. In { -5 | 0, {*,*4|*,*4} }, {*,*4|*,*4} is dominated by 0 (in fact, they’re equal since mex({1,4})=0), so we may delete it, leaving {-5|0}=-1. We already could have done that because the equality case is also a consequence of II.2.1. However, this theorem about deleting dominated options that took a little work is much more general.

Reversible Options

As with the deleting of dominated options, this next method of simplification is also motivated by relatively simple strategic concerns. Suppose you move in F to a position G where I can move to a position H that’s at least as good for me as F was (as if I’ve at least undone your move to G, and perhaps done even better). Then instead of moving to G, it would be simpler if you could just jump straight to your options in H. It may not be obvious that this sort of replacement wouldn’t change the value of the game in combinations. For instance, you may want to think about the case where I have an even better option than H (call it H′) in G; why is it ok to let you jump to options of H instead of options of H′?

More formally, suppose G has a left option Gℓ1 which has a right option Gℓ1r1≤G. Then Gℓ1 is said to be “reversible”, and we say that it “reverses through” Gℓ1r1. Similarly, a right option of G is reversible if it has a left option ≥G. To formalize the “jumping”, we can talk about replacing reversible options:

6. If Gℓ1 reverses through Gℓ1r1, then replacing G’s option Gℓ1 with all left options Gℓ1r1ℓ yields an equivalent position (and similarly for reversible right options).
Why? By symmetry, I’ll just prove the reversible left option case. We have to prove that {Gℓ1r1ℓ, Gℓ′ | Gr}={Gℓ1, Gℓ′ | Gr} where Gr ranges over the right options of G, Gℓ′ ranges through all of the left options of G except Gℓ1, and Gℓ1r1ℓ ranges through all of the left options of Gℓ1r1. Once again, we have to show that the difference is a P-position; we’re looking at {Gℓ1r1ℓ, Gℓ′ | Gr}-{Gℓ1, Gℓ′ | Gr}={Gℓ1r1ℓ, Gℓ′ | Gr}-G={Gℓ1r1ℓ, Gℓ′ | Gr}+{-Gr | -Gℓ1, -Gℓ′}.

  • Moves by first player to one of the ±Gℓ′ or ±Gr can be responded to in the other component to leave 0 (e.g. Gr5-Gr5).
  • A move by Left to Gℓ1r1ℓ-G is bad for Left since Gℓ1r1ℓ⊳ıGℓ1r1 by 1. and Gℓ1r1≤G by reversibility. Combining these and using 3. tells us that Right would win.
  • The remaining case is if Right moves to {Gℓ1r1ℓ, Gℓ′ | Gr}-Gℓ1. Left can respond by moving to {Gℓ1r1ℓ, Gℓ′ | Gr}-Gℓ1r1.
    • Then, if Right tries to move to something like {Gℓ1r1ℓ, Gℓ′ | Gr}-Gℓ1r1ℓ, Left will respond by moving to Gℓ1r1ℓ-Gℓ1r1ℓ=0.
    • If instead, Right moves to something like Gr-Gℓ1r1, they’ve lost because Gr-G≤Gr-Gℓ1r1 (by reversibility) and 0⊳ıGr-G (by 1.) so by 3. this is bad for Right.

It’s good to think about when we’ve replaced reversible options in the past. Consider {0|5}. Since the right option 5={4|} has a left option 4≥{0|5} (this inequality can be checked without knowing what number {0|5} is), 5 reverses through 4, and we may replace 5 with the right options of 4={3|}. Since Right has no options in 4, we can replace 5 with nothing, and have {0|5}={0|}=1. Of course we knew this already from our analysis of Numbers, but this is just an example of the power of replacing reversible options.

A slightly more complicated example would be the impartial game G={ {*|*},*,*3|{*|*},*,*3}. *3 has a right option *2 that’s equal to G (and hence at least as good for Right as G), so the left *3 reverses through *2 and we can replace it with all of *2’s left options, leaving G={{*|*},*, 0,*|{*|*},*,*3}. Similarly, the other *3 reverses through *2 and we have G={{*|*},*, 0,*|{*|*},*, 0,*}. Since * is the same position as *, we don’t need two copies on each side, so G={{*|*},*,0|{*|*},*,0}. Since {*|*}=0 (they’re equivalent positions), we can delete {*|*} from each side for being a dominated option. This leaves us with a much simpler G={0,*|0,*}. (Of course two applications of the mex rule would have told us the same thing.)

Canonical Forms

Let’s say you’ve deleted dominated options and replaced reversible options repeatedly and were able to get to a point where you couldn’t do it anymore. Then it turns out that in some sense there’s no other simplification you could possibly do after that. Also, sort of like putting fractions in simplest form, finite Conway positions have a “canonical form”. Also like fractions, you can simplify partially, and full simplification is tedious and not always necessary, although it makes it very easy to check equality once you’ve done it.

7. If G and H have no dominated or reversible options, then G=H exactly when every left/right option of G is equal to a corresponding left/right option of H and vice versa.
Why? If the corresponding options are equal, then by II.2.1, G=H (even without the assumption).

Now assume G=H and there are no dominated/reversible options. Since G=H, G-H is a P-position, so no matter what move Left makes, Right has a winning response (to a position ≤0). Suppose Left moves to a position like Gℓ+(-H). It can’t be that something like Gℓr-H≤0 because then we’d have Gℓr≤H=G so Gℓ would be reversible. Therefore, Right’s response must be in -H. A right option of -H is the negative of a left option in H, so we have ∀Gℓ∃Hℓ Gℓ≤Hℓ. By the same argument with G and H switched, we have ∀Hℓ∃Gℓ Hℓ≤Gℓ.

Combining these two facts gives statements like “for any Gℓ1, we can write something like Gℓ1≤Hℓ1≤Gℓ2“, but that would mean that G has dominated left options unless all of these inequalities were actually equivalences. Thus, every left option of G is equal to a left option of H. The other three cases (e.g. “every right option of H is equal to a right option of G”) are all similar.

The reason 7. was so awkwardly worded is that there are different positions that are equivalent that might come up. For instance, { {|} | } is {0|}=1 and has no dominated or reversible options. Note that { {*|*} | } is equivalent to {0|}=1, and it also has no dominated/reversible options. Therefore, by 7., its left option {*|*}=0, as already known. Incidentally, it’s worth thinking about 7. in non-short cases: If you have a position G that’s equal to ω+1 (which is {ω|}), and G has no dominated or reversible options, then G must have no right options and only one left option equal to ω.

8. Short Conway positions have a unique equivalent “canonical form”.
Note that 0={|} has no options at all, so it certainly has no dominated/reversible options; {|} will be the canonical form for any position equivalent to 0. By induction, assume that all of G’s options are written in their unique canonical forms. Then delete dominated options and replace reversible options until you can’t do so anymore. By 7., what you end up with is unique. ✓

We’ve seen some canonical forms before: for Numbers and stars. For example, the canonical form for {0,-7|1,1+1/2,3/4} (or any equivalent position) is {0|1} where 1 stands for {0|} exactly and 0 stands for {|} exactly. The canonical form for {0,*5|0,*5}=* is {0|0}, i.e. { {|} | {|} }.

The shortness condition in 8. is essential. Consider ω={0,1,2,3,…|}. It has no reversible options since nonnegative integers have no right options. However, all of its options are dominated. 5. tells us we can delete one of the options (and hence any finite bunch of them), but we can’t delete them all (we’d end up with {|}=0). It’s not even true that we can delete only finite bunches of them; our analysis of Numbers tells us that as long as we leave an infinite bunch of nonnegative integers, it’d still be equivalent to ω. For example, we can delete all of the non-squares, and find that ω={0,1,4,9,…|}.