Infinite Chess | Infinite Series

Infinite Chess | Infinite Series


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? 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]

100 thoughts on “Infinite Chess | Infinite Series

  1. Capture the black king? CAPTURE THE BLACK KING?? Ugh, go back to your infinitesimally small lengths and tangents to curves and never come to the wonderful world of chess. So many of you mathematicians are defiling it. Understand the brilliance of it first, then comment on it. UGH!!

  2. Forgive my ignorance. Is infinite chess always played with both pieces near each other or normally, at opposite ends of the board; if it is the latter then the pieces will never meet to engage in the game.

  3. I would like to see infinite chess in real life.. 🙂 When a player dies then someone takes over. Th game would last as long as humanity. And of course, if machines outlive humans, then they can continue the game.. By the way, what if in the beginning "1" and "8" rows are infinite rows apart?

  4. 0:24 BOARD SET UP INCORRECTLY. WHITE SQUARE SHOULD BE ON THE LOWER RIGHT (from the players perspective). Do you research, PBS!!

  5. Will there be a video explaining more about the fact that a game's determinacy can depend on the chosen set theory axioms? (perhaps there's one already?)

  6. There is a simple solution that would lead to black winning or draw by no pieces taken or repetition which is the move room D4 to E4

  7. 9:41 I feel the doomsday clock being infinite is totally wrong. Let's just imagine a function f(x)=y, where the domain are the squares you can place your rook at, and the range is the doomsday clock value. We can't just say that f(∞)=∞, because we all know that you can't just plug in infinite as our x, and have infinite as our result, because this would mean we have squares like h∞, or ∞'8 (∞' here would represent the final column) or even ∞'∞. The board is infinite, that means it doen't have a final square…

  8. Chess supports draws, so it’s not clear that Chess has a winner. But it either have one color that always wins or it always end in draw, with perfect game of course

  9. There's is a small problem here. The game is draw if there are no captures for more than 50 moves. So all black has to do is to move 50 squares away from it's starting square and the game is a draw.

  10. In addition to infinite chess, there is chess where the board is infinite, but the bishop, rook, and queen are limited to moving one million squares at a time. There are different rules you can use for knights. In the 1970's, there was a chess puzzle in Scientific American using a board like this.

  11. On your board at 6:59, I don't think there's anywhere, even on an infinite board, that you can position the white king to make him immune to attack by black's rooks. At least one of the rooks will always be able to move into the same row or column as the king, placing him in check, and preventing white from moving forward with its own check. Black can then keep this going by chasing the king around the board with the rooks, and may even be eventually able to force a win; I'm not sure. But in any case, the situation is more complicated than what you've presented. It only really works if white doesn't actually have a king, in which case… yeah, you're right, it's hard to imagine a scenario in which they lose.

  12. I have an idea, on one of your moves you move your bishop/queen/rook to the further most square, this will take infinite time to do, so both you and your opponent will die at the board resulting in a draw

  13. The goal is NOT to capture the other player's king. She completely lost me with that comment! Sorry, if she doesn't know the rules of winning, she cannot analyze the math of winning.

  14. Chess would get really interesting (more than what it currently is) with more than two dimensions. Infinite 4D chess anyone?

  15. Bah.. Apply your win determinism analysis for Infinite 3 Dimensional Quantum Chess then Miss clever trousers! Fascist.
    😉

  16. My friend forgot to put his King down on the board and we accidentally started playing and when we noticed…guess who won? ME!!!
    6:28 that animation tho XD

  17. So this is supposed to be Infinite Chess, and you said the black rook can move as far as it wants on it's first move. Then why can the rook only move a finite number of squares then?

  18. More mathemagics…why do mathematicians think that their rules written into equations based upon assumptions that they pull out of their arses have anything to do with everyday reality. People win games because they see more than the opponent. Perception wins. Increase your perception. See more win more.

  19. With that chess position, assuming the white king exists and is out of sight, black could use his three rooks to perpetually check the white king. That should be doable with care.

  20. In the example after minute 7 she says white has a wining strategy but couldnt black just move the center rock one field to the left to then have a winning strategy

  21. Don't do videos on logic and chess if you actually don't care about a correct argumentation. Maybe you should try proofing Zermelo's theorem yourself before making such a ridiculous video…

  22. Since chess is always played over a finite number of moves, a limit value for the game could not be more than omega, assuming perfect play of course. It doesn't matter how many times it can delay the game, what matters is that that number is finite. Finite times finite is still finite, and so omega will do for every extended game, you simply have a finite number of moves of the whole game no matter how many times you get a delay (if finite). Omega is not a number that ever turns up in the equation, other than as the definite (up to but not equal to) limit.

  23. This makes no sense. At 9:00, she basically explains that since the board is infinite, there's a doomsday clock. (To prevent games from going too long, of course… Right?) Except the doomsday clock is also infinite. Is chess that complicated that we're getting into like quantum physics where something is true and false at the same time? WTF am I even watching?

  24. English Draughts, or Checkers, is a draw by perfect play by both sides. By the “one player has a winning strategy” this game would not be considered determined?!? What am I missing? Why is it not “determined” to be a draw? It fits all possible conditions but a forced win by either side. And as such, would cast doubt on define chess as determined given the above definition and Draughts creating a doubt about the assumptions made.

  25. Around the 8:30 mark I was looking at it and think I see away to get out of the situation but I’m not sure I may just be blind

  26. 0:24 my brain hurts looking at that chessboard. It's set up incorrectly. Why is it so hard for people to get something as simple as the correct starting position right?

  27. This is so confusing to me, it has nothing to do with chess if you remove ties or remove boundaries or any other rules. Also, it is not very informative to just discuss a hand full of positions, I dont see how infinite chess is easier to solve, compared to finite chess, so why looking at it in the first place? Why not look at the "real" game which almost a billion people play ^^

  28. How can you make a entire video about winning strategy in chess and get it wrong that there doesn't have to be a winning strategy

  29. This is wrong, (sorry) but I have deeply researched this subject. Theory has it that neither white NOR black has a winning strategy
    at 7:40 another error not two but one move!

  30. Things can't be both ways if. 33 is equal 1/3 and. 66 is equal to 2/3 and .99 is equal to 1 then if the first player moves the maximum number of spaces the game will never end because the number of spaces will be equal to infinity

  31. Me: checkmate
    Opponent:w-where?!
    Me:*points somewhere off In the distance* I put a bishop there a while ago, so I win

  32. Actually, chess has ties, so it might or might not be determined, which is part of why no one knows the "optimal" strategy.

  33. I might be stupid, but I dont understand why infinite chess must have a winner. My intuition as a chess player is that there would be much much more draws, since already in normal chess a huge portion of games are decided either via zugszwang(for which there are much less opportunities for), or worse, via queening a pawn, which is impossible in infinite chess?
    That means that if you don't design a position with a winning plan,

  34. Foolproof strategy: the day before your match, tell your opponent that you're severely narcoleptic. They of course will be reluctant to play you (because who wants to risk having their opponent randomly fall asleep on them, how boring it would be), which is when you introduce the house rule that slipping into unconsciousness constitutes a forfeit. Then, on the day of your match, treat your opponent to a (spiked) drink as a sign of sportsmanship. The rest follows.

Leave a Reply

Your email address will not be published. Required fields are marked *