问题标签 [monte-carlo-tree-search]

我在一定程度上理解算法的工作原理。我不完全理解的是该算法在实践中是如何实现的。

我有兴趣了解对于相当复杂的游戏（也许是国际象棋）来说，最佳方法是什么。即递归方法？异步？同时？平行？分散式？数据结构和/或数据库？

-- 我们期望在单台机器上看到什么类型的限制？（我们可以在多个内核上同时运行...... gpu 可能吗？）

——如果每个分支都导致一个全新的游戏被玩，（这可能达到数百万）我们如何保持整个系统的稳定？& 我们如何重用已经玩过的分支？

我正在尝试实现蒙特卡洛树搜索以在 Python 中玩井字游戏。我目前的实现如下：

我有一个 Board 类来处理井字棋棋盘的更改。棋盘的状态由 2x3x3 numpy 数组表示，其中 2 个 3x3 矩阵中的每一个都是二进制矩阵，分别表示 X 的存在和 O 的存在。

然后我有一个 Node 类，它在构建搜索树时处理节点的属性：

最后，我有 UCT 功能，可以将所有内容整合在一起。该函数接受一个棋盘对象并构建蒙特卡洛搜索树，以确定给定棋盘状态的下一个最佳可能移动：

我已经搜索了这个代码几个小时，但在我的实现中根本找不到错误。我已经测试了许多棋盘状态并使两个代理相互对抗，但即使是最简单的棋盘状态，该函数也会返回糟糕的操作。我错过了什么和/或我的实施有什么问题？

编辑：这是一个如何实现两个代理的示例：

感谢阅读本文。我开发了像 AlphaGo Lee 或 AlphaGo Zero 这样的国际象棋 AI。我用过 Python 和 tensorflow。国际象棋AI由Montecarlo-Tree-Search、策略网络和价值网络组成。

我为蒙特卡罗树搜索学习了政策和价值网络。没有问题。但是，蒙特卡罗树搜索中的每个模拟都太慢了。所以我想提高每个模拟速度。

我知道由于 GIL，python 不共享对象。我真的需要为此提供帮助。如果你们有在 python 多处理中共享对象的经验，请分享你的经验。

我在此页面下方发布摘要代码。

ps：我英文不好。因此，如果您在阅读此页面时感到不舒服，那是我的错。请理解。

我目前正在尝试提高 Java 代码的性能。在深入了解需要优化的地方后，我最终得到了以下设置（为清楚起见进行了简化）。

被大量调用的 Board 构造函数（~200k 到 2M）：

在另一个班级：

结果让我很困惑。事实上，我观察到两件事：

1. SIMULATION_DURATION 越大，max(duration)越大；
2. 当 SIMULATION_DURATION = 10s 时， max(duration)的值可以达到 2s（是秒，没有错字）。如果 SIMULATION_DURATION = 100 毫秒，我观察到最大（持续时间）约为 30 毫秒。

我的问题如下：

1. 9 个整数数组的副本怎么会花这么长时间？
2. 为什么持续时间在 99% 的情况下小于 0.1 毫秒，而剩下的 1% 则非常高？
3. 为什么它取决于 SIMULATION_DURATION 的值？
4. 我是否在使用 System.currentTimeMillis() 进行这种基准测试时犯了错误，因此结果完全不准确？
5. 当我创建大量 Board 对象时，GC 是否参与了这种奇怪的行为？

我正在为 2 人游戏创建一个 MCTS（蒙特卡洛树搜索）程序。

为此，我从交替的角度在树中创建节点（第一个节点从玩家 1 的角度来看，任何子节点都从玩家 2 的角度来看，等等）

在确定最后一步时（在模拟了许多节点之后），我选择获胜机会最高的一步。这个获胜机会取决于更深节点的获胜机会。例如，假设我有 2 个合法动作要做。第一个（调用关联节点 C1 - Child 1）我做了 100 次模拟并赢得了 25 个，而对于第二个（C2）我做了 100 次模拟并赢得了 50 个。然后第一个节点有 25% 的获胜机会对 50 % 为第二个，所以我应该更喜欢第二个节点。

但是，这并没有考虑到我的对手将采取的“可能”行动。假设从 C2 开始有两个可能的合法移动（对于我的对手），让我们称之为 C21 和 C22。我为两者做了 50 次模拟，在 C21 中，我的对手在 50 场比赛中赢了 50 场（100% 获胜机会），而在 C22 中，他们在 50 场比赛中赢了 0 场（0% 获胜机会）。完成这些模拟后，我可以看到我的对手更有可能采取行动 C21 而不是 C22。这意味着如果我走 C2 步，那么我的 -statistic-win 机会是 50%，但我的 -expected-win 机会接近 0%。

考虑到这些信息，我会选择移动 C1 而不是 C2，即使获胜的概率较低。我可以对我的算法进行编程来做到这一点，从而提高性能。

这似乎是对 MCTS 算法的一个非常明显的改进，但我没有看到任何对它的引用，这让我怀疑我错过了一些重要的东西。

任何人都可以指出我的推理中的缺陷或指出任何涉及此问题的文章吗？

所以我使用 UCT 在蒙特卡洛树搜索算法中实现了一个转置表。这允许保持游戏状态的累积奖励值，无论在整个树中遇到的位置和次数。这提高了针对特定游戏状态收集的信息的质量。

唉，我注意到这给 UCT 的开发与探索选择阶段带来了一定的问题。简而言之，分配给状态的 UCT 分数考虑了访问父状态的次数与访问子状态（我们正在为其计算 UCT 分数）的次数之间的比率。从这张图中可以看出，当从转置表中拉入一个状态到树的一个新创建的分支时，这个比例完全不正常，子状态已经被访问了很多次（来自其他地方）树）和父状态被访问的次数要少得多，这在技术上应该是不可能的。

因此，使用转置表并保持状态的累积奖励值有助于算法的利用部分做出更好的选择，但同时它以潜在有害的方式扭曲了算法的利用部分。你知道有什么方法可以解决这个意想不到的问题吗？

我正在参加强化学习课程，但我不明白如何将策略迭代/价值迭代的概念与蒙特卡洛（以及 TD/SARSA/Q 学习）结合起来。在下表中，如何填充空单元格：应该/可以是二进制是/否，一些字符串描述还是更复杂？

我已经为一个运行良好的 4 人游戏实现了 MCTS，但是当游戏结束移动在实际树中而不是在部署中时，我不确定我是否理解扩展。

一开始，游戏的赢/输位置只能在推出时找到，我知道如何对这些进行评分并将它们传播到树上。但是随着游戏的进行，我最终找到了一个由 UCB1 选择的无法扩展的叶节点，因为它是一个失败的位置，不允许任何移动，所以没有什么可以扩展，也没有游戏可以“推出”。目前，我只是将这作为最后一名剩余球员的“胜利”得分，并为他们反向传播胜利。

但是，当我查看访问统计信息时，该节点被重新访问了数千次，因此显然 UCB1 多次“选择”访问该节点，但这确实有点浪费，我是否应该反向传播其他东西而不是单个赢得这些“永远赢”的节点？

我已经在 Google 上进行了很好的搜索，但实际上找不到太多提及它，所以我是否误解了某些东西或遗漏了一些明显的东西，“标准”MCTS 教程/算法甚至都没有提到树中的游戏结束节点作为特殊情况，所以我担心我误解了一些基本的东西。

我正在尝试进行蒙特卡洛最小化来求解给定方程的参数。我的方程有 4 个参数，使我的迭代大约 4**n

当我尝试迭代时n = 100，我发现搜索所有参数空间并不是一个好主意。

这是我的代码：

问题：

1. 有没有办法让这个算法运行得更快（或者通过减少搜索/相位空间）？

2. 我觉得我在重新发明轮子。请问有人知道可以做我想做的事情的python模块吗？

在此先感谢您的帮助

所以我熟悉更基本的树搜索算法，如带极小值的游戏搜索，但我一直在尝试更多地了解蒙特卡洛树搜索算法，并且想知道它如何处理“精确线”。

在国际象棋的背景下，您可能处于 30 次失败但只有 1 条获胜线的位置，MTCS 算法，更具体地说是 UCB1 函数如何处理这个问题？我理解 UCB1 的方式是，它本质上是对其子节点进行某种平均，因此在你有 30 个失败的棋步和一个获胜的棋步的棋行中，UCB1 值应该看起来很低？

我仍在学习 MCTS，但我一直有这个问题，希望有人能解释即使 UCB1 值可能非常低，MCTS 如何仍会收敛到极小值。

任何知识将不胜感激！谢谢