search - 井字游戏战略缩减

Question

我决定写一个解决井字游戏的小程序，以尝试一些剪枝技术在一个小游戏上的效果。使用 minimax 解决它的完整博弈树最终只有 549,946 个可能的博弈。通过 alpha-beta 剪枝，需要评估的状态数量减少到 18,297 个。然后我应用了一个转置表，将数字降低到 2,592。现在我想看看这个数字能走多低。

我要应用的下一个增强功能是战略性缩减。其基本思想是结合具有同等战略价值的国家。例如，在第一步中，如果 X 先下，那么选择一个角而不是另一个角在策略上没有什么不同（假设你的对手打得最好）。在同样的情况下，板壁的中心也是如此，中心也很重要。通过仅减少重要状态，您最终只会在第一步中评估 3 个状态而不是 9 个。这种技术应该非常有用，因为它会修剪靠近博弈树顶部的状态。这个想法来自 CMU 的一个小组创建的 GameShrink 方法，只是我试图避免编写通用形式，而只是做将技术应用于井字游戏所需的操作。

为了实现这一点，我修改了我的哈希函数（用于转置表）以枚举所有战略上等效的位置（使用旋转和翻转函数），并且只返回每个板的最低值。不幸的是，现在我的程序认为 X 在先走时可以从空棋盘中强制在 5 步内获胜。经过长时间的调试会话后，我发现程序总是返回具有最低战略意义的移动（我将最后一个移动存储在换位表中作为我的状态的一部分）。有没有更好的方法可以添加此功能，或者有一种简单的方法来确定适用于当前情况的正确移动方式以及我已经完成的操作？

Answer 1

我的直觉是你用太大的锤子来解决这个问题。9 个点中的每一个只能有两个标签之一：X 或 O 或空。那么您最多有 3^9 = 19,683 个独特的板。由于每块板有 3 个等效反射，因此您实际上只有 3^9 / 4 ~ 5k 块板。您可以通过丢弃无效的板来减少这种情况（如果它们同时有一行 X 和一行 O）。

因此，使用紧凑的表示形式，您将需要不到 10kb 的内存来枚举所有内容。我会评估整个游戏图并将其存储在内存中。

我们可以通过自下而上而不是自上而下计算极大极小值（如在您的树搜索方法中），用其真正的极小极大值标记每块棋盘。这是一个总体大纲：我们计算所有独特棋盘的极小极大值，并在游戏开始前首先将它们全部标记。要进行极小极大移动，您只需查看当前状态之后的棋盘，然后选择具有最佳极小极大值的移动。

这是执行初始标记的方法。生成所有有效的独特板，抛出反射。现在我们开始标记具有最多移动 (9) 的棋盘，并向下迭代到具有最少移动 (0) 的棋盘。用胜利、失败和平局标记任何残局。对于轮到 X 移动的任何非残局棋盘： 1) 如果存在 X 获胜的后续棋盘，则将此棋盘标记为获胜；2) 如果在后续棋盘中没有获胜但有平局，则将此棋盘标记为平局；3) 如果在随后的棋盘中没有获胜和没有平局，则将此棋盘标记为失败。标记轮到 O 时的逻辑类似。

就实现而言，由于状态空间很小，我会将“如果存在”逻辑编码为所有 5k 状态的简单循环。但是，如果您真的想针对渐近运行时间进行调整，您将构建一个有向图，其中哪些棋盘状态导致哪些其他棋盘状态，并通过沿边缘的相反方向遍历来执行极小极大标记。

Answer 2

当您考虑反射和旋转时，您走在正确的轨道上。但是，您将其应用到错误的地方。不要将它添加到你的转置表或你的转置表代码中——把它放在移动生成函数中，从一开始就消除逻辑上等价的状态。

使您的转置表和相关代码尽可能小且高效。

Answer 3

出于好奇，我编写了一个程序来构建一个完整的转置表来玩游戏，而无需任何额外的逻辑。考虑到 8 个对称性，并假设计算机 (X) 启动并发挥确定性，那么只需要 49 个表条目！

1个空板条目

2 件 5 个条目

4 件 21 个条目

6 件 18 个条目

8 件 4 个条目

Answer 4

您需要返回（反向）转置以及最低值位置。这样，您可以将反向换位应用于预期的移动，以获得下一个位置。

Answer 5

为什么需要使转置表可变？最好的举动不取决于历史。

Answer 6

关于这一点有很多可以说的，但我在这里只给出一个可以减少树大小的提示：Matt Ginsberg 开发了一种称为分区搜索的方法，它可以在板上进行等效减少。它在 Bridge 中运行良好，他以井字游戏为例。

Answer 7

您可能想尝试使用蒙特卡罗模拟来解决井字游戏。如果其中一个（或两个）玩家是机器玩家，它可以简单地使用以下步骤（这个想法来自Coursera课程“计算原理 1”中的一个迷你项目，该课程是“计算专业基础”的一部分，由 RICE 大学教授。）：

每个机器玩家都应该使用蒙特卡罗模拟从给定的井字棋棋盘位置中选择下一步。总的想法是从位置开始玩一系列随机移动的游戏，然后使用这些游戏的结果来计算一个好的移动。

当一个特定的机器玩家赢得这些随机游戏之一时，它想要偏爱它所玩的方格（希望选择获胜的动作）并避开对手所玩的方格。相反，当它输掉其中一场随机游戏时，它想要偏向对手所玩的方格（以阻止其对手）并避开它所玩的方格。

简而言之，获胜玩家在这些随机游戏中所玩的方格应该比失败者所玩的方格更受青睐。在这种情况下，两个玩家都是机器玩家。

下面的动画展示了 2 个机器玩家之间的游戏（以平局结束），在每个棋盘状态下使用 10 次 MC 试验来确定下一步。

它显示了每个机器玩家如何通过使用蒙特卡罗模拟来学习玩游戏，在棋盘的每个状态下进行 10 次试验（少量试验），使用每个网格方块右下角显示的分数由每个玩家在相应的回合中选择下一步行动（根据模拟结果，较亮的单元格代表当前玩家更好的行动）。

这是我的博客以获取更多详细信息。