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ī)器的計(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)典游戲，這是由于其巨大的搜索空間以及難于評估的棋盤盤面和走子肛响。這里我們介紹了一個(gè)新方法：使用價(jià)值網(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ī)的自我對抗盤局雹有。我們還提出了一種將蒙特卡羅仿真和價(jià)值網(wǎng)絡(luò)以及策略網(wǎng)絡(luò)結(jié)合起來的新搜索算法。使用該搜索算法后臼寄， AlphaGo 在和其他圍棋程序的對弈中霸奕，贏了 99.8%的盤局，并且以 5 比 0 擊敗了歐洲圍棋冠軍吉拳。這是計(jì)算機(jī)程序首次在全尺寸的圍棋對抗中擊敗職業(yè)圍棋選手质帅，這個(gè)壯舉以前被認(rèn)為是至少十年以后才會發(fā)生。

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

多臂賭博機(jī)問題

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

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

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

那么請問這樣的做法是能保證最大收益么掸犬？ 實(shí)際上這是一個(gè)兩難的境地(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

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

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

怎么衡量策略的好壞呢丹墨？

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

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

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

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

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

是的偿衰，我們可以挂疆。

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

前后提出了以下算法：

UniformBandit Algorithm

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

思想：

• 拉動每個(gè)拉桿w次

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

  
  
  image.png

Policy Rollout Algorithm

思想：

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

Multi-Stage Rollout

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

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

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

Sparse Sampling

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

image.png

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

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

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

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

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

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

Sparse Sampling Search Tree

我們能否平衡exploitation 和 exploration呢？

UCB1算法

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

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

簡單的說這個(gè)算法辣往，平衡了exploitation 和 exploration。在保證一定收益的同時(shí)鹿霸，又不放棄潛在的收益。

ucb1

UCT算法

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

UCT

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

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

蒙特卡洛樹搜索（MCTS： Monte-Carlo tree search）利用蒙特卡洛 rollouts 來評估每個(gè)盤面在搜索樹中的值。運(yùn)行越多的仿真荣刑，搜索樹變得越大馅笙，相對值也越準(zhǔn)確。用于在搜索過程選擇動作的策略也隨著時(shí)間推移而提高厉亏，該策略是通過選擇有更高值的子樹實(shí)現(xiàn)的董习。逐漸地，策略收斂到最優(yōu)方案爱只，評估也收斂到最優(yōu)值函數(shù)皿淋。目前最強(qiáng)的圍棋程序是基于MCTS 的，并通過訓(xùn)練成能預(yù)測專業(yè)選手的走子來得以加強(qiáng) 恬试。這些策略用于將搜索收窄到一束最有可能的動作窝趣，并在下棋時(shí)采樣動作。該方法達(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)域打敗了人類世界冠軍瞪浸。下面簡要介紹一下這是如何實(shí)現(xiàn)的。

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

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ò)對抗時(shí)泛鸟，RL策略網(wǎng)絡(luò)贏得了80%的棋局。

image.png

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

4 Searching with Policy and Value Networks
AlphaGo將策略和價(jià)值網(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ò)以及價(jià)值網(wǎng)絡(luò)結(jié)合的思想。

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

啟示

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

參考資料

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

[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.