蒙特卡羅樹搜索，反向傳播（備份）步驟：爲什麼要改變獎勵值的角度？

我一直在閱讀Browne等人的Monte Carlo Tree Search調查報告。人：蒙特卡羅樹搜索，反向傳播（備份）步驟：爲什麼要改變獎勵值的角度？

http://ccg.doc.gold.ac.uk/papers/browne_tciaig12_1.pdf

「蒙特卡洛樹搜索方法綜述」

我與頁上的只是一片僞代碼的摔跤。 9.我的問題在Backup和BackupNegamax函數中都以類似的形式出現。

假設我是2人零和遊戲中的玩家1。（所以，使用BackupNegamax函數。）輪到我了，我正在使用MCTS來選擇我的移動。在BackupNegamax中，爲什麼在備份樹時，delta值被否定了？我明白，在雙人零和遊戲中，如果獎勵是玩家1（我）的三角洲，那麼它是 - 玩家2的三角。但是不應該從玩家1的角度來看整個樹？（如果我沒有弄錯的話，這將類似於節點在極大極樹中的評分。）

如果Q值的角度來回切換，取決於您所在的樹的級別，這不會搞亂BestChild函數中顯示的計算嗎？具體來說，假設某個節點v具有非常高的Q值，因爲它經常導致玩家1的高回報。給定的僞代碼似乎表明v的父母，我將稱之爲u，可能會有非常低的負數）Q值（當然你的Q值也會考慮到其他孩子的Q值）

所以對我來說，u（父母）的Q值非常低，v孩子）有一個非常高的。我知道v是來自玩家1在僞代碼中的角度，而u是來自玩家2的角度，但我的問題是爲什麼。爲什麼不是從播放器1的角度存儲節點的Q值？這樣，u和v都將具有高Q值，因此具有很高的開採評級，並且根據BestChild函數，它們都被認爲對進一步開發具有價值。

（我在MCTS來從極小的經驗，並在極小整個樹是從最大的角度來看，這就是爲什麼我用不同的想法在這裏掙扎。）

我的問題也適用於備份 - 爲什麼每個Q值都根據樹中該層的玩家角度更新，而不是從「我的」角度更新一切？

我希望我的問題已經很清楚了。非常感謝您的幫助！

來源

2015-05-28 Bob Smith

我也很困惑這個想法。 – alexzzp

有兩種方式來描述這種機制：

全局：從根玩家的角度看，這種情況下在每個第二層上的播出值被否定，因爲對手是作用在根球員。
本地：從剛剛移動到每一層的玩家的角度來看，在這種情況下，玩家的價值不會被消除，因爲每個玩家都會嘗試最大化自己的獎勵。

標準公式使用選項1，因爲它更容易描述，並且在雙人組合遊戲中有其基礎。但是，我傾向於在我的實際實施中使用第二個公式，因爲它更靈活;它處理與兩個以上玩家的遊戲，少於兩個玩家，可變移動次序，多部分移動，合作目標等。

這只是證實了其他答案中所說的內容。

來源

2015-05-29 05:22:15

有兩種方式來看待MCTS算法：

從根玩家的角度看。
從剛搬家的玩家角度來看。

我發現方式1更受歡迎。例如維基百科explanation使用它。

使用方式1的參考MCTS實現：C++，Java。

來源

2015-05-28 14:30:18

這是有道理的，我是如何理解事情的工作。那麼我的問題是如何理解Browne等人在論文中指出的BackupNegamax僞代碼函數。人。這是一篇經典的論文，所以我不認爲這是錯的 - 也許只是一種不同的表述？布朗的課堂筆記在http://ccg.doc.gold.ac.uk/teaching/ludic_computing/ludic16.pdf，p。關於後向傳播，也建議否定每層的價值。 –

@BobSmith確實，這沒有錯，它只是一個不同的表述。 –

java示例鏈接消失了 – alexzzp

我一直與MCTS混淆了一段時間，特別是反向傳播部分。如果每個節點的勝利值（稱爲Q）用於指示當前節點的玩家贏家時間。在每個非可擴展節點中，我們選擇最大的UCT節點。它怎麼會是一個好的選擇？考慮以下兩個玩家的遊戲，完整的樹是這樣的：

A /| \ B1 B2 B3 | A1

在樹B1，B3是B贏得終端節點，而B2只有一個選擇，導致甲A奪冠終端節點A1。

如果我們caculate的比賽中MCTS方法，結果就會像下圖：

所以最好的選擇將是B1或B3爲A，這是荒謬的，如何解釋呢？

裁判：MCTS caculation process reference

來源

2016-10-16 08:44:03 alexzzp

的損失或贏終端的情況下，你應該使用int.max分數或分數int.lowest所以當你backpropogate虧損將有可能的最低得分，無論多麼低的樹你是，並贏得最高分

來源

2017-12-14 10:34:25 dhkts1

蒙特卡羅樹搜索，反向傳播（備份）步驟：爲什麼要改變獎勵值的角度？

回答

相關問題