一点背景知识:作为在 C++ 中学习多节点树的一种方法,我决定生成所有可能的 TicTacToe 棋盘并将它们存储在树中,以便从节点开始的分支都是可以从该节点开始的所有棋盘,以及节点是一步步跟随的棋盘。之后,我认为编写一个人工智能来使用该树作为决策树来玩 TicTacToe 会很有趣。
TTT 是一个可以解决的问题,完美的玩家永远不会输,所以对于我第一次尝试人工智能来说,它似乎是一个很容易编写的人工智能。
现在,当我第一次实现人工智能时,我返回并在生成时向每个节点添加了两个字段:在该节点下的所有子节点中,X 将获胜的次数和 O 将获胜的次数。我认为最好的解决方案是简单地让我的人工智能在每次移动时选择并沿着它获胜次数最多的子树走下去。然后我发现,虽然它在大多数时候都表现得很完美,但我找到了可以击败它的方法。这不是我的代码的问题,只是我让人工智能选择路径的方式有问题。
然后我决定让它选择计算机获胜最大的树或人类损失最大的树,以较大者为准。这使得它的性能更好,但仍然不完美。我仍然可以打败它。
所以我有两个想法,希望大家能提出意见,哪个更好:
1)我不是最大化胜利或失败,而是可以为胜利指定值 1,为平局指定值 0,为失败指定 -1。然后选择具有最高值的树将是最好的移动,因为下一个节点不能是导致损失的移动。这是主板一代的一个简单更改,但它保留了相同的搜索空间和内存使用情况。或者...
2) 在棋盘生成过程中,如果有一个棋盘使得 X 或 O 在下一步行动中获胜,则只会生成阻止获胜的子棋盘。不会考虑其他子节点,之后生成将正常进行。它缩小了树的大小,但是我必须实现一种算法来确定是否有一步获胜,我认为这只能在线性时间内完成(我认为这会使棋盘生成速度慢很多?)
哪个更好,或者有更好的解决方案吗?
基于决策树实现人工智能的(通常)正确方法是使用“Minimax“ 算法:
- 为每个叶节点分配一个分数(+1=玩家获胜,-1=玩家失败,0=平局)
-
沿着树向上移动,将以下规则应用于每个节点:
- 对于偶数深度(当玩家移动时),选择得分最高的子节点,并将该得分复制到节点。
- 对于奇数深度(当计算机将进行移动时),选择分数最低的子节点,并将该分数复制到节点。
当然,偶数和奇数可能需要颠倒,具体取决于您决定谁先走。
您可以在以下位置阅读更多内容:
- http://ai-depot.com/articles/minimax-explained/ http://ai-depot.com/articles/minimax-explained/
- http://en.wikipedia.org/wiki/Minimax http://en.wikipedia.org/wiki/Minimax
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)