探索圍棋官子最優解（二）：組合博弈論
探索官子最優解（一）：卡片圍棋 傳送門。
本文主要參考資料：Elwyn R. Berlekamp, David Wolfe, Mathematical Go：Chilling Gets the Last Point.
本文暫時謝絕一切轉載。
一、引言
在正式介紹數學理論之前，請大家先看一道「簡單」的官子題。
本大題共兩小問，每小問10分。（1）棋局進行到接近終局，尚余若干小官子。請問，在a、b兩處官子中，黑棋應該選哪一個？
（2）類似的情形，下圖中的a、b兩處官子，黑棋又應該選哪一處？
參考答案：（1）b （2）a
在圖1的情形下，取決於盤面剩餘官子的情況，有時候選a和選b一樣好；但有時選b會比選a最終便宜一目。圖2同理。和直覺相反，黑棋應該進攻己方俘虜較少的一邊，而不是較多的一邊，也不是「走廊」更長的一邊。
為什麼呢？對於圖１，我們可以製造一個對稱的局面，只剩４個官子，ａ／ｂ各二，如下圖。
現在白棋走１位，輪到黑棋。如果黑棋走ｂ是模仿白棋，可以守住平局。而若黑棋走ａ，則白棋可以在右上繼續突進。接下來只要白棋不失誤，即可以１目獲勝。讀者可自行驗證。
以上並不構成一個完整的證明，畢竟棋盤剩餘的部分可以千變萬化。為了研究一般情形下選擇小官子的優先順序，我們需要引入新的數學工具。
二、超現實數與圍棋
英國數學家約翰·何頓·康威（John Horton Conway）在1974年提出超現實數（Surreal Number）。超現實數形如｛Ｌ｜Ｒ｝，其中Ｌ和Ｒ是集合。超現實數採用遞歸的方式定義，即從最簡單的整數開始逐步構造較複雜的數。我們先構建整數集：
０＝｛｜｝（如果Ｌ和Ｒ中有空集，則可以略去不寫。Ｌ和Ｒ都是空集，則定義了０）
{ 0 | } = 1
{ 1 | } = 2
{ 2 | } = 3（正整數的遞歸定義）
{ | 0 } = ?1
{ | ?1 } = ?2
{ | ?2 } = ?3（負整數的遞歸定義）
然後可以在此基礎上構建二進分數，即分母形如2^n的分數。
{ 0 | 1 } = 1/2
{ 1/2 | 2 } = 5/4
{ 5/4 | 3 } = 17/8
．．．．．．
讀到這裡，你可能會問，為什麼要這樣定義數呢？其實，康威教授創造超現實數，靈感來源就是圍棋的官子。請看下圖：
這是一個官子局面。請問，紅圈範圍內的白棋，應該判斷為多少目？
按照一般的官子理論，黑棋下在Ａ，則是０目；白棋下在Ａ，則是１目。因為雙方下在Ａ都是後手，取平均值即是1/2目。對應到超現實數，就是{ 0 | 1 }=1/2，即把黑先的結果寫在左邊，白先的結果寫在右邊。
那麼，藍圈範圍內的白棋，又應該判斷為多少目呢？如果白棋下在Ｂ，則是兩目；而若黑棋下在Ｂ，則局部變為與紅圈內一致的形狀，即1/2目。取兩者平均值，則是1又1/4目。用超現實數的寫法，就是 { 1/2 | 2 }=5/4 。
（註：方便起見，一般把白棋的目數記為負數，黑棋的目數記為正數。）
以此類推，棋盤下方黑棋空出４格的走廊，應判斷為｛５/４｜３｝＝17/8，即2又1/8目。
我們可以依次推出2、3、4以至n格走廊的目數，見上圖中間一欄。由此可以進一步推出在n格走廊處收官的價值，見最右一欄。此處的「價值」在前文介紹過；比如第一欄的1/2，指此處官子的價值相當於「逆收1/2目」。同理，沖「五格走廊」的價值相當於逆收31/32目。傳說李昌鎬研究官子精確到三十二分之一目，看來做到這個精確度並不是很難。
更難的在下面呢。
三、冷卻
比如說我們有這樣一個官子局面，餘下的官子價值差不多都是逆收１目或者後手２目。於是，此局面的重點變成了收到最後一個官子。既然每個官子的價值差不多，為了突出「爭奪最後一手」的重點，我們不妨規定每走一步棋就要扣除１目。我們將此種處理稱為冷卻（chilling or cooling）。比如說Ａ位，按照（二）的分析，價值1/2目。此時若黑棋走A位，扣除1目以後，餘下-1/2目。其含義是，黑棋走A位相對於正解虧損了1/2目。
通過冷卻分析，圍棋這個搶目數的遊戲，被轉化成了搶最後一手的遊戲。冷卻分析法的好處將在下文自現。
四、無窮小量
莊子雲，「一尺之錘，日取其半，萬世不竭。」其中蘊含了無窮小量的思想。所謂無窮小量，就是一個比零大，而比任何其他正數都小的量。學過高等數學的讀者可能知道，無窮小量在標準的數學分析當中被擯棄不用。但無窮小量這個概念又確有其實用價值。於是，現代數學家發展出若干非標準的數學分析體系，引入無窮小量解決問題。
在超現實數的基礎上，埃爾文教授引入了一系列與圍棋有關的無窮小量。
（ａ）星（star, ※）
考慮上圖，黑棋將一顆白子含在嘴裡的官子。此局面應該判斷為多少目？
黑先，則黑提一子得兩目；白先，則白救回一子，局部零目。結果是｛２｜０｝。這個數等於１嗎？答案是不等。此處就要用到冷卻分析法。
首先，因為局部可以判斷為黑棋約有１目，所以先把黑棋這一目扣掉，以白子上的一個點標記。接下來，如果黑先，吃掉白子，得兩目；但走這一步棋要扣除一目，在白子上再加一點標記；這樣總共要扣除兩目，最終結果是２－２＝０目。如果白先，則白棋救回一子，代價是扣除白棋一目，以刪去白子上的一點標記。最終結果是－１＋１＝０目。因此冷卻以後的局部可以用｛０｜０｝標記。｛０｜０｝不屬於超現實數，而是一個新的無窮小量，我們將其命名為星，標記為※。
一處（未冷卻的）單官也可以用｛０｜０｝表示，因此單官也是※。單官的優先順序永遠在有「實際價值」的官子之後，但最後總是要填的，且在中國規則下也算分，所以它不是零。若對單官做冷卻處理，則沒有人會去填單官（還得扣一目呢）。局部沒有選擇，就是空集，用｛｜｝表示，也就是０. 零意味著遊戲結束，輪到誰下誰就輸，因為最後一步棋被對手搶走了。
星號有以下性質：※+※=0. 即兩個星號的和是零。這不難理解：兩個單官總是一人一個，見合了。另外，星號比任何正數小，且比任何負數大。但是星號與零無法比較，因為對於※，誰先走誰就能搶到最後一手，即勝負未定。
（ｂ）箭頭（tiny，↑ 或 ↓）
來看一個稍有不同的官子。黑棋嘴裡仍然含著一個子，只是這個白子藏得更深一路。以冷卻分析法，我們將這顆白子視為囊中之物，扣除黑棋「應得」的兩目。若是黑先，則黑棋封口，得三目；下了一步棋扣一目，再扣原有的兩目，無得無失，是０。若是白先，白棋進一步，則還原成（ａ）中分析過的局面，是※。因此本局部寫作｛０｜※｝，我們將其定義為↑，箭頭。若是黑白交換，則記作↓，向下的箭頭。
向上的箭頭↑對黑棋稍有利，因為無論誰先手，黑棋總能搶到最後一手。向下的箭頭↓則對白棋稍有利。換句話說，↑＞０＞↓。但是，↑＋※與０無法比較，因為白棋先手可以搶到最後一個官子。
採用遞歸的方式，我們可以計算帶有俘虜的ｎ格走廊的冷卻後價值，見下圖。
其中，雙箭頭（三箭頭）表示兩個（三個）↑的和。↑※表示↑＋※。注意，對於ｎ＞１的情況，黑白雙方在此處行棋的價值並不對等。走廊越長，黑棋防守走廊入口的價值越大；而白棋進攻走廊的價值不變，都是↑※。
五、案例分析
至此，我們已經可以分析一些簡單的局面。比如，我們把上文提到過的一個局面分解，得到下圖（白先，讀者可以先思考此局面下白棋所有可能的選擇）：
有ａ－ｈ八個局部，互相獨立。分別冷卻分析每個局部，得到結果如下：
其中ａ＝↓；ｂ＝１/２；ｃ＝※；ｄ＝－１/４；ｅ＝↓；ｆ＝－１/４；ｇ＝↑↑※；ｈ＝※。
求和，得１/２＋（－１/４）＋（－１/４）＋↓＋↓＋↑↑※＋※＋※＝※。也就是說，這個局面等價於一個星號※。
如果輪到白棋先下，白棋只需消去一個※，就可以把局面化為０，也就是白棋有必勝策略的局面。因此，白棋可以選擇ｃ或ｈ二者之一。走ｇ的價值是↑※，將局面化為↓，也可以獲勝，而且比得到０「更好」一點。其他的選擇ａ/b/d/e/f 都會給黑棋翻盤的機會。
在此做一個小結：我們可以把有多個官子的局面分解，用冷卻法分析，將其化簡為一個無窮小量，判斷誰能在此局面下走到最後一手。比如某局面分析的結果是盤面３目加上↑※。因為↑※與零無法比較，因此最優解下的最終結果可能是盤面４目（黑先）或２目（白先）。若分析結果是盤面３目加↑↑※，或者盤面３目加↑，則最終結果會是盤面４目（黑先）或３目（白先）。因為↑↑※和↑都比０大。若是分析的結果帶有分數，比如３又１/４加↑※，則結果也是盤面４目（黑先）或盤面３目（白先），因為無窮小量總是比分數要小。
圍棋中的無窮小量不止這兩種。下一篇我們會引入一個新的無窮小量，並完整的比較各種小官子的優劣。
續篇地址：探索圍棋官子最優解（三）：組合博弈論
推薦閱讀：
探索圍棋官子最優解（二）：組合博弈論
探索官子最優解（一）：卡片圍棋 傳送門。
本文主要參考資料：Elwyn R. Berlekamp, David Wolfe, Mathematical Go：Chilling Gets the Last Point.
本文暫時謝絕一切轉載。
一、引言
在正式介紹數學理論之前，請大家先看一道「簡單」的官子題。
本大題共兩小問，每小問10分。（1）棋局進行到接近終局，尚余若干小官子。請問，在a、b兩處官子中，黑棋應該選哪一個？
（2）類似的情形，下圖中的a、b兩處官子，黑棋又應該選哪一處？
參考答案：（1）b （2）a
在圖1的情形下，取決於盤面剩餘官子的情況，有時候選a和選b一樣好；但有時選b會比選a最終便宜一目。圖2同理。和直覺相反，黑棋應該進攻己方俘虜較少的一邊，而不是較多的一邊，也不是「走廊」更長的一邊。
為什麼呢？對於圖１，我們可以製造一個對稱的局面，只剩４個官子，ａ／ｂ各二，如下圖。
現在白棋走１位，輪到黑棋。如果黑棋走ｂ是模仿白棋，可以守住平局。而若黑棋走ａ，則白棋可以在右上繼續突進。接下來只要白棋不失誤，即可以１目獲勝。讀者可自行驗證。
以上並不構成一個完整的證明，畢竟棋盤剩餘的部分可以千變萬化。為了研究一般情形下選擇小官子的優先順序，我們需要引入新的數學工具。
二、超現實數與圍棋
英國數學家約翰·何頓·康威（John Horton Conway）在1974年提出超現實數（Surreal Number）。超現實數形如｛Ｌ｜Ｒ｝，其中Ｌ和Ｒ是集合。超現實數採用遞歸的方式定義，即從最簡單的整數開始逐步構造較複雜的數。我們先構建整數集：
０＝｛｜｝（如果Ｌ和Ｒ中有空集，則可以略去不寫。Ｌ和Ｒ都是空集，則定義了０）
{ 0 | } = 1
{ 1 | } = 2
{ 2 | } = 3（正整數的遞歸定義）
{ | 0 } = ?1
{ | ?1 } = ?2
{ | ?2 } = ?3（負整數的遞歸定義）
然後可以在此基礎上構建二進分數，即分母形如2^n的分數。
{ 0 | 1 } = 1/2
{ 1/2 | 2 } = 5/4
{ 5/4 | 3 } = 17/8
．．．．．．
讀到這裡，你可能會問，為什麼要這樣定義數呢？其實，康威教授創造超現實數，靈感來源就是圍棋的官子。請看下圖：
這是一個官子局面。請問，紅圈範圍內的白棋，應該判斷為多少目？
按照一般的官子理論，黑棋下在Ａ，則是０目；白棋下在Ａ，則是１目。因為雙方下在Ａ都是後手，取平均值即是1/2目。對應到超現實數，就是{ 0 | 1 }=1/2，即把黑先的結果寫在左邊，白先的結果寫在右邊。
那麼，藍圈範圍內的白棋，又應該判斷為多少目呢？如果白棋下在Ｂ，則是兩目；而若黑棋下在Ｂ，則局部變為與紅圈內一致的形狀，即1/2目。取兩者平均值，則是1又1/4目。用超現實數的寫法，就是 { 1/2 | 2 }=5/4 。
（註：方便起見，一般把白棋的目數記為負數，黑棋的目數記為正數。）
以此類推，棋盤下方黑棋空出４格的走廊，應判斷為｛５/４｜３｝＝17/8，即2又1/8目。
我們可以依次推出2、3、4以至n格走廊的目數，見上圖中間一欄。由此可以進一步推出在n格走廊處收官的價值，見最右一欄。此處的「價值」在前文介紹過；比如第一欄的1/2，指此處官子的價值相當於「逆收1/2目」。同理，沖「五格走廊」的價值相當於逆收31/32目。傳說李昌鎬研究官子精確到三十二分之一目，看來做到這個精確度並不是很難。
更難的在下面呢。
三、冷卻
比如說我們有這樣一個官子局面，餘下的官子價值差不多都是逆收１目或者後手２目。於是，此局面的重點變成了收到最後一個官子。既然每個官子的價值差不多，為了突出「爭奪最後一手」的重點，我們不妨規定每走一步棋就要扣除１目。我們將此種處理稱為冷卻（chilling or cooling）。比如說Ａ位，按照（二）的分析，價值1/2目。此時若黑棋走A位，扣除1目以後，餘下-1/2目。其含義是，黑棋走A位相對於正解虧損了1/2目。
通過冷卻分析，圍棋這個搶目數的遊戲，被轉化成了搶最後一手的遊戲。冷卻分析法的好處將在下文自現。
四、無窮小量
莊子雲，「一尺之錘，日取其半，萬世不竭。」其中蘊含了無窮小量的思想。所謂無窮小量，就是一個比零大，而比任何其他正數都小的量。學過高等數學的讀者可能知道，無窮小量在標準的數學分析當中被擯棄不用。但無窮小量這個概念又確有其實用價值。於是，現代數學家發展出若干非標準的數學分析體系，引入無窮小量解決問題。
在超現實數的基礎上，埃爾文教授引入了一系列與圍棋有關的無窮小量。
（ａ）星（star, ※）
考慮上圖，黑棋將一顆白子含在嘴裡的官子。此局面應該判斷為多少目？
黑先，則黑提一子得兩目；白先，則白救回一子，局部零目。結果是｛２｜０｝。這個數等於１嗎？答案是不等。此處就要用到冷卻分析法。
首先，因為局部可以判斷為黑棋約有１目，所以先把黑棋這一目扣掉，以白子上的一個點標記。接下來，如果黑先，吃掉白子，得兩目；但走這一步棋要扣除一目，在白子上再加一點標記；這樣總共要扣除兩目，最終結果是２－２＝０目。如果白先，則白棋救回一子，代價是扣除白棋一目，以刪去白子上的一點標記。最終結果是－１＋１＝０目。因此冷卻以後的局部可以用｛０｜０｝標記。｛０｜０｝不屬於超現實數，而是一個新的無窮小量，我們將其命名為星，標記為※。
一處（未冷卻的）單官也可以用｛０｜０｝表示，因此單官也是※。單官的優先順序永遠在有「實際價值」的官子之後，但最後總是要填的，且在中國規則下也算分，所以它不是零。若對單官做冷卻處理，則沒有人會去填單官（還得扣一目呢）。局部沒有選擇，就是空集，用｛｜｝表示，也就是０. 零意味著遊戲結束，輪到誰下誰就輸，因為最後一步棋被對手搶走了。
星號有以下性質：※+※=0. 即兩個星號的和是零。這不難理解：兩個單官總是一人一個，見合了。另外，星號比任何正數小，且比任何負數大。但是星號與零無法比較，因為對於※，誰先走誰就能搶到最後一手，即勝負未定。
（ｂ）箭頭（tiny，↑ 或 ↓）
來看一個稍有不同的官子。黑棋嘴裡仍然含著一個子，只是這個白子藏得更深一路。以冷卻分析法，我們將這顆白子視為囊中之物，扣除黑棋「應得」的兩目。若是黑先，則黑棋封口，得三目；下了一步棋扣一目，再扣原有的兩目，無得無失，是０。若是白先，白棋進一步，則還原成（ａ）中分析過的局面，是※。因此本局部寫作｛０｜※｝，我們將其定義為↑，箭頭。若是黑白交換，則記作↓，向下的箭頭。
向上的箭頭↑對黑棋稍有利，因為無論誰先手，黑棋總能搶到最後一手。向下的箭頭↓則對白棋稍有利。換句話說，↑＞０＞↓。但是，↑＋※與０無法比較，因為白棋先手可以搶到最後一個官子。
採用遞歸的方式，我們可以計算帶有俘虜的ｎ格走廊的冷卻後價值，見下圖。
其中，雙箭頭（三箭頭）表示兩個（三個）↑的和。↑※表示↑＋※。注意，對於ｎ＞１的情況，黑白雙方在此處行棋的價值並不對等。走廊越長，黑棋防守走廊入口的價值越大；而白棋進攻走廊的價值不變，都是↑※。
五、案例分析
至此，我們已經可以分析一些簡單的局面。比如，我們把上文提到過的一個局面分解，得到下圖（白先，讀者可以先思考此局面下白棋所有可能的選擇）：
有ａ－ｈ八個局部，互相獨立。分別冷卻分析每個局部，得到結果如下：
其中ａ＝↓；ｂ＝１/２；ｃ＝※；ｄ＝－１/４；ｅ＝↓；ｆ＝－１/４；ｇ＝↑↑※；ｈ＝※。
求和，得１/２＋（－１/４）＋（－１/４）＋↓＋↓＋↑↑※＋※＋※＝※。也就是說，這個局面等價於一個星號※。
如果輪到白棋先下，白棋只需消去一個※，就可以把局面化為０，也就是白棋有必勝策略的局面。因此，白棋可以選擇ｃ或ｈ二者之一。走ｇ的價值是↑※，將局面化為↓，也可以獲勝，而且比得到０「更好」一點。其他的選擇ａ/b/d/e/f 都會給黑棋翻盤的機會。
在此做一個小結：我們可以把有多個官子的局面分解，用冷卻法分析，將其化簡為一個無窮小量，判斷誰能在此局面下走到最後一手。比如某局面分析的結果是盤面３目加上↑※。因為↑※與零無法比較，因此最優解下的最終結果可能是盤面４目（黑先）或２目（白先）。若分析結果是盤面３目加↑↑※，或者盤面３目加↑，則最終結果會是盤面４目（黑先）或３目（白先）。因為↑↑※和↑都比０大。若是分析的結果帶有分數，比如３又１/４加↑※，則結果也是盤面４目（黑先）或盤面３目（白先），因為無窮小量總是比分數要小。
圍棋中的無窮小量不止這兩種。下一篇我們會引入一個新的無窮小量，並完整的比較各種小官子的優劣。
續篇地址：探索圍棋官子最優解（三）：組合博弈論
推薦閱讀：