TicTacToe AI做出错误的决策

Question

小背景:为了学习C++中的多节点树，我决定生成所有可能的TicTacToe板并将它们存储在树中，这样从节点开始的分支就是可以跟随该节点的所有板，而节点的子节点就是一步到位的板。在那之后，我认为用这棵树作为决策树来编写一个AI来玩TicTacToe会很有趣。

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

现在，当我第一次实现AI时，我返回并一代又一代地为每个节点添加了两个字段:X将获胜的次数&O在该节点下的所有子节点中获胜的次数。我认为最好的解决方案是让我的人工智能在每次移动时选择并沿着它赢得最多次数的子树下。然后我发现，虽然它大部分时间都玩得很好，但我找到了可以击败它的方法。这不是我的代码的问题，只是我让AI选择它的路径的方式的问题。

然后我决定让它选择对计算机或人类损失最大的树，取两者中较多者。这使得它的性能更好，但仍然不完美。我还是可以打败它的。

所以我有两个想法，我希望得到关于哪一个更好的意见：

1)而不是最大化输赢，相反，我可以为胜利赋值1，为平局赋值0，为输赋值-1。那么选择具有最高值的树将是最好的移动，因为下一个节点不能是导致丢失的移动。这在电路板生成中很容易改变，但它保留了相同的搜索空间和内存使用量。或者..。

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

哪一个更好，还是有更好的解决方案？

Answer 1

(通常)实现基于决策树的AI的正确方法是使用"Minimax“算法：

1. 为每个叶节点分配一个分数(+1=player wins，-1=player loses，0=tie)
2. 在树中向上移动，对每个节点应用以下规则：

- For even depths (when the player would make a move), pick the child with the highest score, and copy that score to the node.
- For odd depths (when the computer would make a move), pick the child with the lowest score, and copy that score to the node.

​

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

您可以在以下位置阅读更多内容：

• http://ai-depot.com/articles/minimax-explained/
• http://en.wikipedia.org/wiki/Minimax

Answer 2

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

所以基本上，丢弃玩家下一步可能导致不可用情况的任何分支，然后运行您现有的算法。这导致了最高的机会赢得一个非完美的对手，同时消除了失败的可能性。

Answer 3

Tic-Tac-Toe可以使用greedy algorithm来解决，并且不需要决策树。

如果您想继续使用当前的算法，请按照巡查的建议进行操作，并将每次决策失败的可能性降至最低。

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

如果可能的话，possible.

• Block

1. 完成了一个获胜的Tic-Tac-Toe，如果可能的话，
2. 会根据每个方块的可取性对每个方块进行评分，对于每个方块(由AI在一条线上)取的每个方块，为该方块增加一分可取程度。对于对手占据的每个方块，移除一个合意点。

例如，如果电路板当前为：

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

左上角的可取值为0 (1代表同一行中的X，1代表对角线中的X，但-1代表每个O)。

• 在最理想的方块上玩。任意断绝关系。

在上面的例子中，AI会选择右边中间的方块，因为它的可取性为2，这将导致下一轮获胜。

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

• win (或平局)。

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