與 AI 博弈：從 AlphaGo 到 MuZero（三）

• AlphaGo 論文地址：https://www.nature.com/articles/nature16961
• AlphaGo Zero 論文地址：https://www.nature.com/articles/nature24270
• AlphaZero 論文地址：https://arxiv.org/abs/1712.01815
• MuZero 論文地址：https://arxiv.org/abs/1911.08265

DeepMind 官網(wǎng)介紹：https://deepmind.com/research/case-studies/alphago-the-story-so-far

4. AlphaZero

2017 年底，DeepMind 推出了 AlphaZero，這是一個從零開始自學如何掌握國際象棋、日本將棋（Shogi）和圍棋游戲的單一系統(tǒng)，在這些游戲中都能擊敗世界冠軍程序。并且人類在 AlphaZero 的游戲中看到了一種開創(chuàng)性的、高度動態(tài)的、非傳統(tǒng)的游戲風格，與之前的任何游戲程序都與眾不同。

AlphaGo Zero 算法在圍棋比賽中取得了超人的表現(xiàn)，它通過使用深度卷積神經(jīng)網(wǎng)絡來表示圍棋知識，該網(wǎng)絡完全是通過從自我博弈中進行強化學習來訓練的。而 AlphaZero 應用了一個類似但通用的算法。

1997 年，深藍在國際象棋擊敗了人類世界冠軍，實現(xiàn)了人工智能的里程碑。在接下來的二十年里，計算機國際象棋程序繼續(xù)穩(wěn)步超越人類水平。這些程序使用專家手工制作的特征和仔細調整的權重來評估位置，并結合高性能的 alpha-beta 搜索，該搜索使用大量巧妙的啟發(fā)式方法和特定領域的適應來擴展龐大的搜索樹。

就計算的復雜性而言，將棋是一個比國際象棋難得多的游戲：它是在一個更大的棋盤上進行的，任何被吃掉的對手的棋子都會改變方向，并可能次第地被丟在棋盤的任何地方。之前最強的將棋程序，如計算機象棋協(xié)會（CSA）的世界冠軍 Elmo，最近才打敗了人類冠軍。這些程序使用與計算機國際象棋程序類似的算法，同樣是基于高度優(yōu)化的 alpha-beta 搜索引擎和許多特定領域的適應性。

圍棋非常適合 AlphaGo 中使用的神經(jīng)網(wǎng)絡架構，因為游戲規(guī)則是平移不變的（與卷積網(wǎng)絡的權重共享結構相匹配），以棋盤上各點之間的相鄰關系所對應的自由度來定義（與卷積網(wǎng)絡的局部結構相匹配），并且是旋轉和反射對稱的（允許數(shù)據(jù)增強和組合）。此外，行動空間很簡單（在每個可能的位置都可以放置一塊棋子），游戲結果被限制為二進制的勝利或失敗，這兩點都有助于神經(jīng)網(wǎng)絡的訓練。

國際象棋和將棋不太適合 AlphaGo 的神經(jīng)網(wǎng)絡結構。這些規(guī)則與位置有關和不對稱。規(guī)則包括遠距離的互動。國際象棋的行動空間包括棋盤上所有棋手棋子的所有合法目的地；將棋還允許將被吃掉的棋子放回棋盤上。國際象棋和將棋除了贏和輸之外，還可能導致平局；事實上，人們認為國際象棋的最佳解決方案是平局。

AlphaZero 是 AlphaGo Zero 的一個更通用的版本，該算法是在圍棋的背景下首次推出的。它用深度神經(jīng)網(wǎng)絡和零樣本強化學習算法（ Tabula rasa reinforcement learning ）取代了傳統(tǒng)對弈程序中使用的人工知識和特定領域的增強功能。

4.1 AlphaZero 網(wǎng)絡結構

AlphaZero 利用參數(shù)為 的深度神經(jīng)網(wǎng)絡 ，而不是人工設計的評估函數(shù)和移動排序啟發(fā)法。這個神經(jīng)網(wǎng)絡將棋盤上的位置 作為輸入，并輸出一個移動概率向量 ，其中每個行動 的成分 ，以及一個估計來自位置 的預期結果 的標量值 ，。AlphaZero 完全從自我博弈中學習這些行動概率和價值估計；然后用這些來改進其搜索。

AlphaZero 使用通用蒙特卡洛樹搜索 (MCTS) 算法，而不是具有特定領域增強功能的 alpha-beta 搜索。每次搜索都由一系列模擬的自我博弈組成，這些游戲從根到葉遍歷一棵樹。根據(jù)當前神經(jīng)網(wǎng)絡 ，每個模擬通過在每個狀態(tài) 中選擇具有低訪問次數(shù)、高移動概率和高價值（在從 中選擇 動作的模擬的葉子節(jié)點狀態(tài)上平均值）的移動 來進行。搜索返回一個向量 ，表示移動的概率分布，與根狀態(tài)的訪問計數(shù)成比例或貪心。

AlphaZero 中深度神經(jīng)網(wǎng)絡的參數(shù) 是通過自我博弈強化學習訓練的，從隨機初始化的參數(shù) 開始。通過 MCTS 為兩個玩家選擇移動來玩游戲 。游戲結束時，根據(jù)游戲規(guī)則對終局位置 進行評分，以計算游戲結果 (-1 為負，0 為平局，+1 為贏)。更新神經(jīng)網(wǎng)絡參數(shù) 以最小化預測結果 和游戲結果 之間的誤差，并使策略向量 與搜索概率 的相似度最大化。具體來說，參數(shù) 通過損失函數(shù) 的梯度下降進行調整，該損失函數(shù) 為均方誤差和交叉熵損失求和，

其中 是控制 權重正則化水平的參數(shù)。更新后的參數(shù)用于后續(xù)的自我博弈。

AlphaZero 算法在以下幾個方面與原始的 AlphaGo Zero 算法不同:

• AlphaGo Zero 估計并優(yōu)化獲勝的概率，假設二元輸贏結果。相反，AlphaZero 會估計和優(yōu)化預期結果，同時考慮平局或潛在的其他結果。
• 圍棋的規(guī)則對旋轉和反射（reflection）是不變的。AlphaGo 和 AlphaGo Zero 以兩種方式利用了這個事實。首先，通過為每個位置生成 8 個對稱點來增加訓練數(shù)據(jù)。其次，在 MCTS 搜索期間，棋盤位置在被神經(jīng)網(wǎng)絡評估之前，使用隨機選擇的旋轉或反射進行轉換，這樣蒙特卡洛評估在不同的偏差上是平均的。國際象棋和將棋的規(guī)則是不對稱的，通常來說，不能假設對稱性。AlphaZero不增加通過這種方式訓練數(shù)據(jù)，也不在 MCTS 搜索期間轉換棋盤位置。
• 在 AlphaGo Zero 中，自我博弈的棋局是由之前所有迭代中的最佳棋手生成的。在每次迭代訓練之后，新網(wǎng)絡的表現(xiàn)都要與最佳網(wǎng)絡進行比較；如果新網(wǎng)絡以 55% 的優(yōu)勢獲勝，那么它就會取代最佳網(wǎng)絡，隨后由這個新網(wǎng)絡生成自我博弈對局。相比之下，AlphaZero 只是維護了一個不斷更新的單一神經(jīng)網(wǎng)絡，而不是通過迭代完成。自我博弈通過使用該神經(jīng)網(wǎng)絡的最新參數(shù)，省略了評估步驟和最佳網(wǎng)絡的選擇。
• AlphaGo Zero 通過貝葉斯優(yōu)化調整了搜索的超參數(shù)。在 AlphaZero 中，作者為所有游戲重用相同的超參數(shù)，而無需針對游戲進行調整。唯一的例外是添加到先前策略中以確保探索的噪音；這與該游戲典型合法動作數(shù)成比例。
• AlphaZero 與 AlphaGo Zero 一樣，棋盤狀態(tài)由空間平面編碼，只基于每個游戲的基本規(guī)則。動作由空間平面或平面向量編碼，同樣僅基于每個游戲的基本規(guī)則。

4.2?AlphaZero?訓練及效果

作者將 AlphaZero 算法應用于國際象棋、將棋和圍棋。除非有特殊的設置，三款游戲均使用相同的算法設置、網(wǎng)絡架構和超參數(shù)。作者為每個游戲訓練了一個單獨的 AlphaZero 實例。訓練進行了 700,000 步（大小為 4,096 的小批量），從隨機初始化的參數(shù)開始，使用 5,000 個第一代 TPU 生成自玩游戲，并使用 64 個第二代 TPU 來訓練神經(jīng)網(wǎng)絡。

在國際象棋中，AlphaZero 在 4 小時后首次超越 Stockfish；在將棋中，AlphaZero 在 2 小時后首次超越了 Elmo；而在圍棋中，AlphaZero 在 30 小時后首次超越了 2016 年擊敗傳奇棋手李世石的 AlphaGo 版本。每個訓練步驟代表 4,096 個棋盤位置。

在每次評估中，AlphaZero 都毫無懸念地擊敗了其他冠軍程序：

• 在國際象棋中，AlphaZero 擊敗了 2016 年 TCEC（第 9 季）世界冠軍 Stockfish，贏得了 155 場比賽，但在 1,000 場比賽中僅輸了 6 場。為了驗證 AlphaZero 的穩(wěn)健性，作者還進行了一系列的比賽，從常見的人類開局開始。在每個開局中，AlphaZero 都擊敗了 Stockfish。作者還玩了一場從 2016 年 TCEC 世界錦標賽中使用的開局位置開始的比賽，同時還進行了一系列額外的比賽，對陣的是 Stockfish 的最新開發(fā)版本，以及使用強大開局的 Stockfish 變體。在所有的比賽中，AlphaZero 都贏了。
• 在將棋中，AlphaZero 擊敗了 2017 年 CSA 世界冠軍版的 Elmo，贏得了 91.2% 的比賽。
• 在圍棋中，AlphaZero 擊敗了 AlphaGo Zero，贏得了 61% 的對局。

值得關注的是對于每一步，AlphaZero 只搜索傳統(tǒng)國際象棋引擎考慮的一小部分位置。例如，在國際象棋中，它每秒僅搜索 6 萬個國際象棋位置，而 Stockfish 大約為 6000 萬個。

參考資料

• http://tromp.github.io/go.html
• https://towardsdatascience.com/the-upper-confidence-bound-ucb-bandit-algorithm-c05c2bf4c13f
• https://en.wikipedia.org/wiki/AlphaGo
• https://deepmind.com/blog/article/alphago-zero-starting-scratch
• https://towardsdatascience.com/the-evolution-of-alphago-to-muzero-c2c37306bf9