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 *un*familiar 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 Gr_{1}≤Gr_{2} then Gr_{2} is “dominated” by Gr_{1} (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ℓ_{1}r_{1}≤G. Then Gℓ_{1} is said to be “reversible”, and we say that it “reverses through” Gℓ_{1}r_{1}. 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ℓ_{1}r_{1}, then replacing G’s option Gℓ_{1} with all left options Gℓ_{1}r_{1}ℓ 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ℓ

_{1}r

_{1}ℓ, 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ℓ

_{1}r

_{1}ℓ ranges through all of the left options of Gℓ

_{1}r

_{1}. Once again, we have to show that the difference is a

*P*-position; we’re looking at {Gℓ

_{1}r

_{1}ℓ, Gℓ′ | Gr}-{Gℓ

_{1}, Gℓ′ | Gr}={Gℓ

_{1}r

_{1}ℓ, Gℓ′ | Gr}-G={Gℓ

_{1}r

_{1}ℓ, 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. Gr
_{5}-Gr_{5}). - A move by Left to Gℓ
_{1}r_{1}ℓ-G is bad for Left since Gℓ_{1}r_{1}ℓ⊳ıGℓ_{1}r_{1}by**1.**and Gℓ_{1}r_{1}≤G by reversibility. Combining these and using**3.**tells us that Right would win. - The remaining case is if Right moves to {Gℓ
_{1}r_{1}ℓ, Gℓ′ | Gr}-Gℓ_{1}. Left can respond by moving to {Gℓ_{1}r_{1}ℓ, Gℓ′ | Gr}-Gℓ_{1}r_{1}.- Then, if Right tries to move to something like {Gℓ
_{1}r_{1}ℓ, Gℓ′ | Gr}-Gℓ_{1}r_{1}ℓ, Left will respond by moving to Gℓ_{1}r_{1}ℓ-Gℓ_{1}r_{1}ℓ=0. - If instead, Right moves to something like Gr-Gℓ
_{1}r_{1}, they’ve lost because Gr-G≤Gr-Gℓ_{1}r_{1}(by reversibility) and 0⊳ıGr-G (by**1.**) so by**3.**this is bad for Right.

- Then, if Right tries to move to something like {Gℓ

✓

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,…|}.

Pingback: II.8: Arrows | Combinatorial Games