10

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

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

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

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

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

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

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

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

4

4 回答 4

14

基于决策树实现 AI 的（通常）正确方法是使用“ Minimax ”算法：

  1. 为每个叶节点分配一个分数（+1=玩家获胜，-1=玩家失败，0=平局）

  2. 沿着树向上工作，对每个节点应用以下规则：

    • 对于偶数深度（当玩家移动时），选择得分最高的孩子，并将该得分复制到节点。
    • 对于奇数深度（当计算机会移动时），选择得分最低的孩子，并将该得分复制到节点。

当然，偶数和奇数可能需要颠倒，这取决于你决定谁先走。

你可以阅读更多：

于 2009-12-08T19:19:39.433 回答
8

您现有的算法很好，除了您忘记了一件事。永远不要选择任何其他玩家的举动导致您至少无法平局的路径。

因此，基本上，丢弃玩家下一步行动可能导致无法捆绑的情况的任何分支，然后运行您现有的算法。这导致在与非完美对手的比赛中获胜的机会最高，同时消除了失败的可能性。

于 2009-12-08T19:04:14.580 回答
4

Tic-Tac-Toe 可以使用贪心算法来解决，实际上并不需要决策树。

如果您想继续使用当前的算法，请按照 patros 的建议进行操作，并尽量减少在每个决定中失败的可能性。

如果你想要更简单的方法，让 AI 每回合执行以下操作：

  1. 如果可能，完成一个获胜的井字游戏。
  2. 如果可能，阻止对方的井字游戏。

  3. 对每个方格的可取性进行评分，对于在一条线上（由 AI）取的每个方格，为该方格添加一个可取点。对于对手占据的每一个方格，移除一个可取点。

    例如，如果董事会当前是：

    _|O|X
_|X|_
O| |

    左上角的合意性为 0（1 表示同一行中的 X，1 表示对角线中的 X，但每个 Os 为 -1）。

  4. 在最理想的广场上玩耍。任意断绝关系。

    在上面的示例中，AI 会选择右中方格，因为它的合意性为 2，这将导致下一回合获胜。

  5. 如果游戏刚刚开始，则玩中心方块，如果占据中心方块，则随机选择一个角。

  6. 获胜（或平局）。

这是我 10 年级的 Visual Basic 学期项目。与存储决策树相比，它不可能被击败并且需要的内存要少得多。

于 2009-12-08T19:04:57.147 回答
0

这样做的“天真”方法（对于两个玩家轮流移动的任意游戏）是递归地尝试每个可能的移动，直到你最终得到一个赢家的棋盘，然后在树中向上回溯将节点标记为“O 胜”、“X 胜”或“平局”。

每次你走上一步（这样的一步通常称为一层），根据谁的移动，假设玩家选择了最适合他/她的移动。由于您是从叶子节点向上移动，因此您将始终知道每个子节点的最佳可能结果。

在计算子树中可能赢或输的棋盘数量时，您实际上是在假设每个玩家总是会随机移动。正如您所指出的，如果您与聪明的玩家对战，这将不是很有效。相反，我在上面概述的方案假设对手总是做出完美的举动，试图获胜。

于 2009-12-08T19:10:40.603 回答