英國數學家,普林斯頓大學教授約翰·H·康威(John Horton Conway)證實於美國東部時間4月11日因新冠肺炎在美國新澤西州的住處逝世,享年82歲。
Conway的離世是數學界的重大損失。在緬懷Conway教授的帖子裡,有數學愛好者評論說:「Conway終究遺憾地輸掉了他的生命遊戲」。
生命遊戲(Conway’s Game of Life)是Conway最廣為人知的發明。
生命遊戲是一種元胞自動機(cellular automaton),源自大名鼎鼎的數學家馮·諾依曼在1950年代模擬細胞自我複製的發明。
馮·諾依曼貴為學界泰山北鬥,但他的初代元胞自動機並未引起學界重視。
而Conway的生命遊戲卻在問世之後立即在學界成為爆款。元胞自動機由此成為一門全新的學科,而生命遊戲則為數學家與碼農所熟知。
著名碼農刷題平臺Leetcode(力扣)的題庫中,第289題就是用代碼實現生命遊戲,標定難度中等。
這道題的確不難,因為Conway設計此遊戲的首要原則就是「規則簡潔」。生命遊戲的背景是無盡正方形格子組成的宇宙,其中每一格代表一個細胞。
每個細胞有兩種狀態,生存或是死亡。
細胞的繁殖或死去取決於其與周圍八個相鄰細胞的互動,遵循以下規則:
1. 若一個活細胞周圍活著的鄰居只有0個或1個,則此細胞下回合死亡。(模擬人口過少)
2. 若一個活細胞周圍活著的鄰居恰有2個或3個,則此細胞下回合存活。
3. 若一個活細胞周圍活著的鄰居超過3個,則此細胞下回合死亡。
(模擬人口過剩)
4. 若一個死細胞周圍活著的鄰居正好有3個,則此細胞下回合變為活細胞。
(模擬人口繁殖)
簡潔、合理的規則之下,生命遊戲蘊含著不勝枚舉的有趣「生命形態」。
Conway宇宙中,最簡單的永久生物是一個2×2的「方塊」。由6個活細胞組成的「蜂巢」也是一種簡單永久生物。
若沒有外來因素影響,永久生物將持續生存下去,其形態不會改變。
「方塊」 「蜂巢」
除永久生物外,另有一種周期性改變形態的生物。「脈衝星」是其中最漂亮的之一。
「脈衝星」有三種不同的狀態,每三回合循環各出現一次。
「脈衝星」
比周期型生物變化更頻繁的,是「飛船型」生物。
飛船型生物不僅周期性改變其形狀,且位置也會持續變化。
舊的細胞不斷死去,而新的細胞在新的位置持續重生。
這讓人想起那個古老的哲學問題「忒修斯之船」:如果忒修斯之船上的木頭被持續替換,直到船上所有的木頭都不是原本的木頭,那麼這艘船還是「忒修斯之船」嗎?
「重型飛船」
Conway的生命遊戲曾令無數極客沉迷於其中。不過,對於Conway本人而言,生命遊戲只是他數學研究結出的,相對不重要的成果之一。
實際上,Conway的研究成果遍及數論、有限群理論、扭結理論、編碼理論、組合博弈論等數學分支。
在今天,數學各子領域高度專業化,大部分數學家一生的研究只局限於一兩個領域。像Conway這樣研究橫跨多個不相關領域的數學家,實為鳳毛麟角。
因此,Conway被廣泛讚譽為「數學魔術師(mathemagician)」。
Conway很早就展露出數學研究的超凡天賦,但他在年輕時也曾陷入迷茫。
在20多歲時,Conway就對一些形式特別的趣味數學問題感興趣,卻擔心其他數學家將其研究評價為「平凡無奇」。
平凡無奇,即trivial,這是數學工作者絕不想聽到的最低評價。因此,Conway在相當長的一段時間裡,研究進度逡巡不前。
數年磨刃之後,Conway以一篇關於有限群的嚴肅論文一鳴驚人,在學界聲名鵲起。但Conway很快意識到,這世界上數學家總共沒有多少,因此他們的評價也沒有想像中的重要。那麼,為什麼要在意他人類似「不夠嚴肅」、「平凡無奇」的評價呢?
認清「他人的評價不重要」之後,Conway決定放飛自我,優先研究自己感興趣的方向。
生命遊戲是Conway投入思考的方向之一,不過這只是一盤開胃菜。
在發明生命遊戲的同一時期,也就是1970年前後,Conway發明了一套後來被稱為「超現實數(Surreal Number)」的數字體系。
超現實數與名為「超現實主義」的藝術流派沒有直接關聯,只是超現實數的問世本身就是一件帶有「超現實」色彩的事件。
在複數與超複數(如四元數)等數字體系建立後,數學界在很長一段時間內認為,數字體系的發展已基本走到盡頭。而Conway的超現實數,可謂於無聲處起驚雷。
比超現實數的發明本身更令人驚奇的是,Conway最初的目的並不是發展新的數字體系,而是研究一門來自東方的古老遊戲——圍棋。
在劍橋大學學習和工作期間,Conway接觸到圍棋,並沉迷於其中。
劍橋大學1985年出版的《數學人》一書中記載,在創造生命遊戲期間,「Conway與身邊的研究生一起工作,一面寫滿了數以畝計的草稿紙,一面手中把玩撲克牌、硬幣、貝殼、圍棋子,直到他們找出能夠平衡生與死的遊戲規則」。
或許是圍棋簡潔的規則啟發了Conway,使得他創造的生命遊戲同樣簡潔、美麗。
圍棋與生命遊戲的關係我們只能從一些隻言片語裡推斷,不過圍棋啟發了超現實數的發明,這一點確鑿無疑。
Conway在研究圍棋的官子(即終局階段)時領悟到,全局性的圍棋官子問題可以被視作若干局部官子問題的總和(例如下圖)。
而局部性的官子問題可以被進一步抽象為數字,超現實數則在此認識的基礎上應運而生。
Figure 1 圍棋官子問題
超現實數的基本形式是G={L|R},可以被視作像圍棋這樣雙人回合制遊戲的抽象。
L代表執黑棋方下一手導致所有可能結果的集合,而R則代表執白棋方下一手導致所有可能結果的集合。
超現實數具體到圍棋上,Conway考慮的是圍棋規則的一種變體——無停著圍棋(No-pass Go)。
常規的圍棋允許棋手在沒棋下的時候停一著,而無停著圍棋則不允許停著,這會導致一些微妙的區別。
第一個被創造的超現實數是0 = { | },L和R都是空集,相當於黑白雙方都沒有合法著數可下的局面,見下圖:
0 = { | }
現在若輪到黑方走棋,那麼根據規則,黑棋不能在C、D處白棋的「眼」裡自殺。
而圍棋的基礎知識告訴我們,兩隻真眼才能活棋。所以黑棋也不能自填僅有的A、B兩隻眼,因此黑棋無棋可下。
同理,若輪到白棋下,白棋也無棋可下。因此,{ | }這個局面的結果被指定為0。其含義是,此局面下,輪到哪那一方下棋,那一方就必輸無疑。
緊接著0 = { | }之後,下一組超現實數是1 = { 0 | },和-1 = { | 0 }。
在圍棋盤上,前者可以用下圖表示。此局面下,黑棋有A、B、C三個眼,而白棋只有D、E兩個眼。
若輪到黑方走棋,黑方可以走A、B、C的任意一點,結果都等價於上圖的0 = { | }。
而若輪到白方,她沒有任何可行的選項。因此,{ 0 | }這個超現實數,豎線的左邊代表黑方有可行著法,並導致「0」這一結果;而豎線右邊代表白方沒有可行著法,因此留空。
{ 0 | }等於1,其含義是黑方比白方多1個可行的選項。換句話說,無論輪到誰走棋,這個局面都是黑方勝。
1 = { 0 | }
-1 = { | 0 } 是 1 = { 0 | }的相反數。
在圍棋盤上,前者相當於在後者的基礎上交換了黑白子,如下圖。
{ | 0 }等於 -1的含義是,白方比黑方多一個可行的選項。因此無論輪到誰走棋,此局面都是白方勝。
-1 = { | 0 }
到目前為止,三個超現實數,0、1、-1已經被創造出來,但這還沒有超出我們熟悉的整數的範圍。
而下一個超現實數,則不再屬於整數,也不是分數、無理數,甚至不是複數。
這個數是 * = { 0 | 0 }。其對應的圍棋局面如下圖。
與0 = { | }的局面相比,此局面只多出C一處空點。這個點在圍棋術語裡叫做「單官」。
若現在輪到黑走棋,則A、B、D、E仍是不可行的著法,只有走C,其結果和 0 = { | }一樣。
若輪到白走棋,白方也只能走C,結果還是0 = { | }。所以,此局面被記作{ 0 | 0 },即黑、白雙方的唯一策略均指向「0」這個局面。
{ 0 | 0 }的結果與{ | }正好相反:輪到黑方下則黑勝,輪到白方下則白勝。
Conway因此用「*」這個特殊符號記錄此結果,指定 * = { 0 | 0 }。
* = { 0 | 0 },「單官」。
總結四個基本的超現實數,我們可以得到下表:
就像普通的數字一樣,超現實數也可以進行四則運算。
比如超現實數的0+1=1; 1+(-1)=0, 1+1=2; 這些運算的結果,有興趣的讀者可以自行驗證。
筆者潘達在這裡要介紹的是一個特殊的運算結果,* + * = 0。這個式子看上去很抽象,不過放到圍棋盤上就容易理解了。
前文提到,* 相當於一個單官,那麼 * + * 就相當於兩個單官,可以用下圖表示:
* + * = 0
棋盤上有C、D兩處單官,是僅有的可下之點。
無論是黑棋還是白棋先下,結果都是黑、白各佔一點。因此最後總是回歸到「0」這個局面(上圖右)。左圖是 * + *;右圖是0,兩者等價。因此用超現實數的語言總結,* + * = 0。
在上述四個基本的超現實數的基礎上,我們可以遞歸定義出分數、無理數、無窮小量、無窮大等各種超現實數。篇幅所限,本文在此不再展開介紹。
Conway的超現實數理論脫胎於圍棋,其適用範圍也遠遠超過了圍棋。
在超現實數的基礎上,Conway與同行一起開創了組合博弈論這一數學領域,用於研究包括圍棋在內的一大類數學遊戲。
其中,與Conway一道創立組合博弈論的Elwyn Ralph Berlekamp教授,在超現實數的基礎上發展出一套專門適用於圍棋官子的數學理論。
像下圖這道Berlekamp設計的官子問題(輪白棋下),曾經難倒過中、日、韓三國的職業棋手,也讓新時代的圍棋AI無從下手。
而Berlekamp的理論,不僅能夠成功解出此題,並且能夠給出嚴謹的證明。
Berlekamp給出的解題思路
AI給出的錯誤解答
很遺憾,Berlekamp教授已於2019年4月逝世,Conway教授也在前天離開人世。兩位大師的離去是學界的重大損失,不過,我們或許不必為此過度傷心。
有一句網絡流行語說得好,「男人至死是少年」。
Conway作為一位天才數學家,內心可以強大到無視世俗的評價,而醉心於研究常人眼中的「玩物」,踐行了超越現實的遊戲人生態度。
而Conway前兩年的採訪也可確證,他不會因為死亡的臨近感到緊迫,或因為無法看到重大數學未解之謎的最終解決感到遺憾,因為他的一生都已獻給他所熱愛的研究。
在緬懷Conway教授的帖子中,有網友以Conway教授創造的生命遊戲和Conway的人生態度撰寫了一則墓志銘,筆者以此結束本文。
「Conway創造了生命遊戲。而因為新冠肺炎疫情導致的社交距離限制,名為Conway的元胞沒有足夠多的鄰居,遺憾地退出了生命遊戲。」
想找高手陪你下棋
卻找不到組織找不到對手?
想有意義地度過每一天
就在超有愛的圍棋交流群
掃描下方二維碼即刻加入
一起下棋,聊天,進步
本文是【奇略研究所】原創內容
未經授權禁止轉載
如需轉載請在後臺聯繫開白
喜歡本文,記得給奇略點個在看噢