Day16 Bouzy's 5/21 Algorithm
===


突然想起Day6說到會分享利用Morphology做圍棋形式判斷，剛好昨天講到了用Monte Carlo Method來評估局勢，所以在介紹MCTS之前趕緊鬼轉，回頭介紹一下利用Morphology來靜態評估圍棋局勢。

## Mathematical Morphology
這邊指的Morphology是Mathematical Morphology (數學形態學)，廣泛應用於影像處理，這邊只簡單介紹一下基本操作，因為後續也只會用到基本概念。
### 基本操作
* Dilation (膨脹)
膨脹擴展圖像中的前景區域。用一個結構元素(Structure element)在圖像上滑動，結構元素滑過圖像時，任何與前景像素重疊的區域都會使該像素變為前景像素。這會擴大物體並填補細小的間隙。
$A \oplus B = \left\{ z \mid \left( \hat{B} \right)_z \cap A \neq \emptyset \right\}$


* Erosion (侵蝕)
侵蝕會縮小圖像中的前景區域，將圖像中的物體邊緣「吃掉」。用一個結構元素在圖像上滑動，如果結構元素的所有像素都與前景像素重合，則該像素保持不變，否則被移除。這有助於消除小物體或斑點。
$A \Theta B = \left\{ z \mid \left( \hat{B} \right)_z \subseteq A \right\}$


大多數Morphology的方法都是使用這兩個運算去組合變形而成。

### Opening
其實就是先做Erosion 再做 Dilation，用結構元素在目標圖形內掃描，結構元素掃不到的範圍就會被刪除掉，可以將圖形凸出的銳角給鈍化。
$A \circ B = (A \Theta B) \oplus B$


### Closing
跟Opening反過來，是先做Dilation 再 Erosion，結構元素在目標圖形外部掃描，掃不到的範圍就填滿，可以將圖形內陷的銳角給鈍化。
$A \bullet B = (A \oplus B) \Theta B$


圖片皆取自Steven大大的簡報，但網路上找到的資料很多也都是這幾張圖，我不知道原始出處，麻煩知道的人可以留言跟我說。

### 形態學濾波應用
* 噪聲去除：Opening可用來移除小的噪聲點或孤立像素，保持較大區域的完整性，常用於去除二值化圖像中的雜訊。
* 物體邊界提取：Erosion操作可以縮小物體，然後再用Dilation還原，這有助於獲得物體的邊界輪廓。
* 填補空洞：Closing能填補圖像中物體內部的細小間隙，使物體看起來更加連貫。
* 形狀分析：形態學濾波還可以應用於分析物體形狀特徵，例如骨架化和區域提取等。

在圍棋中，Dilation可以用來辨識棋串的「氣」，Closing能夠辨識「眼」。
(但這邊辨識出的眼僅限於一般情況的眼，圍棋的例外有點太多了。)

## 圍棋形勢判斷
下圍棋最重要也最困難的一點就是**形勢判斷**，圍棋是個比誰圍到的地盤多的遊戲，但是在還沒有完全把地盤包圍住時，很難去評估到底哪裡算是誰的地盤，尤其是愈往棋盤中間的地盤通常愈難判斷。
這樣的審局函數就會比較難設計，象棋、西洋棋很多都是用評估子力的方式做審局函數，比如「車」在象棋中的影響力非常大，我用一隻兵換掉你一隻車，評估起來可能就是我賺了，但圍棋不是這麼一回事，你吃我一顆子跟我吃你兩顆子，可能吃兩顆子的還虧了，因為必須要考慮到周圍領地的問題，每顆棋子對於周圍領地的影響力就很難評估。

### Zobrist's Model
Zobrist提出的一個棋子影響力模型，將棋盤上的點標記，黑棋標記為 +50，白棋標記為 -50，空點標記為 0。
從正負數的點開始往外擴張出去，將相鄰的點 +1 或 -1，然後重複四次。

                 0
             0   0   0
         0   0   0   0   0
     0   0   0   0   0   0   0
  0  0   0   0  50   0   0   0   0
     0   0   0   0   0   0   0
         0   0   0   0   0
             0   0   0
                 0

1.
                 0
             0   0   0
         0   0   0   0   0
     0   0   0   1   0   0   0
  0  0   0   1  50   1   0   0   0
     0   0   0   1   0   0   0
         0   0   0   0   0
             0   0   0
                 0

2.
                 0
             0   0   0
         0   0   1   0   0
     0   0   1   2   1   0   0
  0  0   1   2  54   2   1   0   0
     0   0   1   2   1   0   0
         0   0   1   0   0
             0   0   0
                 0

3.
                 0
             0   1   0
         0   1   2   1   0
     0   1   3   6   3   1   0
  0  1   2   6  58   6   2   1   0
     0   1   3   6   3   1   0
         0   1   2   1   0
             0   1   0
                 0

4.
                 1
             2   2   2
         2   4   6   4   2
     2   4   8  10   8   4   2
  1  2   6  10  62  10   6   2   1
     2   4   8  10   8   4   2
         2   4   6   4   2
             2   2   2
                 1

### Bouzy's 5/21 Algorithm
Bouzy改進了Zobrist's Model發明了Bouzy's 5/21 Algorithm，其實他就是用了5次Dilation加上21次的Erosion，來模擬人類對圍棋領地判斷，平衡棋子的影響力和領地界限。

在使用這個演算法前要先清除棋盤上的死子，像是昨天介紹到的Sabaki使用Monte Carlo Method來清除死子。
此演算法的流程為：
1. 將棋盤上的點標記，黑棋標記為 +128，白棋標記為 -128，空點標記為 0。
2. 進行 5 次Dilation：
對於每個點，如果該點的值大於等於 0 並且其相鄰的點沒有小於 0 的值，則將相鄰大於 0 的點數加到該點。如果交點的值小於等於 0 並且其相鄰的點沒有大於 0 的值，則減去相鄰小於 0 的點數。
3. 進行 21 次Erosion：
對於每個點，如果其值大於 0（或小於 0），則減去（或加上）相鄰點的值，直到值變為 0。

比如現在棋盤上有兩顆隔了一格的黑棋。


           128    0    128   


1 dilation :

 	
            1          1 

       1   128    2   128   1

            1          1

2 dilations :

 	
            1          1

       2    2     3    2    2

   1   2   132    4   132   2   1

       2    2     3    2    2
              
            1          1


3 dilations :

 	
            1          1

       2    2     3    2    2
     
   2   4    6     6    6    4   2

1  2   6   136    8   136   6   2   1

   2   4    6     6    6    4   2

       2    2     3    2    2

            1          1
            
3 dilations and 1 erosion :

 	
             2     2     2

    0   4    6     6     6    4

0   2   6   136    8    136   6    2

    0   4    6     6     6    4

             2     2     2


3 dilations and 2 erosions :

 	
                 1

      2    6     6     6    2

      6   136    8    136   6

      2    6     6     6    2
      
                 1


3 dil. / 3 erosions :

 	
           5     6     5

      5   136    8    136   5
      
           5     6     5
           
3/4 :

 	
          3     5     3 
          
      2  136    8    136   2          
           
          3     5     3
          
3/5 :

 	
          1     4     1

         136    8    136
          
          1     4     1
          

3/6 :

 	
                3
         
         135    8    135
         
                3


3/7 :

 	
         132    8    132      

這樣最後剩下來在兩個黑棋中間的點就是黑棋的領地。

這邊有一個公式：Erosion次數應為 1 + n(n-1)，其中 n 為Dilation次數，按照這個公式可以保證孤立的棋子不會被誤判定為領地。

至於為什麼是5跟21這兩個神秘的數字呢？
按照公式的話3/7跟4/13次也是可以，只是會在第六線以上的領地判斷效果不佳，透過人類經驗修正後得到5/21次是較佳的作法。
論文我放在底下了，有興趣的可以再自行去深入研究。

## 實際案例
今天就不放程式碼了，直接來看一盤實際案例吧，主要注意兩個部分：
1. 邊角
2. 中央

下圖是按照Bouzy's 5/21 Algorithm所實作出來的形式判斷，其實左下角的白棋的評估我認為稍微有點過於保守了，還有對於中央空曠地區也是偏保守。


下圖為知名圍棋對弈網：野狐圍棋
這是它內建的形式判斷功能，蠻多人會使用這個功能的，具體使用了什麼演算法不知道，但想來也是各種Bouzy's 5/21 Algorithm變形，我們可以注意到他對棋盤中間空曠地方的評估其實是很寬鬆的，對於左下角的判斷也是比較符合一般人類的判斷。


下圖為我與Steven實作的形式判斷，我們對於中央的判斷較為野狐保守，對於邊角則較野狐更寬鬆，我們認為這個結果可能與人類的判斷更為相近。
Steven就是之前提到過的UCLA博士生，碩士畢業後工作了幾年，毅然決然的到美國讀博，現在是光學AI大師，他說我寫文章就寫文章不要亂吹捧他，所以我把這段藏在文章中間XDD


棋譜選自29屆LG盃世界棋王戰8強：柯潔(黑)vs韓相朝(白)
就是今天9/30剛下完熱騰騰的棋譜。

## Reference
* [Mathematical morphology applied to computer go](https://helios2.mi.parisdescartes.fr/~bouzy/publications/Bouzy-IJPRAI.pdf)
* [數學形態學](https://zh.wikipedia.org/zh-tw/%E6%95%B0%E5%AD%A6%E5%BD%A2%E6%80%81%E5%AD%A6)
* [Bouzy's 5/21 algorithm](http://gnu.ist.utl.pt/software/gnugo/gnugo_14.html)
* [Bouzy Map](https://senseis.xmp.net/?BouzyMap)
* [【影像處理】形態學 Morphology](https://jason-chen-1992.weebly.com/home/-morphology)