AlphaGo小白的人工智能之路課件

小白的人工智能之路2018-6AlphaGo

&

AlphaGo

Zero小白的人工智能之路2018-6AlphaGo&Alpha1在接下來的一個小時中，你將會……認識“誰”是可愛的AlphaGo

還有它的兄弟AlphaGo

Zero……探知AlphaGo和AlphaGo

Zero的實現(xiàn)原理

深度神經(jīng)網(wǎng)絡(luò)……蒙特卡洛樹搜索……有監(jiān)督學(xué)習(xí)做自己的井字棋AI

/人機對弈程序

易于實現(xiàn)的極大極小樹算法在接下來的一個小時中，你將會……認識“誰”是可愛的Alph2AlphaGo

Human

or

AI？AlphaGo

HumanorAI？3AlphaGo小白的人工智能之路ppt課件4AlphaGo戰(zhàn)績2016年1月27日

AlphaGo以5:0完勝歐洲圍棋冠軍樊麾2016年3月9日到15日挑戰(zhàn)世界圍棋冠軍李世石的AlphaGo以4:1取得勝利2017年5月23日到27日烏鎮(zhèn)圍棋峰會，AlphaGo以3:0戰(zhàn)勝世界圍棋冠軍柯潔AlphaGo戰(zhàn)績2016年1月27日5AlphaGo家族

AlphaGo→AlphaGoZero→AlphaZeroAlphaGo:于2014年開始由GoogleDeepMind開發(fā)的人工智能圍棋軟件。它以人類圍棋高手的棋譜作為參考數(shù)據(jù)。

AlphaGoZero:AlphaGo的團隊于2017年10月19日在《自然》雜志上發(fā)表了一篇文章，介紹了AlphaGoZero，這是一個沒有用到人類數(shù)據(jù)的版本（圍棋棋盤大小與規(guī)則除外），比以前任何擊敗人類的版本都要強大。通過跟自己對戰(zhàn)，AlphaGoZero經(jīng)過3天的學(xué)習(xí)，以100:0的成績超越了AlphaGoLee的實力，21天后達到了AlphaGoMaster的水平，并在40天內(nèi)超過了所有之前的版本。

AlphaZero:AlphaZero使用與AlphaGoZero類似但更一般性的算法，在不做太多改變的前提下，并將算法從圍棋延伸到將棋與國際象棋上。AlphaGo家族

AlphaGo→AlphaGoZ6AlphaGo家族有多可怕？！訓(xùn)練第0天的AlphaGo

Zero

什么都不懂，訓(xùn)練第3天打敗AlphaGo

Lee，訓(xùn)練第21天打敗AlphaGoMaster，訓(xùn)練第40天超越了此前AlphaGo系列的所有成員。AlphaGo家族有多可怕？！訓(xùn)練第0天的Alpha7AlphaGo家族有多可怕？！AlphaZero在短時間訓(xùn)練后能達到其他算法的同等或更高水平AlphaGo家族有多可怕？！AlphaZero在短時間訓(xùn)8版本使用規(guī)則硬件Elo等級分的理論峰值戰(zhàn)績AlphaGo樊(v13)中國規(guī)則176個GPU，分布式3,1445比0戰(zhàn)勝[???]AlphaGo李(v18)48個TPU，分布式3,7394比1戰(zhàn)勝[???]AlphaGoMaster4個TPUv2，單機4,858網(wǎng)棋60比0戰(zhàn)勝職業(yè)棋手；

3比0戰(zhàn)勝柯潔；1比0戰(zhàn)勝人類團隊AlphaGoZero川普-泰勒規(guī)則4個TPUv2，單機5185100:0戰(zhàn)勝AlphaGo李;

與AlphaGoMaster對戰(zhàn)勝率達90%AlphaZero4個TPUv2，單機N/A60:40戰(zhàn)勝AlphaGoZero（3天版本）版本使用規(guī)則硬件Elo等級分的理論峰值戰(zhàn)績AlphaGo樊9AlphaGo走下神壇AlphaGo的勝利意味著AI技術(shù)有了突破性的進展？AlphaGo的勝利意味著機器打敗人腦？答案是否定的。其實，AlphaGo在算法層面上并沒有太多新意，而是通過Google強大的團隊和計算平臺，把已有的技術(shù)整合在一起，利用大量的訓(xùn)練數(shù)據(jù)和計算資源來提高準確性。AlphaGo

=蒙特卡洛樹搜索算法(MCTS)

+深度神經(jīng)網(wǎng)絡(luò)AlphaGo走下神壇AlphaGo的勝利意味著AI技術(shù)10博弈樹把游戲看作一棵樹每個結(jié)點是一種游戲狀態(tài)。博弈樹把游戲看作一棵樹11名稱棋盤大小(位置數(shù))狀態(tài)空間復(fù)雜度(狀態(tài)數(shù))狀態(tài)樹復(fù)雜度(葉子結(jié)點數(shù))平均游戲長度井字棋(Tic-Tac-Toe)91031059四子棋(Connect4)421013102121翻轉(zhuǎn)棋(Reversi/Othello)641028105858跳棋(Internationaldraughts/Checkers)501030105490中國象棋9010401015095國際象棋(Chess)6410471012370五子棋(Gomoku)22510105107030圍棋(Go)3611017010360150六子棋(Connect6)361101721014030常見對弈游戲的狀態(tài)復(fù)雜度對比名稱棋盤大小(位置數(shù))狀態(tài)空間復(fù)雜度(狀態(tài)數(shù))狀態(tài)樹復(fù)雜度(12圍棋的狀態(tài)復(fù)雜度為10170那么10的170次方意味著什么呢？21個百億億億億億億億億億億億億億億億億億億億億億圍棋的狀態(tài)復(fù)雜度為10170那么10的170次方意味著什么呢13這個規(guī)模十分可怕！由于不能將所有狀態(tài)都遍歷一次，于是AlphaGo使用“蒙特卡羅樹搜索”算法(MCTS)這個規(guī)模十分可怕！由于不能將所有狀態(tài)都遍歷一次，于是14先從蒙特卡羅方法開始：

假設(shè)我們要計算一個不規(guī)則圖形的面積。蒙特卡羅方法基于這樣的思想：假想你有一袋豆子，把豆子均勻地朝這個圖形上撒，然后數(shù)這個圖形之中有多少顆豆子，這個豆子的數(shù)目就是圖形的面積。當(dāng)你的豆子越小，撒的越多的時候，結(jié)果就越精確。AlphaGo

——

什么是蒙特卡羅樹搜索(MCTS)？圖：計算機蒙特卡羅方法模擬借助計算機程序可以生成大量隨機的、均勻分布坐標點，統(tǒng)計出圖形內(nèi)的點數(shù)，通過它們占總點數(shù)的比例和坐標點生成范圍的面積就可以求出圖形面積。先從蒙特卡羅方法開始：AlphaGo——什么是蒙特卡羅樹15AlphaGo

——什么是蒙特卡羅樹搜索(MCTS)？如何讓計算機“看懂棋局”：

AlphaGo中一個游戲狀態(tài)的大小是19*19*17。不僅要考慮當(dāng)前棋盤狀態(tài)，還要考慮前幾次下棋的位置。其中19*19是圍棋棋盤的大小,17=8+8+1：

1、過去8步的黑棋位置

2、過去8步的白棋位置

3、當(dāng)前走棋方(黑棋/白棋)AlphaGo——什么是蒙特卡羅樹搜索(MCTS)？如何讓16AlphaGo

——

什么是蒙特卡羅樹搜索(MCTS)？蒙特卡羅樹的一個結(jié)點：對應(yīng)一個游戲盤面樹節(jié)點的子結(jié)點：從該狀態(tài)出發(fā)可以產(chǎn)生的后續(xù)狀態(tài)父結(jié)點到子結(jié)點的邊：落子動作每個結(jié)點還具有信息

N和W：N

=結(jié)點(動作)被選擇的次數(shù)W

=

所有子結(jié)點的價值總和價值：獲勝的期望值,-1為負,0為平,1為勝。

AlphaGo——什么是蒙特卡羅樹搜索(MCTS)？蒙特17圖：一棵蒙特卡羅樹圖：一棵蒙特卡羅樹18AlphaGo

——

什么是蒙特卡羅樹搜索(MCTS)？蒙特卡羅樹搜索的一次迭代包括四個階段：選擇、擴展、模擬、反向傳播（回溯）AlphaGo——什么是蒙特卡羅樹搜索(MCTS)？蒙特19蒙特卡羅樹搜索的一次迭代選擇(Selection)：從當(dāng)前結(jié)點的子結(jié)點的中選擇U值最大的一個。

U

=

f(N,W)

擴展(Expansion)：擴展結(jié)點，列出所有可能的動作及其游戲狀態(tài)。蒙特卡羅樹搜索的一次迭代選擇(Selection)：從當(dāng)前結(jié)20模擬(Simulation)：對于一個節(jié)點，多次隨機模擬博弈直到?jīng)Q出勝負。用頻率代替概率，估算這個子節(jié)點的價值

W。勝:W

:=

W

+

1平:W

:=

W

+

0負:W

:=

W

-1蒙特卡羅樹搜索的一次迭代模擬(Simulation)：對于一個節(jié)點，多次隨機模擬博弈21蒙特卡羅樹搜索的一次迭代進行多次模擬后，可以近似認為W/N就是獲勝的期望值。蒙特卡羅樹搜索的一次迭代進行多次模擬后，可以近似認為W/N就22反向傳播(Backpropagation)：

回溯更新父節(jié)點到子節(jié)點的路徑上所有結(jié)點的(N,W)值。蒙特卡羅樹搜索的一次迭代反向傳播(Backpropagation)：蒙特卡羅樹搜索的23AlphaGo等算法中，不同于傳統(tǒng)MCTS方法的隨機模擬博弈，W/N的值由深度神經(jīng)網(wǎng)絡(luò)(后述)估算。選擇子結(jié)點時，除了N,W以外還需要考慮落子概率P。AlphaGo中使用人類專業(yè)棋手的棋譜數(shù)據(jù)訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)，落子更接近于人的思維。而AlphaGoZero和AlphaZero算法中，在進行多次MCTS迭代后，以(子結(jié)點N/父結(jié)點N)估算落子概率，再以此訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)。AlphaGo等算法中MCTS的創(chuàng)新AlphaGo等算法中，不同于傳統(tǒng)MCTS方法的隨機模擬博弈24注:圖中Q=W/N,U正相關(guān)于P/(N+1)(不同于前述傳統(tǒng)MCTS的U）注:圖中Q=W/N,U正相關(guān)于P/(N+1)25深度神經(jīng)網(wǎng)絡(luò)可以用函數(shù)f(s)表示,s表示當(dāng)前游戲狀態(tài)。函數(shù)f(s)有兩個輸出:P(落子概率)和W(價值)，按下圖的方式應(yīng)用到MCTS的計算中。根據(jù)N,W,P的值，進一步選擇子結(jié)點并迭代。最初使用傳統(tǒng)MCTS隨機模擬的估算結(jié)果來訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)。迭代的次數(shù)足夠后，用深度神經(jīng)網(wǎng)絡(luò)的輸出代替隨機模擬。用深度神經(jīng)網(wǎng)絡(luò)預(yù)測落子概率和價值的方法比傳統(tǒng)MCTS的隨機模擬速度更快，效果更好。深度神經(jīng)網(wǎng)絡(luò)可以用函數(shù)f(s)表示,s表示當(dāng)前游戲狀態(tài)。26AlphaGo小白的人工智能之路ppt課件27AlphaGoAlphaGo

=

深度神經(jīng)網(wǎng)絡(luò)

+

蒙特卡羅樹搜索算法

||

估值網(wǎng)絡(luò)

+

走棋網(wǎng)絡(luò)使得電腦像人類的大腦一樣自發(fā)學(xué)習(xí)使得電腦可以結(jié)合樹狀圖進行長遠推斷AlphaGoAlphaGo=深度神經(jīng)網(wǎng)絡(luò)+蒙特卡羅28AlphaGo

——

什么是深度神經(jīng)網(wǎng)絡(luò)？圖：一個三層結(jié)構(gòu)的簡單神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)三要素：輸入層隱藏層輸出層AlphaGo——什么是深度神經(jīng)網(wǎng)絡(luò)？圖：29AlphaGo小白的人工智能之路ppt課件30走棋網(wǎng)絡(luò)(PolicyNetwork)的輸出是19*19+1維向量，表示在19*19的棋盤上每個位置落子的概率，以及當(dāng)前走棋方(黑棋/白棋)。估值網(wǎng)絡(luò)(ValueNetwork)的輸出是范圍在[-1,1]的標量。AlphaGo的估值網(wǎng)絡(luò)和走棋網(wǎng)絡(luò)是獨立的，并且沒有用到殘差層。AlphaGoZero、AlphaZero的估值網(wǎng)絡(luò)與走棋網(wǎng)絡(luò)共享前面的網(wǎng)絡(luò)層。走棋網(wǎng)絡(luò)(PolicyNetwork)的輸出是19*19+31AlphaGo等算法的強化學(xué)習(xí)流程(ReinforcementLearning)（1）自對弈(Self-Play)當(dāng)前網(wǎng)絡(luò)自對弈25000局，保存每一步的游戲狀態(tài)、MCTS中的結(jié)點概率以及最終的獲勝者。AlphaGo等算法的強化學(xué)習(xí)流程(Reinforcemen32AlphaGo等算法的強化學(xué)習(xí)流程(ReinforcementLearning)（2）訓(xùn)練(RetrainNetwork)

從500000局游戲中抽取2048個樣本。

樣本包括上述的游戲狀態(tài)、MCTS的結(jié)點概率以及最終獲勝者。

將游戲狀態(tài)作為深度神經(jīng)網(wǎng)絡(luò)的輸入。

然后將預(yù)測輸出與實際結(jié)果對比，得到損失函數(shù)的值。最后，反向傳播調(diào)整深度神經(jīng)網(wǎng)絡(luò)中的參數(shù)。AlphaGo等算法的強化學(xué)習(xí)流程(Reinforcemen33AlphaGo等算法的強化學(xué)習(xí)流程(ReinforcementLearning)（3）評價網(wǎng)絡(luò)(EvaluateNetwork)

調(diào)整后的網(wǎng)絡(luò)與原網(wǎng)絡(luò)對弈400局。若調(diào)整后的網(wǎng)絡(luò)能贏下至少55%的對局，則接受調(diào)整后的網(wǎng)絡(luò)，并替代原網(wǎng)絡(luò)。AlphaGo等算法的強化學(xué)習(xí)流程(Reinforcemen34實戰(zhàn)環(huán)節(jié)：做自己的井字棋AI

/人機對弈程序19×19的圍棋A