深度學習筆記——“Mastering the game of Go with deep neural networks and tree search”論文學習

題目

“通過深度神經網絡和樹搜尋征服圍棋遊戲”，英文原文連結點選這裡。

摘要

圍棋遊戲一直被視為人工智能經典遊戲中最具挑戰性的遊戲，因為它具有巨大的搜尋空間和評估棋盤盤面和移動的難度。在這裡，我們介紹一種新的計算方法，它使用“價值網絡”(value networks)來評估棋盤盤面，并使用“政策網絡”(policy networks)來選擇走法。這些深度神經網絡采用了一種新穎的方法進行訓練，即将有監督學習（從人類職業比賽中學習）和強化學習（從自我對抗的比賽中學習）相結合。在沒有使用任何前瞻性搜尋的情況下，這些神經網絡的水準已經相當于最先進的使用蒙特卡羅樹搜尋(MCTS：Monte Carlo tree search)的程式，這些程式模拟了成千上萬的随機的自我對抗盤局。我們還引入了一種新的搜尋算法，将蒙特卡羅模拟與價值和政策網絡相結合。使用這種搜尋算法後，我們的程式AlphaGo在和其它圍棋程式的對弈中達到了99.8%的勝率，并且以5比0擊敗了歐洲圍棋冠軍。這是計算機程式首次在全尺寸的圍棋對抗中擊敗人類職業圍棋選手，這是一項以前被認為至少需要十年才能完成的壯舉。

• 筆記：需要掌握的有：“價值網絡”(value networks)、“政策網絡”(policy networks)、蒙特卡羅樹搜尋(MCTS：Monte Carlo tree search)、将蒙特卡羅模拟與價值和政策網絡相結合的搜尋算法

引言

所有完美資訊博弈(games of perfect information)[^1]都有一個優值函數， v*(s)，它從每一個棋局或者說狀态s中決定了最終的博弈結果（在所有對手都完美發揮的情況下）。可以通過在搜尋樹中遞歸計算優值函數來解決這個博弈，它大約需要計算 b d b^{d} bd個可能的落子序列，其中，b是博弈的寬度（每次下棋時合法的落子個數），d是它的深度（博弈步數的長度）。在大型博弈中，比如國際象棋（b≈35，d≈80）、以及尤其是圍棋中（b≈250，d≈150），窮舉搜尋是不可行的，但是有效的搜尋空間可以通過兩種通用的原則減少。首先是，可以通過棋局評估來減少搜尋的深度： 在狀态 s 時對搜尋樹進行剪枝，并且通過一個近似的估值函數 v(s) ≈ v*(s) 來替換 s 下面的子樹，進而預測狀态 s 的結果[^2]。這種方法在國際象棋、跳棋、黑白棋中都獲得了超人的表現，但在圍棋中卻被認為是難以駕馭的，因為圍棋實在是太複雜。其次是，搜尋的廣度可以通過來自政策 p(a∣s) 的采樣動作來降低，該政策 p(a | s) 是在某一位置 s 處可能的落子位置 a 的機率分布[^3]。例如，比如蒙特卡洛走子方法搜尋到最大深度時候根本不使用分枝界定法，它通過政策 p 對雙方棋手的一系列下棋走法進行采樣。計算這些走子的平均數可以産生一個有效的棋局評估，在西洋雙陸棋戲和拼字遊戲中獲得了超出人類的性能表現，并且在圍棋中達到了業餘低段水準。

• 筆記：
• [^1]感覺“完美資訊”和“完全資訊”兩個概念不是很好區分，我覺得可能用反面例子來解釋會比較好了解。
  • 在博弈的每個行動時點上，參與人可能無法獲悉決策所需的全部資訊。這包括相關的外部環境——比如天氣——的不确定性，以及對方先前或目前的行動，這類情況稱為不完美資訊(imperfect information) ；
  • 當一個參與人比另一個參與人了解更多資訊時，這類情況稱為不完全資訊(incomplete information)，或者更恰當的稱呼是非對稱資訊(asymmetric information)
  • 是以，下棋時，雙方既知道目前的戰況以及過去的棋步，也沒有不确定的外部環境，而且雙方了解的資訊同樣多，是以應該認為下棋為一種完美資訊博弈。
• [^2]不是很懂，棋局評估如何完成？ v(s) ≈ v*(s) 又是如何得到的呢？這裡是不是就是所謂的中間評估函數(intermediate valuation function)，因為由于博弈樹的巨大，我們并不能預測整個遊戲的結局，而又隻有終點結才被賦予了由博弈規則所刻畫的支付(payoff)，是以我們必須賦予我們所能預見到的非終點結以某種支付，這種賦予非終點結支付的規則被稱為中間評估函數(intermediate valuation function)，（參考自《政策博弈》中國人民大學出版社 第三章 序貫行動博弈），是以依靠它，我們可以減少搜尋的深度。它的改進可以通過反複的實戰經驗和對棋盤上錯綜複雜的關系的認知而得來，這種就是我們所說的微妙的弈棋思維，這對人類來說很容易擷取，但對計算機來說就不那麼容易了，是否這就會用到該篇論文之後介紹的深度神經網絡來完成？
• [^3]這個機率分布是如何得到的？

蒙特卡洛樹搜尋（MCTS）[^4]使用蒙特卡洛走子方法（Monte Carlo rollouts）[^5]，評估搜尋樹中每一個狀态的估值。随着模拟的次數越來越多，搜尋樹也越來越大，而且相關估值愈發精确。在搜尋過程中用于選擇下棋動作的政策，也随着時間的推移有所改進，這種改進也就是選擇具有更高價值的子樹。漸漸地，該政策收斂于最優下法，并且評估也收斂到最優值函數。目前最強的圍棋程式是基于MCTS的，通過訓練來預測人類棋手的落子，進而越來越強。這些政策過去是用來縮小搜尋範圍的，使搜尋範圍成為一束高機率的下棋動作，并且用來在快速走棋中對動作進行采樣。這種方法達到了較好的業餘段位水準，但是，以前的工作僅局限于基于對輸入特征進行線性組合的估值函數或者淺層政策的限制。

• 筆記：
• [^4]參考連結可以大緻明白MCTS的原理，以及我在github上找到了一個簡單實作MCTS的小項目，能幫助更好的了解MCTS，其中函數TREEPOLICY、EXPAND和BESTCHILD實作前兩步，選擇和擴充，之後DEFAULTPOLICY完成模拟，最後BACKUP完成回溯。UCTSEARCH函數中，反複疊代這幾個過程，使得最後的“勝率”收斂。
• [^5]Rollout：在西洋雙陸棋中，每一個位置的期望值就叫做這個位置的期望(“equity”)，通過蒙特卡洛采樣對"equity"進行估計就叫做進行"rollout"。論文中一般稱為快速走棋。

最近，深度卷積神經網絡在視覺領域取得了前所未有的成績，例如圖像分類、人臉識别和Atari遊戲。它們使用許多層神經元，層與層之間像瓦片一樣排列重疊在一起，來構造逐漸抽象的、局部的圖像表示。我們采用類似的架構來進行圍棋遊戲。我們将棋局以一個19*19大小的圖檔傳入，然後使用卷積層來構造位置的表示。我們使用這些神經網絡來降低搜尋樹的有效的深度和廣度：使用價值網絡評估棋局，使用政策網絡對落子動作進行取樣[^6]。

• 筆記：[^6]是以價值網絡應該與第三步模拟，即上述github項目中的DEFAULTPOLICY完成的功能類似，或者說與快速走子政策完成的功能類似，政策網絡應該與上述github項目中的BESTCHILD完成的功能類似。

我們使用由幾個機器學習階段組成的管道來訓練神經網絡（圖1）。我們首先直接利用人類專業棋手的落子來訓練監督學習（SL）政策網絡pσ 。這通過即時的回報和高品質的梯度，提供了快速、高效的學習更新。與以前的工作類似，我們還訓練了快速政策網絡 pπ ，它能夠在rollout期間迅速對動作進行采樣。接下來，我們訓練強化學習（RL）政策網絡pρ ，它能夠通過優化自我博弈的最終結果，來改善SL政策網絡的性能。這會将政策調整到以赢棋為正确目标，而不是最大化提高預測精度。最後，我們訓練一個價值網絡 vθ，來預測RL政策網進行自我博弈的結果。我們的AlphaGo程式利用MCTS将上述政策網絡和價值網絡有效地結合在一起。