<mark id="oztn4"></mark>
8
| 本文作者： 新智元 | 2016-01-28 11:30 | 專題：人工智能和李世石的世紀(jì)之戰(zhàn) |
編者按：本文由新智元原創(chuàng)翻譯自Nature。如果覺得此文深奧，關(guān)于機(jī)器學(xué)習(xí)，還可看雷鋒網(wǎng)早期文章：《機(jī)器自學(xué)72小時堪比國際大師，深度學(xué)習(xí)到底有多厲害？》
圍棋一直被視為人工智能最難破解的游戲。就在今天，《Nature》雜志以封面論文的形式，介紹了 Google DeepMind 開發(fā)的人工智能程序 AlphaGo，它擊敗了歐洲圍棋冠軍樊麾，并將在 3 月和世界冠軍李世乭對戰(zhàn)！Google 特地為此準(zhǔn)備了 100 萬美元獎金。
從國際象棋的經(jīng)驗看，1997 年人工智能第一次打敗人類后，2006 年成為了人類在國際象棋的絕唱，自此之后人類沒有戰(zhàn)勝過最頂尖的人工智能國際象棋選手。在 AlphaGo 打敗了歐洲圍棋冠軍后，世界冠軍李世乭和 AlphaGo 的對弈，是否會成為人類在圍棋領(lǐng)域的絕唱？
Nature 封面論文：Mastering the game of Go with deep neural networks and tree search（通過深度神經(jīng)網(wǎng)絡(luò)和搜索樹，學(xué)會圍棋游戲）
AlphaGo 給圍棋帶來了新方法，它背后主要的方法是 Value Networks（價值網(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ī)自己和自己下棋的結(jié)果）。我們也引入了一種新搜索算法，這種算法將蒙特卡洛模擬和價值、策略網(wǎng)絡(luò)結(jié)合起來。
通過這種搜索算法，AlphaGo 在和其他圍棋程序比賽的勝率達(dá)到了 99.8%，并以 5：0 的比分擊敗了人類歐洲圍棋冠軍樊麾。這是電腦程序第一次在全尺寸（19X19）的棋盤上擊敗了人類專業(yè)選手，這一成果過去認(rèn)為至少需要 10 年才能實現(xiàn)。
歐洲圍棋冠軍樊麾：2005 年樊麾被正式聘任為法國圍棋隊和少年圍棋隊的總教練，那一年的他才 24 歲。他是 2013、2014 和 2015 歐洲圍棋賽冠軍。
通過將 Value Networks、Policy Networks 與樹搜索結(jié)合起來，AlphaGo 達(dá)到了專業(yè)圍棋水準(zhǔn)，讓我們看到了希望：在其他看起來無法完成的領(lǐng)域中，AI 也可以達(dá)到人類級別的表現(xiàn)！
關(guān)于DeepMind 團(tuán)隊對圍棋項目的介紹，可進(jìn)入新智元查看。
所有完全信息（perfect information）博弈都有一個最優(yōu)值函數(shù)（optimal value function），它決定了在所有參與博弈的玩家都做出了完美表現(xiàn)的情況下，博弈的結(jié)果是什么：無論你在棋盤的哪個位置落子（或者說是狀態(tài)s）。
這些博弈游戲是可能通過在含有大約個bd可能行動序列（其中b是博弈的寬度，也就是在每個位置能夠移動的步數(shù)，而d是博弈的深度）的搜索樹（search tree）上反復(fù)計算最優(yōu)值函數(shù)來解決的。在象棋（b≈35，d≈80）和圍棋之類（b≈250，d≈150）的大型博弈游戲中，窮盡地搜索是不合適的，但是有效搜索空間是可以通過2種普遍規(guī)則得到降低的。
首先，搜索的深度可能通過位置估計（position evaluation）來降低：在狀態(tài)s時截取搜索樹，將隨后的子樹部分（subtree）替換為根據(jù)狀態(tài)s來預(yù)測結(jié)果的近似的值函數(shù)v(s)≈v*(s)。這種方法使程序在象棋、跳棋、翻轉(zhuǎn)棋（Othello）的游戲中表現(xiàn)超越了人類，但人們認(rèn)為它無法應(yīng)用于圍棋，因為圍棋極其復(fù)雜。
其次，搜索的寬度可能通過從策略概率p(a| s)——一種在位置s時表示出所有可能的行動的概率分布——中抽樣行動來降低。比如，蒙特卡洛法通過從策略概率p中為博弈游戲雙方抽樣長序列的行動來讓搜索達(dá)到深度的極限、沒有任何分支樹。將這些模擬結(jié)果進(jìn)行平均，能夠提供有效的位置估計，讓程序在西洋雙陸棋（backgammon）和拼字棋（Scrabble）的游戲中展現(xiàn)出超越人類的表現(xiàn)，在圍棋方面也能達(dá)到低級業(yè)余愛好者水平。
圍棋為何如此復(fù)雜？
圍棋有3361 種局面，而可觀測到的宇宙，原子數(shù)量才1080。
圍棋難的地方在于它的估值函數(shù)非常不平滑，差一個子盤面就可能天翻地覆，同時狀態(tài)空間大，也沒有全局的結(jié)構(gòu)。這兩點加起來，迫使目前計算機(jī)只能用窮舉法并且因此進(jìn)展緩慢。
但人能下得好，能在幾百個選擇中知道哪幾個位置值得考慮，說明它的估值函數(shù)是有規(guī)律的。這些規(guī)律遠(yuǎn)遠(yuǎn)不是幾條簡單公式所能概括，但所需的信息量還是要比狀態(tài)空間本身的數(shù)目要少得多（得多）。一句話，窮舉狀態(tài)并不是最終目標(biāo)，就算以后超超級計算機(jī)能做到這一點，也不能說解決了人工智能。只有找到能學(xué)出規(guī)律的學(xué)習(xí)算法，才是解決問題的根本手段。By 田淵棟
蒙特卡洛樹搜索（MCTS）使用蒙特卡洛算法的模擬結(jié)果來估算一個搜索樹中每一個狀態(tài)（state）的值。隨著進(jìn)行了越來越多的模擬，搜索樹會變得越來越龐大，而相關(guān)的值也會變得越來越精確。通過選取值更高的子樹，用于選擇行動的策略概率在搜索的過程中會一直隨著時間而有所改進(jìn)。目前最強(qiáng)大的圍棋程序都是基于蒙特卡洛樹搜索的，通過配置經(jīng)訓(xùn)練后用于預(yù)測人類棋手行動的策略概率進(jìn)行增強(qiáng)。這些策略概率用于將搜索范圍縮小到一組概率很高的行動、以及在模擬中抽樣行動。這種方法已經(jīng)取得了高級業(yè)余愛好者水平的表現(xiàn)。然而，先前的工作僅局限于基于輸入特征（input features）的線性組合的粗淺策略概率和值函數(shù)。
近期，深度卷積神經(jīng)網(wǎng)絡(luò)在視覺領(lǐng)域有很多前所未有的表現(xiàn)：例如，圖像分類、臉部識別、玩雅特麗游戲等。他們使用很多層神經(jīng)元，每個被安排在交疊的區(qū)塊（Tiles）中來構(gòu)建越來越抽象和本地化的圖片表示。我們在圍棋游戲中采用了一個相似的構(gòu)架。我們用19X19的圖像來傳遞棋盤位置，使用卷積層來構(gòu)建位置的表示。我們使用這些神經(jīng)網(wǎng)絡(luò)來減少搜索樹的有效深度和寬度（breadth）：使用一個Value Networks（價值網(wǎng)絡(luò)）來估算位置，使用Policy Network（策略網(wǎng)絡(luò)）來對動作進(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ì)量的梯度和即時反饋。與之前的工作相似，我們也訓(xùn)練了一個快速策略網(wǎng)絡(luò)pπ，它可以快速地在模擬中對動作進(jìn)行抽樣。接下來，我們訓(xùn)練了強(qiáng)化學(xué)習(xí)（RL）策略網(wǎng)絡(luò)pρ，這個網(wǎng)絡(luò)通過優(yōu)化“自己對抗自己”的最終結(jié)果來改善監(jiān)督學(xué)習(xí)策略網(wǎng)絡(luò)。這將策略調(diào)整到贏棋這一正確目標(biāo)上，而非讓預(yù)測精確率最大。最后，我們訓(xùn)練了價值網(wǎng)絡(luò)vθ，它可以預(yù)測出RL策略網(wǎng)絡(luò)通過模擬“自己對抗自己”而得出的策略中哪種是最佳策略。我們的程序AlphaGo高效地結(jié)合將策略和價值網(wǎng)絡(luò)與蒙特卡洛樹搜索結(jié)合起來。
為了評估AlphaGo，我們在諸多AlphaGo變體和一些其他圍棋程序中進(jìn)行了內(nèi)部比賽，這其中包括了最強(qiáng)大的商業(yè)程序Crazy Stone和Zen，還有最大的開源程序Pachi和Fuego。所有這些程序都是基于高性能MCTS算法。此外，比賽也包含了開源程序GnuGo，這個程序使用了在MCTS之前出現(xiàn)的最先進(jìn)的方法。規(guī)定所有程序每次落子有5秒的計算時間。
比賽的結(jié)果表明單機(jī)AlphaGo領(lǐng)先任何之前的圍棋程序很多段位，取得了495局比賽中494次勝利的成績（99.8%）。為了給AlphaGo提出更大的挑戰(zhàn)，我們也讓AlphaGo讓四子（讓子，即對手自由落子）來比賽；AlphaGo讓子競賽中對陣Crazy Stone、Zen和Pachi時分別取得了77%、86%和99%的成績。分布式AlphaGo明顯更強(qiáng)大，對陣單機(jī)AlphaGo取得77%的成績，完勝其他程序。
詳解：AlphaGo 如何在對弈中選擇步法
黑色棋子代表AlphaGo正處于下棋狀態(tài)，對于下面的每一個統(tǒng)計，橙色圓圈代表的是最大值所處的位置。
紅色圓圈表示AlphaGo選擇的步法；白方格表示樊麾作出的回應(yīng)；樊麾賽后評論說：他特別欣賞AlphaGo預(yù)測的（標(biāo)記為1）的步法。
AlphaGo與樊麾的比賽結(jié)果
以編號形式展示了AlphaGo和樊麾進(jìn)行圍棋比賽時各自的落子順序。棋盤下方成對放置的棋子表示了相同交叉點處的重復(fù)落子。每對中的第一個棋子上的數(shù)字表示了何時發(fā)生重復(fù)落子，而落子位置由第二個棋子上的數(shù)字決定。（見補(bǔ)充信息 Supplementary Information）
第一盤：AlphaGo 以 2 目半獲勝
第二盤：AlphaGo 中盤勝
第三盤：AlphaGo 中盤勝
第四盤：AlphaGo 中盤勝
第五盤：AlphaGo 中盤勝
最終，我們評估了分布式AlphaGo與樊麾的比賽，他是專業(yè)2段位選手，2013、14和15年歐洲圍棋賽冠軍。在2015年10月5日到9日，AlphaGo和樊麾正式比賽了5局。AlphaGo全部獲勝。這是第一次一個電腦圍棋程序，在沒有讓子、全尺寸（19X19）的情況下?lián)魯∪祟悓I(yè)選手，這一成果過去認(rèn)為至少需要 10 年才能實現(xiàn)。
在我們的工作中，我們開發(fā)了圍棋程序，它將深度神經(jīng)網(wǎng)絡(luò)和樹搜索結(jié)合起來。這個程序可以達(dá)到最強(qiáng)的人類選手的表現(xiàn)，因此完成了一個人工智能“偉大挑戰(zhàn)”。我們也為圍棋首創(chuàng)了高效步法選擇和位置評估函數(shù)，這是通過具有創(chuàng)新性地將監(jiān)督和強(qiáng)化學(xué)習(xí)兩種方法結(jié)合起來從而訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)。我們也引入了一個新搜索算法，這一算法成功的整合了神經(jīng)網(wǎng)絡(luò)評估和蒙特卡洛樹模擬算法。我們的程序AlphaGo在高性能樹搜索引擎中從一定規(guī)模上將這些成分整合在一起。
在和樊麾的比賽中，AlphaGo在評估位置方面要比深藍(lán)與Kasparov4比賽時所評估的位置少幾千倍，這是由于我們使用了策略網(wǎng)絡(luò)更智能地選擇那些位置，還使用了價值網(wǎng)絡(luò)更精確地評估它們，而價值網(wǎng)絡(luò)更接近人類的下棋方式。另外，深藍(lán)依靠手工設(shè)計評估方程，而AlphaGo的神經(jīng)網(wǎng)絡(luò)是直接通過純比賽數(shù)據(jù)訓(xùn)練，也使用了通用監(jiān)督和強(qiáng)化學(xué)習(xí)方法。
圍棋代表了很多人工智能所面臨的困難：具有挑戰(zhàn)性的決策制定任務(wù)、難以破解的查找空間問題和優(yōu)化解決方案如此復(fù)雜以至于用一個策略或價值函數(shù)幾乎無法直接得出。之前在電腦圍棋方面的主要突破是引入MCTS，這導(dǎo)致了很多其他領(lǐng)域的相應(yīng)進(jìn)步：例如，通用博弈，經(jīng)典的計劃問題，計劃只有部分可觀測問題、日程安排問題和約束滿足問題。通過將策略和價值網(wǎng)絡(luò)與樹搜索結(jié)合起來，AlphaGo終于達(dá)到了專業(yè)圍棋水準(zhǔn)，讓我們看到了希望：在其他看起來無法完成的領(lǐng)域中，AI也可以達(dá)到人類級別的表現(xiàn)。
我認(rèn)為AI技術(shù)征服人類不需要太長時間，可能就發(fā)生在今年，AI技術(shù)征服人類。
——微軟亞洲工程院院長劉震
I thought AI won't beat human in Go for a long time... It may be this year! Google's AlphaGo beats European professional champion 5:0; next on deck: 李世石九段 in March for $1M Google prize.
——陳雷，萬同科技CEO，留德MBA，連續(xù)創(chuàng)業(yè)者，現(xiàn)致力于人工智能+圍棋的互聯(lián)網(wǎng)服務(wù)，圍棋網(wǎng)絡(luò)9段
對于人而言，圍棋競技是智力、心理和靈性三個維度的綜合比拼。根據(jù)Deep Mind現(xiàn)有的計算機(jī)圍棋解決方案描述，可以判斷程序在智力維度取得了很大的進(jìn)展。在智力方面，計算機(jī)圍棋研究領(lǐng)域中要解決的核心問題是如何對盤面做形勢判斷，即專家評估系統(tǒng)的解決方案，專家評估系統(tǒng)能力的顯著提高會導(dǎo)致圍棋AI水準(zhǔn)的本質(zhì)提升。Deep Mind的計算機(jī)圍棋解決方案其實可歸結(jié)為精確的專家評估系統(tǒng)（value network）、基于海量數(shù)據(jù)的深度神經(jīng)網(wǎng)絡(luò)（policy network），及傳統(tǒng)的人工智能方法蒙特卡洛樹搜索的組合。有理由相信這個程序已經(jīng)達(dá)到與標(biāo)準(zhǔn)業(yè)余6段棋手或中國職業(yè)棋手等級分200位之后的棋手實力相當(dāng)?shù)牡夭健慕?jīng)驗上看，由于缺少心理和靈性維度的突破，AlphaGo戰(zhàn)勝人類最頂尖的圍棋高手尚需時日。
Google DeepMind 是一家英國人工智能公司，創(chuàng)立于2010年，名為DeepMind Technologies，2014年被谷歌收購，更名為Google DeepMind。
這家公司由Demis Hassabis、Shane Legg和Mustafa Suleyman創(chuàng)立。公司目標(biāo)是“解決智能”，他們嘗試通過合并機(jī)器學(xué)習(xí)最好的方法和系統(tǒng)神經(jīng)科學(xué)來構(gòu)建強(qiáng)大的通用學(xué)習(xí)算法。他們試圖形式化智能，進(jìn)而不僅在機(jī)器上實現(xiàn)它，還要理解人類大腦。當(dāng)前公司的焦點在于研究能玩游戲的電腦系統(tǒng)，研究的游戲范圍很廣，從策略型游戲圍棋到電玩游戲。
創(chuàng)始人介紹
Demis Hassabis，人工智能研究人員，神經(jīng)科學(xué)家，電腦游戲設(shè)計者，畢業(yè)于劍橋大學(xué)，并在倫敦大學(xué)獲得PhD，研究興趣：機(jī)器學(xué)習(xí)、神經(jīng)科學(xué)。
Shane Legg，計算學(xué)習(xí)研究人員，DeepMind創(chuàng)始人，研究興趣：人工智能、神經(jīng)網(wǎng)絡(luò)、人工進(jìn)化、強(qiáng)化學(xué)習(xí)和學(xué)習(xí)理論。
Mustafa Suleyman，英國企業(yè)家，DeepMind Technologies的共同創(chuàng)始人和產(chǎn)品運(yùn)營主管，同時也是Reos Partners的共同創(chuàng)始人，被谷歌收購后，他成為Google DeepMind的應(yīng)用AI部門主管。
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
專題
