深度學習工程師：為什么AlphaGo難取勝？從核心技術解讀圍棋大戰

按：作者李理，出門問問NLP工程師。

AlphaGo在與歐洲圍棋冠軍樊麾(Fan Hui)的對壘

從技術的角度分析，個人覺得，3月份AlphaGo要戰勝李世石難度是比較大的。為什么呢？請看下文。 

一、 AlphaGo的兩大核心技術

• MCTS(Monte Carlo Tree Search)

MCTS之于圍棋就像Alpha-Beta搜索之于象棋，是核心的算法，而比賽時的搜索速度至關重要。就像深藍當年戰勝時，超級計算機的運算速度是制勝的關鍵因素之一。

 MCTS的4個步驟：Selection，Expansion，Evaluation(rollout)和Backup

MCTS的并行搜索：

 (1) Leaf Parallelisation

     最簡單的是Leaf Parallelisation，一個葉子用多個線程進行多次Simulation，完全不改變之前的算法，把原來的一次Simulation的統計量用多次來代替，這樣理論上應該準確不少。但這種并行的問題是需要等待最慢的那個結束才能更新統計量；而且搜索的路徑數沒有增多。

(2) Root Parallelisation

多個線程各自搜索各自的UCT樹，最后投票

(3) Tree Parallelisation

這是真正的并行搜索，用多個線程同時搜索UCT樹。當然統計量的更新需要考慮多線程的問題，比如要加鎖。

另外一個問題就是多個線程很可能同時走一樣的路徑（因為大家都選擇目前看起來Promising的孩子），一種方法就是臨時的修改virtual loss，比如線程1在搜索孩子a，那么就給它的Q(v)減一個很大的數，這樣其它線程就不太可能選擇它了。當然線程1搜索完了之后要記得改回來。

《A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm》使用了一種lock-free的算法，這種方法比加鎖的方法要快很多，AlphaGo也用了這個方法。

 Segal研究了為什么多機的MCTS算法很難，并且實驗得出結論使用virtual loss的多線程版本能比較完美的scale到64個線程(當然這是單機一個進程的多線程程序）。AlphaGo的Rollout是用CPU集群來加速的，但是其它的三個步驟是在一臺機器完成的，這個就是最大的瓶頸。

• DCNN(Deep Convolutional Neural Network)
  

（使用深度神經網絡訓練的Policy Network和Value Network）

神經網絡訓練的時間一般很長，即使用GPU，一般也是用天來計算。Google使用GPU Cluster來訓練，從論文中看，訓練時間最長的Value Network也只是用50個GPU訓練了一周。

給定一個輸入，用卷積神經網絡來預測，基本運算是矩陣向量運算和卷積，由于神經網絡大量的參數，用CPU來運算也是比較慢的。所以一般也是用GPU來加速，而AlphaGo是用GPU的cluster來加速的。

更多技術細節請參考我的文章《alphaGo對戰李世石誰能贏？兩萬字長文深挖圍棋AI技術》

 1. 論文送審時(2015年11月)AlphaGo的水平

論文里使用Elo Rating系統的水平：

a圖是用分布式的AlphaGo，單機版的AlphaGo，CrazyStone等主流圍棋軟件進行比賽，然后使用的是Elo Rating的打分。

筆者認為AlphaGo的水平超過了FanHui（2p)，因此AlphaGo的水平應該達到了2p。【不過很多人認為目前Fanhui的水平可能到不了2p】

b圖說明了Policy Network Value Network和Rollout的作用，做了一些實驗，去掉一些的情況下棋力的變化，結論當然是三個都很重要。

c圖說明了搜索線程數以及分布式搜索對棋力的提升，這些細節我們會在下一節再討論，包括AlphaGO的架構能不能再scalable到更多機器的集群從而提升棋力。

•  AlphaGo的真實棋力

筆者這里根據一些新聞做推測。而且從文章提交Nature審稿到3月份比賽還有一段不短的時間，AlphaGo能不能還有提高也是非常關鍵。這里我只是推測一下在文章提交Nature時候AlphaGo的棋力。至于AlphaGo棋力能否提高，我們下一節分析實現細節時再討論（假設整體架構不變，系統能不能通過增加機器來提高棋力）。

網上很多文章試圖通過AlphaGo與fanhui的對局來估計AlphaGo的棋力，我本人圍棋水平離入門都比較遠，所以就不敢發表意見了。我只是搜索了一些相關的資料，主要是在弈城上一個叫DeepMind的賬號的對局信息來分析的。

比如這篇《金燦佑分析deepmind棋譜 認為99%與谷歌團隊相關》。作者認為這個賬號就是AlphaGo。如果猜測正確的話，AlphaGo當時的棋力在弈城8d-9d之間，換成我們常用的ranking system的話大概也就是6d-7d（業余6段到7段）的水平，如果發揮得好，最多也許能到1p的水平，戰勝fanhui也有一定合理性（很多人認為fanhui目前實際水平可能已經沒有2p了，那算1p的話也差不多）

知乎的這個話題AlphaGo也有很多討論，可供參考。

二、 AlphaGo到比賽前可能的提升

不同分布式版本的水平比較，使用的是Elo rating標準

最強的AlphaGo使用了64個搜索線程，1920個CPU的集群和280個GPU的集群（其實也就二十多臺機器）

三、 AI戰勝圍棋大師李世石：我看懸

之前我們討論過分布式MCTS時說過，MCTS很難在多機上并行，所以AlphaGo還是在一臺機器上實現的LockFree的多線程并行，只不過Rollout和神經網絡計算是在CPU和GPU集群上進行的。Google的財力肯定不只二三十臺機器，所以分布式MCTS的搜索才是最大的瓶頸。如果這個能突破，把機器堆到成百上千臺應該還是能提高不少棋力的。

我個人估計在3月與李世石的對弈中這個架構可能還很難有突破，可以增強的是RL Policy的自對弈學習，不過這個提升也有限（否則不會只訓練一天就停止了，估計也收斂的差不多了）。

所以，這一次，AI的勝算并沒有李世石的大。

雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。