一大波Master正在靠近 盤點各國圍棋AI的發展

人工智慧

　　文章來源：科技蜘蛛公眾號

　　一個不透露姓名的神秘 Master，突然出現橫掃人類圍棋高手，豪取60連勝。一份不完全的手下敗將名單 ： 古力，柯潔，陳耀燁，范廷鈺，常昊，時越，羋昱廷，唐韋星，江維傑，柁嘉熹，周睿羊，朴廷桓，元晟溱，姜東潤，金志錫，朴永訓，井山裕太。。。。

　　我猜 DeepMind 團隊肯定有成員看過中國武俠小說，一名神秘殺手於月黑風高間殺遍江湖，武林腥風血雨，尊嚴盡喪。正在各種傳言盛囂塵上之時，殺手現身。絕妙的營銷。一個技術頂尖還懂搞噱頭的團隊，就像你身邊某個智商情商雙爆表，多金，長的還帥的同事，你恨不恨！

　　其實除了AlphaGo，近幾年還有一些很優秀的人工智慧圍棋程序，它們也經常和人類棋手過招，各有勝負，只是宣傳力度遠不如Google。在 DeepMind 的 AlphaGo 異軍突起之前，人工圍棋軟體的佼佼者們，基本被法國和日本等國佔據。它們有共同的基本思路，也有各自獨特的亮點。其中 Facebook 的 darkforest 提供詳細的論文和代碼，別的電腦圍棋程序則比較神秘。

　　Facebook 的黑暗森林 （Darkforest）

　　黑暗森林是 Facebook AI Research 的兩位華人研究者共同完成的人工智慧圍棋程序，命名來自劉慈欣的《三體II：黑暗森林》。田淵棟博士自己在知乎上謙虛的說 （原話），要是 DeepMind 決定在2015年10月份戰勝樊麾後馬上公開，或者他自己再拖一會兒，決定不投ICLR 而等到2016年的 ICML，那就被滅得連渣都不剩了。如果把科研者的虛懷若谷先放一邊的話，人工智慧的日新月異也可見一斑。

　　和 AlphaGo 一樣，黑暗森林也是基於深度神經網路的模型 （12層），所以也和AlphaGo 具有相似的優勢和缺陷。優勢就不再贅述了，缺陷主要存在於對局部策略的選擇上。為了彌補這一缺陷，黑暗森林也選擇了蒙特卡洛樹搜索作為對深層網路的補充。

　　黑暗森林經歷了三個版本的演進。第一代 darkforest 體現了相比傳統蒙克卡洛搜索的優勢，第二代 darkforest2 達到了穩定的 KGS 3d 的水平，之後，在參考了 alphaGo 的演算法之後，作者又在 darkforest2 的基礎上加入了蒙特卡洛演算法，開發出第三代darkfmcts3，性能得到了進一步提升，差不多達到 KGS 5d 的水平。其實相比 DeepMind 人數眾多的團隊，Darkforest 的開發團隊只有兩人，能取得這樣的性能已相當不容易。

　　相比 AlphaGo 的策略網路每次只預測下一步走棋，Darkforest 可以預測接下去 k 步棋 （predict long-term moves），包括自己的和對手的棋，這是它獨特而強大的地方。個人猜測，當時AlphaGo和李世石下棋的時候，有時會走出一些無用的「電腦手」，一方面是 DCNN 的固有弊端 （Darkforest的論文中也提到類似的問題），另一方面也可能就是因為缺乏長遠規劃。另一個獨特的地方是，Darkforest 的結構採用了多個 softmax 輸出，目的是訓練時可以增強監督。為了提高收斂速度，Darkforest 還使用了最新的深度殘差網路 ResNet。

　　Darkforest 比 AlphaGo 欠缺的是預測大局的估值網路，這部分是AlphaGo 的獨創，個人猜測也是它擁有良好大局觀的原因之一。

　　業界良心，黑暗森林的訓練源碼是開源的，感興趣的請猛擊 Github 鏈接https：//github.com/facebookresearch/darkforestGo

　　日本的 Zen

　　Zen 是目前最著名的圍棋程序之一， 2009年發布了第一個版本，最新版本發佈於2016年6月。和黑暗森林與 AlphaGo 的團隊開發不同，Zen 是日本程序員Yoji Ojima單獨開發的圍棋程序，硬體部分則由 Kato Hideki 實現。Zen 以劣勢的硬體設備 （單機Mac Pro8cores， 當然最新也有mini cluster 或 GPU 版本），連續多年在各種圍棋人工智慧比賽中奪得冠軍。Zen 19K2 也是第一個達到 9D 水準的機器。

　　法國的 CrazyStone

　　CrazyStone 由法國計算機科學家 Rémi Coulom 單獨開發，採用的也是蒙特卡洛搜索方法，在 Grid『5000 大規模計算平台上運行。CrazyStone 2013年被讓4子擊敗石田芳夫，2014年被讓4子擊敗依田紀基。圖為 Rémi Coulom 和依田紀基正在對決。

　　2016年5月，CrazyStone 的最新版本加入了深度學習模塊，使性能大幅提高，達到 KGS 7d 水準，對戰沒有深度學習的CrazyStone 2013版本的勝率達到 90%UnbalanceCorporation 還推出了商業版本， 花80美元你就可以擁有一個職業棋手水準的專職陪練！

　　法國和台灣合作的 MoGo

　　MoGo 是一款由法國INRIA （法國國家信息與自動化研究所） 和一個台灣的團隊共同開發的圍棋軟體。2009年於台灣，MoGo在被讓7子的條件下在19*19全尺寸棋盤上擊敗了周俊勛九段。 MoGo採用的技術主要有：蒙特卡洛方法，基於Armed Bandits 的樹搜索演算法 （在當時是革命性的），以及高性能計算集群 （和Crazy Stone一樣在Grid『5000大規模計算平台上運行）。最近 MoGo 貌似沒有更新一步的動作。

　　韓國的DolBaram

　　作為在圍棋領域和智能科技領域均有相當積累的國家，韓國的一家規模並不大的公司 NuriGrim 決定向日本和法國挑戰，開發出了 DolBaram。在2016年的 UEC Cup 上，DolBaram 取得了第二名的戰績。在流傳出的有限的信息中，可以知道 DolBaram 和 AlphaGo 一樣，也採用了深度學習方法。

　　可以看出，AlphaGo 的成功對人工圍棋軟體這個行業的影響是很明顯的，深度學習和蒙特卡洛結合的方法成為了主流。而圍棋之後，類似的方法在別的需要複雜決策的領域的應用，比如醫療，政府決策，智慧城市等，才是更令人激動的。正是人類智慧才創造了人工智慧，你大爺終究是你大爺。

　　補充： 一些關於AlphaGo的陳詞濫調

　　如果讀到這裡讀者還沒有累，或是對介紹 AlphaGo 的陳詞濫調還沒有厭倦，筆者願意和大家再回顧一下 AlphaGo 的原理，溫故而知新嘛

　　由於巨大的搜索空間 （窮舉搜索是不可能的） 和分析棋局自身的複雜性，圍棋一向被視為是對於人工智慧最具挑戰性的經典遊戲之一。通常情況下，我們可以設法把實際搜索空間縮小。1） 減小深度：把狀態s以下的子樹用一個預測狀態s的輸出的近似函數代替。這種方法已經在國際象棋和跳棋上取得成功，超過了人類的表現，但是因為圍棋的複雜度，被認為行不通。2） 減小廣度：對政策p採樣，政策指的是在某一狀態s下的所有走法的概率分布。比如Monte-Carlo rollouts，隨機選擇一些採樣點，直接不分支搜到樹的最頂部，然後對這些採樣取均值。這種方法可以取得一個較有效的對棋局的判斷，被證明可以戰勝初級圍棋手。

　　AlphaGo 採取了一種新穎的方法，主要由三部分組成：策略網路，負責預測下一步的棋的概率；估值網路，負責評估當前局面，預測獲勝方；蒙塔卡洛樹搜索，作用是把系統連為一體。這三個部分並非缺一不可，但是合作在一起，能取得最好的效果。AlphaGo取得了對其他圍棋程序99.8%的勝率，在擊敗李世石的世紀大戰之前，AlphaGo 曾5比0橫掃歐洲圍棋冠軍。這是計算機首次在全尺寸棋盤圍棋比賽中擊敗人類職業棋手，這樣的成就比人們之前預測的至少提前了十年。

　　1。 策略網路

　　訓練策略網路是 AlphaGo 整個訓練體系的第一步。圍棋棋盤有19*19個棋格，可以看作是一幅19*19像素的圖像，每個像素可以有三個值：黑、白、空。每一個特定時刻的棋局，其實就是一幅19*19的圖，作為深層網路的輸入。2016年1月發布在自然雜誌上的AlphaGo的版本中，策略網路包含了13層神經元，訓練數據是從 KGS Go 伺服器上取得的3000萬個人類棋手的真實棋局，和該棋局對應的下一步走法。

　　經過多個卷積層和非線性激活函數，策略網路在輸出層預測每一個合法落子的概率。機器預測的下一步和人類棋手的下一步會有偏差，網路就以經典的梯度下降演算法調整每個連接的權重，糾正偏差。AlphaGo預測人類棋手下一步的準確率達到了57%。值得注意是，AlphaGo還具備一個快速走子策略。完整的策略網路雖然能提供很高的正確率，但是速度較慢 （預測每一步需要 3 ms ），快速走子可以把速度提高1500倍，達到 2 微秒/步，代價是犧牲一定的準確度。

　　如果說深層卷積網路讓 AlphaGo 具備了模仿人類棋手走下一步棋的能力，那麼接下來的強化學習 （ reinforcement learning ） 進一步優化了預測結果。強化學習，其實就是讓機器不再模仿人類，而是自己跟自己下棋。此時的機器一分為二，一方是當前的狀態，另一方是隨機選取的之前某一步迭代的狀態。隨機選取對手是為了要避免過擬合。有趣的是，如果把只會模仿人類的機器和經過強化學習優化過的機器一對一較量，後者取得了80%的勝率。

　　2。 估值網路

　　估值網路的目的是評估當前局面，預測最後的勝者。估值網路是AlphaGo相比別的人工智慧圍棋演算法的新穎之處。預測局面是圍棋的難點之一，就算是頂尖棋手，在預測的時候也經常出現偏差。

　　訓練估值網路有一個小竅門。如果把同一盤棋的每一步局面都當作輸入訓練的話，因為每兩個相鄰的棋局都只差一顆棋子，相關性很高，所以很容易造成過擬合的問題。作者就讓機器自己生成3000萬個不同的棋局，每個棋局都屬於一盤不同的棋。訓練後的估值網路比採用快速蒙特卡洛推演（ Monte-Carlo rollouts with fast policy） 要準確，同時可以達到一般蒙特卡洛推演的準確度，但是要快15000倍。

　　AlphaGo完全沒有做任何局部分析，純粹用暴力訓練出一個相當不錯的估值網路，實際上證明了深度卷積神經網路的對問題的分解能力。

　　3。 蒙特卡洛樹搜索

　　AlphaGo通過蒙特卡洛樹搜索把策略網路和估值網路結合了起來。目前主要有兩種隨機演算法，蒙特卡洛演算法和拉斯維加斯演算法。簡單的說，蒙特卡洛演算法是採樣越多，越近似最優解，但找到的不一定就是最優解。相反，拉斯維加斯演算法是採樣越多，越有可能找到最優解，也就是說找到了就是最優解，但是不保證能找到。顯然，對於圍棋對弈，要求在有限的採樣內，必須給出一個解，不要求是最優解，但是要盡量接近。這種情況，蒙特卡洛演算法是很合適的，也是各個圍棋軟體很常用的一個方法。

　　如何高效的用蒙特卡洛樹搜索把策略和估值網路結合，對實際的工程水平是有很高要求的。AlphaGo選擇在CPU上運行非同步多線程搜索，在GPU上平行計算策略網路和估值網路。當時和李世石世紀大戰的AlphaGo用了40個搜索線程，48個CPU和8個GPU。還有一個更強大的分散式版本，擁有1202個CPU和176個GPU。