蒙特卡洛樹搜索:

?MCTS使用蒙特卡洛模擬來估計每個節點的價值. 其默認策略為貪婪算法, 即每次選擇價值最高的節點進行模擬, 在每次模擬得到結果后, 將結果反饋回每個上級節點, 更新節點價值. 通常來講, 每個訪問到的節點都會加入到樹中, 實際上為了節省內存每次只加入一個子節點, 可以通過對舊節點剪枝或多次模擬后再加入新節點來進一步節省內存.
　　
?貪婪算法的缺點在于對于一個節點, 如果產生了一次或幾次不利的結果后, 搜索樹就會避開訪問這個節點, 這意味著搜索樹的廣度會降低, 可能會忽略更好的選擇. 這時應該選擇UCB1算法(Upper Confidence Bound), 對應節點產生的價值為:

?其中C為搜索規模常數, 當C取值越大, 樹越偏向廣度搜索, 越小就越偏向深度搜索.

?AMAF(all moves as first) 算法的核心思想是每一步落子有一個恒定的價值, 不管是什么時候落下的.

?當給定狀態s, 模擬出期望結果z, 選取a作為后續落子, AMAF value計算為:

?當第i次模擬時, 動作a被執行, 得到狀態s時返回1, 否則則返回0

?RAVE(rapid action value estimation) 算法融合了蒙特卡洛樹搜索和AMAF算法, 它不計算蒙特卡洛價值, 而是計算AMAF價值. 其核心思想是歸納整個子樹, 即動作a的價值在狀態s下, 或者在子樹中其他狀態下都一樣, 即a的價值是在所有情況下估計得到而不是執行動作時候得到.

?如圖, 當使用蒙特卡洛價值估計時, 在s狀態下, 如果走a, 會導致兩次失敗, 價值為0/2, 如果走b, 會有兩次成功一次失敗, 價值為2/3, 則會選擇走b. 當使用AMAF算法價值估計時, 在s狀態下, 如果走a, 會有三次成功和兩次失敗包含動作a, 價值為3/5, 如果走b, 會有兩次成功和三次失敗包含動作b, 價值為2/5.

?RAVE和AMAF算法得到價值會有一定誤差但是運行速度較快.

總結

以上是生活随笔為你收集整理的Pachi中的蒙特卡洛树搜索,AMAF,Rave的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。