蒙特卡罗搜索树如何运作？

2 回答

• 0

  基本上，蒙特卡罗是：随机尝试多次（*），然后保持移动，在大多数时间导致最好的结果 .

  （*）：次数和深度取决于您想要实现的决定的速度 .

  因此， root node 始终是当前的游戏状态，直接的孩子可能会被移动 . 如果你可以进行2次移动（是/否，左/右，......），那么你有2个子节点 .

  如果你不能做任何动作（可能会发生取决于游戏），那么你没有任何决定，那么Montec Carlo对这一举动毫无用处 .

  如果你有X个可能的动作（国际象棋游戏），那么每个可能的动作都是一个直接的子节点 .

  然后，（在2人游戏中），evey等级交替“你的动作”，“对手移动”等等 .

  如何遍历树应该是随机的（均匀的） .

  你的举动1（子级别1的随机移动）他的移动4（子级别2的随机移动）你的移动3（子级别3的随机移动） - >赢得yay

  选择参考最大深度并评估您赢或输的次数（如果游戏在X深度之后未完成，则具有大量评估功能） .

  您重复操作Y次（非常大）并选择直接子节点（又名：您的移动），这会导致您在大多数时间中获胜 .

  这是为了评估你应该做哪个动作 now . 在此之后，对手移动，轮到你了 . 所以你必须重新创建一个树，根节点是新的当前情况，并重做蒙特卡洛技术来猜测你最好的移动是什么 . 等等 .

  回复于 2024-04-20T10:29:39+08:00
• 0

  选择阶段：MCTS迭代地选择当前状态的得分最高的子节点 . 如果当前状态是根节点，那么这些孩子首先来自哪里？难道你不会只有一个只有一个根节点的树吗？只有一个根节点，您是否可以立即进入扩展和仿真阶段？

  选择步骤通常不实际选择实际存在于树中的节点（通过扩展步骤创建） . 通常ipmlemented在与当前节点匹配的游戏状态的所有可能后继状态中进行选择 .

  所以，在一开始，当你只有一个根节点时，你会希望你的选择步骤仍然能够从所有可能的后继游戏状态中选择一个（即使它们在树中没有匹配的节点）然而） . 通常你会想要一个从未被访问过的游戏状态（在树中没有节点）的非常高的分数（无限或一些非常大的常数） . 这样，您的选择步骤将始终在任何尚未匹配节点的状态中随机选择，并且只能真正使用在所有可能的游戏状态已经在树中具有匹配节点的情况下，探索与利用权衡 .

  如果MCTS在选择阶段选择得分最高的子节点，那么在从树的水平下降时，你永远不会探索其他孩子，甚至可能是一个全新的孩子？

  ''score' ' used by the Selection step should typically not just be the average of all outcomes of simulations going through that node. It should typically be a score consisting of two parts; an 1522390 part, which is high for nodes that have been visited relatively infrequently, and an 1522391 part, which is high for nodes which appear to be good moves so far (where many simulations going through that node ended in a win for the player who'允许选择一个动作） . 这在您链接的论文的第3.4节中有所描述 . W(s, a) / N(s, a) 是开发部分（简称平均分）， B(s, a) 是探索部分 .

  节点的扩展阶段如何？在上图中，为什么不选择叶节点但是决定在叶节点上添加一个兄弟节点？

  扩展步骤通常用于简单地添加与选择步骤选择的最终游戏状态相对应的节点（按照我对第一个问题的回答，选择步骤将始终选择一个之前从未选择过的游戏状态） .

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

  最直接（也可能是最常见）的实现确实是完全随机发挥的 . 尽管如此，也可以这样做 . 例如，您可以使用启发式方法来创建对某些操作的偏见 . 通常，完全随机播放更快，允许您在相同的处理时间内运行更多模拟 . 但是，它通常也意味着每个单独的模拟信息量较少，这意味着您实际上需要运行更多模拟以使MCTS发挥良好 .

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

  MCTS不会将树的所有部分均匀地探索到相同的深度 . 它倾向于探索看起来有趣（强烈的动作）的部分比看起来不感兴趣的部分（弱动作）更深 . 所以，通常你不会真正使用深度限制 . 相反，您将使用时间限制（例如，继续运行迭代，直到您花费1秒，或5秒，或1分钟，或您允许的任何处理时间），或迭代计数限制（例如，允许它运行10K或50K或任何数量的模拟你喜欢） .

  回复于 2024-04-20T10:29:39+08:00