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

极小极大算法和蒙特卡洛树搜索 (MCTS) 可用于实现具有完整信息的玩确定性（即非概率）游戏（如国际象棋或井字游戏）的代理。

是否有适用于信息不完整的游戏和/或具有概率成分的游戏（例如扑克或桥牌）的通用方法？

在 Wikipedia 中描述的 mcts 算法中，它在每个节点选择中只执行一次播放（模拟）。现在，我正在一个简单的 connect-k 游戏中试验这个算法。我想知道，在实践中，我们是否会进行更多的播放以减少差异？

我用一个随机播放（无偏见）尝试了原始算法。与我使用 alpha-beta 修剪的启发式搜索相比，结果很糟糕。它收敛得非常缓慢。相反，当我执行 500 次播放时，噪音要小得多。但是，每个节点模拟对于算法来说太慢了，无法在给定时间内探索树的其他部分，因此有时会错过最关键的移动。

然后我将 AMAF（尤其是 RAVE 转换）启发式添加到基本 MCTS。我没有注意到 500 场比赛有太大差异，也许是因为差异已经很低。我还没有分析 1 场比赛的结果。

谁能给我任何见解？

尝试使用 YouTube 视频和类似这样的论文来学习 MCST。

http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf

但是，除了高级理论解释之外，我对理解细节的运气并不好。以下是上述论文的一些引述和我的问题。

1. 选择阶段：MCTS 迭代选择当前状态得分最高的子节点。如果当前状态是根节点，那么这些孩子最初是从哪里来的？你不会有一棵只有一个根节点的树吗？只有一个根节点，您是否会立即进入扩展和模拟阶段？

2. 如果 MCTS 在选择阶段选择了得分最高的子节点，那么您在沿着树的各个层级走下去时永远不会探索其他子节点甚至可能是全新的子节点？

3. 节点的扩展阶段如何发生？在上图中，为什么它没有选择叶子节点，而是决定给叶子节点添加兄弟节点？

4. 在模拟阶段，随机策略用于为两个玩家选择合法的移动，直到游戏终止。这种随机策略是否是一种硬编码行为，并且您基本上是在模拟中掷骰子以选择每个玩家之间轮流直到结束的可能动作之一？

5. 我理解这一点的方式是您从单个根节点开始，并通过重复上述阶段将树构造到一定深度。然后你选择第二级得分最高的孩子作为你的下一步行动。您愿意构建的树的大小基本上是您对 AI 响应能力的硬性要求，对吧？由于在构建树时，游戏将停止并计算这棵树。

I'm trying to implement the MCTS algorithm on a game. I can only use around 0.33 seconds per move. In this time I can generate one or two games per child from the start state, which contains around 500 child nodes. My simulations aren't random, but of course I can't make a right choice based on 1 or 2 simulations. Further in the game the tree becomes smaller and I can my choices are based on more simulations.

So my problem is in the first few moves. Is there a way to improve the MCTS algorithm so it can simulate more games or should I use another algorithm?

任何人都可以澄清一下（因为我在任何地方都没有找到任何明确的例子）MCTS算法为第二个玩家迭代。

我看起来的一切似乎都在玩，例如每次都在玩 P1 移动。我了解一个代理的步骤，但我从来没有找到任何显示 P2 放置计数器的代码的东西，这在生长树时肯定会发生。

基本上我希望：

对于每个迭代：

选择节点 Player1 展开 Player1

选择节点 Player2 展开播放器 2

推出反向传播

下一次迭代

这是正确的吗？？有人可以拼出一些伪代码来显示吗？无论是迭代还是递归，我都不介意。

谢谢你的帮助。

我的结构有问题。我正在研究蒙特卡洛树搜索算法的实现，并创建了一个名为 Node 的结构，它具有特定的变量。现在我需要存储节点类型的父对象和子对象。因为一个节点可以是其他节点的父节点，也可以是节点的子节点，这很重要。

这就是问题所在：

有谁知道我该如何解决这个问题？

我正在根据早期版本的 AlphaGo（AlphaGo Fan 或 AlphaGo Lee）的架构实现一个围棋程序，例如使用策略网络、价值网络和蒙特卡洛树搜索（MCTS）。目前我已经训练了一个像样的策略网络和一个不敏感的价值网络，而且我没有一个快速推出的策略。我所说的“不敏感”是指价值网络无法判断复杂的情况，除非情况简洁，否则只能输出50％左右的胜率。价值网络可以正确判断简洁的棋盘（没有大吵大闹）。

使用这个策略网络和价值网络，我还实现了 MCTS 算法（树节点的评估仅由价值网络完成）。由于价值网络不准确，MCTS 恐怕在 MCTS 的时间还没到之前就容易陷入坏棋。为了更好地微调 MCTS 的超参数，以弥补价值网络不准确带来的不良影响，我有两个问题要问：

1. 节点选择由 完成arg max (p_value + lambda * p_policy/visit_cnt)。微调参数有lambda帮助吗？
2. 直觉上，我希望 MCTS 尽可能地探索。节点扩容阶段，设置扩容条件expand a leaf once it is visited a very small number of times, like 3有用吗？我应该使用什么扩展方法？

编辑：第二个问题是关于典型“选择、扩展、评估、备份”MCTS 算法的“扩展”阶段。我认为通过尽快扩展，MCTS 可以更深入地探索，并提供更准确的值近似值。我将参数设置n为how many times a leaf node is visited before it is expanded. 我想直观地知道，n大小n会影响 MCTS 的性能。

关于井字游戏 MCTS 的 hello world 示例的简单问题，

假设我们有一个董事会，我们想要做出最佳决策。因为我不明白在模拟（直到遇到叶子）时连续节点的选择是由探索/利用权衡函数（如维基百科所述）决定的。我真的很想知道这里函数的第一个组件（利用）背后的直觉是什么，特别是对于两个目标相反的玩家之间的游戏。那么“最有希望”的含义会根据谁出手而改变。这个功能不应该根据谁做出下一步行动（尤其是它的第一个组件）而改变吗？

我尝试实现井字游戏 hello-world MCTS 游戏播放器，但遇到了问题。

在模拟游戏并选择“最有前途”（利用/探索）节点时，我只考虑总获胜次数（“利用”部分） - 这会导致某些问题，产生的算法根本不是防御性的。因此，在选择时

• 导致（100 平；10 输）的移动
• 导致（1胜；109负）的移动

选择了最差的（1; 109），因为我的 uct 函数贪婪地计算平均胜利而不是“价值”。

我是否正确识别了这个问题？我应该从“平均获胜”切换到考虑所有结果类型的其他价值指标吗？

欢迎任何建议，谢谢

我试图将蒙特卡洛算法应用于二叉树，但我的印象是算法中有错误，因为它返回了我的默认值。

这是树的图形结构：

您可以在 GitHub 上找到代码，但这里是：

问题是，当我尝试运行此代码时，它会返回：

这意味着它没有正确开始：从一开始我们就直接通过终端状态而无法启动第一个节点。