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

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]才打開來看的。機會難得,我想看看中文版怎樣翻譯那些例句。」

「嗯~」少女對歐威爾明顯不感興趣:「難得有機會跟作者聊天卻被其他讀者打斷,你該不會站在那邊等下去吧。」

「才沒有。我的行程緊湊得很還要去找一堆只在最後一天現身的人,只能後約他們吃飯了吧?到時你還有哪本想要簽名一併給我。」

她揮舞著手上略舊橙色封面的小說:「不用了,簽名就是要在特別的時空才有紀念價值嘛。說起來,」她又指著她身下夾在她和電梯中間的大紙袋:「這是慰勞你的。」

他早就瞄到那袋東西,紙袋上的品牌很明顯不是來自出版商,也不會是補習班、教育軟件、宗教團體、文具商、棋院……等會理所當然出現在書展的公司。但他還是決定裝傻:「不會是鋼筆墨水吧?我有看到他們大減價,但日元貶這麼多算起來還是不划算,而且自從我改由網上改卷以後就沒怎樣用鋼筆了……」

「笨蛋,那有人用這麼大一個紙袋裝墨水的。」她從紙袋中抽出一小袋東西,那是一袋炸雞皮:「是上面的零食展啦。」

到這裡少年才猛然想起其實五樓其實另外有個零食展同時進行,說不定不少進場客都是為了零食才進來。說來也是,以前能擺滿一三五七四個展館的書展現在兩個都擺不滿,今時今日還有誰要讀書呢?只有他是個例外,幾天都抽不出時間上去看。

他接過那一包炸雞皮,包裝上的雞皮跟某上校炸雞的雞皮很像:「不會要在這裡打開來吃吧?可是出去的話外面太熱我一刻都不想待呢。」其實聽說為了遷就零食展,那個長久以來不准外帶飲食的規矩放鬆了一點。

她直接從紙袋裡抽出另一包炸雞皮打開,算是對少年問題的回應。

咔嚓咔嚓。雞皮香脆,但是雞油香味不足,像一塊比較厚的炸粉。二人就這樣看著窗外的維港景色把手上的零食消滅掉。電梯後面運輸工人們的聲音沒有停過,誰也沒空理會這對吃炸物發出嚴重噪音的狗男女。

「你在偷笑甚麼?」少女突然轉過去問他。

「沒……只是在回味這幾天下來各種互動而已。感覺掛上了參展者的牌子就像RPG裡換了個職業一樣,跟NPC的對話都會變得不同呢。出書的成本、找靈感的玄學……實在太多新東西了。」

他開始把不同作者的話題逐個介紹,反正手上還有零食她也樂得一邊吃一邊聽。不過吃到一半她的喉嚨就開始在抗議,她有預感今晚非來點涼茶不可了。

「對了,我記得亞士厘道有間不錯的日式餐廳。我們要不要去試試?」少年的邀請把她從夏枯草還是廿四味的訣擇中拉了回來。

「好啊。坐地鐵去?」她從紙袋裡拿出個膠袋把二人剩下的炸雞皮塞回去,然後拿出消毒紙巾一人一張。膠袋是買罐裝咖啡時拿的,現在要收一塊。

少年露出厭惡神色:「會展站是近但兩層單面的設計太糟糕了,人流的動線和指示都沒規劃好。我都不只一次不小心坐錯方向直接過海到紅磡。而且去尖沙嘴的話要到金鐘站轉車怎樣想都很奇怪。」

「那就只能……」

「船。」提到天星小輪時他的表情跟提到會展站時完全相反:「晚上吹吹海風會涼快一點,地理上也方便很多。」

對他來說,坐船其實是每年逛展不可或缺的一部分。提著戰利品站在圍欄旁邊,那短短十分鐘(大概沒有)的路程裡總是能反思到甚麼。又或者更直接地他只是想在船上輕唱一曲而已:

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

七月的香港當然沒甚麼寒冷的北風。可是在彼岸的家那邊,現在可是冬天啊。

*

旅居生活點滴,重返十幾年沒去過的活動意義重大。感謝所有抽空跟我說過話的人。

上面沒提過但我覺得最有趣的一件事是我買了某書的重制版,回家想想把這書的原版(~2009)翻出來時卻找到一模一樣的重制版--原來這本書在2018重制時我已托人買了一本,這次買的是重制版二刷。這本書又是哪本呢?在這個博客上找2018書展前後的帖文不難找到。

這次特別挑了幾首背景時空完全不同的樂曲。但其實我看見兩岸燈火的時候想唱的是這一首:

♪~幸せ幸せよ 嬉しい気持ちが止まらない
雨よ雨よもっと降れ
早く建てよ私のため
建てよ 進め 高い塔を
建てよ 進め 高い塔を--

2023.8.8
快將熱死之人