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

Advertisements

One thought on “II.6: Simplifying Conway Positions

  1. Pingback: II.8: Arrows | Combinatorial Games

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s