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

我想并行化我的 MCTS 程序。做这件事有很多种方法：

1. 叶并行化，其中每个叶都被并行扩展和模拟。
2. 根并行化，其中每个线程/进程创建一个单独的树，当完成一些模拟时，将树组合起来以提供更好的统计信息
3. 树并行化，所有线程/进程共享同一棵树，每个线程/进程探索树的不同部分。

（如果我的解释不清楚，请查看这篇关于 MCTS 的评论文章。在第 25 页，详细描述了并行化 MCTS 的不同方法。）

问题：

由于 Python中的多处理必须创建单独的子进程，因此 2. 根并行化非常适合，而我假设 3. 树并行化是不可行的。（因为对于树并行化，所有子进程都必须共享同一棵树——这在 Python 中很难做到）

我对么？我浏览了多处理文档，如果我理解正确，似乎可以在某些基本数据类型的子进程之间来回传递信息，但由于速度等原因，非常不鼓励这样做。

如果是这样，Python 中的树并行化将是一个坏主意，对吧？

我正在使用 MCTS 在 Connect6 上编程。

蒙特卡洛树搜索基于随机移动。它计算某些动作的获胜次数。（无论是3回合还是30回合获胜）

转数少的动作比转数多的动作更有力吗？如果是这样，给转牌获胜较少的一方赋予更大的权重是否有意义？

我在 Python 中有一个树搜索实现，这只是我使用速度慢的一种方式。我怎样才能更快地运行它？我读过有 numba 但我无法理解它是如何工作的，它可以支持什么，什么不能。有人使用 numba 来加快树搜索吗？提前谢谢你！

我正在阅读Silver et al (2012) "Temporal-Difference Search in Computer Go"，并试图了解资格跟踪算法的更新顺序。在论文的算法 1 和 2 中，在更新资格跟踪之前更新了权重。我想知道这个顺序是否正确（算法 1 的第 11 和 12 行，以及算法 2 的第 12 和 13 行）。考虑一个极端的情况lambda=0，参数不会用初始状态-动作对更新（因为e仍然是 0）。所以我怀疑这个顺序可能应该是相反的。

有人可以澄清这一点吗？

我觉得这篇论文对学习强化学习领域很有指导意义，所以想详细了解一下这篇论文。

如果有更合适的平台问这个问题，也请告诉我。

我的游戏 AI 使用了一种算法，该算法根据我可以做出的动作搜索所有可能的未来状态（minimax / monte carlo esque）。它使用评分系统评估这些状态，选择得分最高的最终状态并遵循它。

这在大多数情况下都很有效，但在奖励稀少的情况下效果很差。例如：在我右侧 3 格处有一个理想的收藏品。自然的解决方案是向右->向右->向右。

但是，我的算法搜索 6 转深。它会找到许多最终收集对象的路径，包括需要超过 3 圈的路径。例如，它可能会找到一条路径：上->右->下->右->右->下，而不是在第 5 回合收集对象。

由于在这两种情况下，最终的叶节点都将对象检测为已收集，因此它自然不会偏爱其中一个。因此，不是在第 1 弯向右走，而是向上、向下或向左走。这种行为会在下一回合准确地重复，所以它基本上会在可收集的物体前随机跳舞，只有运气才会让它踩到它。

这显然不是最理想的，我想修复它，但是已经没有如何正确处理这个问题的想法了。这个问题是否有任何解决方案，或者是否有任何理论工作来处理这个问题？

我尝试过的解决方案：

• 使其在较早的回合中更重视对象收集。虽然这有效，但要击败评估者的“噪音”，转弯之间的差异必须相当大。回合 1 的评级必须高于 2，回合 2 的评级必须高于 3，等等。回合 1 和 6 之间的差异必须如此之大，以至于最终导致行为极度贪婪，这在大多数情况下是不可取的。在具有多个对象的环境中，它最终可能会选择在第 1 回合抓取对象的路径，而不是在第 5 回合和第 6 回合抓取对象的更好路径。

• 将对象指定为目标并为其指定距离。如果不逐个进行，原始问题仍然存在。如果在轮到轮的基础上完成，每轮所需的重要性差异再次使其过于贪婪。这种方法也会降低灵活性并导致其他问题。目标选择不是微不足道的，并且有点破坏了极小极大风格算法的要点

• 在我的搜索中进行更深入的搜索，以便它总能找到第二个对象。这将花费如此多的计算能力，以至于我不得不做出让步，比如更积极地修剪路径。如果我这样做，我会回到同样的问题，因为我不知道如何让它更喜欢修剪 5 回合版本而不是 3 回合版本。

• 为上一回合制定的计划提供额外的价值。如果它至少可以遵循次优路径，那么就不会有那么大的问题。不幸的是，这再次必须是一个非常强大的效果，它才能可靠地工作，使其在所有场景中都遵循次优路径，从而损害整体性能。

当我运行我的程序时，我得到这个错误：

我将相同的 MCTS 代码用于 3x3 板尺寸，它不会崩溃并快速返回有竞争力的动作。但是当我尝试将它用于 15x15 板尺寸时，游戏在 1235 次迭代后崩溃，并出现上述错误。

我想我已经通过在 1235 次迭代后不允许扩展任何节点来解决问题的症状。这最终确实会带来竞争性举措，尽管这需要很长时间才能发生。

对我来说，根本原因是我试图创建的树的大小，因为相同的代码适用于 3x3 板，但不适用于 15x15 板；包含所有节点对象的树的大小太大了。因此，这只是这种方法的问题，而不是我的编码问题。

我确实认为我可以尝试：在 x 次迭代之后，如果一个节点已被访问 y 次但获胜分数低于 z，则删除该节点。我的想法是，如果经过 x 次迭代，并且被访问 y 次但获胜分数仍然很低，那么这个节点可能会占用树中不必要的空间，因此可以删除。

我的问题是：

有没有更好的方法让我的程序返回移动而不是崩溃，而不仅仅是减少扩展的数量并且不必实施上述检查？（即使最好的移动需要很长时间才能计算出来）。

这是我的一些未经编辑的代码：

已编辑** MCTS 扩展功能：

MCTSPlayer 功能：

新包含在下面**

选择初始节点函数（将继续，直到可能的移动列表大小 == 为 0）：

"+initialNode.childrenList()); //System.out.println("剩余节点可能的移动："+initialNode.getPossibleMovesSize()); } return initialNode; }

选择功能：

childrenLeft函数：

我正在研究 t=1,...,40 个周期的有限视野决策问题。在每个时间步 t 中，（唯一的）代理必须选择一个动作 a(t) ∈ A(t)，而代理处于状态 s(t) ∈ S(t)。在状态 s(t) 中选择的动作 a(t) 会影响到下一个状态 s(t+1) 的转换。所以存在有限视界马尔可夫决策问题。

在我的情况下，以下情况成立：A(t)=A 和 S(t)=S，而 A 的大小为 6 000 000，S 的大小为 10^8。此外，转换函数是随机的。

由于我对蒙特卡洛树搜索 (MCTS) 的理论比较陌生，所以我问自己：MCTS 是否适合我的问题（特别是由于 A 和 S 的大小以及随机转换函数？）

我已经阅读了很多关于 MCTS 的论文（例如渐进式加宽和双渐进式加宽，听起来很有希望），但也许有人可以告诉我他将 MCTS 应用于类似问题的经验或解决此问题的适当方法（大状态/动作空间和随机转换函数）。

我有一个使用 MCTS ( http://mcts.ai/code/python.html ) 的家庭作业，可以根据需要使用 MCTS 玩尽可能多的井字游戏。该任务的目标是训练一个决策树分类器，该分类器可以根据游戏的当前状态和玩游戏的玩家来预测要采取的最佳行动。数据标记为 1.0 或 2.0 或 0，具体取决于哪个玩家在井字游戏网格中标记了他选择的位置（0 表示没有玩家）。到目前为止，我设法以如下格式将数据保存到 CSV：

未命名：0 玩家 0 1 2 ... 6 7 8 best_move 获胜

0 0 1.0 0.0 0.0 0.0 ... 0.0 0.0 0.0 4 0

我的第一个也是主要问题是如何使用 scikit-learn 制作一个包含所有相等状态的决策树分类器，即根应该有 9 个可供第一个玩家使用的决策，然后有 8 个可供第二个玩家使用，依此类推（1.0播放器 1，播放器 2 为 2.0）。第二个相互关联的问题是我如何一遍又一遍地表示 0-8 (9) 间隔中的重复数据，以便在读取第 9 个间隔后，它将在下一场比赛中从根部重新开始。当然，最好将玩家 1 或玩家 2 相同的子状态组合在一起。

这是我的代码生成的树的 pdf 视图。下面是我用来训练决策树的代码。

这是数据的格式：

如您所见，进行了 9 次移动，然后数据集在新游戏中重复（从 0 开始）。当每个玩家轮流移动时，每个玩家的数据在 1.0 和 2.0 之间循环。我还根据要求为赢得比赛的一组动作添加了一个获胜列（但不确定如何使用它，所以我没有将它包含在预测数据中）。理想情况下，决策树应该按照描述合并所有开始游戏状态，并预测最佳移动应该是什么。

我有 10 个变量，如下所示

V1=1, V2=2, V3=3, V4=4, V5=5, V6=6, V7=7, V8=8, V9=9 和 V10=10

注意：每个变量可以有任何值

现在我想选择最好的 3 个变量组合，如下所示

V1V3V4 或 V10V1V7 或 V5V3V9 等。

最好的组合只不过是组合中 3 个变量的总和。

例子：

组合1（V1V2V3）：1+2+3=> 6

组合2（V8V9V10）：8+9+10=> 27

在上面的示例中，组合 2(V8V9V10)的总和值最高。所以组合2（V8V9V10）是这里最好的组合。

像这样，如果我有大量变量，则意味着哪种机器学习算法从所有意义上都选择了最佳组合。

建议我选择最佳变量组合的最佳机器学习算法。提前致谢。

注意：据我所知，我认为蒙特卡洛算法是这种场景的算法之一。但与蒙特卡洛算法相比，我需要最好的算法。

TLDR

MCTS 代理实现在本地运行没有错误，针对启发式驱动的 minimax 实现了 >40% 的胜率，但自动评分器失败 - 这是提交项目之前的要求。自动分级机抛出IndexError: Cannot choose from an empty sequence。我正在寻找最有可能引发此异常的代码部分的建议。

嗨，我目前被困在这个项目上，我需要在两周后完成我注册的项目之前清除这个项目。我已经完成的任务是在两个国际象棋骑士之间的隔离游戏中实现一个代理来对抗启发式驱动的极小极大代理。游戏的完整实施细节可以在这里找到。对于我的项目，游戏将在一块 9 x 11 的板上进行，使用位板编码。我的 MCTS 实现很简单，紧跟本文提供的伪代码（第 6 页）。

本质上，通用 MCTS 方法包括这 4 个部分，它们分别由 CustomPlayer 类中的以下嵌套函数实现：

1. 选择 - tree_policy
2. 扩展 - best_child，扩展
3. 模拟 - default_policy

4. 反向传播 - backup_negamax, update_scores

   /li>

缺少颜色格式确实使代码很难阅读。所以，请随时在我的github上查看。我在本地运行游戏没有任何问题，我的 MCTS 代理对 minimax 玩家的胜率超过 40%（低于 150 毫秒/移动限制）。但是，当我尝试将我的代码提交给自动评分器时，它会被IndexError: Cannot choose from an empty sequence异常拒绝。

根据我与课程代表的讨论，我们认为该错误很可能是由使用random.choice(). 在我的实现中有 4 个使用它的实例：

1. 第 39 行，在 MCTS 算法之前，向队列提供随机移动
2. 第 66 行，随机选择一个没有尝试过的招式
3. 第 114 行，如果最佳动作得分相同，则随机选择一个动作
4. 第 122 行，随机模拟游戏，直到选择移动的最终状态

我假设游戏实现是正确的，只要状态是终端，调用 state.actions() 将始终返回可能移动的列表。因此，唯一可以触发此异常的实例是第 3 项。第 1 项和第 4 项只是从可用操作中随机选择，同时进行了显式检查以确保 random.choice() 没有提供空列表。因此，我将日志记录应用到第 3 项（即使在本地运行时没有引发异常），果然，在 50 场比赛后没有捕获任何异常。

对于这篇冗长的帖子，我深表歉意，但我确实希望那里的人能够抓住我在实施过程中遗漏的东西。