问题标签 [tic-tac-toe]

在井字游戏的实现中，我想具有挑战性的部分是确定机器要玩的最佳动作。

可以追求的算法有哪些？我正在研究从简单到复杂的实现。我将如何解决这部分问题？

我用 Java 编写了一个井字游戏，我目前确定游戏结束的方法考虑了以下可能的游戏结束情况：

1. 棋盘已满，尚未宣布获胜者：游戏为平局。
2. 克罗斯赢了。
3. 圈子赢了。

不幸的是，要这样做，它会从表中读取一组预定义的这些场景。考虑到棋盘上只有 9 个空格，这并不一定是坏事，因此桌子有点小，但是是否有更好的算法方法来确定游戏是否结束？确定某人是否获胜是问题的关键，因为检查 9 个空格是否已满是微不足道的。

表方法可能是解决方案，但如果不是，那是什么？另外，如果电路板没有尺寸n=9怎么办？如果它是一个更大的棋盘，比如说n=16,n=25等等，导致连续放置的获胜项目的数量是x=4,x=5等等？一个通用的算法供所有人使用n = { 9, 16, 25, 36 ... }？

我已经为大型（更高维度）井字游戏考虑了一些启发式方法。我如何检查其中哪些实际上是一致的？

无论如何，一致性是什么意思？

通过考虑所有情况，可以轻松解决小型（3x3、4x4）井字游戏。但例如，您有一个 30x30 的井字游戏。在这种情况下，你会使用什么算法来决定下一个最佳动作？

Minimax + alpha-beta 修剪是我知道的一种方法。

有没有其他更高效/不是更高效但更酷的方法？

我知道这不会是一个非常有趣的游戏。我说 30x30 只是为了问我想问什么，即哪种算法在这类游戏中效果最好，其中要考虑的完美解决方案的案例数量非常多，因此不可行。

因此，我正在尝试编写一种方法来在某人赢、输或平局后重播井字游戏。所以基本上我试图让重播工作，不起作用。如果玩家 1 获胜并且我输入 1 进行重播，它会询问玩家 2 的输入。

伪代码大纲：

我的实际代码：

我已经写了一个井字游戏代码。我也有 Alpha-Beta 修剪工作。我遇到了一个我需要想法的问题，而不是代码。我如何选择将在 4 步中获胜的步法与将在 8 步中获胜的步法。我遇到的问题是从 minimax/AB 修剪中返回最佳分数的分支可能会在 8 步中获胜，因此它可能会修剪掉可能会在 4 步中获胜的分支。

我遇到了一些想法，例如杀手启发式、转置表和迭代深化搜索。任何想法都会很棒

一点背景知识：作为在 C++ 中学习多节点树的一种方法，我决定生成所有可能的井字棋棋盘并将它们存储在树中，这样从一个节点开始的分支都是可以从该节点跟随的所有棋盘，并且一个节点是一次跟随的棋盘。在那之后，我认为用那棵树作为决策树来编写一个 AI 来玩井字游戏会很有趣。

TTT 是一个可以解决的问题，完美的玩家永远不会输，所以在我第一次尝试 AI 时，它似乎是一个简单的 AI 编码。

现在，当我第一次实现 AI 时，我返回并在生成时为每个节点添加了两个字段：X 将获胜的次数和 O 将在该节点下的所有子节点中获胜的次数。我认为最好的解决方案是让我的 AI 在每一步中选择并沿着获胜次数最多的子树向下走。然后我发现虽然它在大多数情况下都表现完美，但我找到了可以击败它的方法。这不是我的代码有问题，只是我让 AI 选择路径的方式有问题。

然后我决定让它选择计算机获得最大胜利或人类损失最大的树，以较大者为准。这使它表现更好，但仍然不完美。我仍然可以击败它。

所以我有两个想法，我希望输入哪个更好：

1）我可以分配值 1 表示胜利，0 表示平局，-1 表示失败，而不是最大化胜利或失败。然后选择具有最高值的树将是最好的移动，因为下一个节点不能是导致损失的移动。这是板生成中的一个简单更改，但它保留了相同的搜索空间和内存使用。或者...

2) 在棋盘生成过程中，如果有一个棋盘使得 X 或 O 在下一步中获胜，则只会生成阻止该获胜的子棋子。不会考虑其他子节点，然后生成将照常进行。它缩小了树的大小，但是我必须实现一个算法来确定是否有单步获胜，我认为这只能在线性时间内完成（我认为让棋盘生成速度慢很多？）

哪个更好，或者有更好的解决方案？

按字符数发布您的最短代码，以检查玩家是否赢了，如果赢了，是哪个。

假设您在变量（棋盘）中有一个整数数组b，其中包含井字棋盘和玩家的移动，其中：

• 0 = 没有设置
• 1 = 玩家 1 (X)
• 2 = 玩家 2 (O)

所以，给定数组b = [ 1, 2, 1, 0, 1, 2, 1, 0, 2 ]将代表棋盘

对于这种情况，您的代码应输出1以指示玩家 1 已获胜。如果没有人获胜，您可以输出0或false。

我自己的（Ruby）解决方案将很快推出。

编辑：抱歉，忘记将其标记为社区 wiki。您可以假设输入格式正确，不必进行错误检查。

更新：请以函数的形式发布您的解决方案。大多数人已经这样做了，但有些人还没有这样做，这并不完全公平。该板作为参数提供给您的函数。结果应该由函数返回。该函数可以具有您选择的名称。

我正在尝试使用迭代 Alpha-Beta 修剪来玩井字游戏，我的移动有一秒钟的限制，但由于某种原因它不能很好地工作。

我修改了常规的 alpha-beta 代码，因此它不是返回 alpha 或 beta，而是返回一个状态（这是下一步的棋盘）

每次我创建孩子时，我都会更新他们的深度。

但是由于某种原因，我一直在输，我看到我的 alpha beta 没有看到最好的举动。

这是我的代码：

外循环：

阿尔法贝塔：

如果有人能告诉我是否有问题，我会非常感激。我怀疑这可能与我返回“s”而不是返回评估的常规 alpha beta 有关，但我没有设法找到错误。

提前致谢，

莉娜

我正在尝试在 C++ 中为游戏 tictactoe 3D 应用 minimax 算法。我正在努力为它找到一个好的评估函数。

有人知道哪里有很好的资源可以找到评估函数吗？

谢谢你。