井字游戏AI做出错误的决定 [英] TicTacToe AI Making Incorrect Decisions
问题描述
一个小背景：作为一种学习的多节点的树木在C ++中，我决定生成所有可能的井字游戏板，并将其存储在一棵树上，这样开始在一个节点分支是可以从该节点遵循所有板，和一个节点的孩子都跟着一个此举板。在那之后，我认为这将是有趣的写一个AI使用该树作为决策树玩井字游戏。
A little background: as a way to learn multinode trees in C++, I decided to generate all possible TicTacToe boards and store them in a tree such that the branch beginning at a node are all boards that can follow from that node, and the children of a node are boards that follow in one move. After that, I thought it would be fun to write an AI to play TicTacToe using that tree as a decision tree.
TTT是一个可以解决的问题，一个完美的球员将永远不会失去，所以它似乎是一个简单的AI至$ C $下我第一次尝试的AI。
TTT is a solvable problem where a perfect player will never lose, so it seemed an easy AI to code for my first time trying an AI.
现在，当我第一次实现了AI，我回去，并增加了两个领域的每一个节点产生在：次＃X将赢得与放大器;次澳＃将赢得低于节点的所有孩子。我想最好的解决办法是简单地拥有我的爱对每个移动选择再往那里赢得次数最多的子树。后来我发现，虽然它发挥完美的大部分时间里，我找到了，我可以击败它。这不是我的code，一个简单的的方式，我有AI选择它的路径问题一个问题。
Now when I first implemented the AI, I went back and added two fields to each node upon generation: the # of times X will win & the # of times O will win in all children below that node. I figured the best solution was to simply have my AI on each move choose and go down the subtree where it wins the most times. Then I discovered that while it plays perfect most of the time, I found ways where I could beat it. It wasn't a problem with my code, simply a problem with the way I had the AI choose it's path.
然后，我决定把它选择了树，无论是最大的胜利为计算机或最大损失的人，无论是多。这使得它有更好的表现，但还不够完善。我仍然可以打败它。
Then I decided to have it choose the tree with either the maximum wins for the computer or the maximum losses for the human, whichever was more. This made it perform BETTER, but still not perfect. I could still beat it.
所以，我有两个想法，我希望上输入这是更好的：
So I have two ideas and I'm hoping for input on which is better:
1），而不是最大化胜或负的，而不是我能一胜，0平局分配值1和-1的损失。然后，具有最高值选择树将是最好的举动，因为下一个节点不能此举造成的损失。这是一个简单的变化，在董事会的产生，但它保留了相同的搜索空间和内存使用情况。还是......
1) Instead of maximizing the wins or losses, instead I could assign values of 1 for a win, 0 for a draw, and -1 for a loss. Then choosing the tree with the highest value will be the best move because that next node can't be a move that results in a loss. It's an easy change in the board generation, but it retains the same search space and memory usage. Or...
2）在董事会的产生，如果有一个板上，使得X或澳的赢在他们的下一步行动，只有$的胜利将产生p $ pvents孩子。没有其他子节点将被视为，然后一代人将继续为后正常。它缩小了树的大小，但我要实现的算法，以确定是否存在一招取胜，我认为只能在线性时间内完成（使电路板产生速度慢了很多，我认为？）
2) During board generation, if there is a board such that either X or O will win in their next move, only the child that prevents that win will be generated. No other child nodes will be considered, and then generation will proceed as normal after that. It shrinks the size of the tree, but then I have to implement an algorithm to determine if there is a one move win and I think that can only be done in linear time (making board generation a lot slower I think?)
这是更好的，或者是有没有更好的解决方案？
Which is better, or is there an even better solution?
推荐答案
根据决策树来实现人工智能的（通常是）正确的方法是使用极大极小的算法：
The (usually) correct way to implement AI based on a decision tree is to use the "Minimax" algorithm:
- 在为每一个叶节点分（+ 1 =玩家获胜，-1 =球员失去，0 =并列）
-
工作的方式上树，应用下列规则对每个节点：
- Assign each leaf node a score (+1=player wins, -1=player loses, 0=tie)
Work your way up the tree, applying the following rules to each node:
- 对于偶数深度（当玩家将做出的举动），摘果子的最高分，并复制比分的节点。
- 在奇数深度（计算机会做出的举动），摘果子得分最低，并复制分数的节点。
当然，奇数和偶数可能需要得到扭转，这取决于你决定先走谁。
Of course, even and odd might need to be reversed, depending on who you decide goes first.
您可以阅读更多的：
- <一个href="http://ai-depot.com/articles/minimax-explained/">http://ai-depot.com/articles/minimax-explained/
- http://en.wikipedia.org/wiki/Minimax
- http://ai-depot.com/articles/minimax-explained/
- http://en.wikipedia.org/wiki/Minimax
这篇关于井字游戏AI做出错误的决定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
