如果某些动作是强制性的,是否还需要静止搜索?

人工智能 游戏-ai 极小极大 α-β-修剪 跳棋 静止搜索
2021-11-07 03:36:28

某些游戏,如跳棋,有强制移动。例如,在跳棋中,如果有可用的跳跃,玩家必须超越任何非跳跃动作。

如果跳跃是强制性的,是否还需要静止搜索?

我的想法是我可以开发一个静止搜索的实现,它首先检查跳转是否可用。如果有那么它可以跳过所有非跳跃动作。如果只有一个跳跃动作可用,那么我根本不需要进行搜索。

因此,如果我最初不必在第一步中跳跃,我只会使用静止搜索。我只会在我的 alpha-beta 剪枝中激活静默搜索。(只有当我的第一个算法首先检查是否有可用的跳转返回 0 时,alpha-beta 才会激活,这意味着没有可用的跳转。)

我实施静止搜索的想法是否正确?


由于严重的内存限制,在优化方面我的选择很少,因此我不会使用 PVS 或其他类似的算法,因为它们需要额外的内存。

1个回答

我理解你的问题是:

如果某些招式是强制性的,而我的代理人无法选择下一步该采取哪个招式,我是否需要进行搜索,或者我可以退回强制性招式吗?

答案取决于你的目标是什么。

如果您的目标是创建一个与您对战的交互式代理,那么您是对的:无需执行搜索。只需返回强制移动,然后在您的代理下次选择要做什么时运行搜索。

如果您的目标是确定玩游戏的最佳方式,或从某个游戏位置获得的预期收益(搜索技术的另一种常见用途),那么您应该正常运行搜索,因为强制移动不一定会领先到特定的最终状态。

切切地,如果您对加快搜索跳棋的方法感兴趣,请查看 Chinook 论文。这里有一个普及的帐户,还有Schaeffer 等人在此处此处提供的更多技术帐户。