It's quite rare for me to talk about a particular youtube video on twitter, let alone on this blog. The previous exception is Alan Becker's animation series which makes sense considering the long time nostalgia. But from a creator of 2 videos?
I guess I just can't refuse the combination of chess and maths.
Chess is my recent hobby, entering around the world championship 23'. I don't really play 10 min games on toilet tub like others, but at least I am doing the puzzles every day now rated close to 2000. And needless to say, math is my lifelong hobby (or occupation).
Ordinal is always an abstract idea and often comes with even more with its abstract applications except for the Riemannian hotel I guess. But the above video is quite a concrete realisation of what ω is.
Let us examine the phrase "mate in ω" carefully. Consider the setup as shown in 3:02 of the video.
First, is it a mate-in-X? Yes, one side has a winning strategy in finite moves no matter what, and it's not a draw. Yes, finite moves -- this is the most fascinating concept in the whole thing, where you can create an ω with apparently finite stuffs.
Next we would like to find X. Clearly X is larger than any natural numbers given those infinite board setups, so ω is a potential candidate. Is it ω+1, ω+2 or any aω+b? This is the first tricky bit in the whole argument. The steps we need to checkmate is a cardinal, a number. The cardinality of those infiniteness is are equal (cue Hilbert here), so we can't really say this is ω+1 and that is ω because that setup takes 1 more steps to checkmate.
Below is the framework I would suggest:
Definition 1. A setup is Mω (mate in ω) if each possible opponent move results in a mate in k where k is a positive integer, but the supremum of such k's does not exist in natural numbers.
The extension of the clock to ordinals is simply a min-max thing. For example let us think about the finite case so that we can extend it to the transfinite one. What does it mean by a setup of M6? That means for each opponent move the best you can move is to keep it at most M5 (with is at least one opponent move that makes it M5). Now in the transfinite case it would be the following:
Definition 2. A setup is Mγ if there is a corresponding self move for every opponent move such that the best self move results in a mate number γ' that is less than γ, and that supremum of all such (γ'+1) is γ.
Together with the fact that a setup has a mating clock only if the game can be won finitely, the above covers all setups with a clock by transfinite induction (unless you doesn't believe in ZFC...).
Theorem. The mating clock as in Definition 2 is well-defined for all setup that is winning. In other words, any setup is either a draw or a mate for either side.
Proof: Suppose not. Then there is a setup that is not a draw but without a mating clock. By Definition 2 that setup has an opponent move that no self move would render a new setup with well-defined mating clock. That creates an infinite descent, contradicting the fact that a winning setup is finite.
Ok we are now done with the abstract bullshit. What's more important is whether the definition fits the intuition? Like how we judge the clock in the video? The answer is a clear yes. When the clock is of non-zero constant term, the opponent's move is just a regular one: the best your opponent can do is to retain the clock. But when the clock value is a limit ordinal (with no predecessor), it is then the time for the opponent to make the 'announcement' -- which drops the limit ordinal to something lower.
A Mω setup is clearly what we would expect intuitively: the opponent move is the announcement of Mk for k being finite.
A M(ω+1) is the setup that is one move away from Mω. The best the opponent can do is a move that keeps the board at M(ω+1) so that the self move would turn it to Mω.
A M(2ω) setup is where the opponent makes the announcement to turn it to M(ω+k) before it renders down to Mω, then to Mk.
And M(ω^2)? It is where the opponent makes the announcement to turn it into M(aω+b) (note that ω^2 is the supremum of all aω as well as of all aω+b). It's straightforward to verify that the setup at 6:58 exactly does that.
There is a separate problem though. Is there really a setup with mating clock Mγ for every γ? There are setups that are Mω and M(ω^2) respectively. Adding a constant is straightforward. How about M(2ω)? That is easy: add another double column of pawns from the example of Mω on 5:24.
Before even thinking about larger ordinals common seen in logic problems like $\varepsilon _0$, the video already addressed that M(ω^3) is a problem. Is that so? My guess is that it's probably the case due to planarity (or that the chess board is 2-dimensional) and the fact that chess pieces can only move in a finite set of inclination (45 degrees for bishop, 90 for rook, and 63.4 for knights). Even if M(ω^3) is possible, there should be a concrete value k so that setup of M(ω^k) does not exist, for some small k like 4 or 5.
When I first tried to create the framework for the clock I made multiple approaches to the problem. How do we define the clock value? Mω is always obvious, but the intuition is a definition that identifies M(2ω) and M(ω^2) clearly.
I have thought of measuring the asymptotic of possible mating sequences, before realizing that one may put infinitely many garbage to disrupt the mating sequence. In that way we cannot get the constant coefficient right too, but the constant should be clear defined just like above -- regular move required before the ω-announcement.
At the end the framework is so simple and elegant. What's more surprising is how close is it to how ordinals are built canonically. In other words, the way the mating clock is built in the exactly same way as how ordinals are constructed. How can you not love this analogy?
*
Before we conclude for today I just want to say the comment section is also treasury. Allow me to pick a few:
- Never realized how important the 50 moves rule is
- I want to flip the board but I can't on an infinite board
- Mathematicians finding how an infinite hotel ran out of rooms but here we are finding how a rook on infinite board ran out of checks
But the most interesting one is the one asking if we have an algorithm finding these ordinal mating value? Thinking again that we can put infinitely many garbage around I don't really have much hope...it should barely be on the horizon of being decidable if not undecidable (just my guess). Of course, another comment ask if infinite chess simulates logic gates as well. In that case, well, the halting problem will be what decides the complexity of this question.
Update (2024/1): they actually made a new video showing examples of M(ω^3) and M(ω^4)! They even claimed that M(ω^ω) or anything countably higher is possible! The examples are convincing, but the other claim requires some extra thoughts...
No comments:
Post a Comment