java - 蒙特卡洛树搜索 UCT 实现

Question

你能解释一下如何构建树吗？

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

有人能给我指出一个评论很好的算法实现吗(我需要将它用于人工智能)？或者更好的解释/例子？

网上没找到很多资源，这个算法比较新……

Answer 1

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

当我实现算法时，我使用随机播放，直到达到终点或终止状态。我有一个静态评估函数，可以计算此时的 yield ，然后从这一点开始的分数被传播回树。每个玩家或“团队”都假设对方会为自己下最好的棋，而对对手来说可能是最坏的棋。

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

---

例如:玩家 1 的第一步可以模拟 future 10 步，玩家 1 和玩家 2 交替进行。每次你必须假设对方球员会尽量减少你的分数，同时最大化他们自己的分数。有一个基于此的整个领域，称为博弈论。一旦你模拟到 10 场比赛结束，你再次从起点迭代(因为只模拟一组决策没有意义)。树的这些分支中的每一个都必须在分数向上传播的情况下进行评分，并且分数代表进行模拟的玩家可能获得的最佳返回，假设其他玩家也在为自己选择最佳 Action 。

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

1. 在选择步骤中，树从根节点，直到我们到达节点 E，在这里我们选择一个尚未添加到树中的位置。

2. 接下来，在出局步骤中， Action 以 self 对局方式进行，直到游戏结束。这个“模拟”游戏的结果 R 在黑方获胜(LOA 中的第一个玩家)的情况下为 +1，在平局的情况下为 0，在白方获胜的情况下为 -1。

3. 随后，在扩展步骤中，将 E 的子级添加到树中。

4. 最后，在反向传播步骤中，R 沿着从 E 到根节点的路径反向传播。当时间到时，程序所下的棋步是最高值的根的子步。(这个例子取自这篇论文 - PDF

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

这里有一些实现:

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

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