Tictactoe战略还原

Question

我决定编写一个小程序来解决Tictactoe，以尝试一些修剪技术对琐碎游戏的影响。使用minimax解决的完整游戏树最终只能获得549,946个可能的游戏。随着α-beta修剪，评估所需的状态数量减少到18,297。然后，我应用了一个将数字降至2,592的换位表。现在，我想看看这个数字可以走多么低。

我要应用的下一个增强功能是战略性减少。基本思想是结合具有等效战略价值的国家。例如，在第一步，如果X首先播放，那么在选择一个角落而不是另一个角落而不是另一个角落的战略上没有什么不同的。在同一情况下，董事会墙壁的中心也是如此，并且中心也很重要。通过仅降低重要状态，您最终只能获得3个州进行第一步的评估，而不是9个州。该技术应该非常有用，因为它在游戏树的顶部附近进行了修剪状态。这个想法来自CMU组创建的gameshrink方法，只是我试图避免编写通用形式，而只是做需要将技术应用于Tictactoe所需的事情。

为了实现这一目标，我修改了我的哈希函数（用于换位表）以列举所有策略上等效的位置（使用旋转和翻转功能），并仅返回每个板的最低值。不幸的是，现在我的程序认为X可以在第一次前进时从空板上赢得5次胜利。经过长时间的调试会议，对我来说，该计划总是在战略性意义上的举动返回这一举动（我将最后一步存储在转置表中，这是我的状态的一部分）。有没有更好的方法来添加此功能，或者是确定适用于当前情况的正确移动的简单方法？

Answer 1

当您考虑思考和旋转时，您的轨道正确。但是，您将其应用于错误的地方。不要将其添加到换位表或换位表代码中 - 将其放入移动生成功能中，以消除从一开始的逻辑等效状态。

保持您的转换表和关联的代码尽可能小且尽可能高效。

Answer 2

我的直觉是，您正在使用太大的锤子来攻击这个问题。这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状态的简单循环。但是，如果您真的想对此进行调整 渐近学 运行时间，您将构建一个有向图的董事会状态导致其他董事会所示，并通过在边缘的反向方向上横穿横穿来执行最小值标记。

Answer 3

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

Answer 4

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

Answer 5

关于这一点，可以说很多话，但是我只会在这里提供一个小费，这将减少您的树大小：Matt Ginsberg开发了一种称为的方法 分区搜索 这会减少董事会。它在桥梁中运行良好，他以tic-tac-toe为例。

Answer 6

您可能需要尝试使用Monte-Carlo模拟来解决TIC-TAC-TOE。如果一个（或两个）玩家是机器播放器，则可以简单地使用以下步骤（此想法来自其中一个小型项目 Coursera 课程 计算原理1 这是赖斯大学教授的计算专业基础的一部分。）：

每个机器玩家都应使用蒙特卡洛模拟从给定的Tictactoe板位置选择下一步。一般的想法是玩一系列游戏集，从位置开始，然后使用这些游戏的结果来计算好的动作。

当一个Paretular Machine Player赢得这些随机游戏之一时，它希望偏爱它玩的正方形（希望选择获胜的举动）并避免对手玩的正方形。相反，当它失去这些随机游戏之一时，它希望偏爱对手打的正方形（阻止对手），并避免弹奏的正方形。

简而言之，在这些随机比赛中赢得的球员在这些球员中扮演的正方形应该比输球玩家玩的正方形受到青睐。在这种情况下，两个玩家将是机器玩家。

以下动画显示了2个机器玩家之间玩的游戏（以 领带），在每个董事会状态下使用10个MC试验来确定下一步。

它显示了每个机器玩家如何通过使用董事会的每个州使用蒙特卡洛模拟（少量试验）来学习游戏的方式， 右下 每个玩家在相应的转弯处使用每个网格正方形的使用，以选择其下一步（根据仿真结果，更明亮的单元代表了当前播放器的更好动作）。

这是我的 博客 有关更多详细信息。