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

我正在实现一个 AlphaZero 版本（AlphaGo 的最新版本），以应用于其他领域。

该算法的关键是状态空间 (CPU) 的蒙特卡洛树搜索与来自 eval 模式 (GPU) 的神经网络的“直觉”（概率）交错。然后使用 MCTS 结果来训练神经网络。

我已经通过启动多个进程来并行化 CPU 执行，每个进程都建立自己的树。这是有效的，现在已经导致GPU 瓶颈！（nvidia-smi 始终以 100% 显示 GPU）

我设计了 2 种策略来并行化 GPU 评估，但是它们都有问题。

• 每个进程仅在其自己的树中的批次上评估网络。在我最初的幼稚实现中，这意味着批量大小为 1。然而，通过重构一些代码并添加“虚拟损失”来阻止（但不完全阻止）同一个节点被选中两次，我们可以获得更大的批量大小 1 -4。这里的问题是，在我们评估批次或准确性受到影响之前，我们不能允许大的延迟，所以小批量是这里的关键。

• 将批次发送到一个中央“神经网络工作者”线程，该线程组合和评估它们。这可以在 32 个或更多的大批量中完成，因此可以非常有效地使用 GPU。这里的问题是树工作者发送 CUDA 张量“往返”，这不受 PyTorch 支持。如果我先克隆它们是受支持的，但是所有不断的复制使这种方法比第一种方法慢。

我在想也许一个我没有看到的聪明的批处理方案可以使第一种方法起作用。使用多个 GPU 也可以加速第一种方法，但是 PyTorch 本身并不支持我想要的那种并行性。也许将所有张量保留在 NN worker 中并且只发送 id 可以改进第二种方法，但是这里的困难是如何有效地同步以获得大批量而不使 CPU 线程等待太久。

我几乎没有发现有关 AlphaZero 或 AlphaGo Zero 在各自论文中如何并行化的信息。我能够在网上找到有限的信息，但这导致我改进了第一种方法。

如果有任何建议，我将不胜感激，特别是如果我错过了某些观点或方法。

从很多博客和这个https://web.archive.org/web/20160308070346/http://mcts.ai/about/index.html 我们知道 MCTS 算法的过程有 4 个步骤。

1. 选择：从根节点 R 开始，递归地选择最优子节点，直到到达叶节点 L。

叶节点 L 在这里是什么意思？我认为它应该是一个代表游戏结束状态的节点，或者另一个结束游戏的词。如果 L 不是终端节点（游戏的一个结束状态），我们如何确定选择步骤在节点 L 上停止？

2. 扩展：如果L不是一个终端节点（即它没有结束游戏）则创建一个或多个子节点并选择一个C。

从这个描述中我意识到我之前的想法显然是错误的。那么如果 L 不是终端节点，则意味着 L 应该有孩子，为什么不在“选择”步骤继续从 L 中寻找孩子呢？在这一步我们有 L 的孩子列表吗？
从这一步本身的描述来看，我们什么时候创建一个子节点，什么时候需要创建多个子节点呢？我们根据什么规则/策略选择节点 C？

3. 模拟：从 C 运行模拟播放，直到获得结果。

由于第一个问题的混乱，我完全无法理解为什么我们需要模拟游戏。我认为从选择步骤，我们可以到达终端节点，游戏应该在这条路径的节点 L 上结束。我们甚至不需要做“扩展”，因为节点 L 是终端节点。

4. 反向传播：用模拟结果更新当前移动序列。

美好的。最后一个问题，你从哪里得到这些问题的答案？

谢谢

顺便说一句，我也发布了同样的问题https://ai.stackexchange.com/questions/16606/how-to-understand-the-4-steps-of-monte-carlo-tree-search

我的 IS-MCTS 实现总是选择 allin，我不知道为什么。也许你们可以帮助我？

我已经尝试将节点中保存的值从wins更改为value，这意味着获得的筹码数量，但也得到了不好的结果。该算法甚至输给了一个随机玩家并且只跟注玩家。

mcts 方法有什么问题吗？如果不是，它可能是 ucb1 方法或“节点”类。

我想它必须是节点类中的某些东西，它选择了错误的孩子。

我希望你做得很好。我目前正在做一个项目，我们需要使用 Mcts（蒙特卡洛树搜索）来实现一个 connect4-agent。据我了解，mcts基本上分为四个阶段：

1）树构造

2) 通过 Ucb1 值进行选择，直到到达叶节点

3) 如果叶节点已被访问，则展开

4) Rollout = 随机模拟，直到达到最终状态并为该最终状态评分（例如，我们赢了--> 分数 =1，我们输了--> 分数 = -1，平局--> 分数 = 0）

5) 对分值进行反向传播，并对访问的节点添加一次访问。

6）根据1级的得分值决定移动。

我们的代码运行良好。不过，我不确定如何执行扩展阶段。如果我们到达一个已经被访问过的叶子节点，我们知道我们需要从这个节点展开树。考虑一下你有 3 个可能的动作。我们如何决定是否要使用 move=1、move =2 或 move = 3 扩展树？

现在算法随机选择这些动作之一进行扩展，但我相信这远非最优。

最好的问候，阿尔贝托

阅读这篇文章有助于更好地理解 AlphaZero 背后的原理。不过，有些事情我并不完全确定。

下面是作者的UCT_search方法，可以在他在 Github 上的代码中查阅：https
://github.com/plkmo/AlphaZero_Connect4/tree/master/src 在这里，UCTNode.backup()将网络添加value_estimate到所有遍历的节点（另见此“备忘单”）。

这种方法似乎只访问与根节点直接相连的节点。
然而，最初的 DeepMind 论文（关于 AlphaGo Zero）说：

每个模拟从根状态开始，并迭代地选择最大化置信上限 Q(s, a) + U(s, a) 的移动，其中 U(s, a) ∝ P(s, a)/(1 + N (s, a))，直到遇到叶节点 s'。

所以相反，我会期待类似的东西：

^{(UCTNode.is_expanded是False如果节点还没有被访问过（或者是结束状态，即游戏结束）}

你能解释一下为什么会这样吗？还是我忽略了什么？
提前致谢

我看过一些关于 MCTS 和 GPU 的讨论。据说使用 GPU 没有优势，因为它没有很多矩阵乘法。但是使用 CPU 确实有一个缺点，因为设备之间的数据传输确实需要时间。这里我的意思是节点和树应该在 GPU 上。然后他们可以在 GPU 上处理数据，而无需从 CPU 复制数据。如果我只是创建类节点和树，他们会让他们的方法在 CPU 上工作。所以我想知道我是否可以将搜索部分移动到 GPU。有什么例子吗？

我知道，在完全可观察的环境（国际象棋/围棋等）下，您可以运行具有最佳策略网络的 MCTS，以用于未来的规划目的。这将允许您为游戏选择操作，这将导致该状态的最大预期回报。

但是，在部分可观察的环境中，我们还需要在游戏过程中运行 MCTS 吗？为什么我们不能在给定当前状态的情况下从训练好的最优策略中选择最大动作？MCTS 在这里提供什么实用程序

我是强化学习的新手，正在尝试了解 MCTS / 规划在部分可观察环境中的目的。

我目前正在为策略游戏 AI 编写 Monte Carlo Tree Search 的实现，并且对 Rollout（模拟阶段）有疑问。

该算法的描述建议您应该运行模拟，直到达到最终状态，但是当您有很大的搜索空间和有限的时间时，这是不切实际的。就我而言，我将模拟步骤的数量限制为某个值（如果终止，则提前完成）。

在模拟的每个步骤中，我都会评估状态，但由于模拟由一系列随机动作组成，因此评估值可以在模拟期间增加或减少。问题是：对于非终端状态模拟，我应该返回最后的状态评估，还是在运行期间观察到的最佳状态评估？

环境是一个有向图，由具有自己“优点”的节点（标记为绿色）和具有价格的边（标记为红色）组成。在这种环境中存在价格（P）约束。目标是尽可能从节点中累积最多的“好”点，同时制作一个圆圈（例如 0-->6-->5-->0）并且不超过价格限制。.

在没有约束的情况下，我设法实现了 Q-Learning 算法，但我不完全了解如何在逼近 Q-Function 时添加硬约束。

例如，起点是 0。价格限制是 13。走路径 0-->1-->2-->3-->4-->5-->0 对Agent来说不是一个有效的选择，因为在节点 5达到价格(13) 限制，因此，代理应该因违反约束而受到惩罚。然而，采取路径 0-->6-->5-->0 对代理来说是正确的选择，因此他应该得到奖励。我不明白，如何告诉代理有时从 5 到 0 是完美的选择，有时它不适用，因为违反了一些约束。如果违反价格限制并立即结束剧集，我试图给予巨额罚款，但这似乎并没有奏效。

我的问题：

• 如何为 Q-Learning 等 RL 算法添加硬约束？

• Q-Learning 是解决这类问题的有效选择吗？

• 是否应该选择其他算法，例如蒙特卡洛树搜索而不是 Q-Learning。

我认为这是现实世界场景中非常常见的问题，但我找不到任何关于此的示例。

我正在实现一种树搜索，它需要能够从树中获取“最有希望的节点”，然后对该节点执行某些操作，以便为下一次迭代更新树的其余部分。

问题：一个对象指针Board*的向量属性似乎在return产生它们的函数和Board*调用环境中保存它们的值之间发生变化。

我的输出：

我的期望：