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.

Advertisements

One thought on “II.7: Adding Numbers to Other Games

  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