TicTacToe战略缩减

Question

我决定写一个小程序来解决TicTacToe问题，以便在一个微不足道的游戏中尝试一些剪枝技术的效果。使用minimax来解决这个问题的完整游戏树最终只有549,946个可能的游戏。使用alpha-beta剪枝，评估所需的状态数量减少到18,297个。然后我应用了一个转置表，将这个数字降到了2592。现在我想看看这个数字能有多低。

我想要应用的下一个增强是战略缩减。基本思想是将具有同等战略价值的国家组合在一起。例如，在第一步棋中，如果X先玩，那么选择一个角落而不是另一个角落在战略上没有什么不同(假设你的对手玩得最好)。在同样的情况下，板的墙的中心也是如此，并且中心也很重要。通过只减少到重要的状态，你最终在第一步中只有3个状态进行评估，而不是9个。这个技术应该非常有用，因为它修剪了游戏树顶部附近的状态。这个想法来自于CMU的一个小组创建的GameShrink方法，只是我试图避免编写通用表单，而只是做将该技术应用于TicTacToe所需的事情。

为了实现这一点，我修改了我的散列函数(用于转置表)，以枚举所有战略上等价的位置(使用旋转和翻转函数)，并仅返回每个棋盘的最低值。不幸的是，现在我的程序认为X可以在第一步时从一个空棋盘上强制在5步中获胜。经过长时间的调试后，对我来说，很明显程序总是返回具有最低战略意义的移动(我将最后的移动作为状态的一部分存储在转置表中)。有没有更好的方法来添加这个功能，或者有一种简单的方法来确定适用于当前情况的正确移动，以及我已经做的事情？

Answer 1

出于好奇，我写了一个程序来构建一个完整的转换表来玩这个游戏，而不需要任何额外的逻辑。考虑到8个对称性，并假设computer (X)启动并确定播放，那么只需要49个表项！

1空板条目

2个作品的5个条目

4个作品21个条目

6个作品的18个条目

8件4件作品

Answer 2

当你考虑反射和旋转时，你是在正确的轨道上。但是，您将其应用到了错误的位置。不要将其添加到转置表或转置表代码中--将其放入移动生成函数中，以便从get-go中消除逻辑上等价的状态。

保持你的转换表和相关的代码尽可能的小和高效。

Answer 3

您需要返回(反向)转置以及最低值位置。这样，你就可以将反向转置应用到预期的动作中，以便获得下一个位置。