你能解释一下如何建造这棵树吗？
我非常了解节点是如何选择的，但是更好的解释真的会帮助我实现这个算法。我已经有一个代表游戏状态的棋盘，但我不知道（理解）如何生成树。
有人可以指出我对该算法的评论很好的实现（我需要将它用于 AI）吗？或者更好的解释/例子？
我在网上没有找到很多资源，这个算法比较新……
问问题
23627 次
3 回答
24
生成树的最佳方式是一系列随机播放。诀窍是能够在探索和利用之间取得平衡（这就是 UCT 的用武之地）。这里有一些很好的代码示例和大量研究论文参考：https ://web.archive.org/web/20160308043415/http://mcts.ai:80/index.html
当我实现算法时，我使用随机播放直到达到终点或终止状态。我有一个静态评估函数，可以计算此时的收益，然后从这一点开始的分数被传播回树。每个玩家或“团队”都假设对方会为自己下最好的棋，而对对手来说可能是最坏的棋。
我还建议查看 Chaslot 的论文和他的博士论文，以及一些参考他工作的研究（基本上是从那时起所有 MCTS 工作）。
例如：玩家 1 的第一步可以模拟未来 10 步，玩家 1 和玩家 2 交替进行。每次你必须假设对方球员会尽量减少你的分数，同时最大化他们自己的分数。有一个基于此的整个领域，称为博弈论。一旦你模拟到 10 场比赛结束，你再次从起点迭代（因为只模拟一组决策没有意义）。树的这些分支中的每一个都必须在分数向上传播的情况下进行评分，并且分数代表进行模拟的玩家的最佳可能回报，假设其他玩家也在为自己选择最佳移动。
MCTS 由四个战略步骤组成，只要有时间就重复。步骤如下。
在选择步骤中，树从根节点开始遍历，直到我们到达节点 E，在这里我们选择了一个尚未添加到树中的位置。
接下来，在出局步骤中，以自我对局方式进行移动，直到游戏结束。这个“模拟”游戏的结果 R 在黑方获胜（LOA 中的第一个玩家）的情况下为 +1，在平局的情况下为 0，在白方获胜的情况下为 -1。
随后，在扩展步骤中，将 E 的子级添加到树中。
最后，在反向传播步骤中，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
于 2012-01-30T00:47:24.513 回答
3
来自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.
于 2014-04-05T19:16:21.077 回答
3
如果你有兴趣，我写了这个：https ://github.com/avianey/mcts4j
于 2015-03-02T12:43:54.300 回答