Saturday 19 August 2023

Formal framework of ordinal mate in infinite chess

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 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...

Tuesday 8 August 2023

夢.十夜 (X6) Fair



♪~一點一點增加濕度 滴汗是特別訊號
 很心急想找出路 但是並未做到
 似聽到看到海嘯 不需三秒便由旱土 改變做瀑布



♪~あゝ 君よ

鈴聲不合時宜地從少年的手機響起。手機被他調到震動模式,唯獨起床鬧鐘和少女來電都會響起這一首La prière的君よ。本來只是因為開頭的漸進音階作成鬧鐘鈴聲應該不錯,後來又覺得藍月なくる那個穿透的聲線十分醒神,聽著聽著就成了他的指定鈴聲。至於因為少女來電而響起這首歌,在這部手機上是第一次。










「很可惜沒有呢。我當時在對面的攤檔拿著一本George Orwell的Why I write中譯本一邊看一邊偷瞄作者到底有空了沒,一直到纏住作者的粉絲都離開再等作者回去休息室喝了口水出來我才撲過去找他,沒想到不到三五分鐘又有讀者找上門來了。只能說他的粉絲累積得越來越多了啊。」

「Why I Write你也看?不愧是Orwell的粉絲。不過這種東西回家看就好了嘛。」

「Why I Write其實很短,中文版還收錄了他幾篇其他散文。我看到裡面有政治與英語[Politics and the English Language]才打開來看的。機會難得,我想看看中文版怎樣翻譯那些例句。」



















♪~夜渡欄河再倚 北風我迎頭再遇
動盪如這海 城在兩岸凝神對視






♪~幸せ幸せよ 嬉しい気持ちが止まらない
建てよ 進め 高い塔を
建てよ 進め 高い塔を--