編者按：本文由新智元原創(chuàng)翻譯自Nature。如果覺得此文深?yuàn)W，關(guān)于機(jī)器學(xué)習(xí)，還可看雷鋒網(wǎng)早期文章：《機(jī)器自學(xué)72小時(shí)堪比國際大師，深度學(xué)習(xí)到底有多厲害？》

圍棋一直被視為人工智能最難破解的游戲。就在今天，《Nature》雜志以封面論文的形式，介紹了 Google DeepMind 開發(fā)的人工智能程序 AlphaGo，它擊敗了歐洲圍棋冠軍樊麾，并將在 3 月和世界冠軍李世乭對(duì)戰(zhàn)！Google 特地為此準(zhǔn)備了 100 萬美元獎(jiǎng)金。

從國際象棋的經(jīng)驗(yàn)看，1997 年人工智能第一次打敗人類后，2006 年成為了人類在國際象棋的絕唱，自此之后人類沒有戰(zhàn)勝過最頂尖的人工智能國際象棋選手。在 AlphaGo 打敗了歐洲圍棋冠軍后，世界冠軍李世乭和 AlphaGo 的對(duì)弈，是否會(huì)成為人類在圍棋領(lǐng)域的絕唱？

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 評(píng)估棋盤位置，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é)合起來。

通過這種搜索算法，AlphaGo 在和其他圍棋程序比賽的勝率達(dá)到了 99.8%，并以 5：0 的比分擊敗了人類歐洲圍棋冠軍樊麾。這是電腦程序第一次在全尺寸（19X19）的棋盤上擊敗了人類專業(yè)選手，這一成果過去認(rèn)為至少需要 10 年才能實(shí)現(xiàn)。

歐洲圍棋冠軍樊麾：2005 年樊麾被正式聘任為法國圍棋隊(duì)和少年圍棋隊(duì)的總教練，那一年的他才 24 歲。他是 2013、2014 和 2015 歐洲圍棋賽冠軍。

通過將 Value Networks、Policy Networks 與樹搜索結(jié)合起來，AlphaGo 達(dá)到了專業(yè)圍棋水準(zhǔn)，讓我們看到了希望：在其他看起來無法完成的領(lǐng)域中，AI 也可以達(dá)到人類級(jí)別的表現(xiàn)！

關(guān)于DeepMind 團(tuán)隊(duì)對(duì)圍棋項(xiàng)目的介紹，可進(jìn)入新智元查看。

| 論文簡(jiǎn)介

所有完全信息（perfect information）博弈都有一個(gè)最優(yōu)值函數(shù)（optimal value function），它決定了在所有參與博弈的玩家都做出了完美表現(xiàn)的情況下，博弈的結(jié)果是什么：無論你在棋盤的哪個(gè)位置落子（或者說是狀態(tài)s）。

這些博弈游戲是可能通過在含有大約個(gè)b^d可能行動(dòng)序列（其中b是博弈的寬度，也就是在每個(gè)位置能夠移動(dòng)的步數(shù)，而d是博弈的深度）的搜索樹（search tree）上反復(fù)計(jì)算最優(yōu)值函數(shù)來解決的。在象棋（b≈35，d≈80）和圍棋之類（b≈250，d≈150）的大型博弈游戲中，窮盡地搜索是不合適的，但是有效搜索空間是可以通過2種普遍規(guī)則得到降低的。

首先，搜索的深度可能通過位置估計(jì)（position evaluation）來降低：在狀態(tài)s時(shí)截取搜索樹，將隨后的子樹部分（subtree）替換為根據(jù)狀態(tài)s來預(yù)測(cè)結(jié)果的近似的值函數(shù)v(s)≈v*(s)。這種方法使程序在象棋、跳棋、翻轉(zhuǎn)棋（Othello）的游戲中表現(xiàn)超越了人類，但人們認(rèn)為它無法應(yīng)用于圍棋，因?yàn)閲鍢O其復(fù)雜。

其次，搜索的寬度可能通過從策略概率p(a| s)——一種在位置s時(shí)表示出所有可能的行動(dòng)的概率分布——中抽樣行動(dòng)來降低。比如，蒙特卡洛法通過從策略概率p中為博弈游戲雙方抽樣長(zhǎng)序列的行動(dòng)來讓搜索達(dá)到深度的極限、沒有任何分支樹。將這些模擬結(jié)果進(jìn)行平均，能夠提供有效的位置估計(jì)，讓程序在西洋雙陸棋（backgammon）和拼字棋（Scrabble）的游戲中展現(xiàn)出超越人類的表現(xiàn)，在圍棋方面也能達(dá)到低級(jí)業(yè)余愛好者水平。

圍棋為何如此復(fù)雜？

圍棋有3³⁶¹ 種局面，而可觀測(cè)到的宇宙，原子數(shù)量才10⁸⁰。

圍棋難的地方在于它的估值函數(shù)非常不平滑，差一個(gè)子盤面就可能天翻地覆，同時(shí)狀態(tài)空間大，也沒有全局的結(jié)構(gòu)。這兩點(diǎn)加起來，迫使目前計(jì)算機(jī)只能用窮舉法并且因此進(jìn)展緩慢。

但人能下得好，能在幾百個(gè)選擇中知道哪幾個(gè)位置值得考慮，說明它的估值函數(shù)是有規(guī)律的。這些規(guī)律遠(yuǎn)遠(yuǎn)不是幾條簡(jiǎ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ù)測(cè)人類棋手行動(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)建越來越抽象和本地化的圖片表示。我們?cè)趪逵螒蛑胁捎昧艘粋€(gè)相似的構(gòu)架。我們用19X19的圖像來傳遞棋盤位置，使用卷積層來構(gòu)建位置的表示。我們使用這些神經(jīng)網(wǎng)絡(luò)來減少搜索樹的有效深度和寬度（breadth）：使用一個(gè)Value Networks（價(jià)值網(wǎng)絡(luò)）來估算位置，使用Policy Network（策略網(wǎng)絡(luò)）來對(duì)動(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π，它可以快速地在模擬中對(duì)動(dòng)作進(jìn)行抽樣。接下來，我們訓(xùn)練了強(qiáng)化學(xué)習(xí)（RL）策略網(wǎng)絡(luò)pρ，這個(gè)網(wǎng)絡(luò)通過優(yōu)化“自己對(duì)抗自己”的最終結(jié)果來改善監(jiān)督學(xué)習(xí)策略網(wǎng)絡(luò)。這將策略調(diào)整到贏棋這一正確目標(biāo)上，而非讓預(yù)測(cè)精確率最大。最后，我們訓(xùn)練了價(jià)值網(wǎng)絡(luò)vθ，它可以預(yù)測(cè)出RL策略網(wǎng)絡(luò)通過模擬“自己對(duì)抗自己”而得出的策略中哪種是最佳策略。我們的程序AlphaGo高效地結(jié)合將策略和價(jià)值網(wǎng)絡(luò)與蒙特卡洛樹搜索結(jié)合起來。

| 實(shí)現(xiàn)過程 

為了評(píng)估AlphaGo，我們?cè)谥T多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次勝利的成績(jī)（99.8%）。為了給AlphaGo提出更大的挑戰(zhàn)，我們也讓AlphaGo讓四子（讓子，即對(duì)手自由落子）來比賽；AlphaGo讓子競(jìng)賽中對(duì)陣Crazy Stone、Zen和Pachi時(shí)分別取得了77%、86%和99%的成績(jī)。分布式AlphaGo明顯更強(qiáng)大，對(duì)陣單機(jī)AlphaGo取得77%的成績(jī)，完勝其他程序。

• 詳解：AlphaGo 如何在對(duì)弈中選擇步法

黑色棋子代表AlphaGo正處于下棋狀態(tài)，對(duì)于下面的每一個(gè)統(tǒng)計(jì)，橙色圓圈代表的是最大值所處的位置。

紅色圓圈表示AlphaGo選擇的步法；白方格表示樊麾作出的回應(yīng)；樊麾賽后評(píng)論說：他特別欣賞AlphaGo預(yù)測(cè)的（標(biāo)記為1）的步法。

• AlphaGo與樊麾的比賽結(jié)果
  

以編號(hào)形式展示了AlphaGo和樊麾進(jìn)行圍棋比賽時(shí)各自的落子順序。棋盤下方成對(duì)放置的棋子表示了相同交叉點(diǎn)處的重復(fù)落子。每對(duì)中的第一個(gè)棋子上的數(shù)字表示了何時(shí)發(fā)生重復(fù)落子，而落子位置由第二個(gè)棋子上的數(shù)字決定。（見補(bǔ)充信息 Supplementary Information）

第一盤：AlphaGo 以 2 目半獲勝

第二盤：AlphaGo 中盤勝

第三盤：AlphaGo 中盤勝

第四盤：AlphaGo 中盤勝

第五盤：AlphaGo 中盤勝

最終，我們?cè)u(píng)估了分布式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)了高效步法選擇和位置評(píng)估函數(shù)，這是通過具有創(chuàng)新性地將監(jiān)督和強(qiáng)化學(xué)習(xí)兩種方法結(jié)合起來從而訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)。我們也引入了一個(gè)新搜索算法，這一算法成功的整合了神經(jīng)網(wǎng)絡(luò)評(píng)估和蒙特卡洛樹模擬算法。我們的程序AlphaGo在高性能樹搜索引擎中從一定規(guī)模上將這些成分整合在一起。

在和樊麾的比賽中，AlphaGo在評(píng)估位置方面要比深藍(lán)與Kasparov4比賽時(shí)所評(píng)估的位置少幾千倍，這是由于我們使用了策略網(wǎng)絡(luò)更智能地選擇那些位置，還使用了價(jià)值網(wǎng)絡(luò)更精確地評(píng)估它們，而價(jià)值網(wǎng)絡(luò)更接近人類的下棋方式。另外，深藍(lán)依靠手工設(shè)計(jì)評(píng)估方程，而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ì)劃只有部分可觀測(cè)問題、日程安排問題和約束滿足問題。通過將策略和價(jià)值網(wǎng)絡(luò)與樹搜索結(jié)合起來，AlphaGo終于達(dá)到了專業(yè)圍棋水準(zhǔn)，讓我們看到了希望：在其他看起來無法完成的領(lǐng)域中，AI也可以達(dá)到人類級(jí)別的表現(xiàn)。

| 新智元特約專家評(píng)論

我認(rèn)為AI技術(shù)征服人類不需要太長(zhǎng)時(shí)間，可能就發(fā)生在今年，AI技術(shù)征服人類。

——微軟亞洲工程院院長(zhǎng)劉震

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段

對(duì)于人而言，圍棋競(jìng)技是智力、心理和靈性三個(gè)維度的綜合比拼。根據(jù)Deep Mind現(xiàn)有的計(jì)算機(jī)圍棋解決方案描述，可以判斷程序在智力維度取得了很大的進(jìn)展。在智力方面，計(jì)算機(jī)圍棋研究領(lǐng)域中要解決的核心問題是如何對(duì)盤面做形勢(shì)判斷，即專家評(píng)估系統(tǒng)的解決方案，專家評(píng)估系統(tǒng)能力的顯著提高會(huì)導(dǎo)致圍棋AI水準(zhǔn)的本質(zhì)提升。Deep Mind的計(jì)算機(jī)圍棋解決方案其實(shí)可歸結(jié)為精確的專家評(píng)估系統(tǒng)（value network）、基于海量數(shù)據(jù)的深度神經(jīng)網(wǎng)絡(luò)（policy network），及傳統(tǒng)的人工智能方法蒙特卡洛樹搜索的組合。有理由相信這個(gè)程序已經(jīng)達(dá)到與標(biāo)準(zhǔn)業(yè)余6段棋手或中國職業(yè)棋手等級(jí)分200位之后的棋手實(shí)力相當(dāng)?shù)牡夭?。從?jīng)驗(yàn)上看，由于缺少心理和靈性維度的突破，AlphaGo戰(zhàn)勝人類最頂尖的圍棋高手尚需時(shí)日。

| 關(guān)于 Google DeepMind

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í)算法。他們?cè)噲D形式化智能，進(jìn)而不僅在機(jī)器上實(shí)現(xiàn)它，還要理解人類大腦。當(dāng)前公司的焦點(diǎn)在于研究能玩游戲的電腦系統(tǒng)，研究的游戲范圍很廣，從策略型游戲圍棋到電玩游戲。

創(chuàng)始人介紹

Demis Hassabis，人工智能研究人員，神經(jīng)科學(xué)家，電腦游戲設(shè)計(jì)者，畢業(yè)于劍橋大學(xué)，并在倫敦大學(xué)獲得PhD，研究興趣：機(jī)器學(xué)習(xí)、神經(jīng)科學(xué)。

Shane Legg，計(jì)算學(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)營主管，同時(shí)也是Reos Partners的共同創(chuàng)始人，被谷歌收購后，他成為Google DeepMind的應(yīng)用AI部門主管。

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。