我决定编写一个小程序来解决TicTacToe,以便尝试一些修剪技术对一个琐碎游戏的影响.使用minimax解决它的完整游戏树最终只有549,946个可能的游戏.通过alpha-beta修剪,评估所需的状态数量减少到18,297.然后我应用了一个转换表,将数字降至2,592.现在我想看看这个数字有多低.
我想申请的下一个改进是战略性削减.基本思想是结合具有同等战略价值的国家.例如,在第一步中,如果X首先发挥作用,那么在选择一个角落而不是另一个角落时,没有任何战略上的差异(假设你的对手发挥得最佳).在相同的情况下,板的中心也是如此,中心也很重要.通过仅减少到显着状态,最终只有3个状态用于第一步而不是9的评估.这种技术应该非常有用,因为它修剪了游戏树顶部附近的状态.这个想法来自CMU的一个小组创建的GameShrink方法,只是我试图避免编写一般形式,只是做了将技术应用于TicTacToe所需的东西.
为了实现这一点,我修改了我的哈希函数(对于转置表)来枚举所有策略上等效的位置(使用旋转和翻转函数),并且仅返回每个板的最低值.不幸的是,现在我的计划认为X可以在第一次出局时从空板上强行取胜5次.经过长时间的调试会议后,对我来说很明显,程序总是返回最低战略意义的移动(我将最后一个移动存储在转置表中作为我的状态的一部分).有没有更好的方法可以添加此功能,或者使用我已经完成的确定适用于当前情况的正确移动的简单方法？
我的直觉是你使用太大的锤子来解决这个问题.9个斑点中的每一个都只能有两个标签中的一个:X或O或空.那么你最多有3 ^ 9 = 19,683个独特的电路板.由于每个电路板有3个等效反射,因此实际上只有3 ^ 9/4~5k电路板.你可以通过丢弃无效的板来减少这种情况(如果它们同时有一排X和一排O).
因此,通过紧凑的表示,您需要少于10kb的内存来枚举所有内容.我会评估并将整个游戏图存储在内存中.
我们可以通过自下而上计算最小极大值而不是自上而下(如树搜索方法),为每个单板标记其真正的极小极大值.这是一个概括:我们计算所有独特电路板的最小值,并在游戏开始前将它们全部标记.要使minimax移动,您只需查看当前状态之后的板,然后选择具有最佳minimax值的移动.
以下是如何执行初始标记.生成所有有效的独特电路板,抛出反射.现在我们开始用最多的移动标记板(9),并以最少的移动(0)向下迭代到板.用胜利,亏损和平局标记任何残局牌.对于X轮到之后的任何非终局董事会:1)如果存在一个X的胜利的继任董事会,则将该董事会标记为胜利; 2)如果在继任委员会中没有胜利但是有平局,则将该委员会标记为平局; 3)如果在后继董事会中没有胜利而没有抽奖,则将该董事会标记为亏损.标记为O转弯时,逻辑类似.
就实现而言,由于状态空间的小尺寸,我将"如果存在"逻辑编码为所有5k状态的简单循环.但是如果你真的想要为渐近运行时调整它,你可以构建一个有向图,其中哪些电路板状态导致其他电路板状态,并通过沿边缘的反向遍历来执行最小极大标记.
京公网安备 11010802040832号 | 京ICP备19059560号-6 