|
新智元編譯1 來源：Nature 參與：王嘉俊 王婉婷 張巨巖 李宏菲 林坤 特別感謝：陳雷 Nature 封面論文：Mastering the game of Go with deep neural networks and tree search（通過深度神經(jīng)網(wǎng)絡(luò)和樹搜索，學(xué)會(huì)圍棋游戲） AlphaGo 給圍棋帶來了新方法，它背后主要的方法是 Value Networks（價(jià)值網(wǎng)絡(luò)）和 Policy Networks（策略網(wǎng)絡(luò)），其中 Value Networks 評估棋盤位置，Policy Networks 選擇下棋步法。這些神經(jīng)網(wǎng)絡(luò)模型通過一種新的方法訓(xùn)練，結(jié)合人類專家比賽中學(xué)到的監(jiān)督學(xué)習(xí)，以及在自己和自己下棋（Self-Play）中學(xué)到強(qiáng)化學(xué)習(xí)。這不需要任何前瞻式的 Lookahead Search，神經(jīng)網(wǎng)絡(luò)玩圍棋游戲的能力，就達(dá)到了最先進(jìn)的蒙特卡洛樹搜索算法的級(jí)別（這種算法模擬了上千種隨機(jī)自己和自己下棋的結(jié)果）。我們也引入了一種新搜索算法，這種算法將蒙特卡洛模擬和價(jià)值、策略網(wǎng)絡(luò)結(jié)合起來。 通過將 Value Networks、Policy Networks 與樹搜索結(jié)合起來，AlphaGo 達(dá)到了專業(yè)圍棋水準(zhǔn)，讓我們看到了希望：在其他看起來無法完成的領(lǐng)域中，AI 也可以達(dá)到人類級(jí)別的表現(xiàn)！ DeepMind 團(tuán)隊(duì)對圍棋項(xiàng)目的介紹（新智元翻譯） 所有完全信息（perfect information）博弈都有一個(gè)最優(yōu)值函數(shù)（optimal value function）， 譯者注：圍棋為何如此復(fù)雜？ 圍棋難的地方在于它的估值函數(shù)非常不平滑，差一個(gè)子盤面就可能天翻地覆，同時(shí)狀態(tài)空間大，也沒有全局的結(jié)構(gòu)。這兩點(diǎn)加起來，迫使目前計(jì)算機(jī)只能用窮舉法并且因此進(jìn)展緩慢。但人能下得好，能在幾百個(gè)選擇中知道哪幾個(gè)位置值得考慮，說明它的估值函數(shù)是有規(guī)律的。這些規(guī)律遠(yuǎn)遠(yuǎn)不是幾條簡單公式所能概括，但所需的信息量還是要比狀態(tài)空間本身的數(shù)目要少得多（得多）。一句話，窮舉狀態(tài)并不是最終目標(biāo)，就算以后超超級(jí)計(jì)算機(jī)能做到這一點(diǎn)，也不能說解決了人工智能。只有找到能學(xué)出規(guī)律的學(xué)習(xí)算法，才是解決問題的根本手段。By 田淵棟 蒙特卡洛樹搜索（MCTS）使用蒙特卡洛算法的模擬結(jié)果來估算一個(gè)搜索樹中每一個(gè)狀態(tài)（state）的值。隨著進(jìn)行了越來越多的模擬，搜索樹會(huì)變得越來越龐大，而相關(guān)的值也會(huì)變得越來越精確。通過選取值更高的子樹，用于選擇行動(dòng)的策略概率在搜索的過程中會(huì)一直隨著時(shí)間而有所改進(jìn)。目前最強(qiáng)大的圍棋程序都是基于蒙特卡洛樹搜索的，通過配置經(jīng)訓(xùn)練后用于預(yù)測人類棋手行動(dòng)的策略概率進(jìn)行增強(qiáng)。這些策略概率用于將搜索范圍縮小到一組概率很高的行動(dòng)、以及在模擬中抽樣行動(dòng)。這種方法已經(jīng)取得了高級(jí)業(yè)余愛好者水平的表現(xiàn)。然而，先前的工作僅局限于基于輸入特征（input features）的線性組合的粗淺策略概率和值函數(shù)。 近期，深度卷積神經(jīng)網(wǎng)絡(luò)在視覺領(lǐng)域有很多前所未有的表現(xiàn)：例如，圖像分類、臉部識(shí)別、玩雅特麗游戲等。他們使用很多層神經(jīng)元，每個(gè)被安排在交疊的區(qū)塊（Tiles）中來構(gòu)建越來越抽象和本地化的圖片表示。我們在圍棋游戲中采用了一個(gè)相似的構(gòu)架。我們用19X19的圖像來傳遞棋盤位置，使用卷積層來構(gòu)建位置的表示。我們使用這些神經(jīng)網(wǎng)絡(luò)來減少搜索樹的有效深度和寬度（breadth）：使用一個(gè)Value Networks（價(jià)值網(wǎng)絡(luò)）來估算位置，使用Policy Network（策略網(wǎng)絡(luò)）來對動(dòng)作進(jìn)行抽樣。 我們使用由若干機(jī)器學(xué)習(xí)階段（Stages）構(gòu)成的流水線來訓(xùn)練神經(jīng)網(wǎng)絡(luò)（例1）。我們直接使用人類專家的步法來訓(xùn)練監(jiān)督學(xué)習(xí)策略網(wǎng)絡(luò)pσ。這為快速而有效的學(xué)習(xí)更新（Learning Updates）提供了高質(zhì)量的梯度和即時(shí)反饋。與之前的工作相似，我們也訓(xùn)練了一個(gè)快速策略網(wǎng)絡(luò)pπ，它可以快速地在模擬中對動(dòng)作進(jìn)行抽樣。接下來，我們訓(xùn)練了強(qiáng)化學(xué)習(xí)（RL）策略網(wǎng)絡(luò)pρ，這個(gè)網(wǎng)絡(luò)通過優(yōu)化“自己對抗自己”的最終結(jié)果來改善監(jiān)督學(xué)習(xí)策略網(wǎng)絡(luò)。這將策略調(diào)整到贏棋這一正確目標(biāo)上，而非讓預(yù)測精確率最大。最后，我們訓(xùn)練了價(jià)值網(wǎng)絡(luò)vθ，它可以預(yù)測出RL策略網(wǎng)絡(luò)通過模擬“自己對抗自己”而得出的策略中哪種是最佳策略。我們的程序AlphaGo高效地結(jié)合將策略和價(jià)值網(wǎng)絡(luò)與蒙特卡洛樹搜索結(jié)合起來。 為了評估AlphaGo，我們在諸多AlphaGo變體和一些其他圍棋程序中進(jìn)行了內(nèi)部比賽，這其中包括了最強(qiáng)大的商業(yè)程序Crazy Stone和Zen，還有最大的開源程序Pachi和Fuego。所有這些程序都是基于高性能MCTS算法。此外，比賽也包含了開源程序GnuGo，這個(gè)程序使用了在MCTS之前出現(xiàn)的最先進(jìn)的方法。規(guī)定所有程序每次落子有5秒的計(jì)算時(shí)間。 比賽的結(jié)果表明單機(jī)AlphaGo領(lǐng)先任何之前的圍棋程序很多段位，取得了495局比賽中494次勝利的成績（99.8%）。為了給AlphaGo提出更大的挑戰(zhàn)，我們也讓AlphaGo讓四子（讓子，即對手自由落子）來比賽；AlphaGo讓子競賽中對陣Crazy Stone、Zen和Pachi時(shí)分別取得了77%、86%和99%的成績。分布式AlphaGo明顯更強(qiáng)大，對陣單機(jī)AlphaGo取得77%的成績，完勝其他程序。 詳解：AlphaGo 如何在對弈中選擇步法 黑色棋子代表AlphaGo正處于下棋狀態(tài)，對于下面的每一個(gè)統(tǒng)計(jì)，橙色圓圈代表的是最大值所處的位置。 a.用價(jià)值網(wǎng)絡(luò)（value network） b.計(jì)算樹中從根節(jié)點(diǎn)s處伸出來的邊（其中每條邊用(s,a)來表示）的動(dòng)作值Q（s,a），僅當(dāng)（λ=0）時(shí)，取價(jià)值網(wǎng)絡(luò)估值的平均值。 c.計(jì)算了根位置處伸出的邊的動(dòng)作值Q(s,a),僅當(dāng)（λ=1）時(shí)，取模擬估計(jì)值的平均值。 d.直接從SL策略網(wǎng)絡(luò) e.計(jì)算了在模擬過程中，從根節(jié)點(diǎn)選出的某個(gè)動(dòng)作的頻率百分比。 f.表示來自于AlphaGo搜索樹的主要變異性（principal variation）（最大訪問數(shù)路徑），移動(dòng)路徑以序號(hào)形式呈現(xiàn)出來。 紅色圓圈表示AlphaGo選擇的步法；白方格表示樊麾作出的回應(yīng)；樊麾賽后評論說：他特別欣賞AlphaGo預(yù)測的（標(biāo)記為1）的步法。 AlphaGo與樊麾的比賽結(jié)果 以編號(hào)形式展示了AlphaGo和樊麾進(jìn)行圍棋比賽時(shí)各自的落子順序。棋盤下方成對放置的棋子表示了相同交叉點(diǎn)處的重復(fù)落子。每對中的第一個(gè)棋子上的數(shù)字表示了何時(shí)發(fā)生重復(fù)落子，而落子位置由第二個(gè)棋子上的數(shù)字決定。（見補(bǔ)充信息 Supplementary Information）
第二盤：AlphaGo 中盤勝 第三盤：AlphaGo 中盤勝
第五盤：AlphaGo 中盤勝 最終，我們評估了分布式AlphaGo與樊麾的比賽，他是專業(yè)2段位選手，2013、14和15年歐洲圍棋賽冠軍。在2015年10月5日到9日，AlphaGo和樊麾正式比賽了5局。AlphaGo全部獲勝。這是第一次一個(gè)電腦圍棋程序，在沒有讓子、全尺寸（19X19）的情況下?lián)魯∪祟悓I(yè)選手，這一成果過去認(rèn)為至少需要 10 年才能實(shí)現(xiàn)。 在我們的工作中，我們開發(fā)了圍棋程序，它將深度神經(jīng)網(wǎng)絡(luò)和樹搜索結(jié)合起來。這個(gè)程序可以達(dá)到最強(qiáng)的人類選手的表現(xiàn)，因此完成了一個(gè)人工智能“偉大挑戰(zhàn)”。我們也為圍棋首創(chuàng)了高效步法選擇和位置評估函數(shù)，這是通過具有創(chuàng)新性地將監(jiān)督和強(qiáng)化學(xué)習(xí)兩種方法結(jié)合起來從而訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)。我們也引入了一個(gè)新搜索算法，這一算法成功的整合了神經(jīng)網(wǎng)絡(luò)評估和蒙特卡洛樹模擬算法。我們的程序AlphaGo在高性能樹搜索引擎中從一定規(guī)模上將這些成分整合在一起。
在和樊麾的比賽中，AlphaGo在評估位置方面要比深藍(lán)與Kasparov4比賽時(shí)所評估的位置少幾千倍，這是由于我們使用了策略網(wǎng)絡(luò)更智能地選擇那些位置，還使用了價(jià)值網(wǎng)絡(luò)更精確地評估它們，而價(jià)值網(wǎng)絡(luò)更接近人類的下棋方式。另外，深藍(lán)依靠手工設(shè)計(jì)評估方程，而AlphaGo的神經(jīng)網(wǎng)絡(luò)是直接通過純比賽數(shù)據(jù)訓(xùn)練，也使用了通用監(jiān)督和強(qiáng)化學(xué)習(xí)方法。
圍棋代表了很多人工智能所面臨的困難：具有挑戰(zhàn)性的決策制定任務(wù)、難以破解的查找空間問題和優(yōu)化解決方案如此復(fù)雜以至于用一個(gè)策略或價(jià)值函數(shù)幾乎無法直接得出。之前在電腦圍棋方面的主要突破是引入MCTS，這導(dǎo)致了很多其他領(lǐng)域的相應(yīng)進(jìn)步：例如，通用博弈，經(jīng)典的計(jì)劃問題，計(jì)劃只有部分可觀測問題、日程安排問題和約束滿足問題。通過將策略和價(jià)值網(wǎng)絡(luò)與樹搜索結(jié)合起來，AlphaGo終于達(dá)到了專業(yè)圍棋水準(zhǔn)，讓我們看到了希望：在其他看起來無法完成的領(lǐng)域中，AI也可以達(dá)到人類級(jí)別的表現(xiàn)。
|
|
|
，它決定了在所有參與博弈的玩家都做出了完美表現(xiàn)的情況下，博弈的結(jié)果是什么
個(gè)可能行動(dòng)序列（其中b是博弈的寬度，也就是在每個(gè)位置能夠移動(dòng)的步數(shù)，而d是博弈的深度）的搜索樹（search tree）上反復(fù)計(jì)算最優(yōu)值函數(shù)來解決的。在象棋（
）和圍棋之類（
）的
。這種方法使程序在象棋、跳棋、翻轉(zhuǎn)棋（Othello）的游戲中表現(xiàn)超越了人類，但人們認(rèn)為它無法應(yīng)用于圍棋，因?yàn)閲鍢O其復(fù)雜。
——一種在位置s時(shí)表示出所有可能的行動(dòng)的概率分布——中抽樣行動(dòng)來降低。
估測根節(jié)點(diǎn)s處的所有子節(jié)點(diǎn)s’，展示了幾個(gè)最大的獲勝概率估計(jì)值。
