Let's put a handful of chess pieces down on an infinite chess board.

All the pieces move according to their usual rules, but there are no bounds on how far they can move.

Who will win, and in how many moves?

8 00:00:20,890 --> 00:00:25,420 To understand infinite chess, let's start with finite chess.

Chess is the kind of game mathematicians like.

For one, it's a game of perfect information, which means that everything is out in the open to be analyzed, unlike poker, where relevant information-- the other player's hand-- is hidden.

Chess doesn't involve randomness.

Games of chance, like those that involve dice, are often harder to analyze, and you can't guarantee an answer.

Chess only has two players, and provided you play with some standard rules about not repeating positions, each game must end in a finite number of moves.

Let's also assume we're playing with some rules that exclude ties.

That'll make things simpler.

Mathematicians have many favorite examples of these kinds of games.

Chess, checkers, Go, dots and boxes, and many more.

Check out the links in the description to learn more about these mathy games.

Chess, even in its finite version, is complicated.

Let's start with a simpler game.

A single pile version of Nim, which I'll call pile game.

Start with a big pile of marbles.

Alice and Bob alternate taking 1, 2, or 3 marbles from the pile, and the person who takes the last marble wins.

Let's say they start with 5 marbles and Alice takes 3.

Bob could take 1, but then he'd lose, because Alice will take the final 1.

A better idea is for him to take the final 2.

Then he'll win.

This game seems a little boring, but the strategy behind it is pretty cool.

If they start with n marbles, what's the best strategy for Alice?

What about Bob?

If you haven't seen this problem before, I strongly recommend playing with different numbers of starting marbles and trying to find a strategy.

We can make a game tree for our pile game, which is sort of like a diagram of all possible games.

If we start with 5 marbles, Alice can pick either 1, 2, or 3 marbles.

Then they'll be 4, 3, or 2 left, respectively.

Then we map Bob's choices in the same way.

Then Alice's, then Bob's, and then Alice's.

Each time someone takes the last marble, we mark their win.

Notice that Alice has a winning strategy, which means that she has a method of playing that guarantees she will win.

First, she picks one marble.

Then Bob has three choices, take 1, 2, or 3.

Regardless of what he does, she can respond in a way that guarantees her win.

By definition, at most one player in a game can have a winning strategy.

Not both.

So if both players are playing optimally, Alice will win.

But how long will it take for Alice to win?

Let's define a doomsday clock.

The doomsday clock tells us how many moves it will be until the inevitable winner, Alice, in this case, wins.

By the way, that's not a math term.

Mathematician Joel Hamkins calls this the game value, and in chess they call this mate-in-n. Let's look at a game with 5 marbles.

In the beginning, the doomsday clock is 3.

Alice can force a win in 3 moves.

After she moves, the doomsday clock is 2.

No matter what Bob does, he'll lose in 2 moves.

After he goes, the clock is 1, meaning Alice wins after she makes her turn.

OK.

Here's an important definition for us.

A game is determined if one player has a winning strategy.

And here's an important theorem known as Zermelo's Theorem.

Every game of the type we've been talking about-- games with perfect information, no randomness, two alternating players, no ties, that end in a finite number of moves-- these kind of games are determined.

You can actually use the game tree to prove Zermelo's theorem by backtracking through the tree.

I'll let you fill in the details of the proof, or give an entirely different proof.

Let us know what you're thinking in the comments.

Why is this such a big deal?

Well, for one it implies that chess, the normal, finite version, is determined.

There is either a strategy for White or a strategy for Black that will guarantee a win.

Of course, nobody knows this strategy, mostly because the game tree is really huge.

Now, let's move into the world of infinite games.

Infinite games are ones that could last infinitely many moves.

Our big theorem about finite games was that they are determined.

Now, the analogous question is, are infinite games determined.

Does one player have a winning strategy?

Well, just like pretty much every other time we step from the finite world to the infinite world, things get weirder.

Whether or not all infinite games are determined is a complicated issue depending, surprisingly, on what set theory axioms you choose.

But within the standard system, ZFC, there are some types of infinite games which are determined and there are some games which are not determined.

What matters for our purposes is that infinite chess is determined.

There is a winning strategy.

So from any starting position, one player in infinite chess will always have a winning strategy.

Let's get more precise about the infinite chess we're playing.

Both White and Black have, at most, one king on the board, and, as always, the goal is to capture the other side's king.

Normal checkmate.

And importantly, that checkmate will always happen at some finite time during the game.

There can be any number of any of the other pieces, including possibly infinitely many, starting off in any arrangement.

The pieces move normally, but they're unbounded.

For example, the king can hop one in any direction, and the bishop can move diagonally as far as it wants.

Knowing that infinite chess is determined, we can ask about winning strategies from different starting positions.

Is White or Black guaranteed to win from a given starting position?

And how long does it take to force a win?

That is, what's our doomsday clock say?

Here's a starting position where White is guaranteed to win in six moves.

Black's king is stuck, and so it needs to move the rook up.

White moves its rook to keep the king in check.

Black moves its king, but White can follow with its queen.

The white queen and rook continue to squeeze the black king up to the barricade until it's stuck and forced into checkmate.

So on the first move, what's the doomsday clock?

Well, Black has a few options.

It can move the rook like it did and lose in 6 moves, or do something silly like move one of the pawns, in which case White will win in 2 moves.

Well, in this situation, we say that the doomsday clock is 6, because that's the longest Black can hold out before its king is captured.

It's the maximum time before the game ends.

But can the doomsday clock be infinite?

In the Hydra episode, we discussed infinite ordinals, infinite counting numbers.

After all of the natural numbers, 0, 1, 2, 3, 4, and so on, we have the first infinite ordinal, omega.

Then comes omega plus 1, omega plus 2, and so on.

Then omega times 2, omega times 2 plus 1, and so on.

Then omega times 3, omega times 4, then omega to the omega, and omega to the omega to the omega, and so on.

Let's look at this starting position.

It's like before, except there is no line of pawns blocking the rook.

Notice that the same thing happens.

The black rook moves up to make way for the king, and the white queen and rook continue to chase the black king up until it gets trapped by the rook.

The only difference between this and before is that now the black rook can move as far as it wants on the first turn.

The further the rook moves away, the longer it will take before the white queen and rook trap the black king against it.

So what's the doomsday clock say at the initial position?

Well, the further the black rook moves on its first turn, the longer the game lasts, and the black rook can move an arbitrarily large, but finite, number of moves.

So White will eventually, after a huge, finite number of moves, capture the black king.

Since there's no limit to how far away the rook can move, there's no limit to the number of moves the game could last.

The doomsday clock is the maximum length a game can last.

It must be bigger than all the finite numbers.

It must be the first infinite ordinal, omega.

All the games are finite, but unbounded in length, so the doomsday clock is infinite.

Hamkins and his collaborators have developed an incredible amount of infinite chess mathematics.

They came up with the chess position we just looked at, and have also demonstrated a starting position in infinite chess where the doomsday clock is omega squared.

This is because there are two separate times in which Black can delay its inevitable death by an arbitrarily large number of moves.

There's even examples of infinite chess with doomsday clock omega squared times 4 and omega to the 4.

We've linked to these results and a bunch more in the description.

There are so many cool ideas behind infinite chess that we could make several more episodes on it.

Can you construct an interesting starting position in infinite chess?

Does someone have a winning strategy?

Let us know in the comments.

See you next week on Infinite Series.

Hello.

I wanted to respond to some of the comments about our Fair Division episode.

So Bjorn and several others made an interesting point.

In real life, you might not always pick the free room.

If there's another room, and it's cheap, and it's way better than the free room, you'd probably pick that one.

But in order to get all the math to work out so nicely, we needed to make some assumptions about our mathematical model, and one of the assumptions we made inside of our model was that you would always choose a free room to a non-free room.

All right.

Steve's Mathy Stuff answered our mini-challenge showing that there's an odd number of fully labeled rooms.

Basically, there are an odd number of rooms which you can access from the outside, and there are an even number of rooms which you cannot access from the outside.

Since an odd number plus an even number is an odd number, that means there's an odd number in total of fully labeled rooms.

You should check out his comments for more details.

Finally, elevating moment asked an intriguing question.

Can you rig the system?

Can you lie about your room references in order to get a better outcome?

Maybe.

Lying might also get you a worse outcome.

You might end up with a room you hate.

I'd be really curious to see if one of you can come up with an example where lying improves your outcome, or maybe it makes it worse.

All right.

See you next week.

[MUSIC PLAYING]