雷鋒網按：騰訊圍棋 AI 程式“絕藝”（Fine Art）在世界電腦圍棋大賽 UEC 上力壓多支日韓參賽退伍獲得冠軍， 一時間又引發了大家對 AI 和圍棋的關注和討論。
其實， 自去年 3 月份 AlphaGo 戰勝李世石之後， 人們對會下圍棋的人工智慧程式已經不陌生了。 大部分人都知道 AlphaGo 是利用了一種名叫深度學習的技術， 然後基於互聯網棋譜大資料的支援， 每天自己跟自己對弈， 所以才能這麼厲害。
但鮮有人知道的是：在圍棋這種邏輯縝密的推理遊戲中， AI 究竟是怎麼“思考”每一步的落子的？AI 真的清楚自己每一步落子的意義麼？AI 真的具有推理能力？
為了徹底揭開其中的奧秘， 地平線大牛講堂邀請到 UEC 曾經的打入決賽的隊伍 —— Facebook 圍棋 AI 程式 DarkForest 的首席工程師及第一作者田淵棟博士為我們一探究竟， 本文由亞萌和奕欣整理， 並由田老師做了審核和編輯， 特此感謝。
嘉賓介紹
田淵棟， Facebook 人工智慧研究院研究員， Facebook 圍棋 AI 程式 DarkForest 首席工程師及第一作者， 卡耐基梅隆大學機器人研究所博士， 曾擔任 Google 無人駕駛團隊軟體工程師， 並獲得國際電腦視覺大會（ICCV）瑪律獎榮譽提名。
今天非常榮幸能來地平線科技做分享。 我將簡單介紹一下深度學習在遊戲領域的進展， 結合最近的一些熱點新聞， 比如說像CMU的Poker Player戰勝了世界上最強的撲克高手， 大家也一定很好奇這是怎麼回事， 當然也會結合我們目前所做的一些工作。
遊戲已經成為AI研究測試平臺
研究者可能以前會覺得遊戲只是消遣的工具， 但隨著人工智慧的發展以及它在遊戲上的一些應用， 大家也開始意識到， 遊戲現在已經演變為一種AI研究的工具， 遊戲可以作為一個平臺， 作為一個虛擬環境， 用於測試人工智慧的一些技術。
遊戲作為平臺有兩個好處。
其一是可以生成無限多的帶標注的資料以供神經網路訓練， 解決資料不足的問題；
其二是遊戲的環境是完全可控的， 難度可以調節， 重複性也非常完美。
這兩點讓它成為一個很好的研究平臺。 遊戲其實有很多種， 在這裡我們分為兩類， 即：
完全資訊博弈遊戲：所有玩家都知道發生了什麼事情；
不完全資訊博弈遊戲：玩家需要在環境中探索，
當然還有其它的一些分類， 在此不做贅述。
有些遊戲規則很簡單， 但實際玩起來的時候並沒有想像中的容易。 我舉一個非常簡單的例子：假設有三張牌JQK， 兩個人玩這個遊戲， 每個人各抽一張牌後， 可以根據牌的大小選擇放棄或是加注。 最後雙方亮牌比較大小。 大家可以猜下哪一手具有優勢？後手其實是有優勢的。 根據最優策略的指導， 先手有可能會輸掉1/18的錢， 因為先手不得不做一些決定， 而後手可以根據先手的決定來決定自己的策略。
如果我們把遊戲樹畫出來的話， 可以看到， 即使是這樣一個簡單的遊戲， 它可能有無窮多個納什均衡點。 所以你會發現一個很簡單很簡單的遊戲，
圍棋的規則非常簡單， 但我們可能要花一輩子的時間才能真正理解這個遊戲的內涵。 大家都知道AlphaGo的故事， 一年前我們見證了這場震驚世界的比賽。 一開始我們可能還認為AlphaGo可能不敵世界上最強的棋手， 但結果發現完全不是這麼回事。 通過這個事實， 我們就可以理解以下兩點：
遊戲能作為一個平臺， 對我們的演算法進行效果測試。
遊戲自身也是一個好的體驗平臺， 能夠檢驗我們的演算法。
比如說我們要花很長時間才能證明無人車的效果是否好， 目前來看， 不如做一個遊戲， 能夠打敗最強的棋手， 讓大家瞭解人工智慧的水準，
當然和圍棋相比， 遊戲《星際爭霸》要難得多。 其中有意思的一個地方在於， 它的每一個策略及動作的可選範圍非常大， 而且在很多地方屬於不完全資訊博弈， 你需要猜測對方在做什麼。 另外遊戲的時間非常長， 每一步的選擇非常多時， 就需要做更多更複雜的決策。
我對於遊戲的觀點是：遊戲最終會與現實接軌。 如果我們能將遊戲做得越來越好， 就能將遊戲模型通過某種方式轉換到現實世界中使用。 在我看來， 通過遊戲這條路， 是能夠讓人工智慧在現實世界中實現廣泛應用的。
Game AI是如何工作的？
首先我先簡單介紹一下Game AI是怎麼工作的。
大家可能覺得電腦非常強、無所不能， 但這是不對的， 因為就算電腦有超級超級強的計算能力， 也不可能窮盡所有的情況。
那麼電腦是怎麼做的呢？電腦其實是通過以下的方式來進行遊戲決策。
首先有一個當前狀態，從這個當前狀態出發，我們會做一些搜索。就像我剛才所說的，電腦不可能窮盡所有的決策情況，因此在某些節點時需要停下來計算一下當前的狀況，並用這個結論反過來指導最優的策略。現在基本上所有遊戲智慧都是這麼做的。
當然具體到遊戲裡就各有巧妙不同，主要根據不同的action數目，遊戲所採用的技術也不同。比如跳棋遊戲每步的決策比較少，國象稍微多一些，這樣我們可以用傳統的Alpha-Beta Pruning再加逐步加深的搜索法。在這個辦法裡面，每一次向下搜索，是要考慮到所有的決策的。這是很多國際象棋AI採用的方法，這個方法因為是深度優先搜索，記憶體佔用很小。
但是同樣的辦法不能用在圍棋上，因為每一步的可能選擇太多。所以後來採用了蒙特卡洛樹搜索，這個方法其實在十幾年前才第一次被用在圍棋上，在用了這個方法之後，圍棋的棋藝也提高了很多。在此之前人類學習半年就可以戰勝它。而在深度學習出現之前，這一數字延長到了幾年時間，當然現在你基本上學一輩子也幹不掉了。而像《星際爭霸》這種比較開放的問題，根據你盤面上的各種單位的數目和種類，可能每一步都有指數級的可選行為，現在就沒有人知道怎麼做，如果要從搜索下手的話，第一步都跨不出來。
第二部分估值函數（就是對盤面的估計）也有很多可以討論的地方，比如這裡主要的問題是“這遊戲到底有多難？”，如果這遊戲搜索的深度很淺的話，也許我們可以倒過來做，用一種叫End-game database（殘局庫）的辦法。比如像國際象棋，如果棋盤上只有兩個子或者三個子，那麼它的所有可能位置都能夠窮盡出來，然後反向建立一個資料庫，資料庫會告訴你，如果處於某個局面，下一步該怎麼下，子數少的時候，這完全是可以搜索出來的。這個條件是樹要淺，每一步的可能性要少，深的話就很難做。
另一個盤面估計的方法是人工去設計一些特徵，把這個棋局局面拿過來之後，把這些特徵的值算出來，再加以線性組合得到一個估值。這樣的好處是速度很快，給一個局面可以用微秒級的速度得到結果，但就需要人類去甄別什麼樣的特徵是重要的、什麼樣的特徵是不重要的，這個就是傳統的辦法。
當然，還有在深度學習出現之前圍棋AI裡面用的方法，從當前局面開始通過隨機走子到達一個容易評分的狀態，然後根據得到的結果反過來推剛才的局面是會贏還是會輸。最後現在出現了深度學習的方法，我把關鍵局面輸進神經網路裡去，輸出的結果就是當前局面的分數。
接下來我們講得更細一點。
像國際象棋（中國象棋也差不多）。這兩個遊戲的特點是，它們戰術很多，你可能會挖很深，這個局面可能走了10步、20步，就可以把它將死。這樣的話，靠人去算就會發現總有方法算出所有情況。
這種情況下搜索是很重要的，但對局面的評判沒那麼難，因為對象棋來說，少個馬或者多個車，都會知道你是不是快輸了，或者是不是處於劣勢。雖然評估不是特別難，但對搜索的要求很高，以下有幾種方法可以加速它的搜索。比如 Alpha-beta Pruning（剪枝演算法）、iterative Deepening 和 Transition Table。
我在這簡單介紹下 Alpha-beta Pruning。假設玩家需要對下一步做出判斷，需要搜索它的特徵，一旦發現對方在某一分支有很好的應招，那麼這條路就不用再搜索了，因為對方這個應招會讓你這個分支的最優解劣於另一個分支的最差解。這就是它的一個簡單思想概括。
這樣的搜索是深度優先，所以不需要把之前的動作都保留下來，只要保留從根到葉子節點的搜索棧就可以了。需要從左邊開始搜，搜到最下面到某個固定的深度之後返回。所以要先定好深度，不能搜無限深，否則第一個分支都出不來。注意在使用時，搜索的深度也不是完全固定的，有時候要多往下走幾步。比如說算到這一步看起來很好，我用皇后吃你個車，我多個車特別開心，但再往下算發現自己的皇后被人吃回去了，這個叫作Horizon Effects，需要很多特別的處理步驟。因為存在這個問題，所以要先搜到一些比較好的策略，再一點一點加深 。
圍棋是另外一種思路，它特點是不一樣的：
首先，它的每一步的可能性比較多；
第二，它的路徑比較難做。在座如果有對圍棋有興趣可能會知道，圍棋少個子、多個子，就會對整個局面有天翻地覆的變化，完全不能以子數或者位置作為評判輸贏的標準。
我先介紹一下AlphaGo是怎麼做的，之後說一下我們是怎麼做的。
大家知道，AlphaGo用的神經網路分為策略網路和值網路，主要能實現以下功能：
給出一個局面後，可以決定下哪些位置；
給出一個關鍵局面時，判斷它們的值，到底是白優還是黑優。
AlphaGo首先用了很多的電腦資源，採用了上萬塊GPU進行訓練，甚至採用像TPU這樣的硬體進行處理，所以計算資源是非常多非常厲害的。
具體到細節上來說，分為以下幾個部分：
Policy network，決定下一步怎麼走；
Value network，決定這個局面分數是多少。
中間還有一部分是High quality playout/rollout policy，是在前兩者返回結果速度較慢的時候，在微秒級可以先得到結果。就是說我如果用微秒級的快速走子預測下一步，它的準確率是24.2%，但後來我自己做實驗發現可以做到30%多些。
AlphaGo的訓練分為以下幾個部分：
第一部分，通過人類遊戲先去訓練一個神經網路下棋，不然對於神經網路來說每個步驟要往怎麼下子都不知道，如果你隨便搜，很多東西都搜不到，所以需要人類棋譜先進行訓練。這其實是圍棋革命的開始，可以訓練出很好的結果。
這張圖上有一些trade off，雖然訓練的第一步走子準確率比較高，但訓練出來的網路可能前饋速度比較慢。所以最後取了折衷原則，灰色的那行就是最後採用的網路（至少是在AlphaGo這篇文章發佈的時候），所以可以發現時間是比較快的，4.8毫秒就可以往前算一步。
這裡就可以發現遊戲AI的指標是比較綜合性的，不僅包括一步預測的準確度，還包括每秒能跑多少次，這樣樹會很深，棋力就會變強，一定程度上也是提高棋力的一種方法。
AlphaGo快速走子（Fast Rollout）可以做到2微秒，同時也有比較好的精確度。
如果從開始預測遊戲最後的結果，那就是瞎猜50%的正確率。但在遊戲進行一陣之後再預測的時候，正確率就會提高。我希望這個下降的速度越快越好，比如在下到40手或45手的時候就知道遊戲結局是什麼。所以，這條線下降得越快，結果應該越好。我們這裡看 Fast Rollout 這條虛的藍線，效果當然沒有用神經網路來得好，但是它兼顧了速度和準確率，下降的速度也是比較快的。
AlphaGo用的另一個主要的技術是蒙特卡羅樹搜索。這其實是個標準的方法，大家可以在任何一本教科書上找到怎麼做。它的中心思想是，在每個樹節點上存有目前的累計勝率，每次採樣時優先選勝率高的結點，一直探索到葉節點，然後用某種盤面估計的方法得到勝負的結果，最後回溯剛才探索的過程，反過來更新路徑上節點的勝率。這樣的話，下次探索的時候，如果發現這條路線的勝率變高了，下次更有可能往這上面走。
所以它與Alpha-beta Pruning不一樣的地方是，沒有界定它的深度是多少，就從0開始，讓它自動生長，長出來後我們會發現很多路線是不會搜索的，可能往下走幾步就不走了，因為它發現這幾步非常糟糕，就不會走下去；而有些招法非常有意思，就會挖得非常深，在某些特定招法下可能往下挖五六十步，都是有可能的。最後演算法會選探索次數最多的節點作為下一步的棋。
這是蒙特卡羅樹搜索比較有意思的地方，它比較靈活，不像國際象棋，後者每次打開樹的時候，要保證所有下一步的招法都要考慮到；而蒙特卡羅樹搜索不需要，有些招不會搜索到。反過來說，它也有可能漏掉一些好棋，這樣就需要好的策略函數來協同。
接下來我介紹一下值網路（Value Network），AlphaGo稱是用了3000多萬場次左右互搏的遊戲訓練出來的，左右互搏是怎麼生成的呢？這是我早上畫的一張圖，解釋了系統是如何收集資料的：
遊戲開始，我們先讓演算法自動走，走的時候是去採樣通過監督學習學得的策略網路（SL network）。
走到某一步的時候，我們隨便走一步，感覺好象我要故意輸的樣子，這樣的好處是讓棋局更加多樣化（diverse），讓演算法看到完全不一樣的棋局，擴大它的適用面。
隨機走那一步之後，得到了當前棋局，然後用更準確的通過強化學習增強的策略網路（RL network）去計算之後的應對，得到最後的輸贏。這樣就得到了當前狀態到輸贏之間的一個樣本點，用這些樣本點去訓練策略網路。
然後你會發現，AlphaGo的能力變得很強，這個圖表最右欄有個叫ELO Ranking的東西（雷鋒網按：Elo Ranking是一種用於計算對抗比賽中對手雙方技能水準的方法，由Arpad Elo創建），這決定了圍棋的棋藝有多強。右邊本來是2400，現在變成快2900，中間差了500分，500分基本上相當於兩個子的差距。本來是業餘高段的水準，現在變成了職業初段的水準。當然，現在應該要比以前牛很多很多，我這裡講的只是公開出來的一些例子。
騰訊“絕藝”
最近“絕藝”打UEC杯，還贏了冠軍，我相信很多人都對此感興趣。我們去年也參加了拿了第二名。當然，今年的水準高出去年非常多。我不知道他們是怎麼做的，文章也沒有發出來，所以也不是特別清楚，但是我相信他們應該達到了AlphaGO 發文章時候的水準。之後AlphaGO又做了很多改進，變成了Master，但那些改進到最近都沒發出來，這部分還是未知的。
去年8月份我去美國圍棋大會（US Go Congress），見到了Aja Huang和Fan Hui，就問他們AlphaGO現在做的怎麼樣？他們沒有透露，但是從言語中我感覺到之前Nature上發的那篇文章，其實是有瓶頸的，就是說沿著這條路走下去，可能不一定能做的非常好。所以，他們如果是要再往上走，比如走到Master這個層面，需要用一些其它的方法，要有更進一步的創新。像我是聽說他們最近把訓練好的值網路單獨拿出來，根據它再從頭訓練一個策略網路。我覺得這樣做的好處是會發現一些看起來很怪但其實是好棋的招法，畢竟人類千百年下棋的師承形成了思維定式，有些棋在任何時候都不會走，所以按照人類棋譜訓練出來的策略網路終究會有局限性；而從頭訓練一個策略網路的話，則會發現很多新招。
當然，我不知道現在騰訊是不是有特別好的新想法出來，或者用了更大量的對局資料。不過看他們跟Zen對弈的棋局，我稍微點了一下步數，大概200步不到就可以讓Zen認輸，所以還是非常厲害的。
德州撲克
接下來我們講一下德州撲克。首先我們要確認，這是“一對一無限注德州撲克”遊戲（Heads-up no-limit Texas Hold'em）。“一對一”意思就是我和你兩個人的零和遊戲，我輸錢你贏錢、我贏錢你輸錢，並不是很多人在一張牌桌上有人當莊家的那種。多人遊戲要難很多，主要是現在用的辦法在多人遊戲下不能保證效果，然後狀態空間也變大很多。
“無限注”就是你每次下注的時候不一定是之前的整數倍，可以是任意數。那麼有限注德撲就是每次下注的時候，是成倍數地下，“有限注”的問題已經在兩三年以前就解決了，當時是發了一篇Science文章。那篇文章其實本應該會跟AlphaGO一樣受到很大矚目，但是不知道為什麼，當時並沒有。
有兩個很牛的撲克AI，這兩個都是用的同樣的框架，叫作Counterfactual Regret Minimization（CFR），簡言之是把遊戲中遇到的可觀測狀態（叫作資訊集Information Set）都羅列出來，然後對於每個可觀測狀態，通過最小化最大悔恨值的辦法，找到對應的策略。然後反復反覆運算。
一個是CMU的Libratus，它打了20天的比賽，贏了4個最牛的撲克玩家。（雷鋒網按：在2017年1月，Libratus玩了12萬手一對一不限注的德州撲克。到比賽結束時，人工智慧領先人類選手共約177萬美元的籌碼。）
另外一個叫DeepStack（雷鋒網按：加拿大阿爾伯塔大學、捷克布拉格查理大學和捷克理工大學訓練的AI系統與11位元職業撲克手進行了3000場無限注德州撲克比賽，勝率高達10/11），他們在網上也打過一些大型職業比賽。
CMU Poker bot
CMU Poker bot沒有用深度學習。他們用到了End-game solver，因為德撲一局時間比較短，可能就幾個回合就結束了，所以你可以從下往上構建遊戲樹。這樣的好處是，最下面節點遊戲樹的狀態是比較容易算出來的，用這個反過來指導設計上面的遊戲樹。另外他也用了蒙特卡羅方法，標準的CFR在每次反覆運算的時候，要把整個遊戲樹都搜一遍，這個對於稍微複雜一點的遊戲來說是不可接受的，因為是指數級的複雜度，所以用蒙特卡羅方法，每次選一些節點去更新它上面的策略。還有一點就是，一般來說我們在做遊戲的時候往往會想到怎麼去利用對方的弱點，但其實不是這樣的。更好的方法是，我儘量讓別人發現我的弱點，然後據此我可以去改進它，變得越來越強。用術語來講，就是去算一下對手的最優應對（Best response），讓對手來利用你的弱點，然後用這個反過來提高自己的水準。
阿爾伯塔大學的DeepStack
我們看到DeepStack的基本流程是AlphaGo和國象的某種混合版本，即有限深度的搜索，加上用值網路估值。具體來說，從當前狀態出發向前看三四層的子樹，在最底一層用值網路估算一下值（誰好誰壞），然後用通常的CFR去求解這棵子樹的的最優策略。對於值網路來說，每個人有兩張手牌，52選2，就有1326種情況，但每種情況都有概率，以這個作為輸入。輸入同時也包括當時的籌碼數和公共牌。輸出的是在每種手牌情況下，估計的值函數（counterfactual value）會是多少。
深度學習在遊戲AI中的角色
之前說了各種各樣的遊戲AI，為什麼Deep Learning 在其中扮演重要的角色呢？
遊戲AI裡需要解決的一個核心問題就是，給策略函數和值函數建模。那傳統的方法存在兩個缺陷，一個是傳統方法需要很多手動步驟把一個大問題分解成子問題，然後把每個子問題單獨建模，這個造成工作量很大；還有一個問題就是手調的參數太多，以前的遊戲AI就是這樣，每個參數都要調，人力是要窮盡的，這也是個缺陷；最後就是寫遊戲AI的人需要真的精通這個遊戲。比如說寫圍棋AI，作者得要有棋力，然後把棋力變成一條條規則放進去。那現在我們用深度學習的方法，就會發現能夠很大程度上解決這些問題，而且效果還好很多，像我圍棋水準很爛也沒有關係。這也是它為什麼那麼火的原因。
DarkForest
接下來我介紹一下我們的圍棋AI，DarkForest。當時我們在AlphaGo出來的3個月前（2015年11月），就發了一篇文章，並且公佈了在KGS（一個國外的圍棋平臺）上的對局統計。當時很多人跑過來說這個很有意思，也有一些媒體報導。這個想法其實很簡單，就是我們設計一個神經網路，輸入當前局面，希望預測一步甚至三步的落子，通過這種方式提高性能。DarkForest當時在沒有搜索的時候，在KGS上能夠做到業餘三段的水準，這在當時是非常有意思的結果。當然現在隨便一個本科生都可以訓練出來了。
這是一些分析，左邊是一些特徵，右邊是通過訓練的時候，發現三步比一步要穩定，效果也要好一點。
當時我和我的實習生去參加第九屆UEC的比賽，我們從DCNN裡拿出來前3或前5步使用，每一步做蒙特卡洛樹搜索了75000次，達到了業餘五六段的水準，拿了第二名。之後我們就把代碼都放在網上，大家都可以用，都是開源的。當然，我們在圍棋上的投入還是比較少的。
DarkForest也可以拿來分析AlphaGO和李世石的對弈。可以發現勝率會有變化。第一局102手，AlphaGO的打入，當時討論這是不是一個勝負關鍵點，至少會認為在那個點認為有點意思。我們也拿來分析一下，最近Master下的兩局，也可以看到勝率的變化情況。
最近，我們也用了比較相似的框架做了First Person Shooter Game，當時做的是Doom，這是比較復古的一個遊戲。就是在一個虛擬環境裡用上下左右鍵操縱，然後看到敵人就開槍，最後看分數是多少。
我們在這個工作中用了Actor-Critic模型，不僅輸出策略函數還輸出值函數，兩個函數是共用大量參數的。 這個模型我這裡就講一些直觀上的理解。
首先，這個模型在訓練時，會獎勵那些導致超越目前期望分數的行為。也就是說，我們對每個狀態的值有一個估計，在做完了某個動作（或者一連串動作）之後，如果新狀態的綜合獎勵值高於由值函數算出的預期，我們就可以更多地鼓勵它做這個動作。
其次，我們希望值函數的估計越來越准。值函數一開始是隨機的，這樣就連帶拖慢了整個演算法的收斂速度。在訓練時，我們可以用探索得來的綜合獎勵值去更新估計值。這樣反復反覆運算，時間長了以後會反覆運算到真實的值。
另一個要求是增加多樣性，我們希望輸出的行動不要太集中在一個動作上，不然你會發現訓練一陣之後AI變得很機械，只會做固定的動作，或者卡死在一些地方（比如說卡在角落裡轉不出來）。這個通過加一個最大熵的能量項來實現。
這是一方面，算是目前比較標準的強化學習的步驟。這篇文章的創新點是我們加了一個“課程學習”（ Curriculum Training）的過程，因為遊戲裡地圖比較複雜，需要讓它先從簡單地圖學會基本操作（開槍、上子彈等），有了這些基本操作再把這個AI放到比較複雜的環境裡再訓練。
像這個就是我們設計的簡單地圖。在這個地圖裡我們有8個不同的場景，每個場景裡的敵人都不一樣。第一個場景裡敵人動作都非常慢，血也很少，可能一槍就打死了；第二個場景可能敵人行動快一些，難度大些，開始用火箭彈而不是用手槍來對付你。通過這種方法會把bot一點點慢慢訓練出來，然後一點點讓AI變得越來越強。
我們參加了VizDoom AI Competition，這個是機機對戰。我們拿了第一個Track的第一名。我們發現最後得分比其它參賽者的高很多。網上有一些視頻可以看一下，視頻裡比較有意思，就是我們這個AI的動作比較堅決，擊中和移動速度都比較靈活，打別的人時候，自己還會主動躲閃其它人射來的火箭彈。
除了機機對戰，他們還做了一個比賽，讓所有BOT跟一個比較厲害的人類打，很有意思。我們的BOT有30秒鐘的分數超過人的水準，不過後來就不行了。你們會發現，機器和人會有不同的行為，因為人的反應速度不會特別快，但人有一些長期的計畫，他會知道什麼是你的弱點然後去利用它。但BOT在比賽的時候，並不具備學習的能力，所以它們都有恒定的行為模式。像有些BOT一直在轉圈子，有些BOT在原地不動，還有些BOT（比如說第二名）就一邊蹲著一邊打人，沒人打得到它。
這是一些分析，可以看到什麼樣的場景下它的值函數最高和最低。上面一排是分數最高的，也就是子彈馬上就要打到對方了，我們的bot馬上要得分，這個可以說是它最得意的時候；下面一排是分數最低的，也就是我給對方一槍，對方沒死，但此刻我自己也沒有子彈了。
以上，我們可以總結成下面兩句關鍵點：
第一點，就是通過搜索來做出對將來的規劃和推理。
第二點，就是深度學習來做策略函數和值函數的逼近，是比較好的方法。
其實很單調，不是麼？接下來要做什麼？其實我們還有很多問題沒有辦法解決，這裡列了很小一部分。
在星際裡面，我們有指數級的行動可能，在這種情況下怎麼做決策？
如果你要用強化學習的方法來做，沒有激勵機制怎麼辦，這種情況下去訓練一個機器人，它不知道怎麼做才能提高自己的水準。但是人類似乎就可以找到自己的目標；
多個AI間如何溝通協作；
在虛擬環境中訓練出一個AI，要如何應用于現實生活；
我們訓練模型，一般需要大量的資料（數百萬級甚至上億），但是人類稍微在一個環境裡待一段時間就適應了，那麼我們如何讓機器也能做到這一點；
如何讓bot學會戰略性思考，分清戰略和戰術的區別。如何讓它的思考有層次性？
等等，還有很多問題等待我們去解決。
這就是我的發言，謝謝大家！
AI科技評論注：目前田淵棟老師的演講視頻已上傳到騰訊視頻，歡迎關注“AI科技評論”後回復“田淵棟演講”獲取視頻連結。
也不可能窮盡所有的情況。那麼電腦是怎麼做的呢？電腦其實是通過以下的方式來進行遊戲決策。
首先有一個當前狀態，從這個當前狀態出發，我們會做一些搜索。就像我剛才所說的，電腦不可能窮盡所有的決策情況，因此在某些節點時需要停下來計算一下當前的狀況，並用這個結論反過來指導最優的策略。現在基本上所有遊戲智慧都是這麼做的。
當然具體到遊戲裡就各有巧妙不同，主要根據不同的action數目，遊戲所採用的技術也不同。比如跳棋遊戲每步的決策比較少，國象稍微多一些，這樣我們可以用傳統的Alpha-Beta Pruning再加逐步加深的搜索法。在這個辦法裡面，每一次向下搜索，是要考慮到所有的決策的。這是很多國際象棋AI採用的方法，這個方法因為是深度優先搜索，記憶體佔用很小。
但是同樣的辦法不能用在圍棋上，因為每一步的可能選擇太多。所以後來採用了蒙特卡洛樹搜索，這個方法其實在十幾年前才第一次被用在圍棋上，在用了這個方法之後，圍棋的棋藝也提高了很多。在此之前人類學習半年就可以戰勝它。而在深度學習出現之前，這一數字延長到了幾年時間，當然現在你基本上學一輩子也幹不掉了。而像《星際爭霸》這種比較開放的問題，根據你盤面上的各種單位的數目和種類，可能每一步都有指數級的可選行為，現在就沒有人知道怎麼做，如果要從搜索下手的話，第一步都跨不出來。
第二部分估值函數（就是對盤面的估計）也有很多可以討論的地方，比如這裡主要的問題是“這遊戲到底有多難？”，如果這遊戲搜索的深度很淺的話，也許我們可以倒過來做，用一種叫End-game database（殘局庫）的辦法。比如像國際象棋，如果棋盤上只有兩個子或者三個子，那麼它的所有可能位置都能夠窮盡出來，然後反向建立一個資料庫，資料庫會告訴你，如果處於某個局面，下一步該怎麼下，子數少的時候，這完全是可以搜索出來的。這個條件是樹要淺，每一步的可能性要少，深的話就很難做。
另一個盤面估計的方法是人工去設計一些特徵，把這個棋局局面拿過來之後，把這些特徵的值算出來，再加以線性組合得到一個估值。這樣的好處是速度很快，給一個局面可以用微秒級的速度得到結果，但就需要人類去甄別什麼樣的特徵是重要的、什麼樣的特徵是不重要的，這個就是傳統的辦法。
當然，還有在深度學習出現之前圍棋AI裡面用的方法，從當前局面開始通過隨機走子到達一個容易評分的狀態，然後根據得到的結果反過來推剛才的局面是會贏還是會輸。最後現在出現了深度學習的方法，我把關鍵局面輸進神經網路裡去，輸出的結果就是當前局面的分數。
接下來我們講得更細一點。
像國際象棋（中國象棋也差不多）。這兩個遊戲的特點是，它們戰術很多，你可能會挖很深，這個局面可能走了10步、20步，就可以把它將死。這樣的話，靠人去算就會發現總有方法算出所有情況。
這種情況下搜索是很重要的，但對局面的評判沒那麼難，因為對象棋來說，少個馬或者多個車，都會知道你是不是快輸了，或者是不是處於劣勢。雖然評估不是特別難，但對搜索的要求很高，以下有幾種方法可以加速它的搜索。比如 Alpha-beta Pruning（剪枝演算法）、iterative Deepening 和 Transition Table。
我在這簡單介紹下 Alpha-beta Pruning。假設玩家需要對下一步做出判斷，需要搜索它的特徵，一旦發現對方在某一分支有很好的應招，那麼這條路就不用再搜索了，因為對方這個應招會讓你這個分支的最優解劣於另一個分支的最差解。這就是它的一個簡單思想概括。
這樣的搜索是深度優先，所以不需要把之前的動作都保留下來，只要保留從根到葉子節點的搜索棧就可以了。需要從左邊開始搜，搜到最下面到某個固定的深度之後返回。所以要先定好深度，不能搜無限深，否則第一個分支都出不來。注意在使用時，搜索的深度也不是完全固定的，有時候要多往下走幾步。比如說算到這一步看起來很好，我用皇后吃你個車，我多個車特別開心，但再往下算發現自己的皇后被人吃回去了，這個叫作Horizon Effects，需要很多特別的處理步驟。因為存在這個問題，所以要先搜到一些比較好的策略，再一點一點加深 。
圍棋是另外一種思路，它特點是不一樣的：
首先，它的每一步的可能性比較多；
第二，它的路徑比較難做。在座如果有對圍棋有興趣可能會知道，圍棋少個子、多個子，就會對整個局面有天翻地覆的變化，完全不能以子數或者位置作為評判輸贏的標準。
我先介紹一下AlphaGo是怎麼做的，之後說一下我們是怎麼做的。
大家知道，AlphaGo用的神經網路分為策略網路和值網路，主要能實現以下功能：
給出一個局面後，可以決定下哪些位置；
給出一個關鍵局面時，判斷它們的值，到底是白優還是黑優。
AlphaGo首先用了很多的電腦資源，採用了上萬塊GPU進行訓練，甚至採用像TPU這樣的硬體進行處理，所以計算資源是非常多非常厲害的。
具體到細節上來說，分為以下幾個部分：
Policy network，決定下一步怎麼走；
Value network，決定這個局面分數是多少。
中間還有一部分是High quality playout/rollout policy，是在前兩者返回結果速度較慢的時候，在微秒級可以先得到結果。就是說我如果用微秒級的快速走子預測下一步，它的準確率是24.2%，但後來我自己做實驗發現可以做到30%多些。
AlphaGo的訓練分為以下幾個部分：
第一部分，通過人類遊戲先去訓練一個神經網路下棋，不然對於神經網路來說每個步驟要往怎麼下子都不知道，如果你隨便搜，很多東西都搜不到，所以需要人類棋譜先進行訓練。這其實是圍棋革命的開始，可以訓練出很好的結果。
這張圖上有一些trade off，雖然訓練的第一步走子準確率比較高，但訓練出來的網路可能前饋速度比較慢。所以最後取了折衷原則，灰色的那行就是最後採用的網路（至少是在AlphaGo這篇文章發佈的時候），所以可以發現時間是比較快的，4.8毫秒就可以往前算一步。
這裡就可以發現遊戲AI的指標是比較綜合性的，不僅包括一步預測的準確度，還包括每秒能跑多少次，這樣樹會很深，棋力就會變強，一定程度上也是提高棋力的一種方法。
AlphaGo快速走子（Fast Rollout）可以做到2微秒，同時也有比較好的精確度。
如果從開始預測遊戲最後的結果，那就是瞎猜50%的正確率。但在遊戲進行一陣之後再預測的時候，正確率就會提高。我希望這個下降的速度越快越好，比如在下到40手或45手的時候就知道遊戲結局是什麼。所以，這條線下降得越快，結果應該越好。我們這裡看 Fast Rollout 這條虛的藍線，效果當然沒有用神經網路來得好，但是它兼顧了速度和準確率，下降的速度也是比較快的。
AlphaGo用的另一個主要的技術是蒙特卡羅樹搜索。這其實是個標準的方法，大家可以在任何一本教科書上找到怎麼做。它的中心思想是，在每個樹節點上存有目前的累計勝率，每次採樣時優先選勝率高的結點，一直探索到葉節點，然後用某種盤面估計的方法得到勝負的結果，最後回溯剛才探索的過程，反過來更新路徑上節點的勝率。這樣的話，下次探索的時候，如果發現這條路線的勝率變高了，下次更有可能往這上面走。
所以它與Alpha-beta Pruning不一樣的地方是，沒有界定它的深度是多少，就從0開始，讓它自動生長，長出來後我們會發現很多路線是不會搜索的，可能往下走幾步就不走了，因為它發現這幾步非常糟糕，就不會走下去；而有些招法非常有意思，就會挖得非常深，在某些特定招法下可能往下挖五六十步，都是有可能的。最後演算法會選探索次數最多的節點作為下一步的棋。
這是蒙特卡羅樹搜索比較有意思的地方，它比較靈活，不像國際象棋，後者每次打開樹的時候，要保證所有下一步的招法都要考慮到；而蒙特卡羅樹搜索不需要，有些招不會搜索到。反過來說，它也有可能漏掉一些好棋，這樣就需要好的策略函數來協同。
接下來我介紹一下值網路（Value Network），AlphaGo稱是用了3000多萬場次左右互搏的遊戲訓練出來的，左右互搏是怎麼生成的呢？這是我早上畫的一張圖，解釋了系統是如何收集資料的：
遊戲開始，我們先讓演算法自動走，走的時候是去採樣通過監督學習學得的策略網路（SL network）。
走到某一步的時候，我們隨便走一步，感覺好象我要故意輸的樣子，這樣的好處是讓棋局更加多樣化（diverse），讓演算法看到完全不一樣的棋局，擴大它的適用面。
隨機走那一步之後，得到了當前棋局，然後用更準確的通過強化學習增強的策略網路（RL network）去計算之後的應對，得到最後的輸贏。這樣就得到了當前狀態到輸贏之間的一個樣本點，用這些樣本點去訓練策略網路。
然後你會發現，AlphaGo的能力變得很強，這個圖表最右欄有個叫ELO Ranking的東西（雷鋒網按：Elo Ranking是一種用於計算對抗比賽中對手雙方技能水準的方法，由Arpad Elo創建），這決定了圍棋的棋藝有多強。右邊本來是2400，現在變成快2900，中間差了500分，500分基本上相當於兩個子的差距。本來是業餘高段的水準，現在變成了職業初段的水準。當然，現在應該要比以前牛很多很多，我這裡講的只是公開出來的一些例子。
騰訊“絕藝”
最近“絕藝”打UEC杯，還贏了冠軍，我相信很多人都對此感興趣。我們去年也參加了拿了第二名。當然，今年的水準高出去年非常多。我不知道他們是怎麼做的，文章也沒有發出來，所以也不是特別清楚，但是我相信他們應該達到了AlphaGO 發文章時候的水準。之後AlphaGO又做了很多改進，變成了Master，但那些改進到最近都沒發出來，這部分還是未知的。
去年8月份我去美國圍棋大會（US Go Congress），見到了Aja Huang和Fan Hui，就問他們AlphaGO現在做的怎麼樣？他們沒有透露，但是從言語中我感覺到之前Nature上發的那篇文章，其實是有瓶頸的，就是說沿著這條路走下去，可能不一定能做的非常好。所以，他們如果是要再往上走，比如走到Master這個層面，需要用一些其它的方法，要有更進一步的創新。像我是聽說他們最近把訓練好的值網路單獨拿出來，根據它再從頭訓練一個策略網路。我覺得這樣做的好處是會發現一些看起來很怪但其實是好棋的招法，畢竟人類千百年下棋的師承形成了思維定式，有些棋在任何時候都不會走，所以按照人類棋譜訓練出來的策略網路終究會有局限性；而從頭訓練一個策略網路的話，則會發現很多新招。
當然，我不知道現在騰訊是不是有特別好的新想法出來，或者用了更大量的對局資料。不過看他們跟Zen對弈的棋局，我稍微點了一下步數，大概200步不到就可以讓Zen認輸，所以還是非常厲害的。
德州撲克
接下來我們講一下德州撲克。首先我們要確認，這是“一對一無限注德州撲克”遊戲（Heads-up no-limit Texas Hold'em）。“一對一”意思就是我和你兩個人的零和遊戲，我輸錢你贏錢、我贏錢你輸錢，並不是很多人在一張牌桌上有人當莊家的那種。多人遊戲要難很多，主要是現在用的辦法在多人遊戲下不能保證效果，然後狀態空間也變大很多。
“無限注”就是你每次下注的時候不一定是之前的整數倍，可以是任意數。那麼有限注德撲就是每次下注的時候，是成倍數地下，“有限注”的問題已經在兩三年以前就解決了，當時是發了一篇Science文章。那篇文章其實本應該會跟AlphaGO一樣受到很大矚目，但是不知道為什麼，當時並沒有。
有兩個很牛的撲克AI，這兩個都是用的同樣的框架，叫作Counterfactual Regret Minimization（CFR），簡言之是把遊戲中遇到的可觀測狀態（叫作資訊集Information Set）都羅列出來，然後對於每個可觀測狀態，通過最小化最大悔恨值的辦法，找到對應的策略。然後反復反覆運算。
一個是CMU的Libratus，它打了20天的比賽，贏了4個最牛的撲克玩家。（雷鋒網按：在2017年1月，Libratus玩了12萬手一對一不限注的德州撲克。到比賽結束時，人工智慧領先人類選手共約177萬美元的籌碼。）
另外一個叫DeepStack（雷鋒網按：加拿大阿爾伯塔大學、捷克布拉格查理大學和捷克理工大學訓練的AI系統與11位元職業撲克手進行了3000場無限注德州撲克比賽，勝率高達10/11），他們在網上也打過一些大型職業比賽。
CMU Poker bot
CMU Poker bot沒有用深度學習。他們用到了End-game solver，因為德撲一局時間比較短，可能就幾個回合就結束了，所以你可以從下往上構建遊戲樹。這樣的好處是，最下面節點遊戲樹的狀態是比較容易算出來的，用這個反過來指導設計上面的遊戲樹。另外他也用了蒙特卡羅方法，標準的CFR在每次反覆運算的時候，要把整個遊戲樹都搜一遍，這個對於稍微複雜一點的遊戲來說是不可接受的，因為是指數級的複雜度，所以用蒙特卡羅方法，每次選一些節點去更新它上面的策略。還有一點就是，一般來說我們在做遊戲的時候往往會想到怎麼去利用對方的弱點，但其實不是這樣的。更好的方法是，我儘量讓別人發現我的弱點，然後據此我可以去改進它，變得越來越強。用術語來講，就是去算一下對手的最優應對（Best response），讓對手來利用你的弱點，然後用這個反過來提高自己的水準。
阿爾伯塔大學的DeepStack
我們看到DeepStack的基本流程是AlphaGo和國象的某種混合版本，即有限深度的搜索，加上用值網路估值。具體來說，從當前狀態出發向前看三四層的子樹，在最底一層用值網路估算一下值（誰好誰壞），然後用通常的CFR去求解這棵子樹的的最優策略。對於值網路來說，每個人有兩張手牌，52選2，就有1326種情況，但每種情況都有概率，以這個作為輸入。輸入同時也包括當時的籌碼數和公共牌。輸出的是在每種手牌情況下，估計的值函數（counterfactual value）會是多少。
深度學習在遊戲AI中的角色
之前說了各種各樣的遊戲AI，為什麼Deep Learning 在其中扮演重要的角色呢？
遊戲AI裡需要解決的一個核心問題就是，給策略函數和值函數建模。那傳統的方法存在兩個缺陷，一個是傳統方法需要很多手動步驟把一個大問題分解成子問題，然後把每個子問題單獨建模，這個造成工作量很大；還有一個問題就是手調的參數太多，以前的遊戲AI就是這樣，每個參數都要調，人力是要窮盡的，這也是個缺陷；最後就是寫遊戲AI的人需要真的精通這個遊戲。比如說寫圍棋AI，作者得要有棋力，然後把棋力變成一條條規則放進去。那現在我們用深度學習的方法，就會發現能夠很大程度上解決這些問題，而且效果還好很多，像我圍棋水準很爛也沒有關係。這也是它為什麼那麼火的原因。
DarkForest
接下來我介紹一下我們的圍棋AI，DarkForest。當時我們在AlphaGo出來的3個月前（2015年11月），就發了一篇文章，並且公佈了在KGS（一個國外的圍棋平臺）上的對局統計。當時很多人跑過來說這個很有意思，也有一些媒體報導。這個想法其實很簡單，就是我們設計一個神經網路，輸入當前局面，希望預測一步甚至三步的落子，通過這種方式提高性能。DarkForest當時在沒有搜索的時候，在KGS上能夠做到業餘三段的水準，這在當時是非常有意思的結果。當然現在隨便一個本科生都可以訓練出來了。
這是一些分析，左邊是一些特徵，右邊是通過訓練的時候，發現三步比一步要穩定，效果也要好一點。
當時我和我的實習生去參加第九屆UEC的比賽，我們從DCNN裡拿出來前3或前5步使用，每一步做蒙特卡洛樹搜索了75000次，達到了業餘五六段的水準，拿了第二名。之後我們就把代碼都放在網上，大家都可以用，都是開源的。當然，我們在圍棋上的投入還是比較少的。
DarkForest也可以拿來分析AlphaGO和李世石的對弈。可以發現勝率會有變化。第一局102手，AlphaGO的打入，當時討論這是不是一個勝負關鍵點，至少會認為在那個點認為有點意思。我們也拿來分析一下，最近Master下的兩局，也可以看到勝率的變化情況。
最近，我們也用了比較相似的框架做了First Person Shooter Game，當時做的是Doom，這是比較復古的一個遊戲。就是在一個虛擬環境裡用上下左右鍵操縱，然後看到敵人就開槍，最後看分數是多少。
我們在這個工作中用了Actor-Critic模型，不僅輸出策略函數還輸出值函數，兩個函數是共用大量參數的。 這個模型我這裡就講一些直觀上的理解。
首先，這個模型在訓練時，會獎勵那些導致超越目前期望分數的行為。也就是說，我們對每個狀態的值有一個估計，在做完了某個動作（或者一連串動作）之後，如果新狀態的綜合獎勵值高於由值函數算出的預期，我們就可以更多地鼓勵它做這個動作。
其次，我們希望值函數的估計越來越准。值函數一開始是隨機的，這樣就連帶拖慢了整個演算法的收斂速度。在訓練時，我們可以用探索得來的綜合獎勵值去更新估計值。這樣反復反覆運算，時間長了以後會反覆運算到真實的值。
另一個要求是增加多樣性，我們希望輸出的行動不要太集中在一個動作上，不然你會發現訓練一陣之後AI變得很機械，只會做固定的動作，或者卡死在一些地方（比如說卡在角落裡轉不出來）。這個通過加一個最大熵的能量項來實現。
這是一方面，算是目前比較標準的強化學習的步驟。這篇文章的創新點是我們加了一個“課程學習”（ Curriculum Training）的過程，因為遊戲裡地圖比較複雜，需要讓它先從簡單地圖學會基本操作（開槍、上子彈等），有了這些基本操作再把這個AI放到比較複雜的環境裡再訓練。
像這個就是我們設計的簡單地圖。在這個地圖裡我們有8個不同的場景，每個場景裡的敵人都不一樣。第一個場景裡敵人動作都非常慢，血也很少，可能一槍就打死了；第二個場景可能敵人行動快一些，難度大些，開始用火箭彈而不是用手槍來對付你。通過這種方法會把bot一點點慢慢訓練出來，然後一點點讓AI變得越來越強。
我們參加了VizDoom AI Competition，這個是機機對戰。我們拿了第一個Track的第一名。我們發現最後得分比其它參賽者的高很多。網上有一些視頻可以看一下，視頻裡比較有意思，就是我們這個AI的動作比較堅決，擊中和移動速度都比較靈活，打別的人時候，自己還會主動躲閃其它人射來的火箭彈。
除了機機對戰，他們還做了一個比賽，讓所有BOT跟一個比較厲害的人類打，很有意思。我們的BOT有30秒鐘的分數超過人的水準，不過後來就不行了。你們會發現，機器和人會有不同的行為，因為人的反應速度不會特別快，但人有一些長期的計畫，他會知道什麼是你的弱點然後去利用它。但BOT在比賽的時候，並不具備學習的能力，所以它們都有恒定的行為模式。像有些BOT一直在轉圈子，有些BOT在原地不動，還有些BOT（比如說第二名）就一邊蹲著一邊打人，沒人打得到它。
這是一些分析，可以看到什麼樣的場景下它的值函數最高和最低。上面一排是分數最高的，也就是子彈馬上就要打到對方了，我們的bot馬上要得分，這個可以說是它最得意的時候；下面一排是分數最低的，也就是我給對方一槍，對方沒死，但此刻我自己也沒有子彈了。
以上，我們可以總結成下面兩句關鍵點：
第一點，就是通過搜索來做出對將來的規劃和推理。
第二點，就是深度學習來做策略函數和值函數的逼近，是比較好的方法。
其實很單調，不是麼？接下來要做什麼？其實我們還有很多問題沒有辦法解決，這裡列了很小一部分。
在星際裡面，我們有指數級的行動可能，在這種情況下怎麼做決策？
如果你要用強化學習的方法來做，沒有激勵機制怎麼辦，這種情況下去訓練一個機器人，它不知道怎麼做才能提高自己的水準。但是人類似乎就可以找到自己的目標；
多個AI間如何溝通協作；
在虛擬環境中訓練出一個AI，要如何應用于現實生活；
我們訓練模型，一般需要大量的資料（數百萬級甚至上億），但是人類稍微在一個環境裡待一段時間就適應了，那麼我們如何讓機器也能做到這一點；
如何讓bot學會戰略性思考，分清戰略和戰術的區別。如何讓它的思考有層次性？
等等，還有很多問題等待我們去解決。
這就是我的發言，謝謝大家！
AI科技評論注：目前田淵棟老師的演講視頻已上傳到騰訊視頻，歡迎關注“AI科技評論”後回復“田淵棟演講”獲取視頻連結。