蒙特卡罗树搜索的UCT实现

Question

你能给我解释一下怎么做这棵树吗？

我非常理解节点是如何选择的，但一个更好的解释会真正帮助我实现这个算法。我已经有了一个代表游戏状态的棋盘，但我不知道(理解)如何生成树。

有没有人能给我介绍一个注释良好的算法实现(我需要将其用于AI)？或者更好的解释/例子？

我在网上没有找到很多资源，这个算法是比较新的…

Answer 1

生成树的最佳方法是一系列随机播放。诀窍是能够在探索和利用之间取得平衡(这就是UCT的用武之地)。这里有一些很好的代码示例和大量的研究论文参考：https://web.archive.org/web/20160308043415/http://mcts.ai:80/index.html

当我实现该算法时，我使用随机播放，直到到达终点或终止状态。我有一个静态评估函数，它将计算在这一点上的回报，然后从这一点上的分数被传播回树。每个玩家或“团队”都假设对方将为自己打出最好的走法，而为对手打出尽可能最差的走法。

我还建议查看Chaslot的论文和他的博士论文，以及参考他的工作的一些研究(基本上是从那时起MCTS的所有工作)。

例如:玩家1的第一步可以模拟未来的10步，玩家1的移动和玩家2的移动交替进行。每次你都必须假设对方球员会试图最小化你的得分，同时最大化他们自己的得分。有一个完整的领域以此为基础，被称为博弈论。一旦您模拟到10个游戏的结束，您将再次从起点迭代(因为只模拟一组决策是没有意义的)。必须对树的每个分支进行评分，其中分数沿树向上传播，并且分数表示进行模拟的玩家的最佳可能回报，假设其他玩家也在为自己选择最好的动作。

MCTS由四个战略步骤组成，只要还有时间就重复执行。具体步骤如下。

1. 在选择步骤中，树从根节点开始遍历，直到我们到达节点E，在那里我们选择了一个尚未添加到树中的位置。
2. 接下来，在出局步骤中，移动是在自我发挥中进行的，直到游戏结束。这个“模拟”游戏的结果R是+1，如果布莱克获胜(LOA中的第一个玩家)，如果是平局，结果R是0，如果是怀特获胜，结果是−1。
3. 随后，在扩展步骤中，将E的子项添加到树中。
4. 最后，在反向传播步骤中，R沿着从E到根节点的路径传播回来。当时间到时，程序播放的移动是具有最高值的根的子代。(此示例摘自本文- PDF

www.ru.is/faculty/yngvi/pdf/WinandsBS08.pdf

下面是一些实现：

使用一些MCTS实现的库和游戏的列表http://senseis.xmp.net/?MonteCarloTreeSearch

和一个名为Fuego http://fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/group__sguctgroup.html的独立于游戏的开源UCT库

Answer 2

来自http://mcts.ai/code/index.html

Below are links to some basic MCTS implementations in various
programming languages. The listings are shown with timing, testing
and debugging code removed for readability.

Java

Python

Answer 3

如果你感兴趣，我写了这篇文章：https://github.com/avianey/mcts4j