探索圍棋官子最優解(三):組合博弈論

(接上文探索圍棋官子最優解(二):組合博弈論,主參考文獻:Elwyn R. Berlekamp, David Wolfe, Mathematical Go:Chilling Gets the Last Point.)

(本文暫時謝絕一切轉載)

(不想看推導的讀者請直接跳到第九節看有應用價值的結論)

七、正微量與負微量

  請看上圖中的局面,和前文介紹的※有些相似吧。這個官子和※的區別是,黑棋嘴裡有兩個俘虜,而不是一個。我們仍然採用冷卻法做分析:黑先封口,冷卻後的結果是0;白先衝擊,則留下一個價值2目(後手4目)的官子,結果可以用{0|-2}表示。黑白先手的結果結合,則此局面可表示為{0‖0|-2}。注意,雙豎線‖的功能和單豎線|沒有區別,只是標明閱讀順序:從雙豎線所在的位置開始逐級擴展遊戲樹。

   康威教授將此局面定義為「正微量-2」(Tiny 2),本文將其記作 	op_2 (為避免與加號+混淆,筆者選用了與原書不同的表記)。下標的2對應 {0‖0|-2}中的2。若黑白互換,則構成「負微量-2」(Miny 2),記作 ot_2 。也就是說,負微量-2是正微量-2的相反數,即 	op_2+ot_2=0 , 它們的和是0.

  如果俘虜變多,或者俘虜後還有空間,則微量的值也會相應變化。例如下圖:

  一個俘虜加一目空共3目,對應 	op_1 ; 三個俘虜共計6目,對應 	op_4 ; 只有一個俘虜即2目,即 	op_0 ,也就是熟悉的↑。我們通常把↑區別於其他微量對待,因為它與其它正微量的性質有顯著差異。

  一般地,如果白棋沖一下能直接威脅黑棋腹中的x目,則此局面記作「正微量{x-2}」,即 	op_{x-2}

  微量和星號※、箭頭↑一樣,都是無窮小量,因此它們小於任何正數。正微量都是正數,因為無論黑先還是白先,都是黑棋收後;即 	op_n>0 . 而且,微量是比箭頭更小(高階)的無窮小量,比如 uparrow+ot_2=uparrow-	op_2>0. 要證明此不等式,考慮↑和 ot_2 的組合局面。

  無論黑先還是白先,黑棋總能收到最後一官(除非白棋把黑棋兩兄弟放走,那麼黑棋贏得更多),請讀者自行驗證。

  同理,如果x>y,則 	op_x<	op_y ,即下標大的正微量更小(高階無窮小)。注意,此處的無窮小都是冷卻以後的值;越「小」的無窮小,其實價值越接近1目,應該優先選擇。

八、多俘虜長走廊

我們回到上一篇開頭的問題,兩個長長的走廊盡頭,各有兩三個俘虜,走哪一個更好呢?

  隔離右邊的局部,並採用冷卻分析法畫出遊戲樹,如下圖。

  此局部因而可總結為{ ot_2 |0‖0|||0},簡寫為 ot_2|0^3 ,意為黑棋要走三步才能到達 ot_2

  此類棋形比微量要大(低階無窮小),因為對手的衝擊相對不那麼急迫;但此類棋形比箭頭↑要小(高階無窮小),請讀者自行驗證。

九、各類一目官子總結

  上表是各類小官子優先順序的總結。假設y>x>0,則優先順序依次為:

1、攻擊負微量 ot_y

2、走後手y+2目的官子;

3、攻擊負微量 ot_x

4、走後手x+2目的官子;

5、依次攻擊帶有多個俘虜的長走廊;優先攻擊俘虜數量少的;若俘虜數量一樣則優先攻擊較短的走廊;

6、攻擊僅有一個俘虜的走廊(即↓,↓↓※等);無論走廊長短,做這些攻擊是等價的;

7、如果有奇數個※,走※;

8、防守帶有俘虜的長走廊;無論走廊長短或俘虜多少,這些防守是等價的;

9、走價值為分數的走廊;分母大(即更長的走廊)的先走;

10、最後填單官。

十、見合

  見合い,日語,意為「相親」。作為圍棋術語,見合指某局面下有兩個價值相當的選擇,雙方總是各得其一。

  在組合博弈論中的見合(miai)就是指兩個(或更多)數的和為零。比如兩個星號※的和是零,對應到棋盤上就是兩個一路扳粘見合。又比如↑+↓=0,即↑和↓見合。

  在分析某個官子局面時,我們需要先識別出所有見合的局部,然後當它們不存在。做完這一步以後,才可以按照(九)中介紹的流程繼續。

十一、採用數學符號的必要性

  可能有些讀者早已在心中抱怨,為何要引入這些花花綠綠的數學符號呢?只用棋盤上的局部來表示不夠嗎?

  數學符號的特點是抽象。將具體的事物抽象成符號,就能識別出貌不同而本質相同的兩個事物。比如下面這個等式:

  僅僅盯著棋盤看,恐怕很難發現這兩處官子是等價的。

  又比如下面這個等式

  乍一看很難接受。若寫成↑+↑+※=↑↑※,是不是就很簡單了呢?

十二、難倒九段的一道題

  本題即本文題圖。白先。埃爾文教授曾用此題難倒了多位中、日職業九段。本題包含幾處前文不曾提到的棋型,比如DEF、KL、NPOQR等處的斷頭(緊氣後要補一手)。篇幅所限,本文不再展開分析此類棋形,僅給出正解:

上圖是對各個局部做冷卻分析的結果。

  上圖求出各個局部的總和,結果是0+無窮小量。按照此表,對照(九)中介紹的流程,白棋應該走C,為本題唯一正解。

十三、總結

  上世紀九十年代,埃爾文教授曾造訪中國棋院,推銷這一套官子理論。埃爾文教授拿出若干道如(十二)中的考題,讓很多棋手目瞪口呆。然而,少年常昊不畏艱險,挑燈夜戰,最終給出了其中一道題的正解。可是,當常昊向埃爾文教授解釋自己的推理時,雙方都懵逼了。在最淺顯的層面上,常昊採用了「見合」的分析方法,歸併部分官子,算是與組合博弈論不謀而合。但越是深入,常昊的詮釋就不可避免的涉及「先手」、「後手」之類圍棋手習慣的概念。這些常見的概念中蘊藏著風險:何謂「先手」?如何確定先手?你會發現,這些概念都沒有嚴謹的定義。雪上加霜的是,埃爾文教授嘗試將常昊的方法應用於類似的問題,卻無一例外的失敗了。不可重複的演算法在數學上是錯誤的演算法。

  (註:儘管如此,埃爾文教授對常昊的印象非常好。無論如何,能給出如此難題的正解,天賦和恆心均不可或缺。常昊之後成為中國圍棋的一代領軍人物,曾獲得三個世界冠軍。)

  成為一名職業棋手需要十餘年的訓練,成為一名職業數學家也是,這兩者不曾有交集。

  數學家的目標是:尋找最優解,並且給出一個可證明的演算法。

  圍棋手的目標是:尋找近似的解,從而儘可能的少犯錯誤,比對手犯更少的錯誤。

  這兩個目標看上去很接近,而埃爾文教授花了十幾年時間才意識到二者間隱藏著的觀念上的巨大差異。對於圍棋手來說,「證明」的含義是在棋盤上把變化擺出來。數學家和圍棋手,終究活在兩個世界。

  AlphaGo問世,人類敗得潰不成軍。但我們有組合博弈論。在終點線前一米,我們可以和圍棋上帝打成平手。在最後一目的問題面前,AlphaGo有可能被純數學擊敗。這離圍棋在數學上的真正最優解還很遠很遠,但至少我們已經邁出了堅實的第一步。

推薦閱讀:

圍棋入門教程——獻給初學者

TAG:圍棋 | 數學 | 博弈論 |