为了尝试一些剪枝技术在简单游戏中的效果，我决定编写一个求解井字棋的小程序。 使用极小极大算法来解决完整的游戏树最终只有549,946种可能的游戏结果。 通过 alpha-beta 剪枝，需要评估的状态数量减少到18,297个。 然后，我应用了一个转置表，将数字减少到2,592个。 现在我想看看这个数字可以降到多低。

我想要应用的下一个增强是策略简化。 基本思想是组合具有等效策略价值的状态。 例如，在第一步，如果X先下，那么选择一个角和选择另一个角在策略上没有任何不同（假设你的对手发挥最佳水平）。 在相同的情况下，棋盘边缘的中心也是如此，中心也很重要。 通过仅减少到重要状态，您最终只需在第一步评估3个状态而不是9个状态。 这种技术应该非常有用，因为它会修剪游戏树顶部的状态。 这个想法来自卡内基梅隆大学（CMU）的一个小组创建的 GameShrink 方法，但我试图避免编写通用形式，而只是做将该技术应用于井字棋所需的事情。

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

回答：

出于好奇，我编写了一个程序来构建一个完整的转置表，以便在没有任何额外逻辑的情况下玩游戏。 考虑到8个对称性，并假设计算机 (X) 开始并确定性地玩，那么只需要 49 个表条目！

空棋盘需要 1 个条目

2 个棋子需要 5 个条目

4 个棋子需要 21 个条目

6 个棋子需要 18 个条目

8 个棋子需要 4 个条目