本文首發於我的博客：oncemath.com

採用 BY-NC-ND 4.0 協議進行創作。轉載請遵守協議條件。

第八章對蒙特卡羅樹搜索（MCTS）這一重要演算法一帶而過，沒有仔細講解，這裡補充一點 MCTS 方面的一點介紹。

蒙特卡洛樹搜索的主要目的：給出一個『遊戲狀態』並選擇『勝率最高的下一步』。

有限兩人零和回合制遊戲

蒙特卡洛樹搜索運行的框架 / 環境是『遊戲』，其本身是一個非常抽象的廣義術語，這裡只針對於一種遊戲類型——有限兩人零和回合制遊戲：

  • 『遊戲』意味著處理互動情況。
  • 『有限』表示在任何時間點上，玩家之間都有有限的互動。
  • 『兩人』表示參與者只有兩位。
  • 『回合制』表示玩家按照一定順序進行遊戲。
  • 『零和遊戲』意味著遊戲雙方有著相反的目標，換句話說：在遊戲的任何終結狀態下，所有玩家獲得的總和等於零。有時這樣的遊戲也被稱為嚴格競爭博弈。

圍棋、國際象棋等都是有限兩人零和回合制遊戲。

為何採用 MCTS ？

MCTS其實是在線規劃（online planning）的一種，從當前局面出發，以非參數方式估計局部 Q 函數，然後用局部 Q 函數估計去決定下一次採取哪個 action 。

由於是規劃（planning），MCTS的限制就是得要知道環境的全部信息，即有完美的前向模型（forward model），這樣才能知道走完一步後是什麼狀態。圍棋這類『有限兩人零和回合制遊戲』因為規則固定，狀態清晰，有完美快速的前向模型，所以 MCTS是 個好的選擇。

如何表徵一個博弈

可以使用一種著名的數據結構以簡單的形式來表徵一個博弈：博弈樹。

在上圖的井字棋博弈樹（部分展示）的例子中：

  • 頂部為樹的根節點，表示井字棋博弈的初始狀態，即空白棋盤（標記為綠色）；
  • 任何從一個節點向另一個節點的轉換被稱為一個 action ；
  • 井字棋的分支因子是變化的，它依賴於樹的深度；
  • 從一個根節點到一個端節點的樹遍歷表徵了單個博弈過程。

MiniMax 策略和 alpha-beta 剪枝演算法

如何利用博弈樹尋找最有潛力的下一步行動？首先不能提前知道對手的策略，如果完全不瞭解對手，那麼可以使用一種非常保守的策略—— MiniMax 演算法：在假定你的對手執行最佳行動的前提下，最大化你的收益，也可以說在各種獲得最小收益的策略中選擇有最大收益的策略。

這種方法以放棄最優策略為代價，從而最小化了風險，因此它是一種非常保守的方法。在 A 和 B 的兩人有限零和序列博弈中（其中 A 嘗試最大化其收益，而 B 嘗試最小化 A 的收益），極小極大演算法可以用以下的遞歸形式來描述：

egin{aligned} v_A(s_i)=max_{a_i}v_B(mathrm{move}(s_i,a_i))\ v_B(s_i)=min_{a_i}v_A(mathrm{move}(s_i,a_i)) end{aligned}

其中：

  • v_A 和 v_B 分別是玩家 A 和玩家 B 的收益函數
  • move 是一個函數，它在給定當前狀態 s_i 和在該狀態的動作 a_i 下，生成下一個博弈狀態（當前節點的子節點之一）

簡單來說，給定狀態 s，並假定對手嘗試最小化你的收益，你希望找到能最大化收益的動作 a_i 。我們需要做的就是展開整個博弈樹，並反向傳播由遞歸形式的規則得到的值。

上圖中的博弈樹展示了極小極大演算法中的最佳行動選擇過程。白棋希望博弈的結果儘可能黑，而黑棋希望博弈的結果儘可能白。

  • 每一個層級的選擇都是極小極大判斷的最優結果。我們可以從底部的終端節點開始，其中的選擇是很明顯的。黑棋將總是選擇最明亮的顏色，然後白棋將尋找最大的獎勵並選擇到達最暗顏色的路徑。
  • 極小極大演算法的最大弱點是它需要展開整個博弈樹。對於有高分支因子的博弈（例如圍棋或國際象棋），該演算法將導致巨大的博弈樹，使得計算無法進行。

兩種解決辦法：

  1. 僅在確定的深度 d 內展開博弈樹，但是需要一個函數來評估非終端博弈狀態。
  2. 通過 alpha-beta 剪枝演算法來修剪博弈樹。alpha-beta 剪枝是提升版的極小極大演算法，它以極小極大演算法的形式遍歷博弈樹，並避免某些樹分支的展開，其得到的結果在最好的情況下等於極小極大演算法的結果。alpha-beta 剪枝通過壓縮搜索空間提高搜索效率。

蒙特卡洛樹搜索的基本概念

蒙特卡洛樹搜索的主要概念是搜索，即沿著博弈樹向下的一組遍歷過程。顧名思義，蒙特卡洛樹搜索會多次模擬博弈，並嘗試根據模擬結果預測最優方案。

模擬

模擬即單次博弈策略，在模擬中，行動可以通過 rollout 策略函數選擇：

ext{RolloutPolicy:} s_i ightarrow a_i

該函數將輸入一個博弈狀態，併產生下一次行動的選擇。在實踐中，該函數會設計為允許很多次模擬快速進行，一般默認的 rollout 策略函數可以是服從均勻分佈的隨機採樣。

def rollout(node):
while non_terminal(node):
node = rollout_policy(node)
return result(node)

def rollout_policy(node):
return pick_random(node.children)

博弈樹的展開節點、完全展開節點和訪問節點

給定一個根節點並加上博弈的規則，那麼博弈樹的其餘部分就已經隱含表示出來了。我們可以遍歷它而不需要將整棵樹儲存在內存中。

在最初的根節點中，它是完全未展開的，其餘所有節點都沒有被訪問。一旦需要執行一個行動，就需要考慮之後會產生怎樣的結果，因此訪問一個節點後，需要分析該節點帶來的效用。

所有節點可以分為訪問或未訪問，如果某節點的所有子節點都是已訪問節點，那麼它就可視為完全展開的節點，反之未完全展開的節點。

在實踐中，搜索開始時，根節點的所有子節點都未被訪問。然後一個節點被選中，第一個模擬（評估）就開始了。

需要注意，模擬過程中 rollout 策略函數選擇的節點並未被訪問，只有模擬起始節點是被訪問的狀態。

反向傳播：將模擬結果傳播回去

當初次訪問節點的模擬結束後，其結果會反向傳播至當前博弈樹的根節點，模擬開始的節點被標註為已訪問。

反向傳播是從子節點（模擬開始的地方）遍歷回根節點。模擬結果被傳輸至根節點，反向傳播路徑上的每個節點的統計數據都被計算／更新。

反向傳播保證每個節點的數據都會反映開始於其所有子節點的模擬結果。

def backpropagate(node, result):
if is_root(node) return
node.stats = update_stats(node, result)
backpropagate(node.parent)

節點的統計數據

反向傳播模擬結果的目的是更新反向傳播路徑（包括模擬起始的節點）上所有節點 $v$ 的總模擬獎勵 Q(v) 以及總訪問次數 N(v) 。

  • Q(v)即總模擬獎勵，在最簡單的形式中是通過考慮的節點得到的模擬結果的總和。
  • N(v)即總訪問次數，表示節點 v 位於反向傳播路徑上的次數（即它對總模擬獎勵做出了多少次貢獻）。

每個被訪問節點都會保存這兩個值，一旦完成了確定次數的模擬之後，被訪問的節點就保存了它們被利用/探索（expolited/explored）的信息。

這兩個值將反映該節點的潛在價值（總模擬獎勵）和它被探索的程度（總訪問次數）。高獎勵的節點是很好的可利用候選，而那些訪問次數少的節點也可能是有價值的（因為它們尚未得到很好的探索）。

博弈樹遍歷

如何從一個根節點到達一個未訪問節點，來啟動一次模擬？在搜索最開始的時候，由於我們還沒有進行任何模擬，所以先選擇未被訪問的節點。在每個未被訪問的節點上進行單次模擬，結果被反向傳播至根節點，然後根節點即被認為經過了完全展開。

但是接下來怎麼做呢？現在我們如何從完全展開的節點導向未被訪問的節點呢？我們必須遍歷被訪問節點的層，目前沒有很好的繼續進行的方式。

為了在路徑中找到下一個節點，以通過完全展開的節點 v 開始下一次模擬，我們需要考慮 v 所有子節點 v_1, v_2, …, v_k 的信息，以及節點 v 本身的信息。現在我們來思考一下可用信息有哪些：

當前節點（藍色）是完全展開的，因此它必須經過訪問，以存儲節點數據：它及其子節點的總模擬獎勵和總訪問次數。這些值是為了最後一部分：樹的置信上限（UCT）做準備。

樹的置信上限

UCT 是一個函數，使我們在被訪問節點中選擇下一個要遍歷的節點，這也是蒙特卡洛樹搜索的核心函數：

mathbb{UCT}(v_i,v)=frac{Q(v_i)}{N(v_i)}+csqrt{frac{log(N(v))}{N(v_i)}}

UCT 最大的節點就是蒙特卡洛樹搜索遍歷過程中選擇的節點，該函數關於節點 v 及其子節點 v_i 定義，包括兩個部分：

  • dfrac{Q(v_i)}{N(v_i)} ， exploitation
  • csqrt{frac{log(N(v))}{N(v_i)}} ，exploration

參數 c 控制蒙特卡洛樹搜索中 expolitation 和 exploration 部分之間的權衡。

def traverse(node):
while fully_expanded(node):
node = best_uct(node)
return pick_unvisted(node.children) or node

終止蒙特卡洛樹搜索

MCTS 的終止時間需要結合問題背景來確定。

  • 如果『思考時間』有限，或計算能力有限，則需要給定一個深度閾值。
  • 如果資源允許，可以考慮一直運行 MCTS。

一旦 MCTS 過程結束，最好的一步通常是具備最高訪問量 N(v_i) 的一步，因為它的獎勵值評估結果最好（評估值必然很高，因為它被探索的頻率最高）。

def best_child(node):
pick child with highest number of visits
def monte_carlo_tree_search(root):
while resources_left(time,computational power):
leaf = traverse(root)
simulation_result = rollout(leaf)
backpropagate(leaf, simulation_result)
return best_child(root)

本文首發於我的博客：

MCTS - ONCE.MATH?

oncemath.com圖標

採用 BY-NC-ND 4.0 協議進行創作。轉載請遵守協議條件。


推薦閱讀：
相關文章