Chr*_*ass 10 algorithm artificial-intelligence decision-tree tic-tac-toe
一点背景:作为一种在C++中学习多节点树的方法,我决定生成所有可能的TicTacToe板并将它们存储在一棵树中,这样从一个节点开始的分支都是可以跟随该节点的板,以及节点是一步到位的板.在那之后,我认为使用该树作为决策树编写AI来玩TicTacToe会很有趣.
TTT是一个可以解决的问题,一个完美的玩家永远不会丢失,所以我第一次尝试AI时编码似乎很简单.
现在,当我第一次实现AI时,我回过头来为每个节点添加两个字段:X将赢得的次数和O将在该节点下的所有子节点中获胜的次数.我认为最好的解决方案就是让我的每一步动作都选择AI,然后选择最能赢得次数的子树.然后我发现虽然它在大部分时间都是完美的,但我找到了可以击败它的方法.这对我的代码来说不是问题,只是我用AI选择它的路径的问题.
然后我决定让它选择具有计算机最大胜利或人类最大损失的树,以较多者为准.这使它表现更好,但仍然不完美.我仍然可以击败它.
所以我有两个想法,我希望得到更好的输入:
1)而不是最大化赢或输,而是我可以为胜利分配1,为平局分配0,为亏损分配-1.然后选择具有最高值的树将是最佳移动,因为下一个节点不能是导致丢失的移动.这是电路板生成中的一个简单更改,但它保留了相同的搜索空间和内存使用量.要么...
2)在棋盘生成期间,如果有一个棋盘使X或O在下一步中获胜,则只会产生阻止该胜利的孩子.不会考虑其他子节点,然后生成将在此之后正常进行.它缩小了树的大小,但后来我必须实现一个算法来确定是否有一个移动获胜,我认为这只能在线性时间内完成(我认为让板子生成慢很多？)
哪个更好,还是有更好的解决方案？
Edw*_*per 14
基于决策树实现AI的(通常)正确方法是使用" Minimax "算法:
在树上工作,将以下规则应用于每个节点:
当然,偶数和奇数可能需要颠倒,这取决于你决定先行的人.
您可以在以下网址阅读更多
你现有的算法是好的,除了你忘了一件事.永远不要选择任何其他玩家移动导致你无法至少打结的路径.
所以基本上,丢弃玩家下次移动的任何分支都可能导致无法绑定的情况,然后运行现有的算法.这导致赢得对抗非完美对手的最高机会,同时消除失败的可能性.
| 归档时间： |
|
| 查看次数： |
3934 次 |
| 最近记录： |