Monday, February 8, 2016

Infinity plus one and half Infinity (more checker stacks and surreal numbers)

J1, J2 and I spent more time talking about checker stacks and surreal numbers this evening. Most of the conversation was with J1, so J2 and I will have to catch up. I may have J1 lead the conversation and see how much he really understood and can explain.

Tweedledum/Tweedledee strategy

I had taken a look at Winning Ways for Your Mathematical Plays vol1 and thought it would be good to warm them up with the tweedledum-tweedledee strategy. I thought the pictures from hackenbush would be more inspiring, so drew these Tweedledum-Tweedledees. With checker stacks as recent background, J1 got the rules for the new game right away and he also saw the inverse symmetry of the colors (in fact, J3 happened to be there at the time and also noticed that symmetry).

Our wonky anti-twins

I asked which player has a winning strategy and gave him four options: red, blue, first player, second player. After a bit of thinking, he chose the second player and explained the copy strategy. We talked through a couple plays of the game just to see how it would work.

One interesting side conversation was the idea that the copying strategy isn't necessarily the most efficient way for the second player to play. This is in the sense of when the first player makes bad decisions, there could be ways for the second player to open up a huge advantage, while the copying strategy basically keeps returning the game to a 0 value.

On its own, this was quite a nice conversation, thinking through the pros and cons of continuing with the copying strategy. The ideas we discussed were:

  1. does the margin of victory matter? For some games yes, for others no.
  2. Is there a chance that we make a mistake if we stop copying and go for a "bigger" win? There might be some subtle strategic cunning that we are missing and any choice to stop copying could be irreversible.
  3. Is there a chance that we've mis-identified the game and it isn't exactly symmetric? Woe to us if we copy the first player until the error becomes obvious and we're now in a position behind them.
For what it is worth, this links to a dialogue in the Fritz & Chesster series (quoted from memory, not verbatim):
Fritz: What if your opponent isn't very good. Should you just clobber them?
Chesster: What do you mean?
Fritz: What if they make bad moves?
Chesster: Focus on your own strong play and developing your position. Don't play bad moves that assume your opponent is weak.
We also rounded out this part of the discussion by looking at the deep purple and figuring out a stack that is the additive inverse of deep purple.

Some stack values

Omega + 1
Watching more Mike Lawler videos, I saw his kids enjoyed thinking about ω + 1. We have previously talked about a more vague form of infinity and had broadly agreed that infinity - 1 is still infinity and infinity +1 is still infinity. I asked J1 to see if he still thought that (he did) and then asked about omega. If omega is infinity, what about ω +1?

His intuition was that it would still be omega, so we though about how to test. First, we recalled that deep blue has the position value omega, deep red is negative omega. With some thinking, he realized we could look at the game: blue + deep blue + deep red.

What do we need to check? See if blue has a winning strategy as the first player (why is this sufficient)?

Blue does have a winning strategy and J1 saw it faster than I had. Thus, (ω + 1) - ω is positive. "Wow, the omegas can cancel here!" He didn't expect infinity to work like this (nor did it, in our earlier conversations.)

We talked about a couple of other stack values with ω (2 deep blues, three deep blues, etc). I made an incorrect (I think) comment about ω2 and then said that the surreal numbers even have ωω and sqrt(ω) but that I wasn't sure what checker stacks would correspond with those values. He was pretty intrigued about the square root and asked what it would mean. This is all we got:

if A = sqrt(ω), then AxA = ω
Unfortunately, since we don't really know how to think of surreal multiplication in terms of checker stacks (yet?), this doesn't really help us so much.

However, this led J1 to ask, what about ω/2?

For regular 1/2, we had gotten lucky by adding a regular red on top of a regular blue. Maybe that would work here? Could we just add a regular red on top of a deep blue? We wrote down the position deep red + (deep blue)red + (deep blue)red and started checking whether blue would lose if playing first. We saw that this quickly gets to positions that obviously favor blue and concluded that our starting position had a positive value.

We still had our starting game position deep red + (deep blue)red + (deep blue)red on the white board. I figured out the fix and then told J1 that there was actually a simple way to modify what we'd written to correct it. I think he was still following the analogy to 1/2 and suggested making the top checkers deep reds. Talking through the new game for a while, we were convinced that we'd found a representation for ω/2 (wow!)

I thought this was really awesome. While we are still exploring something that other people have done before, he asked and answered a question that wasn't in the guidebook (so to speak).

Deep deep checkers
With the idea of stacking deep checkers on top of each other, we came up with the idea of deep-deep checkers. For example, remember that a deep blue can be taken off, removing itself and anything above it, and the player adds any non-negative finite number of regular blues to that stack. For a deep-deep blue, that checker gets removed along with any checkers above it, then the player adds any non-negative, finite number of deep blue checkers.

Using arguments nearly identical to the deep blue checkers, we figured out that a deep-deep blue + Nx(deep red) is still a winning position for blue, for any finite value N. That means the value of deep-deep blue is larger than Nω, for all finite N. This now seemed like a good candidate for a representation of ω x ω (aka ω2)

One final stack

Now that we've got deep deep checkers, it seemed natural to try something similar to the trick we'd learned earlier when we stacked a deep red on top of a regular blue. Remember, that gave us a stack with position value ε, positive, but smaller than any power of 1/2. Another way to see it was to play games with R + n (B deep Red), see that these are all Red wins, and conclude that B deep Red's position value is smaller than any fraction 1/n, for all positive integers n.

Using similar reasoning, we tested the games deep R + n (deep B deep-deep R). Following very similar reasoning, we think we see a pretty easy winning strategy for red, so the deep Blue deep deep Red has to be positive, but have value smaller than ω/n, for any positive integer n.

Hmm, maybe the position value of this guy is tiny? To be sure, we checked the game nR + (deep B deep-deep R). That is, n regular red checkers against a single copy of our suspect. Well, despite the awesome potential of a deep deep red, it falls whenever blue makes a move and these games are clearly blue wins.

So, what is the value of our new stack? Since it is smaller than ω/n, for any positive integer n, it feels like it could be ω * ε?

The problem: In Jim Propp's post, he says that ε and ω are multiplicative inverses (also, attacked in more detail in section 2.6 here), so their product is 1. However, our stack has value much greater than 1. We will have to think about ways to attack this new value.

Where is J2?

With J2, I teed up the question of how to find the additive inverse for a given checker stacks position. He instantly answered that you just need to swap all the colors. Seems like he is in good shape to verify this by working out the strategy as I did with J1.
On his own, he wanted to move onto the value of the deep purple stack, which he remembered as 2/3. I only had time to encourage him to think about two things:

  1. What stack is the additive inverse of a deep purple checker? As with J1, linking this with a RP stack was interesting.
  2. What could be the second player's winning strategy for 3P + 2R?

No comments:

Post a Comment