這是「圍棋 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 以內的菱形範圍,越靠近棋子數值越大 …