<mark id="oztn4"></mark>
9
| 本文作者： Ticwear | 2016-03-08 15:35 | 專題：人工智能和李世石的世紀(jì)之戰(zhàn) |
按：作者李理，出門問問NLP工程師。
AlphaGo在與歐洲圍棋冠軍樊麾(Fan Hui)的對(duì)壘
從技術(shù)的角度分析，個(gè)人覺得，3月份AlphaGo要戰(zhàn)勝李世石難度是比較大的。為什么呢？請(qǐng)看下文。
MCTS(Monte Carlo Tree Search)
MCTS之于圍棋就像Alpha-Beta搜索之于象棋，是核心的算法，而比賽時(shí)的搜索速度至關(guān)重要。就像深藍(lán)當(dāng)年戰(zhàn)勝時(shí)，超級(jí)計(jì)算機(jī)的運(yùn)算速度是制勝的關(guān)鍵因素之一。
MCTS的4個(gè)步驟：Selection，Expansion，Evaluation(rollout)和Backup
MCTS的并行搜索：
(1) Leaf Parallelisation
最簡(jiǎn)單的是Leaf Parallelisation，一個(gè)葉子用多個(gè)線程進(jìn)行多次Simulation，完全不改變之前的算法，把原來的一次Simulation的統(tǒng)計(jì)量用多次來代替，這樣理論上應(yīng)該準(zhǔn)確不少。但這種并行的問題是需要等待最慢的那個(gè)結(jié)束才能更新統(tǒng)計(jì)量；而且搜索的路徑數(shù)沒有增多。
(2) Root Parallelisation
多個(gè)線程各自搜索各自的UCT樹，最后投票
(3) Tree Parallelisation
這是真正的并行搜索，用多個(gè)線程同時(shí)搜索UCT樹。當(dāng)然統(tǒng)計(jì)量的更新需要考慮多線程的問題，比如要加鎖。
另外一個(gè)問題就是多個(gè)線程很可能同時(shí)走一樣的路徑（因?yàn)榇蠹叶歼x擇目前看起來Promising的孩子），一種方法就是臨時(shí)的修改virtual loss，比如線程1在搜索孩子a，那么就給它的Q(v)減一個(gè)很大的數(shù)，這樣其它線程就不太可能選擇它了。當(dāng)然線程1搜索完了之后要記得改回來。
《A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm》使用了一種lock-free的算法，這種方法比加鎖的方法要快很多，AlphaGo也用了這個(gè)方法。
Segal研究了為什么多機(jī)的MCTS算法很難，并且實(shí)驗(yàn)得出結(jié)論使用virtual loss的多線程版本能比較完美的scale到64個(gè)線程(當(dāng)然這是單機(jī)一個(gè)進(jìn)程的多線程程序）。AlphaGo的Rollout是用CPU集群來加速的，但是其它的三個(gè)步驟是在一臺(tái)機(jī)器完成的，這個(gè)就是最大的瓶頸。
DCNN(Deep Convolutional Neural Network)
（使用深度神經(jīng)網(wǎng)絡(luò)訓(xùn)練的Policy Network和Value Network）
神經(jīng)網(wǎng)絡(luò)訓(xùn)練的時(shí)間一般很長(zhǎng)，即使用GPU，一般也是用天來計(jì)算。Google使用GPU Cluster來訓(xùn)練，從論文中看，訓(xùn)練時(shí)間最長(zhǎng)的Value Network也只是用50個(gè)GPU訓(xùn)練了一周。
給定一個(gè)輸入，用卷積神經(jīng)網(wǎng)絡(luò)來預(yù)測(cè)，基本運(yùn)算是矩陣向量運(yùn)算和卷積，由于神經(jīng)網(wǎng)絡(luò)大量的參數(shù)，用CPU來運(yùn)算也是比較慢的。所以一般也是用GPU來加速，而AlphaGo是用GPU的cluster來加速的。
更多技術(shù)細(xì)節(jié)請(qǐng)參考我的文章《alphaGo對(duì)戰(zhàn)李世石誰能贏？?jī)扇f字長(zhǎng)文深挖圍棋AI技術(shù)》
1. 論文送審時(shí)(2015年11月)AlphaGo的水平
論文里使用Elo Rating系統(tǒng)的水平：
a圖是用分布式的AlphaGo，單機(jī)版的AlphaGo，CrazyStone等主流圍棋軟件進(jìn)行比賽，然后使用的是Elo Rating的打分。
筆者認(rèn)為AlphaGo的水平超過了FanHui（2p)，因此AlphaGo的水平應(yīng)該達(dá)到了2p。【不過很多人認(rèn)為目前Fanhui的水平可能到不了2p】
b圖說明了Policy Network Value Network和Rollout的作用，做了一些實(shí)驗(yàn)，去掉一些的情況下棋力的變化，結(jié)論當(dāng)然是三個(gè)都很重要。
c圖說明了搜索線程數(shù)以及分布式搜索對(duì)棋力的提升，這些細(xì)節(jié)我們會(huì)在下一節(jié)再討論，包括AlphaGO的架構(gòu)能不能再scalable到更多機(jī)器的集群從而提升棋力。
AlphaGo的真實(shí)棋力
筆者這里根據(jù)一些新聞做推測(cè)。而且從文章提交Nature審稿到3月份比賽還有一段不短的時(shí)間，AlphaGo能不能還有提高也是非常關(guān)鍵。這里我只是推測(cè)一下在文章提交Nature時(shí)候AlphaGo的棋力。至于AlphaGo棋力能否提高，我們下一節(jié)分析實(shí)現(xiàn)細(xì)節(jié)時(shí)再討論（假設(shè)整體架構(gòu)不變，系統(tǒng)能不能通過增加機(jī)器來提高棋力）。
網(wǎng)上很多文章試圖通過AlphaGo與fanhui的對(duì)局來估計(jì)AlphaGo的棋力，我本人圍棋水平離入門都比較遠(yuǎn)，所以就不敢發(fā)表意見了。我只是搜索了一些相關(guān)的資料，主要是在弈城上一個(gè)叫DeepMind的賬號(hào)的對(duì)局信息來分析的。
比如這篇《金燦佑分析deepmind棋譜 認(rèn)為99%與谷歌團(tuán)隊(duì)相關(guān)》。作者認(rèn)為這個(gè)賬號(hào)就是AlphaGo。如果猜測(cè)正確的話，AlphaGo當(dāng)時(shí)的棋力在弈城8d-9d之間，換成我們常用的ranking system的話大概也就是6d-7d（業(yè)余6段到7段）的水平，如果發(fā)揮得好，最多也許能到1p的水平，戰(zhàn)勝fanhui也有一定合理性（很多人認(rèn)為fanhui目前實(shí)際水平可能已經(jīng)沒有2p了，那算1p的話也差不多）
知乎的這個(gè)話題AlphaGo也有很多討論，可供參考。
不同分布式版本的水平比較，使用的是Elo rating標(biāo)準(zhǔn)
最強(qiáng)的AlphaGo使用了64個(gè)搜索線程，1920個(gè)CPU的集群和280個(gè)GPU的集群（其實(shí)也就二十多臺(tái)機(jī)器）
之前我們討論過分布式MCTS時(shí)說過，MCTS很難在多機(jī)上并行，所以AlphaGo還是在一臺(tái)機(jī)器上實(shí)現(xiàn)的LockFree的多線程并行，只不過Rollout和神經(jīng)網(wǎng)絡(luò)計(jì)算是在CPU和GPU集群上進(jìn)行的。Google的財(cái)力肯定不只二三十臺(tái)機(jī)器，所以分布式MCTS的搜索才是最大的瓶頸。如果這個(gè)能突破，把機(jī)器堆到成百上千臺(tái)應(yīng)該還是能提高不少棋力的。
我個(gè)人估計(jì)在3月與李世石的對(duì)弈中這個(gè)架構(gòu)可能還很難有突破，可以增強(qiáng)的是RL Policy的自對(duì)弈學(xué)習(xí)，不過這個(gè)提升也有限（否則不會(huì)只訓(xùn)練一天就停止了，估計(jì)也收斂的差不多了）。
所以，這一次，AI的勝算并沒有李世石的大。
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
專題
