井字游戏AI作出不正确的决定

Question

一个小小的背景：作为一个学习方式多节点的树木在C++，我决定产生的所有可能的井字游戏板，并将它们存储在一棵树上这样的分行开始在一个节点都是委员会可以按照从这一节点，以及儿童的一个节点是委员会的后续在一个动。在那之后，我认为这将是有趣的写一AI玩井字游戏的使用，树作为一个决策树。

递是一个可以解决的问题，在一个完美的玩家永远不会失去，因此它似乎是一个容易AI码我的第一次尝试。

现在，当我第一次执行AI,我回去，并添加了两个领域中每个节点时代：该#次X将赢得及的时间O将赢得所有以下的儿童，节点。我想最好的解决办法是只有我AI在每个移动的选择和走下子树在那里赢得多数倍。然后我发现，而它起着完美的大部分时间，我找到了种方式在那里我可以打败它。它不是一个问题与我的代码，只需一问题的方式，我有AI选择的道路。

然后我决定把它选择的树用的最大胜利用计算机或最大损失的人，取得更多。这使它更好地执行，但仍不完善。我仍然可以击败它。

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

1)替代的最大胜利或损失，而不是我能分配的价值观的1个赢,0用于绘制和-1为一个损失。然后选择的树高值将是最好的移动因为那下一个节点可以不被一个移动，结果在一个损失。这是一个简单的改变委员会的产生，但它保留了同样的搜索空间和存储使用。或者...

2)在董事会代，如果有一个董事会这样的，无论是X或O将会赢得他们的下一步行动，只有儿童，防止了这场胜利会将产生的。没有其他的儿童节点将被考虑，然后代人将继续作为正常之后。它缩小尺寸的树，但是然后我需要实行一个算法来确定是否存在一个移动的胜利和我认为，才可以进行在线性时间(使董事会代慢了很多，我觉得吗？)

这是更好的，或者是有更好的解决方案吗？

Answer 1

(通常)正确的方式来实施AI的基础上决策树是使用"Minimax"算法：

1. 分配给每个叶节点分(+1=玩家获胜,-1=了,0=领带)

2. 你的工作方式，树，运用以下规则，每个节点：

   • 甚至深度(当球员会做出的举动)，儿童的最高分，并拷贝这是你的节点。
   • 奇怪的深度(当的计算机将作出的举动)，挑选的儿童得分最低，并拷贝这是你的节点。

当然，即使奇可能需要加以逆转，这取决于你的决定先行。

你可以读取更多的：

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

Answer 2

您现有的算法是好的，但你忘了一两件事。千万不要选择任意路径，其中一个举动其他球员造成您暂时无法至少领带。

所以基本上，丢弃任何分支，其中的下一步行动的玩家可能会导致一个未tieable情况再运行现有的算法。这导致获奖对一个不完美的对手，同时消除丢失的可能性最高的机会。

Answer 3

井字游戏可以解决的使用 贪婪的算法 并不真的需要决定树。

如果你想继续使用目前的算法，做为patros建议，并尽可能减少失去的每一个决定。

如果你想要一个简单的方法有AI做以下每个转：

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

3. 各方针对其可取性，对于每一个其他取广场(由AI)上一条线，增加一点是否应该广场。为每平方采取的对手，除去一点的意。

   例如，如果委员会目前正:

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

   左上角有一个可取的0(1的X在同一行中，1的X在的对角线，但-1为每个Os)。

4. 玩上最理想的平方。打破的联系的随意。

   在从上面的例子，艾会选择中的权利平，因为它有一个可取的2，这会导致一场胜利的以下转。

5. 如果游戏才刚刚开始，发挥中心广场，如果在中心方采取选择一个角落。

6. 赢得(或).

这是我的10年级些基本期的项目。它不可能击败，并需要远远少内存存储的决定树。

Answer 4

在“幼稚”的方式来做到这一点（对两个玩家轮流做一招任意游戏）是向上尝试每个可能的移动递归，直到你结束了董事会，其中一个是赢家，那么反向跟踪树中的标记的节点为“○胜”，“X胜”或“画”。

每个你抓紧时间（一个这样的步骤通常被称为层），取决于谁的举动是，假设玩家选择，是最适合他/她的举动。因为你是从叶片移动和向上，你将永远知道每个子节点的最佳可能的结果。

当计数的数量的可能获胜的或在子树失去板，你基本上是假定每个玩家总会让一个随机的举动。正如你提到的，如果你对战聪明的球员，这将不会是非常有效的。我上面，而不是列出的方案假设对手总是使一个完美的举动，试图赢得。