Monte Carlo 树搜索实现
Monte Carlo Tree Search Implementation
我了解 MCTS 背后的理论，但这是我的问题。 Monte Carlo 游戏中的方法需要从当前状态模拟游戏，直到达到最终状态。为了使搜索收敛到 Minimax（实际的理想移动序列），必须模拟数千个，也许数百万个游戏。
我现在的做法是使用与普通极小极大搜索相同的移动生成函数，以及相同的移动生成函数，并在每次移动后检查是否获胜。在国际象棋或西洋跳棋等复杂游戏中（甚至在简单游戏中），这些都是非常昂贵的操作。我的问题是：是否有更好的方法来实施游戏模拟以降低成本？我可以不执行完整的移动生成，并且每次都不检查获胜吗？任何其他改善模拟时间的方法
My question is: Is there a better way of implementing the game simulations to make them less costly? Can I not perform full move generation, and not check for wins each time?
不，您无法真正避免移动生成和检查终端游戏状态。如果你不生成动作，你也不能 select 动作来玩（你显然需要这样做来推进模拟）。如果您不检查终端游戏状态...您将获得与合法游戏不对应的模拟，并且您不必要地继续模拟太长时间。
加快移动生成速度
在某些游戏中，可能 select 移动而不生成所有移动，只生成一些移动。例如，在国际象棋中，我想你可以先随机选择一个棋子来移动，然后只为那个棋子生成移动，并随机 select 其中一个。这比为所有棋子生成所有合法移动，然后随机 selecting 其中一个要快。然而，它也为您的着法引入了不同的偏差 selection，您最终在模拟中进行的着法的概率分布将不同于所有合法着法的均匀分布。很难说这一定会更好还是更坏，但绝对不同。
提前结束模拟
MCTS 的优点之一是它不一定需要 非终端游戏状态的启发式评估函数。但是，如果您愿意，您仍然可以使用一个。您可以提前结束模拟（在达到终端状态之前），然后使用启发式评估函数来评估这些状态。如果你想保证在给定无限长的处理时间的情况下收敛到最佳解决方案，你需要确保只对你在 Play-out 阶段采取的步骤数设置上限，而不是在选择阶段。在实践中，你往往不会有无限多的处理时间，所以这种差异不会太大（不过我仍然怀疑通过这种区分会有一点改进）
优化实施
当然，也可以简单地优化您的招式生成/终端游戏状态检查/高级功能。在没有看到您的代码的情况下，很难判断这里有多少改进空间。但是，例如，基于位板的状态表示将导致比 naive/straightforward 表示
更有效的功能
我了解 MCTS 背后的理论，但这是我的问题。 Monte Carlo 游戏中的方法需要从当前状态模拟游戏，直到达到最终状态。为了使搜索收敛到 Minimax（实际的理想移动序列），必须模拟数千个，也许数百万个游戏。
我现在的做法是使用与普通极小极大搜索相同的移动生成函数，以及相同的移动生成函数，并在每次移动后检查是否获胜。在国际象棋或西洋跳棋等复杂游戏中（甚至在简单游戏中），这些都是非常昂贵的操作。我的问题是：是否有更好的方法来实施游戏模拟以降低成本？我可以不执行完整的移动生成，并且每次都不检查获胜吗？任何其他改善模拟时间的方法
My question is: Is there a better way of implementing the game simulations to make them less costly? Can I not perform full move generation, and not check for wins each time?
不，您无法真正避免移动生成和检查终端游戏状态。如果你不生成动作，你也不能 select 动作来玩（你显然需要这样做来推进模拟）。如果您不检查终端游戏状态...您将获得与合法游戏不对应的模拟，并且您不必要地继续模拟太长时间。
加快移动生成速度
在某些游戏中，可能 select 移动而不生成所有移动，只生成一些移动。例如，在国际象棋中，我想你可以先随机选择一个棋子来移动，然后只为那个棋子生成移动，并随机 select 其中一个。这比为所有棋子生成所有合法移动，然后随机 selecting 其中一个要快。然而，它也为您的着法引入了不同的偏差 selection，您最终在模拟中进行的着法的概率分布将不同于所有合法着法的均匀分布。很难说这一定会更好还是更坏，但绝对不同。
提前结束模拟
MCTS 的优点之一是它不一定需要 非终端游戏状态的启发式评估函数。但是，如果您愿意，您仍然可以使用一个。您可以提前结束模拟（在达到终端状态之前），然后使用启发式评估函数来评估这些状态。如果你想保证在给定无限长的处理时间的情况下收敛到最佳解决方案，你需要确保只对你在 Play-out 阶段采取的步骤数设置上限，而不是在选择阶段。在实践中，你往往不会有无限多的处理时间，所以这种差异不会太大（不过我仍然怀疑通过这种区分会有一点改进）
优化实施
当然，也可以简单地优化您的招式生成/终端游戏状态检查/高级功能。在没有看到您的代码的情况下，很难判断这里有多少改进空间。但是，例如，基于位板的状态表示将导致比 naive/straightforward 表示
更有效的功能