先简单介绍一下背景：为了学习 C++ 中的多节点树，我决定生成所有可能的井字棋棋盘，并将它们存储在一棵树中，这样从一个节点开始的分支就是所有可以从该节点演变的棋盘，而一个节点的子节点就是下一步棋演变的棋盘。之后，我想编写一个 AI 来使用这棵树作为决策树玩井字棋，应该会很有趣。
井字棋是一个可解的问题，一个完美的玩家永远不会输，因此对于我第一次尝试编写 AI 来说，这似乎是一个简单的 AI。
现在，当我第一次实现 AI 时，我回头在每个节点上添加了两个字段：X 获胜的次数 & O 在该节点以下的所有子节点中获胜的次数。我认为最好的解决方案是让我的 AI 在每一步都选择并进入它获胜次数最多的子树。然后我发现，虽然它在大多数时候都表现完美，但我找到了我可以击败它的方法。这不是我的代码问题，只是我让 AI 选择路径的方式有问题。
然后我决定让它选择计算机获胜次数最多或人类失败次数最多的树，以哪个为准。这使它的表现更好，但仍然不完美。我仍然可以击败它。
所以我有两个想法，我希望得到关于哪个更好的建议：
1) 我可以不最大化胜负次数，而是为胜利赋值为 1，平局赋值为 0，失败赋值为 -1。然后选择具有最高值的树将是最佳行动，因为下一个节点不可能是导致失败的行动。这对棋盘生成来说是一个简单的改变，但它保留了相同的搜索空间和内存使用量。或者…
2) 在棋盘生成期间，如果存在一个棋盘，使得 X 或 O 将在他们的下一步行动中获胜，则只会生成阻止该胜利的子节点。不会考虑其他子节点，然后生成将照常进行。它缩小了树的大小，但我必须实现一个算法来确定是否存在一步获胜的可能性，我认为这只能以线性时间完成（我认为这会使棋盘生成慢很多？）
哪个更好，或者是否有更好的解决方案？
回答：
基于决策树实现 AI 的（通常）正确方法是使用 “Minimax” 算法：
- 为每个叶节点分配一个分数（+1=玩家获胜，-1=玩家失败，0=平局）
-
逐步向上遍历树，对每个节点应用以下规则：
- 对于偶数深度（当玩家采取行动时），选择具有最高分数的子节点，并将该分数复制到该节点。
- 对于奇数深度（当计算机采取行动时），选择具有最低分数的子节点，并将该分数复制到该节点。
当然，奇数和偶数可能需要反转，这取决于你决定谁先走。
你可以在以下网址阅读更多内容：
