與 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，這是一個從零開始自學(xué)如何掌握國際象棋、日本將棋（Shogi）和圍棋游戲的單一系統(tǒng)，在這些游戲中都能擊敗世界冠軍程序。并且人類在 AlphaZero 的游戲中看到了一種開創(chuàng)性的、高度動態(tài)的、非傳統(tǒng)的游戲風(fēng)格，與之前的任何游戲程序都與眾不同。
AlphaGo Zero 算法在圍棋比賽中取得了超人的表現(xiàn)，它通過使用深度卷積神經(jīng)網(wǎng)絡(luò)來表示圍棋知識，該網(wǎng)絡(luò)完全是通過從自我博弈中進行強化學(xué)習(xí)來訓(xùn)練的。而 AlphaZero 應(yīng)用了一個類似但通用的算法。
1997 年，深藍(lán)在國際象棋擊敗了人類世界冠軍，實現(xiàn)了人工智能的里程碑。在接下來的二十年里，計算機國際象棋程序繼續(xù)穩(wěn)步超越人類水平。這些程序使用專家手工制作的特征和仔細(xì)調(diào)整的權(quán)重來評估位置，并結(jié)合高性能的 alpha-beta 搜索，該搜索使用大量巧妙的啟發(fā)式方法和特定領(lǐng)域的適應(yīng)來擴展龐大的搜索樹。
就計算的復(fù)雜性而言，將棋是一個比國際象棋難得多的游戲：它是在一個更大的棋盤上進行的，任何被吃掉的對手的棋子都會改變方向，并可能次第地被丟在棋盤的任何地方。之前最強的將棋程序，如計算機象棋協(xié)會（CSA）的世界冠軍 Elmo，最近才打敗了人類冠軍。這些程序使用與計算機國際象棋程序類似的算法，同樣是基于高度優(yōu)化的 alpha-beta 搜索引擎和許多特定領(lǐng)域的適應(yīng)性。
圍棋非常適合 AlphaGo 中使用的神經(jīng)網(wǎng)絡(luò)架構(gòu)，因為游戲規(guī)則是平移不變的（與卷積網(wǎng)絡(luò)的權(quán)重共享結(jié)構(gòu)相匹配），以棋盤上各點之間的相鄰關(guān)系所對應(yīng)的自由度來定義（與卷積網(wǎng)絡(luò)的局部結(jié)構(gòu)相匹配），并且是旋轉(zhuǎn)和反射對稱的（允許數(shù)據(jù)增強和組合）。此外，行動空間很簡單（在每個可能的位置都可以放置一塊棋子），游戲結(jié)果被限制為二進制的勝利或失敗，這兩點都有助于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練。
國際象棋和將棋不太適合 AlphaGo 的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。這些規(guī)則與位置有關(guān)和不對稱。規(guī)則包括遠(yuǎn)距離的互動。國際象棋的行動空間包括棋盤上所有棋手棋子的所有合法目的地；將棋還允許將被吃掉的棋子放回棋盤上。國際象棋和將棋除了贏和輸之外，還可能導(dǎo)致平局；事實上，人們認(rèn)為國際象棋的最佳解決方案是平局。
AlphaZero 是 AlphaGo Zero 的一個更通用的版本，該算法是在圍棋的背景下首次推出的。它用深度神經(jīng)網(wǎng)絡(luò)和零樣本強化學(xué)習(xí)算法（ Tabula rasa reinforcement learning ）取代了傳統(tǒng)對弈程序中使用的人工知識和特定領(lǐng)域的增強功能。
4.1 AlphaZero 網(wǎng)絡(luò)結(jié)構(gòu)
AlphaZero 利用參數(shù)為 的深度神經(jīng)網(wǎng)絡(luò) ，而不是人工設(shè)計的評估函數(shù)和移動排序啟發(fā)法。這個神經(jīng)網(wǎng)絡(luò)將棋盤上的位置 作為輸入，并輸出一個移動概率向量 ，其中每個行動 的成分 ，以及一個估計來自位置 的預(yù)期結(jié)果 的標(biāo)量值 ，。AlphaZero 完全從自我博弈中學(xué)習(xí)這些行動概率和價值估計；然后用這些來改進其搜索。
AlphaZero 使用通用蒙特卡洛樹搜索 (MCTS) 算法，而不是具有特定領(lǐng)域增強功能的 alpha-beta 搜索。每次搜索都由一系列模擬的自我博弈組成，這些游戲從根到葉遍歷一棵樹。根據(jù)當(dāng)前神經(jīng)網(wǎng)絡(luò) ，每個模擬通過在每個狀態(tài) 中選擇具有低訪問次數(shù)、高移動概率和高價值（在從 中選擇 動作的模擬的葉子節(jié)點狀態(tài)上平均值）的移動 來進行。搜索返回一個向量 ，表示移動的概率分布，與根狀態(tài)的訪問計數(shù)成比例或貪心。
AlphaZero 中深度神經(jīng)網(wǎng)絡(luò)的參數(shù) 是通過自我博弈強化學(xué)習(xí)訓(xùn)練的，從隨機初始化的參數(shù) 開始。通過 MCTS 為兩個玩家選擇移動來玩游戲 。游戲結(jié)束時，根據(jù)游戲規(guī)則對終局位置 進行評分，以計算游戲結(jié)果 (-1 為負(fù)，0 為平局，+1 為贏)。更新神經(jīng)網(wǎng)絡(luò)參數(shù) 以最小化預(yù)測結(jié)果 和游戲結(jié)果 之間的誤差，并使策略向量 與搜索概率 的相似度最大化。具體來說，參數(shù) 通過損失函數(shù) 的梯度下降進行調(diào)整，該損失函數(shù) 為均方誤差和交叉熵?fù)p失求和，
其中 是控制 權(quán)重正則化水平的參數(shù)。更新后的參數(shù)用于后續(xù)的自我博弈。
AlphaZero 算法在以下幾個方面與原始的 AlphaGo Zero 算法不同:
AlphaGo Zero 估計并優(yōu)化獲勝的概率，假設(shè)二元輸贏結(jié)果。相反，AlphaZero 會估計和優(yōu)化預(yù)期結(jié)果，同時考慮平局或潛在的其他結(jié)果。 圍棋的規(guī)則對旋轉(zhuǎn)和反射（reflection）是不變的。AlphaGo 和 AlphaGo Zero 以兩種方式利用了這個事實。首先，通過為每個位置生成 8 個對稱點來增加訓(xùn)練數(shù)據(jù)。其次，在 MCTS 搜索期間，棋盤位置在被神經(jīng)網(wǎng)絡(luò)評估之前，使用隨機選擇的旋轉(zhuǎn)或反射進行轉(zhuǎn)換，這樣蒙特卡洛評估在不同的偏差上是平均的。國際象棋和將棋的規(guī)則是不對稱的，通常來說，不能假設(shè)對稱性。AlphaZero不增加通過這種方式訓(xùn)練數(shù)據(jù)，也不在 MCTS 搜索期間轉(zhuǎn)換棋盤位置。 在 AlphaGo Zero 中，自我博弈的棋局是由之前所有迭代中的最佳棋手生成的。在每次迭代訓(xùn)練之后，新網(wǎng)絡(luò)的表現(xiàn)都要與最佳網(wǎng)絡(luò)進行比較；如果新網(wǎng)絡(luò)以 55% 的優(yōu)勢獲勝，那么它就會取代最佳網(wǎng)絡(luò)，隨后由這個新網(wǎng)絡(luò)生成自我博弈對局。相比之下，AlphaZero 只是維護了一個不斷更新的單一神經(jīng)網(wǎng)絡(luò)，而不是通過迭代完成。自我博弈通過使用該神經(jīng)網(wǎng)絡(luò)的最新參數(shù)，省略了評估步驟和最佳網(wǎng)絡(luò)的選擇。 AlphaGo Zero 通過貝葉斯優(yōu)化調(diào)整了搜索的超參數(shù)。在 AlphaZero 中，作者為所有游戲重用相同的超參數(shù)，而無需針對游戲進行調(diào)整。唯一的例外是添加到先前策略中以確保探索的噪音；這與該游戲典型合法動作數(shù)成比例。 AlphaZero 與 AlphaGo Zero 一樣，棋盤狀態(tài)由空間平面編碼，只基于每個游戲的基本規(guī)則。動作由空間平面或平面向量編碼，同樣僅基于每個游戲的基本規(guī)則。
4.2?AlphaZero?訓(xùn)練及效果
作者將 AlphaZero 算法應(yīng)用于國際象棋、將棋和圍棋。除非有特殊的設(shè)置，三款游戲均使用相同的算法設(shè)置、網(wǎng)絡(luò)架構(gòu)和超參數(shù)。作者為每個游戲訓(xùn)練了一個單獨的 AlphaZero 實例。訓(xùn)練進行了 700,000 步（大小為 4,096 的小批量），從隨機初始化的參數(shù)開始，使用 5,000 個第一代 TPU 生成自玩游戲，并使用 64 個第二代 TPU 來訓(xùn)練神經(jīng)網(wǎng)絡(luò)。
在國際象棋中，AlphaZero 在 4 小時后首次超越 Stockfish；在將棋中，AlphaZero 在 2 小時后首次超越了 Elmo；而在圍棋中，AlphaZero 在 30 小時后首次超越了 2016 年擊敗傳奇棋手李世石的 AlphaGo 版本。每個訓(xùn)練步驟代表 4,096 個棋盤位置。
在每次評估中，AlphaZero 都毫無懸念地?fù)魯×似渌谲姵绦?/strong>：
在國際象棋中，AlphaZero 擊敗了 2016 年 TCEC（第 9 季）世界冠軍 Stockfish，贏得了 155 場比賽，但在 1,000 場比賽中僅輸了 6 場。為了驗證 AlphaZero 的穩(wěn)健性，作者還進行了一系列的比賽，從常見的人類開局開始。在每個開局中，AlphaZero 都擊敗了 Stockfish。作者還玩了一場從 2016 年 TCEC 世界錦標(biāo)賽中使用的開局位置開始的比賽，同時還進行了一系列額外的比賽，對陣的是 Stockfish 的最新開發(fā)版本，以及使用強大開局的 Stockfish 變體。在所有的比賽中，AlphaZero 都贏了。 在將棋中，AlphaZero 擊敗了 2017 年 CSA 世界冠軍版的 Elmo，贏得了 91.2% 的比賽。 在圍棋中，AlphaZero 擊敗了 AlphaGo Zero，贏得了 61% 的對局。
值得關(guān)注的是對于每一步，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