2016年 AlphaGo 橫空出世，在AI界和圍棋界掀起了一陣腥風(fēng)血雨。寶刀一出，無數(shù)圍棋高手如樊麾，李世石，柯潔等人先后被斬于馬下。

正所謂：十步殺一人，千里不留行。事了拂衣去，深藏功與名。

AlphaGo 使用的技術(shù)有深度神經(jīng)網(wǎng)絡(luò)和樹搜索，這篇文章主要介紹一下樹搜索。

簡單的說 Monte-Carlo Tree Search（MCTS）的意思就是講蒙特卡羅抽樣的思想用到樹搜索上。在我了解到MCTS思想背后的簡單和暴力之后，在棋類領(lǐng)域機(jī)器打敗人類是必然的事情。但我認(rèn)為這僅僅能說明機(jī)器的計算水平很高，這是AI領(lǐng)域進(jìn)步的一小步，現(xiàn)在的AI離真正的智能還很遠(yuǎn)。

[2016, Mastering the game of Go with deep neural networks and tree search - DeepMind]
對于人工智能來說，圍棋一直被視為最具挑戰(zhàn)性的經(jīng)典游戲，這是由于其巨大的搜索空間以及難于評估的棋盤盤面和走子。這里我們介紹了一個新方法：使用價值網(wǎng)絡(luò) (value networks )來評估棋盤盤面和使用策略網(wǎng)絡(luò) (policy networks )來選擇走子。為了訓(xùn)練這些深度神經(jīng)網(wǎng)絡(luò)，我們將有監(jiān)督學(xué)習(xí)（從人類職業(yè)比賽中學(xué)習(xí)）和增強(qiáng)學(xué)習(xí)（從自我對抗的比賽中學(xué)習(xí)）創(chuàng)新地結(jié)合在一起。在沒有使用任何前瞻搜索的情況下，這些神經(jīng)網(wǎng)絡(luò)的水平已經(jīng)相當(dāng)于最先進(jìn)的使用蒙特卡羅樹搜索(MCTS： Monte Carlo tree search)的程序，這些程序模擬了成千上萬的隨機(jī)的自我對抗盤局。我們還提出了一種將蒙特卡羅仿真和價值網(wǎng)絡(luò)以及策略網(wǎng)絡(luò)結(jié)合起來的新搜索算法。使用該搜索算法后， AlphaGo 在和其他圍棋程序的對弈中，贏了 99.8%的盤局，并且以 5 比 0 擊敗了歐洲圍棋冠軍。這是計算機(jī)程序首次在全尺寸的圍棋對抗中擊敗職業(yè)圍棋選手，這個壯舉以前被認(rèn)為是至少十年以后才會發(fā)生。

[知乎]Alphago打敗的可不是李世石抑或全人類，而是圍棋這項智力運(yùn)動千百年來演變發(fā)展積攢而出的人類自信。

多臂賭博機(jī)問題

這里又要介紹一個新的概念了：Multi-Arm Bandit Problem 多臂賭博機(jī)問題。

設(shè)想我們身處在一個賭城中，面前是多臺賭博機(jī)，但我們不知道每臺賭博機(jī)輸或者贏的概率。那我們怎么能在給定一定的次數(shù)，例如玩100次，獲得最大的收益呢？

本能的最簡單想法是，我們將每臺機(jī)器都試w次(例如10次)，統(tǒng)計每臺機(jī)器拉動10次拉桿的最終收益，選擇收益最大的拉桿一直拉。。。

那么請問這樣的做法是能保證最大收益么？ 實際上這是一個兩難的境地(exploration-exploitation)，一方面我們要嘗試了解哪臺機(jī)器會有最大的收益，另一方面我們要犧牲潛在的收益來多嘗試。

以上就是多臂賭博機(jī)問題。

多臂賭博機(jī)問題

馬爾可夫決策過程

我們要求解的問題是Markov Decision Processes(馬爾可夫決策過程)。

什么是Markov Decision Processes呢？

MDPs

An MDP has four components: S, A, Pr, Pt :

• finite state set S
• finite action set A
• Transition distribution Pr(s’ | s, a)
  Probability of going to state s’ after taking action a in state s
  First-order Markov model
• Bounded reward distribution Pr(r | s, a)
  Probability of receiving immediate reward r after taking action a in state s
  First-order Markov model

給定一個MDP，我們希望計算出一個策略，計算這個策略可以是online或者offline的。
一個策略是狀態(tài)到動作的隨機(jī)映射。

π:S → A
π(s) is action to do at state s
specifies a continuously reactive controller

怎么衡量策略的好壞呢？

我們實際上是使用一個值函數(shù)，最優(yōu)的策略是所有狀態(tài)獲得回報(reward)最大的那個策略。

MDP問題規(guī)模比較小的時候，可以使用值迭代或者策略迭代求解。

但我們對有指數(shù)級別的狀態(tài)空間的MDP問題感興趣。傳統(tǒng)的方法對于這類問題就無能為力了。例如象棋，圍棋。

蒙特卡羅與馬爾可夫決策過程

蒙特卡羅思想即抽樣的思想深深的影響了各個領(lǐng)域。那么我們可以用抽樣的思想求解MDPs問題么？

是的，我們可以。

不是狀態(tài)空間大么？ 我們用隨機(jī)模擬的思想求解MDP。

前后提出了以下算法：

UniformBandit Algorithm

UniformBandit Algorithm （NaiveBandit from [Even-Dar et. al., 2002]）在2002年，提出了樸素賭博機(jī)算法。

思想：

• 拉動每個拉桿w次

• 返回平均獎勵最大的拉桿

  
  
  image.png

Policy Rollout Algorithm

思想：

• 對于每個動作，執(zhí)行simQ w次
• 選擇平均獎勵最大的simQ對應(yīng)的動作。

Multi-Stage Rollout

篇幅原因，不做詳細(xì)介紹。

總結(jié)一下上面的算法，雖然好用，但是效率不高，也不能保證最優(yōu)或者接近最優(yōu)。

接下來有人提出了Sparse Sampling 算法。

Sparse Sampling

是Kearns在2002年提出的，這個算法是可以保證最優(yōu)的。

image.png

但是這個算法的問題是建立的搜索樹是指數(shù)級增長的。

Each state generates kw new states
(w states for each of k bandits)
? Total # of states in tree (kw)^h

• 好消息
  這個算法振奮人心的是我們可以獲得近似最優(yōu)，同時這個規(guī)劃算法的運(yùn)行時間不依賴于狀態(tài)空間的大小！

• 壞消息
  但是搜索樹值指數(shù)級的。

• 實際應(yīng)用
  我們使用較小的h。降低指數(shù)級的增長。

Sparse Sampling 不太好用的原因是，它浪費(fèi)掉時間探索樹前景不好的部分。它把資源都平均的分配給了每一個狀態(tài)。

Sparse Sampling Search Tree

我們能否平衡exploitation 和 exploration呢？

UCB1算法

在2002年Auer提出了 UCB1 算法解決多臂賭博機(jī)問題。

UCB1（Upper Confidence Bound）上置信區(qū)間，這是概率論中的一個概念，意思是估計未知參數(shù)的可信程度，以區(qū)間的形式給出。有時我們僅僅關(guān)心上限或者下限。這就提出了單側(cè)置信上限或者下限的概念。

簡單的說這個算法，平衡了exploitation 和 exploration。在保證一定收益的同時，又不放棄潛在的收益。

ucb1

UCT算法

在2006年Kocsis & Szepesvári提出了將UCB1的思想用在解決樹搜索的想法，提出了UCT(Upper Confidence with Tree-based Search)。

UCT

算法圖中的常數(shù)C是一個經(jīng)驗值，根據(jù)實際可以進(jìn)行調(diào)整。

之前的抽樣算法沒有提出抽樣的策略，對應(yīng)于一個狀態(tài)可用的每個動作都是隨機(jī)抽樣執(zhí)行的。一個好的抽樣策略應(yīng)該進(jìn)一步探索有前景的動作，和剪枝不好的動作。

蒙特卡洛樹搜索（MCTS： Monte-Carlo tree search）利用蒙特卡洛 rollouts 來評估每個盤面在搜索樹中的值。運(yùn)行越多的仿真，搜索樹變得越大，相對值也越準(zhǔn)確。用于在搜索過程選擇動作的策略也隨著時間推移而提高，該策略是通過選擇有更高值的子樹實現(xiàn)的。逐漸地，策略收斂到最優(yōu)方案，評估也收斂到最優(yōu)值函數(shù)。目前最強(qiáng)的圍棋程序是基于MCTS 的，并通過訓(xùn)練成能預(yù)測專業(yè)選手的走子來得以加強(qiáng) 。這些策略用于將搜索收窄到一束最有可能的動作，并在下棋時采樣動作。該方法達(dá)到了很高的業(yè)余選手的水平。但是，這些以前的工作局限于膚淺的策略，或值函數(shù)是基于輸入特征的線性組合 。

UCT建立的搜索樹如下：

非對稱的搜索樹

UCT的重點(diǎn)是：

UCT

在2006年以后，學(xué)者又陸續(xù)提出了UCT算法的很多改進(jìn)。這里先不做介紹了。UCT的來源和主要思想在這篇文章中已經(jīng)介紹清楚了。

AlphaGo 與 MCTS

AlphaGo基于深度神經(jīng)網(wǎng)絡(luò)和MCTS在圍棋領(lǐng)域打敗了人類世界冠軍。下面簡要介紹一下這是如何實現(xiàn)的。

在圍棋領(lǐng)域僅僅通過使用MCTS算法，因為問題的復(fù)雜性，在水平上是超過打敗人類的。我認(rèn)為在圍棋領(lǐng)域通過深度神經(jīng)網(wǎng)絡(luò)和MCTS的結(jié)合有效減少了搜索時間。

1 Supervised Learning of Policy Networks
使用有監(jiān)督學(xué)習(xí)訓(xùn)練策略網(wǎng)絡(luò)。策略網(wǎng)絡(luò)輸出的是落子的概率分布。該網(wǎng)絡(luò)預(yù)測專業(yè)選手走子的準(zhǔn)確率為57.7%

image.png

2 Reinforcement Learning of Policy Networks
使用強(qiáng)化學(xué)習(xí)改善第一步訓(xùn)練的策略網(wǎng)絡(luò)。使用RL策略和SL策略網(wǎng)絡(luò)對抗時，RL策略網(wǎng)絡(luò)贏得了80%的棋局。

image.png

3 Reinforcement Learning of Value Networks
價值網(wǎng)絡(luò)的增強(qiáng)學(xué)習(xí)。
訓(xùn)練最后一步關(guān)注盤面落子的評估，估計一個值函數(shù)來預(yù)測盤面s的結(jié)果。價值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)的架構(gòu)類似，但輸出的是一個預(yù)測，而非概率分布。

4 Searching with Policy and Value Networks
AlphaGo將策略和價值網(wǎng)絡(luò)結(jié)合到MCTS算法。

image.png

image.png

image.png

image.png

結(jié)語

近年來圍棋領(lǐng)域最大的突破是MCTS思想的引入。

對于人工智能來說，圍棋在許多方面都是經(jīng)典的難題：富有挑戰(zhàn)的決策任務(wù)，棘手的搜索空間等等。

在2016年的Mastering the game of Go with deep neural networks and tree search - DeepMind一文中，提出了策略或值函數(shù)直接進(jìn)行近似估值似乎不可行，提出了策略網(wǎng)絡(luò)以及價值網(wǎng)絡(luò)結(jié)合的思想。

基于這個思想AlphaGo 最終達(dá)到了圍棋的職業(yè)水準(zhǔn)，這也給其他看起來不可觸及的人工智能領(lǐng)域達(dá)到人類的水平帶來了希望。

啟示

基于計算機(jī)視覺的深度神經(jīng)網(wǎng)絡(luò)和蒙特卡洛樹搜索，終于在圍棋領(lǐng)域打敗的人類。
給我們的啟示是關(guān)于搜索問題，我們還能否提出更加優(yōu)秀的算法？

參考資料

[1] 概率論與數(shù)理統(tǒng)計

[2] L. Kocsis and C. Szepesvári, “Bandit based monte-carlo planning,” Proc. ECML, pp. 282–203, 2006.

[3] C. B. Browne et al., “A Survey of Monte Carlo Tree Search Methods,” Comput. Intell. AI Games, IEEE Trans., vol. 4, no. 1, pp. 1–43, 2012

[4] CS188: Artificial Intelligence https://edge.edx.org/courses/course-v1:Berkeley+CS188+SP17/info

[5] Monte-Carlo Planning: Basic Principles and Recent Progress http://videolectures.net/icaps2010_fern_mcpbprp/

[6] S. Sanner, “Relational dynamic influence diagram language (rddl): Language description,” Unpubl. ms. Aust. Natl. Univ., 2010.

[7] S. J. Russell and N. Peter, Artificial Intelligence A Modern Approach.pdf.

[8] D. Silver et al., “2016 - Mastering the game of Go with deep neural networks and tree search - DeepMind nature16961,” Nature, vol. 529, no. 7587, pp. 484–489, 2016.