井字棋战略简化

Question

井字棋战略简化

searchartificial-intelligencetic-tac-toe

10

我决定写一个小程序来解决井字棋问题，以尝试一些对于这个简单游戏的剪枝技巧的效果。使用minimax解决所有可能的游戏，完整的游戏树仅有 549,946 种可能。利用alpha-beta剪枝技术，评估所需的状态数量减少到 18,297。然后我应用置换表将数量降至 2,592。现在我想看看这个数字能否再次降低。

我想要应用的下一个改进是战略缩减。基本思路是将具有等效战略价值的状态合并。例如，在第一步时，如果X先走，选择其中一个角落与选择另一个角落在战略上没有区别（假设你的对手会最优地行动）。在相同情况下，墙中央的位置也是如此，并且中心位置也非常重要。通过只保留重要状态，您只需要评估三个状态，而不是九个状态，以进行第一步操作。由于这种剪枝技术能够减少游戏树顶部附近的状态，因此该技术应该非常有用。这个想法来自CMU的一个小组创建的GameShrink方法，但我试图避免编写通用表单，只是做必要的工作将该技术应用于井字棋。

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

- Nick Larsen

这是一个有趣的问题，据我所知，所有其他实现都使用“检查每个方格”的方法，而不是构建决策树。但我不确定其中是否有任何可以称之为人工智能的东西 :s - Codesleuth

@Codesleuth 要注意术语——决策树是一种机器学习技术，这里不适用。 - Shaggy Frog

@Codesleuth 决策树并不是神经网络，但它们都是机器学习算法的形式。此外，这里描述的启发式搜索肯定是人工智能的一种形式。我建议你花些时间研究这个主题。 - Shaggy Frog

@Codesleuth 如果你混淆了神经网络和决策树，那么显然还需要进行更多的研究。 - Shaggy Frog

@Shaggy Frog：我想我们已经确定我说“树”而不是“表”是一个错误了。此外，我现在不会再研究人工智能了，你的坚持是无效的。 - Codesleuth

显示剩余3条评论

7个回答

2

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

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

- Shaggy Frog

这非常有帮助。有趣的是，当我这样做时，我遇到了各种问题。原来我一直在试图解决游戏，并尝试从先前评估过的位置进行游戏，但有时这些位置尚未被评估。一旦我修改为每次移动都重新运行搜索，所有问题都消失了。现在我正在研究移动排序技术。您是否知道任何好的移动排序出版物？ - Nick Larsen

不确定，因为移动排序通常与领域紧密相关。在搜索树的顶部附近，它可能非常重要，但在底部附近，它可能比扩展节点所节省的时间更耗费时间。考虑仅在距离底部（例如）>= 3个棋子的节点处执行它。一般而言，一个便宜且简单的方法是对每个节点进行深度1搜索，然后基于此进行排序，这有助于利用您现有的评估函数。 - Shaggy Frog

2

出于好奇，我编写了一个程序来构建一个完整的置换表，以便在没有任何其他逻辑的情况下玩游戏。考虑到8个对称性，并假设计算机（X）开始并进行确定性游戏，则只需要49个表项！

1个空棋盘条目

5个2个棋子的条目

21个4个棋子的条目

18个6个棋子的条目

4个8个棋子的条目

- Avi Tal

1

这太棒了！你能让它也处理第二个播放吗？ - Nick Larsen

2

@NickLarsen 当然可以。另外，如果计算机从中心开始而不是首先玩角落（同时仍然进行“最佳游戏”并且永远不会输），那么表格就会变得更小...我现在正在尝试分析确定（并模拟）其他游戏中需要的最小置换表大小，假设计算机进行确定性游戏。 - Avi Tal

十年后，这太棒了。 - Nick Larsen

“确定性”的意思是计算机在每个特定的板配置上每次都会以完全相同的方式响应。 - Avi Tal

我只编码“可能”的游戏树。也就是说，那些不可能出现的游戏局面因为计算机永远不会导致这些情况而不被编码。一般来说，这样可以仅存储大约总可能位置的平方根数量的数据。 - Avi Tal

1

现在我有一个N = 37的解决方案，可以在这里查看：https://stackoverflow.com/a/65800312/502187 但是我正在存储具有奇数棋子数量的棋盘。 - user502187

1

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

- Chris Dodd

这是我过去发现非常有价值的一种技术，特别是对于像我曾经在扑克牌上工作时那样非常复杂的游戏，但对于这个简单的项目来说，它似乎需要付出更多的努力而不值得。我也从未编写过通用形式状态映射器。你知道有没有类似的吗？可能是一个不错的项目。 - Nick Larsen

0

为什么需要使置换表可变？最佳移动不取决于历史记录。

- namin

0

您可以尝试使用 Monte Carlo 模拟来解决井字游戏问题。如果一方（或双方）是机器玩家, 它可以简单地按照以下步骤进行操作（这个想法来自于 coursera 课程 计算原理1 中的一个迷你项目，该课程是 RICE 大学的基础计算专项课程之一）：

每个机器玩家应该使用 Monte Carlo 模拟从给定的井字棋板局中选择下一步。总体思路是从当前位置开始，玩一系列带有随机移动的游戏，然后利用这些游戏的结果计算一个好的下一步。

当特定机器玩家赢得其中一场随机游戏时，它会偏爱在其中下过棋子的方格（以期选择获胜的下一步），并避免对手下过棋子的方格。相反，当它输掉其中一场随机游戏时，它想要优先选择对方下过棋子的方格（以阻止对手），并避免在其中下过棋子的方格。

简而言之，在这些随机游戏中获胜的玩家所下的方格应该优于输掉游戏的玩家所下的方格。在这种情况下，双方都将是机器玩家。

下面的动画展示了两个机器玩家之间进行的一场游戏（以平局结束），每个棋盘状态使用10次MC试验来确定下一步棋。它展示了每个机器玩家如何通过在棋盘的每个状态上使用Monte-Carlo模拟进行10次试验（少量试验）来学习玩游戏，每个格子右下角显示的分数由每个玩家在其相应的回合中使用，选择其下一步棋（较亮的单元格代表当前玩家更好的移动，根据模拟结果）。

关于此，更多细节请参考我的博客。

- Sandipan Dey

0

关于这个问题可以说很多，但我在这里只给出一个提示，它可以减小你的树大小：Matt Ginsberg开发了一种称为Partition Search的方法，在棋盘上进行等价性缩减。它在桥牌中表现良好，并以井字游戏为例。

- Nathan S.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric · Accepted Answer

我的直觉是你在解决这个问题时使用的工具太大了。每个九宫格只有两种标记：X或O，或者为空。因此，你最多只有3^9 = 19,683个唯一的棋盘。由于每个棋盘有三个等效反射，所以你实际上只有3^9 / 4约5k个棋盘。你可以通过丢弃无效的棋盘（如果它们同时有一行X和一行O）来减少这个数目。

因此，使用紧凑的表示法，你只需要不到10kb的内存就可以枚举所有内容。我会在内存中评估并存储整个游戏图。

我们可以为每个棋盘打上真正的极小化值标签，通过自底向上计算极小化值而不是自顶向下（如你的树搜索方法）。以下是一个概要：我们为所有唯一的棋盘计算极小化值并首先对其进行标记，然后再开始游戏。为了进行极小化移动，你只需查看当前状态后继的棋盘，并选择极小化值最佳的移动。

以下是执行初始标记的方法。生成所有有效的唯一棋盘，丢弃反射。现在我们从最多步数（9）的棋盘开始标记，并迭代到最少步数（0）的棋盘。为任何以胜利、失败和平局结束的棋盘打上标签。对于任何非结束游戏的棋盘，在轮到X走的情况下：1)如果存在一个后继棋盘是X的胜利，则将此棋盘标记为胜利；2)如果在后继棋盘中没有胜利，但存在平局，则将此棋盘标记为平局；3)如果在后继棋盘中没有胜利和平局，则将此棋盘标记为输。当为O的转移打标记时，逻辑类似。

就实现而言，由于状态空间很小，我会将“如果存在”的逻辑编码为简单的循环遍历所有5k个状态。但如果你真的想调整这个算法的渐进运行时间，你可以构建一个有向图，表示哪些棋盘状态导致哪些其他棋盘状态，并通过反向遍历边来执行极小化标记。