超越蒙特卡洛樹搜索：北京大學提出深度交替網路和長期評估圍棋模型

選自arXiv

機器之心編譯

參與：李澤南、吳攀

在五月底與柯潔等人的系列對局之後，人工智慧圍棋大師 AlphaGo 已經功成名就，金盆洗手了，參閱《現場報道 | AlphaGo 被授職業九段，DeepMind 將公開其所有版本細節》；但這並不意味著計算機圍棋研究已經走到了盡頭。近日，北京大學的一組研究團隊宣稱在計算機圍棋研究上取得了另一個方向的研究成果。

和 AlphaGo 等目前領先的圍棋程序不同，北京大學 Wang Jinzhuo、王文敏、王榮剛、高文等人提出的新方法沒有使用蒙特卡洛樹搜索，而是使用了由深度交替網路（DANN）和長期評估（LTE）組成的系統。而且研究者還通過實驗表明該系統的棋力也強於目前大多數基於蒙特卡洛樹搜索的方法。

並不完美的蒙特卡洛樹搜索

圍棋是一種古老的智力遊戲，規則簡單，但變化複雜。由於棋局變化的可能性是海量的，在大多數情況下，我們很難對棋盤上的落子位置構建價值函數。此前，大多數計算機圍棋程序都著重於模擬未來棋局可能的變化，從而選擇最佳落子位置。在這種思路下，蒙特卡洛樹搜索（MCTS）（Gelly & Silver 2011）是最為流行的方法，它構建了一個廣泛而深入的搜索樹來模擬和評估每個落子位置的價值。利用這種方法構建的圍棋程序已經獲得了很大成功。

AlphaGo 結合了監督學習與強化學習的優勢。通過訓練形成一個策略網路，將棋盤上的局勢作為輸入信息，並對有所可行的落子位置形成一個概率分布。然後，訓練一個價值網路對自我對弈進行預測，以-1（對手的絕對勝利）到 1（AlphaGo 的絕對勝利）的標準，預測所有可行落子位置的結果。AlphaGo 將這兩種網路整合進基於概率的蒙特卡羅樹搜索（MCTS）中，實現了它真正的優勢。

然而，蒙特卡洛樹搜索的方法並不是完美的，性能不平衡是這種方法的主要限制。人們發現，利用蒙特卡洛樹方法構建的圍棋程序在對殺、劫爭和關子時時常會出現錯誤的選擇。人們將這些缺陷歸於兩種原因：1. 剪枝搜索是基於先驗知識的動作，距離完美的計算還相去甚遠；2. 由於圍棋的棋盤是廣闊的，對於大部分可能性的計算是無用的。此外，蒙特卡洛樹的葉子輸出難以得到精確評估。

而最重要的是，MCTS 的方法和人類棋手並不相同，因為人類並不會對每一個可能的點位進行粗暴的模擬。相反，人類在落子時會首先通過特徵分析選擇幾個可能的點位，並通過評估這些點位從中選擇一個最優的下法。

隨著近年來深度學習在圖像識別等領域的興起，研究人員開始引入深度學習的方法來構建新一代圍棋程序。與視覺信號相比（如 224x224 像素的圖片），圍棋棋盤的尺寸更小（19x19），而各點的相對位置十分重要，這與圍棋牽一髮而動全身的理念相類似。另一方面，現有的 DCNN 通常通過堆疊更多的卷積層以利用低級特徵的高階編碼來進行推理，層數的增加不僅使參數負擔增加，也無法嵌入局部特徵及其演化。

基於上述討論，北京大學的研究者們提出了由兩個主要部分構成的新型計算機圍棋系統。

論文：超越蒙特卡洛樹搜索：使用深度交替網路和長期評估下圍棋（Beyond Monte Carlo Tree Search: Playing Go with Deep Alternative Neural Network and Long-Term Evaluation）

論文鏈接：https://arxiv.org/abs/1706.04052

摘要

在計算機圍棋領域，蒙特卡洛樹搜索（MCTS）是一種極其流行的方法，其可以通過在一個寬闊且深度的搜索樹中進行巨量的模擬來確定每一步動作。但是，人類專家是通過模式分析和精心的評估來選擇大多數的動作，而非對未來數百萬次互動進行暴力搜索來完成。在這篇論文中，我們提出了一種可以像專家一樣思考和下棋的計算機圍棋系統。我們的系統由兩部分組成。

第一部分是一個全新的深度交替神經網路（DANN/deep alternative neural network），用於生成下一步的候選項。和已有的深度卷積神經網路（DCNN）相比，DANN 會在每個卷積層後插入一個循環層，以一種交替的方式將它們堆疊在一起。我們表明這樣的設置可以保留更多局部特徵及其演化的背景信息（context），這有助於做出走子預測。

第二部分是一個長期評估（LTE/long-term evaluation）模塊，用於提供對候選項的可靠評估，而不僅僅是來自走子預測器的單個概率。這與人類專家下棋的本質是一致的，因為他們可以預見未來數十步並對候選項給出一個準確的評估。在我們的系統中，對於每個候選項，LTE 會在局部變化確定了之後計算未來幾次交互的累積獎勵。

結合來自這兩個部分的指標，我們的系統可以確定下一步的最優選擇。為了更加全面的實驗，我們引入了一個新的職業圍棋數據集（PGD），其包含了 253233 局職業對弈記錄。在 GoGoD 和 PGD 數據集上的實驗表明，相對於 DCNN，DANN 可以顯著提升走子預測的表現。當結合了 LTE 後，我們的系統的表現優於大多數基於 MCTS 的相關方法和開放引擎。

圖 1：研究人員提出使用深度交替神經網路（DANN）和長期評估（LTE）的計算機圍棋系統。給定一個局面，該系統可通過 DANN 生成多個候選項——DANN 在職業對弈記錄上學習過。LTE 會對這些候選項進行進一步的分析，考慮了未來回報後確定最終的動作。

深度交替神經網路

深度交替神經網路以當前的棋盤情況作為輸入，生成可能的未來變化分布。研究人員將 19x19 的棋盤視為帶有不同通道的 19x19 像素圖片，每個通道的編碼承載一種棋盤信息。

表 1. 用於 DANN 的輸入特徵通道

圖 2：DANN（右）和 DCNN（左）的比較。

長期評估模塊

DANN 給出了下一步的可能性分布，而長期評估模塊則進一步加強了模型的性能，因為僅預測下一步會限制低層神經網路的信息獲取。此外，在激烈的局面和對殺情況下，很多情況會讓系統難以評估。當局部變化得到解決後，我們需要準確的判斷。此前已有一些研究將遊戲視為視覺環境下人工智慧代理面臨的連續決策過程。在這裡，研究人員使用了類似的理念，通過計算未來可能交互行動的累積獎勵來評估下一步的位置。結合此前的概率評估，系統得到了下一步可能的分數，並確定最終的落子位置。

圖 3：用於長期評估的循環模型

表 3：新系統和之前的成果（開源引擎）之間的勝率比較

棋力

研究人員使用了一些開源的圍棋程序對新方法和基準方法進行了測試。所有對戰程序都被調至了最高難度，每步的 rollout 數量固定。在實驗中，新的方法與 GnuGo 3.8 level 10、MoGo、Pachi 11.99（帶有模式文件）以及 Fuego 1.1 等方法進行了比較。在每類對戰中，共進行三組 100 場的對弈。上表顯示了對戰的勝率，所有比賽均採用中國圍棋規則。結果顯示，新的方法在大多數情況下佔據優勢，但性能略低于田淵棟等人 2016 年在 Facebook 的研究。

作者表示，未來的研究方向包括進一步改進 DANN 的結構以更好預測未來步驟，更可靠的 LTE 應用等。此外，來自計算機視覺領域的殘差網路也有可能幫助 DANN 獲得性能提升。在長期評估方面，圍棋知識可為下一步棋的選位提供更有效的估計。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！