作者：周秉誼 / 趨勢科技 技術經理
人類大師在西洋棋、象棋和將棋一一被電腦打敗之後，圍棋一向被視為人類智能在對局上的最後領域，在2015年底一般認為短期內難有突破性的進展。2016年初AlphaGo橫空出世後，馬上顛覆了全球職業棋士和研究學者的看法，尤其是和韓國棋士李世石九段對戰四勝一敗的事實，更讓人不得不接受AlphaGo真的很強大。本文從傳統對局演算法談起，再說明AlphaGo架構上最重要的蒙地卡羅樹搜尋及深度學習，以及兩個部份如何整合。
前言
人類大師在西洋棋、象棋和將棋一一被電腦打敗之後，圍棋一向被視為人類智能在對局上的最後領域，龐大的搜尋空間使電腦對局在傳統搜尋樹上表現平平，著名的經典圍棋程式GnuGo在多年發展後，也無法達到人類業餘入段水準。
直到10年前蒙地卡羅樹搜尋配合日漸進步的計算能力，才露出一絲曙光。日本棋院自2007年起每年在東京的電氣通信大學舉辦UEC Cup電腦圍棋比賽，前兩名的程式可以參加跟頂尖人類職業棋士對局的電聖戰，給了新世代的電腦圍棋程式一個切磋進步的機會。在歷屆的EUC Cup比賽中可以看到蒙地卡羅樹搜尋圍棋程式的進步。
然而近幾年蒙地卡羅搜尋已達瓶頸，一直無法突破人類業餘高段水準，在2015年底一般認為短期內難有突破性的進展。Facebook創辦人馬克祖克柏也認為電腦圍棋程式還需要幾年的努力才能跟人類頂尖棋士一較高下。
這個局面在2016年初AlphaGo橫空出世後，馬上顛覆了全球職業棋士和研究電腦對局的學者的看法，尤其是和韓國棋士李世石九段對戰四勝一敗的事實，更讓人不得不接受AlphaGo真的很強大。AlphaGo正是將最近蓬勃發展的Deep Learning，配合在電腦圍棋取得不錯成績的蒙地卡羅樹搜尋，這兩個分屬人工智慧不同領域的方法結合，才完成了這個出人意料的重大突破。
Game tree & MinMax演算法
傳統的電腦對局大多使用MinMax演算法對Game tree進行搜尋，來決定最佳的著手(Move)。Game tree上的每一個Node代表了某一個遊戲的盤面或狀態，每一個Edge代表了遊戲中的著手，使遊戲狀態從一個盤面改變為另一個盤面。而Game tree的每一個Leaf Node就代表了這個遊戲每一個可能的結束情況。以大家常見的井字遊戲來說，雖然井字遊戲的盤面大小只有3x3，但Game tree的Leaf Node就高達了26830個。以棋類遊戲來說，中國象棋可能的盤面組合就有10的48次方，使得Game tree的複雜度高達10的150次方。而19路圍棋的合法盤面更是超過了10的170次方，如果要完整搜尋Game tree來找尋必勝著手，需要的儲存空間會比宇宙中的原子總數更多，更被證明是PSPACE-hard的計算問題。
MinMax演算法是一種最小化最差情況的演算法，在每一個Game tree中的Node，MinMax演算法會以遞迴方式評估各個可能的下一步，選擇對對手來說最佳的著手，來當成這一個Node的分數。因此可以從Game tree中找出最不會輸的著手方式。一般MinMax演算法會配合alpha-beta pruning，來大量的減少Game tree上需要被搜尋過的Node數量。然而對圍棋來說，盤面的分數不容易像象棋一樣，以盤面上殘留的子力或殘局庫來評估，常需要下到終盤才能以勝負來了解盤面好壞，且各個Node的分支太多，無法有效率的評估每一個child node。
MCTS蒙地卡羅樹搜尋
2006年後一種改良過的蒙地卡羅樹搜尋(Monte Carlo tree search)開始被應用在電腦圍棋上。蒙地卡羅樹搜尋的基本概念是，在每一個Game tree的Node上會以隨機模擬的方式產生出很多下到終盤的棋局，這些隨機產生的棋局稱為playout。演算法就以這些playout的結果評估這個Node的勝率，圍棋程式就可以選擇出勝率最高的Node當成下一步的著手。
蒙地卡羅樹搜尋主要有四個動作，Selection、Expansion、Simulation、Backpropagation。Selection是從Root Node開始搜尋目前的Game tree，選擇一個最好的Leaf Node。Expansion就會從這個Leaf Node展開出一個Child Node。Simulation會以這個Child Node當成起點，隨機下棋產生出playout。Backpropagation就會以這個playout的勝負來更新從Child Node到Root Node的路徑上各節點的勝率。
從2007年起，以蒙地卡羅樹搜尋為主體的電腦圍棋程式逐漸在網路圍棋平台嶄露頭尾。從KGS平台的統計可以看到，電腦圍棋程式的棋力由2007年的兩級一路提升，在2012年到達業餘六段的水準。從UEC Cup電聖戰的資料也可以看到，電腦圍棋程式由7子讓子一路進步到4子讓子而可以取勝。
然而2012年之後電腦圍棋程式似乎又碰到瓶頸，在到達業餘六段之後一直沒有明顯突破。因為蒙地卡羅樹搜尋在產生playout過程中的隨機特性，無法針對盤面的局部重點或特殊手順進行正確的評估，使得蒙地卡羅樹搜尋雖然有不錯的全局觀，但對局部攻殺的掌握不足。在playout及Expansion中加入專家知識及分析棋局後的pattern match，可以有所改善但還是無法跟人類棋士以經驗學習到的棋型資訊相提並論。
圖一 KGS上圍棋程式棋力演進
Deep Learning深度學習
深度學習(Deep Learning)是機器學習的一個分支，使用多重非線性的資料處理層級和複雜的網路結構，對資料進行抽象化，達到非監督式(unsupervised)或半監督式(semi-supervised)的特徵學習(feature learning)和分層特徵提取(feature extration)，來取代人工產生的特徵。深度學習包括了非常多不同的網路結構，大多是從類神經網路(Neural Network)的概念轉化而來，各種不同的網路結構可以適用在不同的機器學習問題，包括了電腦視覺、語音辨識、自然語言處理、生物資訊等等各種領域。
類神經網路是種模仿生物體中的神經網路結構的數學模型，在類神經網路中的神經元(Neuron)可以對輸入的資料進行數學上的轉化，再藉由不同的連結方式把轉化過的結果傳遞給下一層的神經元。雖然每個神經元只能進行簡單的資料轉換，但是透過神經元彼此連結，就能組成十分複雜的網路結構，也能處理很有挑戰的機器學習問題。多數的深度學習是將類神經網路的結構加深，增加網路層數及神經元的數量，配合現代的運算能力，就能完成令人驚訝的工作，就像有自動學習的能力一般。
現代的深度學習動輒十層以上的類神經網路，對計算能力的需求非常龐大，大多數的計算平台都使用了GPU這樣特殊的計算環境，來加速計算、加快模型的收歛速度。而另一方面，複雜的類神經網路也需要更龐大的資料量，才能讓模型找出較佳的參數，提供穩定的能力。近年的大數據(Big Data)趨勢及各種分散式計算的進展，剛好提供了深度學習最好的發展時機。
CNN(Convolutional neural networks)是其中一種目前最常見的深度學習模型，使用在影像或其他二維資料上的效果令人驚艷。CNN顧名思義就是在類神經網路中，使用一般的完全相連網路層(Fully connected layer)之前，先使用了卷積層(Convolutional layer)對資料進行處理。以影像資料來說，搭配了二維的Convolutional layer就有自動找出影像中特徵的效果，讓完全不懂影像處理的人士可以直接使用CNN就得到很好的模型。對各個影像分類的資料集，如MNIST、CIFAR，CNN的表現都是名列前茅。
近年來，各種不同的深度學習函式庫也不斷問世，掌握大量資料的公司如Facebook、Google都不約而同地希望使用深度學習來解決各種實際碰到的問題。Google甚至併購了想模擬人類智能的DeepMind團隊，在2015年以深度學習的CNN加上強化學習(Reinforcement learning)，打造出可以自動學習怎麼玩電視遊樂器的程式，甚至還可以玩得比人類更好。在2015年Google更釋出了開放原始碼(Open source)版本的TensorFlow深度學習函式庫，TensorFlow就是Google內部使用的深度學習平台，以開放原始碼授權方式提供大家使用，不難看出Google對深度學習未來發展及應用的佈局。
Pattern比對
回顧過去的電腦圍棋程式，因為圍棋的著手空間太大，不管是傳統遊戲樹搜尋或使用蒙地卡羅樹搜尋，都會需要找出最重要的落子點，優先進行搜尋或提高模擬次數，才能有效提升棋力。傳統作法是建立小區域的局部pattern，如3x3、5x5、7x7大小的pattern資料庫，記錄了下一個著手的優先位置，在樹上進行搜尋或模擬時就去比對目前盤面是否有資料庫中的pattern。如果找到就可針對資料庫中的著手優先搜尋。 然而圍棋盤面千變萬化，相同的局部情勢在不同的全局組合下，可能會有不同的對應方式，光用簡單的局部pattern比對沒辦法做到完全正確。因此早在2012年就有人提出用CNN來解決圍棋全局pattern辨識的問題，Google在2014年也曾發表文章討論使用CNN來產生下一手著手的方式。
AlphaGo
Google在2016年Nature文章中提出了新的做法，將深度學習應用在兩個不同的方面，策略網路(Policy Network)及價值網路(Value Network)，並跟原本的蒙地卡羅樹搜尋整合。Policy Network用來產生下一步的著手，功能上類似人類棋士看到一個盤面時，以直覺和經驗得到的下一步著手。Value Network用來評估目前盤面的局勢，功能上類似人類棋士看到一個盤面時，以直覺和經驗判斷局面好壞。這兩個網路都是深度學習CNN，Policy Network可以視為381個類別的分類問題，而Value Network則是一種Regression。
Policy Network是以監督式學習(supervised learning)方式，來產生下一步著手的分類問題，當然需要大量的訓練資料(Training data)，因此選擇了KGS上高段人類棋士對戰的棋譜，從中取出了16萬譜棋局、2940萬個盤面作為Training data。雖然CNN有特徵提取的能力，但為了降低網路複雜度，還是將盤面資料轉化成11種特徵、48個盤面，方便CNN在有限的網路層級中學習到更深入的特徵。利用這些Training data產生的特徵盤面，訓練出一個13層的Policy Network，做出一個預測只要3ms，預測的準確率可達到57.0%。這樣的成果比其他團隊的44.4%高出非常多，AlphaGo團隊也發現當準確率超過50%後，準確率1%的提升，就能提高10%的勝率。AlphaGo也訓練出一個比較簡單但預測非常快的模型Rollout Policy，用在playout的模擬上。
Value Network用來評估目前盤面的局勢，但Training data是用Reinforcement learning之後的Policy Network自己對下，自動產生出來的3千萬譜棋局，而每個棋局只取用其中隨機選取的一個盤面。訓練出來的Value Network只要對盤面做預測，就可以得到接近使用Policy Network進行playout模擬的準確度，而且還節省了15000倍計算。
在與蒙地卡羅樹搜尋的Expansion中，AlphaGo會使用Policy Network來產生下一個著手並展開那一個點。在Simulation步驟時，會使用Rollout Policy進行模擬下完棋局、產生出playout。這些playout的勝率會再跟Value Network的預測結果整合後，Backpropagation更新到Game tree上。
AlphaGo也跟現在最強的圍棋程式對下測試，在495場對局中贏了494場，勝率高達到99.8%，就連讓四子的棋局也有80%以上的勝率。在2015年底和2016年初實際和不同職業棋士對戰，取得10戰9勝的優異戰績。因此GoRanking網站更將AlphaGo列在他們全球頂尖棋士排名的第二名。
結語
知名學者及業餘棋士沈君山曾在人類心智運作的研究中提出，頂尖人類棋士在下棋時跟電腦圍棋程式最大的差別就是pattern比對。人類棋士利用經驗及直覺可以自然找出盤面上的重點，在計算時就能大幅減少需要思考的棋步、也能對關鍵棋步的變化優先思考。在AlphaGo成功利用深度學習補足pattern比對這一步之後，就大大提升了圍棋程式的棋力，而能威脅到人類智能在對局上的最後領域。
AlphaGo一戰成名更讓人對深度學習的能力和新的應用方式感到興趣，而且深具信心。或許將來真有一天可以用深度學習為基礎，產生出更有「智慧」的「人工智慧」。