RAVE (Rapid Action Value Estimation)
Reference
Sylvain Gelly, David Silver, Monte-Carlo tree search and rapid action value estimation in computer Go, Artificial Intelligence, Volume 175, Issue 11, 2011, Pages 1856-1875, ISSN 0004-3702 https://doi.org/10.1016/j.artint.2011.03.007.
RAVE (Rapid Action Value Estimation)
RAVE 是一種 MCTS 的增強方法。做 MCTS 時，我們會藉由 rollout 等方式得到一個葉節點的 reward，並向上更新 Q(s,a)：在狀態 s 執行 a 的期望（平均）報酬。更新算法如下，造訪次數 N 和平均報酬 Q 都會進行更新。下次 selection 階段會用 Q 和探索項來選擇節點。
AMAF (All moves as first)
這是 RAVE 主要的概念，它是一種 heuristic。像是圍棋這種一顆一顆下的遊戲，一個 move 的 value 常常不太會受到其它 move 的影響，每個 move 應該都有其 general value。同樣一個 move，現在做和晚點做的期望報酬可能不會差太多，所以晚點做的報酬拿來當成現在做的報酬有一定的合理性。假設你在下圍棋並執黑子，這回合 (1,1) 這個位置可以下，下次又換你的回合時 (1,1) 假設還能下，那這兩次 (1,1) 的下法期望值可能不會差太多，所以如果你晚點才下 (1,1)，它的 reward 也能一定程度在當前回合使用。聽起來很繞口，直接來看論文裡的例子：
Q 指的是一般的平均報酬；~Q 指的是利用 AMAF 計算的平均報酬。它計算 ~Q(s,a) 時把 s 狀態下的 a 全部算進去，圖中五個分支都有 a 這個 move，其中三個報酬是 1，所以 ~Q(s,a) = 3/5。以這個例子來看，用一般 MCTS 的方法算起來 b 比 a 的平均報酬高，但用 AMAF 算的話是 a 比 b 高。
狀態 s 是黑色的回合，但有些 a 是白色下的， 把白色下的 a 也算進去看起來滿不可思議的。其實實作上的設計要看遊戲特性，我們用 RAVE 的目的是想要盡可能利用 subtree 的資訊。如果白色下 a 之後白色獲勝，那 a 這一步是不是很重要？把白色下的 a 拿來使用是不是也有價值？又或者，如果是這個遊戲是只要有人下 a 黑就會贏，那把白色下的 a 拿來更新是不是就合理？不同的應用場景會有不同細節設計。
MC-RAVE
用 RAVE 估的 ~Q 有時候會出錯，MC-RAVE 的設計降低了這個問題的影響：設立一個權重 β，隨著樹長越大 ~Q 的比重會逐漸上升。
至於 β 怎麼定有不同的方法：
Hand-selected schedule：當 N(s) 趨近 k 時，β 會趨近於 1/2，也就是 Q 和 ~Q 各有 1/2 的比重。
另一是：
這個推導稍稍複雜一些，有興趣可以看論文原文。