II.8: Arrows

The choices of examples in this post come from Winning Ways

Introduction to Toads and Frogs

A fairly rich example of a Conway game is Guy’s “Toads and Frogs”. It is played on one or more strips of boxes, that are either empty, contain a toad, or contain a frog. A position might look something like Toads and Frogs.
On their turn, Left may move a toad one space to the right (if it has an empty space to move to), or hop over exactly one frog (if it has an empty space to hop to). Similarly, Right moves/hops with frogs to the left. As with all two-player normal play games, you lose if it’s your turn to move and you cannot. Because pictures of toads and frogs take up a lot of space, it’s traditional to use text: For example, the pictured position would be represented by the string “TT□FTF□” (occasionally “.” is used instead of “□” when □ is hard to type). If you’d like to get a feel for the game, you can play various examples of the special case “TT…T□FF…F” at this page. Be warned: they call toads “frogs” and vice versa, in contrast to essentially all literature on the game.

By analyzing small Toads and Frogs positions, lots of familiar values come up. You could make a huge table with positions with uninteresting values (and people have), so let’s consider some carefully-chosen examples together that will lead us somewhere interesting:

In TFTF□, Right has no legal moves (frogs can’t go leftwards), and Left’s only move is to TF□FT. But from there, Right would respond by moving to TFF□T, from which neither player has a legal move. Thus, TFTF□=TFF□T=0.

In TF□TF, if it were Right’s turn, they’d move to TFFT□ and then Left would move to TFF□T=0. If it were Left’s turn, they’d move to □FTTF and then Right would move to F□TTF which has no legal moves. Thus, TF□TF=F□TTF=0.

Now consider TFT□F. Left would move to TF□TF=0 and Right would move to TFTF□=0, so TFT□F=*! Apparently, Toads and Frogs, which seemed so partizan, has a position equivalent to a Nim pile of one piece.

A curious position

Next consider T□TFF. Left would move to □TTFF, which has no legal moves (so it’s 0), and Right would move to TFT□F=*. In other words, T□TFF={0|*}. This is a position that we haven’t discussed in any detail before, so let’s study it carefully.

Firstly, since 0 and * don’t have many options (when written in canonical form), it’s easy to check that {0|*} has no dominated or reversible options. To make things easier, let’s define u={0|*} for “unknown”. From II.6.1, we know 0⊳ıu⊳ı*. This doesn’t tell us very much, because that’s something that’s also true of every *n for n>1 (e.g. 0‖(*2)‖*). Since this isn’t too complicated a position, it should be easy to find out who wins. If Left gets to go first, they simply move to 0 and win. If Right gets to go first, they move to *={0|0} and then Left moves to 0 and wins. Therefore, u is an L-position, i.e. u>0. At this point, we know that 0<u⊳ı*, but we can’t have 0<u<* since 0‖*. So it must be that u‖*; unlike positive Numbers, u is a positive position that’s still not bigger than *.

For any positive Number x, we have u‖*<x, so by II.6.3, we have u⊳ıx. Let’s figure out which positive Numbers u is less than. We can start by comparing u to 1={0|}. In u-1={0|*}+{|0}, Right could start by moving to *-1<0 and win. If Left starts, they’re forced to move to 0-1<0 and Right wins anyway. Thus, 0<u<1. In general, if Right gets to go first in u-x for a Number x>0, then they’ll win by moving to *-x<0, so we only really have to consider what happens if Left goes first. By Number Avoidance, we only have to consider the moves in u. If x is a positive Number, then Left’s move is to -x and they lose, so u<x for all Numbers x! This should be somewhat surprising if you’ve thought about the Surreals in any detail: u is a positive position that’s less than 1/4, and less than 1/ω, and less than 1/[the ordinal corresponding to the size of the set of all functions from ℝ to ℝ], and… In other words, it’s so small that in some sense anything that makes sense as a positive number is bigger than it (even though it’s exemplified by the really accessible T□TFF). Since it’s just barely positive, u is denoted ↑, read “up”. For symmetry, -↑=↓, read “down”.

There’s even more we can ask about ↑, because there are a lot of comparisons we don’t know. For instance, how does ↑ compare to *2? We must see who wins ↑-*2={0|*}+{0,*|0,*}. If Right goes first, they can move to ↑>0 or ↑+*‖0 or *+*2‖0, so they’ve lost. If Left goes first, they can move to ↑ and win. Thus, ↑>*2 (similarly for *3, etc.), even though ↑‖*. Another thing we could ask is “how does ↑+↑>↑ compare to *? In ↑+↑-*, Left could move to ↑+↑ and win. If Right goes first, they either move to ↑+↑>0 or to ↑+*+*=↑>0 and lose. Thus, ↑+↑>*. The convention is to write ⇑ (read “double-up”) for ↑+↑, but that notation doesn’t work well past quadruple-up, so we also write 2.↑=⇑, 3.↑=⇑+↑, etc. Incidentally, n.↑<x for any integer n and positive Number x by an inductive argument (for once, it’s traditional induction).

The Conway “Line”

We now know a number of things about some Conway positions, and they’re not all Numbers so perhaps we shouldn’t speak of the Number line. However, we can still imagine filling in gaps in our knowledge. For instance, suppose 0<y<↑ for some Conway position y (it can’t be a Number). Then y<↑‖* implies y⊳ı* by fact 3. from the previous post. But y<* is impossible since it would imply 0<y<*, contradicting 0‖*. Thus, as we might hope, y‖* for any y between 0 and ↑ (not that we’ve encountered any such positions yet).

Putting many of the inequalities collected so far to use, we obtain the following picture of the Number line plus other positions. Here ☆ represents *n for any n>1, positions are above/below ones they’re confused with, and question marks represent unknown relationships (e.g. we don’t know if there are positions greater than ↑ that * is confused with):

…-1 -1/2 -1/ω ⇓ ↓ 0 ↑ ⇑ 1/ω 1/2 1…
               ?*****?           
                 ?☆?

With this sort of picture in hand, you should be able to answer any question of the form “Who would win this particular given sum of Numbers, arrows, and stars?”. Incidentally, the argument we used above to justify the * line of this picture generalizes to show that any position has a connected “cloud” of positions it’s confused with, in some sense (if it’s confused with both a and b with a<b then it’s confused with anything in between). Also, in some contexts, the number line may be flipped so as to have the L-positions on the left.

Positions with ↑ and ↓ as options

We learned about new positions ↑ and ↓, and we can add them to each other or to stars or Numbers just fine. But the game of Toads and Frogs can even show us positions where arrows are options. Consider TT□FF. Left’s only move is to T□TFF=↑, and by symmetry, Right’s only move is to -↑=↓, so this is {↑|↓}. Certainly this is an N-position, since Left would get to make it positive and Right would get to make it negative, but where does it fit on our Conway “line”?

Well, first we can try and put it in canonical form, to make it simpler to deal with. Obviously neither option is dominated, but what about reversible? If Left moves to ↑={0|*} then Right’s move is to *; is this at least as good for Right than {↑|↓}? We need to check if *-{↑|↓}≤0. For that to be false, Left would have to have a winning move right now. If Left moves in *, then Left leaves -{↑|↓}={↑|↓}, an N-position, for Right to win with. If Left moves to *-↑, this is ↓+* which is an N-position by our Conway “line” picture. Thus, * really is at least as good for Right as the original game, and Left’s move ↑ reverses through * to 0: {↑|↓}={0|↓}. But in our check of reversing, we learned more: by symmetry, since the winning moves for Right were N-positions, Right wouldn’t have a winning move from *-{↑|↓} either, so in fact we have {↑|↓}={0|↓}={↑|0}={0|0}=*.

Another basic position with arrow options we may wonder about is {↑|↑} (note that {↓|↓}=-{↑|↑}). Right off the bat we can say that this is an L-position, because the only moves are to ↑>0. We can also say that, by II.6.1, ↑⊳ı{↑|↑}⊳ı↑, so it must be that {↑|↑}‖↑. Being a positive position confused with ↑, maybe {↑|↑} is ↑+*2, or maybe it’s a totally new position.

To help us find out, we first put {↑|↑} in canonical form. Since {↑|↑}>0, it’s worse for Right than *, a right option of the left option ↑. Therefore, ↑ reverses to 0, and we have {↑|↑}={0|↑}. The right option ↑ doesn’t reverse because 0 (the left option of ↑) isn’t an improvement for Left over {0|↑}. Thus, we have the canonical form. Exercise: Compare {0|↑} to various positions of the form n.↑+*m to find its value (it is equal to one such position).

If you want to cheat, that exercise is actually part of the text of Winning Ways, as well as a chart (which only takes time to derive) of canonical forms for all positions of the form n.↑+*m.

Advertisements

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