Cody Blog

圍棋 AI 學習筆記(一):Bouzy's 5/21 估算地盤

這是「圍棋 AI 學習筆記」系列的第一篇,從一個很老、但很直觀的問題開始:看著一盤棋,電腦要怎麼判斷哪裡是誰的地?

在 AlphaGo 用神經網路直接「看」出形勢之前,早期的圍棋程式多半靠手寫規則來估算勢力範圍。Bruno Bouzy 在 2003 年發表的 5/21 演算法[1]就是其中一個經典做法:借用影像處理的「數學形態學」,把每顆棋子的影響力向外擴散,再把邊緣不穩的部分削掉,剩下來的就是比較確定的地盤。它的膨脹步驟改自 Zobrist 在 1969 年提出的勢力模型[2],Bouzy 再補上對應的侵蝕步驟;這個方法用在他自己的圍棋程式 Indigo 裡,後來也被 GNU Go 採用。

互動演示

下面的棋盤可以自己擺子,拉動步驟滑桿或按播放,看數值怎麼一步步變化。滑鼠移到格點上,會顯示那一步是怎麼算出來的。

演算法

整個過程只有三個階段,每一步都是同時更新所有格點(用上一步的值計算,不會邊算邊影響)。

1. 初始化

黑子設為 +64,白子設為 −64,空點設為 0,這是原論文[1]沿用 Zobrist 模型的設定。正值代表黑方的影響力,負值代表白方的。

2. 膨脹(Dilation)5 次

對每個格點:

  • 如果它 ≥ 0,而且上下左右四鄰沒有負值,就加上四鄰中正值的個數。
  • 負值那一方對稱處理:如果它 ≤ 0,而且四鄰沒有正值,就減去四鄰中負值的個數。
  • 四鄰正負都有的點不動,代表雙方勢力在這裡碰頭。

膨脹讓影響力像水波一樣往外擴散,一次一格。5 次之後,單顆子的影響會涵蓋距離 5 以內的菱形範圍,越靠近棋子數值越大 …

圍棋 AI 學習筆記(二):蒙地卡羅樹搜尋(MCTS)

上一篇的 5/21 是在回答「看著一盤棋,要怎麼判斷形勢」。這個問題對圍棋程式非常關鍵:西洋棋程式用 Alpha-Beta 搜尋,搜到一定深度後就靠評估函數打分數;但圍棋的形勢太難用規則寫清楚,5/21 這類方法再怎麼調也不夠準,加上每一步有上百種下法,傳統搜尋在圍棋上一直做不起來。

蒙地卡羅樹搜尋(Monte Carlo Tree Search,MCTS)換了一個思路:看不出局面好壞,那就把棋下完很多次,統計勝率。終局要判斷誰贏很容易,數子就好。2006 年 Coulom[1]和 Kocsis、Szepesvári[2]先後提出這套方法之後,圍棋程式在幾年內從業餘入門進步到業餘高段;後來的 AlphaGo[3]也是以 MCTS 為骨架,再把神經網路放進去。

互動演示

為了把整棵搜尋樹畫出來,下面用井字棋示範,演算法和圍棋版完全一樣,只是規模小到看得清楚。O 先手。

按「下一步」可以一次走一個階段,看一次模擬裡發生了什麼;看懂之後按「+100」或「+1000」快轉,觀察樹的形狀怎麼變。點樹上的節點,右下角會列出它每個子節點的 UCT 是怎麼算出來的。也可以自己在棋盤上下子,從任何局面開始搜尋。

演算法

MCTS 會從目前的局面(根節點)出發,重複做很多次「模擬」。每個節點記錄兩個數字:

  • N:這個節點被走過幾次
  • W:其中下這一手的一方贏了幾次(和局算 0.5)

所以 W ÷ N 就是這一手的勝率。每次模擬分成四個階段:

1. Selection(選擇)

從根往下走。如果一個節點的所有著手都已經在樹裡了,就用 …