【正文】
/2, 1/4, 1/8, …} 將等于 1/ω ,直觀地說也就是無窮小量。 {0 | 1/ω} 則等于 1/(ω 2) ,而 {1/ω | 1, 1/2, 1/4, 1/8, … } 則等于 2/ω 。我們剛才創(chuàng)造的所有數(shù)都是合法的,它們確實都是一個個的數(shù),它們依舊能比較大小,依舊能參與運算。不過,它們明顯超出了實數(shù)的范圍??磥恚粋€有序域完全有可能比實數(shù)域更大。所以說,Knuth 才把這個外星系統(tǒng)叫做“超實數(shù)”??梢宰C明,由超實數(shù)構成的有序域是最大的有序域,其他所有可能的有序域,都只是超實數(shù)域里的一個子有序域。我們把石板上描述的數(shù)學對象解讀為了我們熟知的數(shù)字(以及我們不熟知的數(shù)字),因為兩者具有相同的代數(shù)結(jié)構。但實際上,別忘了,這些數(shù)學對象其實可以被我們解讀成任何東西,可能是對我們有用的,可能是對我們沒用的。(四)并行的棋局事實上,這個全新的算術系統(tǒng)是 Knuth 從另一位數(shù)學大神 John Conway 那兒聽來的。 Knuth 對此非常感興趣,他把 TAOCP 的寫作計劃擱置了一周,完成了這部 100 多頁的小說,并在 1974 年出版。“超實數(shù)”這個詞是 Knuth 自己杜撰的。 Conway 非常喜歡這個詞,并把它用到了他在 1976 年出版的專著 On Numbers and Games 中。這是一本非常有特色,非常 geek 的書。書的內(nèi)容分成了第零部分 On Numbers 和第一部分 and Games ,全書的第一句是, This book is in two = {zero, one | } parts 。在這本書中, Conway 給出了超實數(shù)背后的直觀意義:博弈游戲。圖 1圖 2圖 3圖 4圖 5讓我們來考慮這樣一個游戲,游戲的名字叫做 Domineering 。兩個玩家輪流在一個形狀不規(guī)則的棋盤上放置多米諾骨牌。不妨把這兩個玩家分別記作“左玩家”和“右玩家”。左玩家只允許在棋盤上放置豎直的多米諾骨牌,右玩家只允許在棋盤上放置水平的多米諾骨牌。誰先不能放了,誰就輸了。顯然,有的棋局可能會對左玩家更有利,有的棋局可能會對右玩家更有利。讓我們來分析幾種局面吧。圖 1 顯示的是一個“空棋盤”。顯然,這是一個“中立棋局”,先走的人直接就輸了,后走的人直接就贏了。圖 2 所示的棋局雖然與空棋盤不同,但本質(zhì)上一樣——這仍然是一個誰后走誰贏的公平局面。圖 3 所示的棋局則明顯對右玩家更有利一些,事實上不管誰先走,右玩家一定都會獲勝。圖 4 所示的棋局則偏向了左玩家,不管誰先走,左玩家都會獲勝。Conway 給出了兩個棋局相加的含義。定義兩個棋局的和為同時包含這兩個棋局的新棋局。如果說有兩個棋局,棋局 A 和棋局 B ,那么 A + B 的意思就是兩個玩家同時在棋局 A 和棋局 B 上游戲。輪到某個玩家行動時,這個玩家可以選擇在 A 上走一步,也可以選擇在 B 上走一步,只要 A 和 B 當中至少一個還能走,他就不算輸。例如,我們可以讓兩個玩家同時在圖 3 和圖 4 上游戲,這個游戲就記作+不難看出,它的效果等價于一個空的棋局——誰后走誰贏。圖 5 所示的 L 形棋盤就更有意思了。如果左玩家先行,他有兩種走法。其中一種走法將剛好給右玩家留下一步,把自己送上了絕路;更聰明的走法則是把棋盤弄斷,從而形成 □ + □ 的局面,讓右玩家直接死掉。如果是右玩家先行,他只有一步可走,但走完之后就再也無計可施,而左玩家還能多走一步。因此,不管誰先走,這個 L 形棋盤都是左玩家必勝的。一個有趣的問題:圖 4 的 I 形棋盤和圖 5 的 L 形棋盤都是左玩家必勝的局面,都是對左玩家有利的局面,那么哪個局面對左玩家更有利一些?換句話說,哪個局面會讓左玩家贏得更爽一些?大家或許會說,當然是 I 形棋盤更爽。憑什么這么說?有什么理由嗎?注意這里我們實際上在做的事情:我們希望能找出一種(對于左玩家來說)棋局優(yōu)劣的判斷標準。其中一種絕妙的想法是,讓 I 和 L 兩個棋局同時進行,不過左玩家要在 L 中扮演右玩家的角色。換句話說,考慮這樣的復合棋盤:兩個玩家仍然輪流放置多米諾骨牌,不過規(guī)則稍有修改:在 I 形棋盤上,左玩家仍然豎直地放牌,右玩家仍然水平地放牌;但在 L 形棋盤上,兩個玩家的身份顛倒了:左玩家只能放水平的牌,右玩家則改放豎直的牌。此時,左玩家在 I 形棋盤上有優(yōu)勢,右玩家在 L 形棋盤上有優(yōu)勢。最終整個棋局更偏向于誰?這顯然是一場赤裸裸的“優(yōu)勢絕對值”之戰(zhàn)。不難驗證,事實上整個棋局仍然是左玩家必勝,不管誰先走誰后走。這說明,左玩家在 I 形棋盤中具有更大的優(yōu)勢,因而 I 形棋盤比 L 形棋盤更好。對于一個棋局 A ,如果我們完全交換左玩家和右玩家的地位,得到的新棋局就叫做棋局 A 的“反棋局”,記作 A 。我們規(guī)定,對于棋局 A 和棋局 B 來說,如果棋局 A 和棋局 B 的反棋局同時進行(即游戲在 A + (B) 上進行),左玩家必勝(不管誰先走),那么對于左玩家來說,棋局 A 比棋局 B 更好,或者說棋局 A 優(yōu)于棋局 B ;反之,如果右玩家必勝(不管誰先走),那么對于左玩家來說,棋局 A 比棋局 B 更差,或者說棋局 A 劣于棋局 B 。如果 A + (B) 是一個誰后走誰必勝的中立局面,我們就認為,棋局 A 和棋局 B 對于左玩家來說優(yōu)劣相同,或者說棋局 A 平于棋局 B 。注意,今后不做特殊說明時,棋盤的優(yōu)劣都是針對左玩家所說的。棋局 A 劣于棋局 B 的另一個等價的定義就是,如果棋局 B 優(yōu)于棋局 A ,我們就說棋局 A 劣于棋局 B 。如果棋局 B 優(yōu)于棋局 A ,說明 B + (A) 是左玩家必勝的,因而整個復合棋局的反棋局將會是右玩家必勝的。整個復合棋局的反棋局是什么?就是 B 的反棋局,加上 A 的反棋局的反棋局,也就是 A + (B) 了。而 A + (B) 對于右玩家必勝,這正好符合之前給出的 A 劣于 B 的定義。不過目前,沒有任何東西可以向我們保證,這些定義是合理的。按照這個優(yōu)劣定義,沒準會出現(xiàn) A 優(yōu)于 B 、 B 優(yōu)于 C 、 C 優(yōu)于 A 的荒唐一幕,或者棋局 A 優(yōu)于棋局 B 但 A + C 劣于 B + C 的悖理情形。不過,或許我們能證明,這些情況都不會出現(xiàn)。至少我們可以證明一些最基本的事實,比如根據(jù)上面的定義,一個棋局一定和它自身的優(yōu)劣程度相同。為此,我們只需要說明棋局 A + (A) 是一個中立局面即可。其實, A + (A) 顯然是誰后走誰必勝的,因為后走的人有一個絕妙的無敵必勝招數(shù):它只需要完全模仿對方的行為即可。先走的人每走一步,他都能在另一個棋盤上照著走一步,從而永遠不可能先無路可走。左玩家必勝(不管誰先走)的棋局 A 也一定優(yōu)于任意一個中立棋局。我們也可以證明這一點,只需要說明棋局 A 加上中立棋局的反棋局后,左玩家能必勝即可。他顯然是能獲勝的,他可以在 A 上該怎么走就怎么走,除非回應右玩家在中立棋局上的行動。反過來,右玩家必勝(不管誰先走)的棋局也就一定劣于中立棋局。現(xiàn)在開始,就是真正神奇的地方了。我們把左玩家走一步之后可能形成的所有局面構成的集合叫做左集合,把右玩家走一步之后可能形成的所有局面構成的集合叫做右集合。看看圖 4 的 I 形棋盤:左玩家無論走哪一步,剩余的棋盤都是圖 2 的樣子;同時,右玩家沒有可以走的空間,右集合是一個空集。一個棋局的左集合和右集合完整地描述了再走一步之后這個棋局所有可能的結(jié)果,于是我們可以用這兩個集合來刻畫該棋局。我們就說:= {| }圖 1 和圖 2 的棋局實質(zhì)上是相同的:左右集合都是空集。它們都應該表示成 { | } 。圖 3 所示的棋盤需要引起額外的注意:“不能走”和“可以走到空棋盤狀態(tài)”是兩個完全不同的概念。因此,圖 3 的棋盤應該被表示為= { | 空棋盤 }類似地,= { 空棋盤 | }圖 5 的 L 形棋盤則可以表示為= {,+|}下面我們來看看,在這種棋局表示法下,如何形式化地定義棋局的加法、棋局的反棋局以及棋局的優(yōu)劣。如果棋局 A 和棋局 B 同時進行,那么左玩家走一步后可以得到的局面,有可能是在棋局 A 當中走一步(同時棋局 B 保持不動)所得,也可能是在棋局 B 當中走一步(同時棋局 A 保持不動)所得;類似的,右玩家能走出的局面,則是由棋局 A 的所有右集合元素都加上棋局 B ,以及棋局 B 的所有右集合元素都加上棋局 A 構成的。如果把棋局 A 的左右集合分別記作 L(A) 和 R(A) ,把棋局 B 的左右集合分別記作 L(B) 和 R(B) ,那么 A + B 的左右集合就應該分別是:L = { u + B | u ∈ L(A) } ∪ { A + v | v ∈ L(B) }R = { u + B | u ∈ R(A) } ∪ { A + v | v ∈ R(B) }左玩家在 A 中的合法移動,也就是 A 的右集合中的元素;右玩家在 A 中的合法移動,也就是 A 的左集合中的元素。別忘了,移動完之后,雙方的決策繼續(xù)保持反著的狀態(tài)。如果棋局 A 的左右集合分別記作 L(A) 和 R(A) ,那么 A 的反棋局的左右集合就應該是:L = { u | u ∈ R(A) }R = { u | u ∈ L(A) }最后,我們給出“劣于或平于”的形式化描述。如果棋局 A 劣于或者平于棋局 B ,這意味著 A + (B) 有兩種可能:右玩家必勝,或者誰后走誰必勝??傊笸婕蚁茸呤墙^不可能有必勝策略的。反過來,如果左玩家先走真的沒有必勝策略(從而右玩家后走將必勝),這正好對應著那兩種情況:如果此時再已知右玩家先走也沒有必勝策略,那就是誰后走誰必勝;如果此時右玩家先走將必勝,那就屬于右玩家必勝的情況。因此, A + (B) 是右玩家必勝或者誰后走誰必勝的,當且僅當左玩家先走沒有必勝策略。這等于是說,左玩家不會在 A + (B) 上走出一種誰后走誰必勝或者左玩家必勝的局面。如果左玩家在 A 上面走一步,結(jié)果一定不會優(yōu)于或平于 B ;同時, A 也一定不會優(yōu)于或平于左玩家在 B 上任意走一步(相當于右玩家在 B 上走一步)的結(jié)果。換句話說 A 的左集合中的元素不會優(yōu)于或平于 B,同時 B 的右集合中的元素不會劣于或者平于 A 。至此為止,大家已經(jīng)發(fā)現(xiàn),棋局的加法運算,棋局的反棋局運算,以及棋局之間的“劣于或平于”關系,完全等同于超實數(shù)的公理和定義!為了保證所有的棋局都是超實數(shù),我們強行規(guī)定,所有棋局也都必須滿足超實數(shù)本身的構造限制,即左集合中沒有元素優(yōu)于或平于右集合中的某個元素。換句話說,對于左玩家來說,左玩家走了一步后所得的棋局,局勢一定比右玩家走了一步后所得的棋局更險惡。更直觀地說,我們這里考慮的都是先走比后走更不利、每多走一步就更接近死亡的游戲。為了讓棋局完全符合超實數(shù),安全地繼承所有超實數(shù)中的結(jié)論,我們可以生硬地、脫離實際意義地定義棋局的乘法:L = { u y + x v – u v | u ∈ L(A), v ∈ L(B) } ∪ { u y + x v – u v | u ∈ R(A), v ∈ R(B) }R = { u y + x v – u v | u ∈ L(A), v ∈ R(B) } ∪ { u y + x v – u v | u ∈ R(A), v ∈ L(B) }這樣便能把誰是 1 確定下來。現(xiàn)在,超實數(shù)的所有公理和定義,都能用來描述棋局的世界了。于是,超實數(shù)的一切定理一切性質(zhì),包括小于等于的傳遞性,加法乘法的交換率,乃至整個系統(tǒng)是一個有序域,也都將適用于棋局。事實上,棋局和超實數(shù)將會變得同構,它們之間存在最為深入的對應關系。每一個棋局都將對應一個數(shù),棋局之間的加法就是數(shù)與數(shù)之間的加法,我們完全不必擔心棋局的運算結(jié)果不符合數(shù)的運算結(jié)果。和超實數(shù)一樣,更準確地說,應該是每一個棋局類都將對應一個數(shù),棋局類之間的加法就是數(shù)與數(shù)之間的加法。不過,和之前講超實數(shù)時一樣,為了簡便起見,接下來我們都省去“類”字??掌灞P = { | } ,也就是 0 ,我們的中立棋局。根據(jù)我們之前的結(jié)論,左玩家必勝的棋局都將優(yōu)于中立棋局,從而對應一個大于 0 的數(shù);右玩家必勝的棋局都將劣于中立棋局,從而對應一個小于 0 的數(shù)。因此,看看棋局所對的數(shù)是正是負,就能判斷棋局究竟對誰有利。舉例來說:= { | 空棋盤 } = { | 0} = 1這個值比 0 小,說明該棋局中右玩家必勝。而= {| } = {0 | } = 1這個值比 0 大,說明該棋局中左玩家必勝。 L 形棋盤= {,+|} = {1, 0 + 0 | 1} = {1, 0 | 1} = 1/2說明它也是對于左玩家來說必勝的。注意到 I 形棋盤的值大于 L 形棋盤,這說明 I 形棋盤優(yōu)于 L 形棋盤,是一個左玩家能贏得更痛快的棋局。一個直觀意義就是,在 I 形棋盤中,左玩家能以一步領先的優(yōu)勢獲勝,這個步數(shù)優(yōu)勢比 L 形棋盤更大。在 L 形棋盤上,左玩家只能以半步的優(yōu)勢險勝。注意 1/2 + 1/2 + (1) = 0 ,而真的就是一個中立棋局!在我們給出棋局的形式化描述時,我們并沒有關心實際的游戲規(guī)則。這是一個非常一般的棋局理論,它還可以用到很多其他的游戲中。回到本文最開頭最開頭的地方。我們當時留下了一個問題。 ○● 真的等于 1/2 嗎?我們現(xiàn)在可以很輕易地回答了。如果把白方想成是左玩家,那么 ○● = {空棋盤 | ○} = {0 | 1} = 1/2 。我們之前曾經(jīng)用 ○● + ○● + ● = 0 的辦法推出了 ○● = 1/2 ,這也是完全有道理的。有了這套理論,我們便能用純代數(shù)的方法對新的棋局進行分析。考慮下面這個問題:對于左玩家來說,棋局 ○● 和 ○●● 相比,哪個的優(yōu)勢更大?為了解決這個問題,我們只需要計算一下 ○●● 的值:○●● = {空棋盤 | ○, ○●} = {0 | 1, 1/2} = 1/4而 ○● = 1/2 ,它的優(yōu)勢更大一些。由此可以進一步推出,棋局○●●●○的值為 1/4 + (1/2) = 1/4 ,即右玩家必勝。而