為什麼AlphaGo不懂圍棋規則也可以擊敗棋王？

電腦圍棋程式AlphaGo如何擊敗韓國棋王李世乭，看了網路半天看不到簡單明瞭好理解的相關文章，只好自己寫。

電腦下棋要贏過人腦，不管是最簡單的井字遊戲，很困難的西洋棋，或是最複雜的圍棋，基本方法都是：每一步棋都要下在最可能獲勝的地方。

以大家都玩過的井字遊戲，也就是○○○ＸＸＸ誰先連成一線誰先贏的遊戲來說，對方先下第一步以後，電腦可以算出接下來一來一往八個棋步，可能有多少種走法，如果畫成流程圖，會看到從第一步開始的一個井字圖，逐漸開枝散葉，越來越多井字圖，形成樹枝狀的演算圖。在這些走法裡，有些我方最後會獲勝，有些會落敗，於是接下來我方要走的，就是獲勝機會最大的那一步。

當然井字遊戲因為十分簡單，即使沒有電腦，用筆算也能畫出樹枝狀演算圖，只是這樣的工作更適合電腦來做。當所有可能走法被電腦窮盡，那麼對手不管下哪一步，都不會贏。後來這樣的演算法就被電腦西洋棋程式深藍（Deep Blue），於1997年用來打敗世界棋王卡斯巴羅夫。這樣的演算法被稱做暴力搜尋法。

然而這樣的演算法要擴展到圍棋並不可能，因為圍棋走法複雜太多，在19X19的棋盤上，當對方落下第一子，接下來有三百六十種可能走法，遠超過目前最強電腦的計算能力，即使算到天荒地老也還算不出來，這就是電腦打敗西洋棋王後，始終無法用同樣的演算法打敗圍棋高手的原因。

電腦必須另闢蹊徑。蒙地卡羅方法早在幾十年前就被發現，那是一種統計模擬方法，運用亂數來解決計算問題。重點來了。圓周率π要怎麼計算？只有天才數學家才能想出解法，但運用蒙地卡羅方法，不懂幾何原理的人也能算出圓周率，方法是在一正方形內劃出一個內切圓，然後拿一把豆子從半空灑落，再看看落在圓形內的豆子數目，跟落在圓形外正方形內的豆子數目，比例是多少，就可換算出π。換言之，這是一種利用機率向上天叩問數學答案的方法。

這跟AlphaGo有什麼關係？AlphaGo不懂圍棋規則，也能下贏棋王，運用的就是類似的機率原理。蒙地卡羅方法後來被運用在井字棋與西洋棋運算，但不了了之，直到2006年，有人又把蒙地卡羅方法找了出來，加了樹枝狀搜尋，成了蒙地卡羅樹枝搜尋法，從此開啟了電腦圍棋程式設計的新天地。當時有人就預言，十到二十年後，圍棋程式將擊敗人類頂尖棋手。

果然，2016年，這個預言實現了。箇中功臣很多，但最值得提起的兩位，就是將AlphaGo運作原理寫成論文，刊載在今年初的《自然》期刊的兩位論文主要作者，英國的大衛西瓦（David Silver）與台灣的黃士傑。大衛西瓦專攻深度神經網絡，尤其是增強式學習網絡，而黃士傑的博士論文寫的就是蒙地卡羅樹枝搜尋法在電腦圍棋程式的運用。

黃士傑是台灣土生土長，自己栽培的電腦程式專家，能有這樣的成就，令人感動！他大學念交大，碩博士念師大，念書之餘對圍棋非常有興趣，拿到了六段資格，後來更以電腦圍棋程式做為研究主軸，而且最重要的，他對自己非常有信心，相信台灣也能做出世界頂尖研究成果，終於大放異彩。他的生涯發展歷程值得台灣年輕學子參考。

黃士傑怎麼做？基本上AlphaGo用的就是蒙地卡羅樹枝搜尋法，而非井字棋或西洋棋所用的暴力搜尋法。

蒙地卡羅樹枝搜尋法有四個步驟：

一、從第一步棋開始，選擇最優勢的下一步棋，一步步擴展，這擴展過程便形成一棵小樹。

二、擴展方式是從樹枝的末端，也就是樹葉往外延伸，尋找下一個棋步。

三、擴展到不想再擴展時，便從最末端的棋步，進行棋局模擬，運用隨機下法，也就是三秒鐘內你來我往亂下一通，看看最後輸贏。

四、是把輸贏結果沿著樹枝往上傳，一直傳回到樹根，這時回傳過程中所經歷的擴展點，都會獲得一次走過的紀錄，而重複上述搜尋千萬次以後，累積起來得到的，最常被走過的那一個棋步，便是我方的下一個走法。

這樣了解嗎？跟暴力搜尋法有何不同？蒙地卡羅樹枝搜尋法，並沒有窮盡所有走法，而是尋找優勢步，算出接下來幾步以後，剩下的便靠機率把這盤棋下完，而如果這步是好步，那麼即使是亂下，贏的機率也比較大。圍棋太複雜，不可能把三百六十步全部算完，AlphaGo大約算了十幾二十步以後，剩下的便靠機率模擬來推算獲勝可能，並據以選擇棋步。

Photo Credit: AP/達志影像

AlphaGo的模擬算法有兩種，一種是估值函數，也就是利用迴歸分析，以歷史棋譜為比對根據，算出目前棋局的可能勝負，另一種是快速布局網絡，也就是利用棋局的局部特徵，以傳統演算法（非深度神經網絡）算出可能勝負，兩種算法的平均值便是勝負估算依據。

問題來了。前面說到，AlphaGo只算了十幾二十步，剩下的便交給機率，那麼這十幾二十步要怎麼算出來？深度神經網絡的角色便在這時出現了。AlphaGo不懂圍棋規則，但它知道，只要模仿歷史棋王的下法，便可能會贏。因此AlphaGo開始了學習歷程，從幾萬局歷史棋譜裡，學習歷史棋王在各種棋局時的下法，並記在腦海，等到比賽時便拿來比對目前盤面狀況，找出最能獲勝的棋步。