蒙特卡罗树搜索 UCT 实现

java tree artificial-intelligence montecarlo

2022-09-02 09:52:13

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

我非常清楚节点是如何选择的，但是更好的解释确实可以帮助我实现这个算法。我已经有一个代表游戏状态的板，但我不知道（理解）如何生成树。

有人可以给我指出一个评论良好的算法实现（我需要将其用于AI）吗？还是更好的解释/例子？

我在网上没有找到很多资源，这个算法是相当新的...

答案 1

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

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

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

例如：玩家 1 的第一步可以模拟未来 10 步，在玩家 1 步和玩家 2 步之间交替。每次你都必须假设对方玩家会试图最小化你的分数，同时最大化他们自己的分数。有一个完整的领域基于这个被称为博弈论。一旦你模拟到10个游戏的结束，你再次从起点迭代（因为没有意义只模拟一组决策）。树的每个分支都必须在分数向上传播树的地方进行评分，并且分数代表了进行模拟的玩家的最佳可能回报，假设另一个玩家也在为自己选择最佳动作。

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

在选择步骤中，树从根节点遍历，直到我们到达节点E，在那里我们选择尚未添加到树中的位置。
接下来，在附加赛期间，步进式动作在自玩中进行，直到游戏结束。如果布莱克（LOA中的第一个玩家）获胜，这个“模拟”游戏的结果R是+1，在平局的情况下是0，如果白人获胜，则结果为-1。
随后，在展开步骤中，E 的子级被添加到树中。
最后，在反向传播步骤中，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 MCTS库

答案 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.

爪哇岛

蟒