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