我正在尝试为Tic Tac脚趾实现一个AI,它足够聪明,不会输。我尝试过两种不同的算法,但人工智能仍然会出错。
我从这个最小最大α-β剪枝算法开始。下面是一个现场演示:http://iioengine.com/ttt/minimax.htm
它运行没有错误,但如果你先从左下角,然后其他两个正方形的底部行- AI没有预见到这一点。我确信这不是minimax算法中的一个缺陷--有人能在我的源代码中看到错误吗?您可以检查演示页面以查看所有内容,但下面是主要的ai函数:
function bestMove(board,depth,low,high,opponent){
var best=new Move(null,-iio.maxInt);
var p;
for (var c=0;c<grid.C;c++)
for(var r=0;r<grid.R;r++){
if (board[c][r]=='_'){
var nuBoard=board.clone();
nuBoard[c][r]=getTypeChar(opponent);
if(checkWin(nuBoard,getTypeChar(opponent)))
p=new Move([c,r],-evaluateBoard(board,getTypeChar(opponent))*10000);
else if (checkScratch(nuBoard))
p=new Move([c,r],0);
else if (depth==0)
p=new Move([c,r],-evaluateBoard(board,getTypeChar(opponent)));
else {
p=bestMove(nuBoard,depth-1,-high,-low,!opponent);
}
if (p.score>best.score){
best=p;
if (best.score > low)
low=best.score;
if (best.score >= high) return best;
}
}
}
return best;
}如果你对否定比较熟悉的话,我也试过了。我直接从此页中提升了逻辑。下面是一个现场演示:http://iioengine.com/ttt/negamax.htm
一旦你达到一个胜利状态,它就会结冰,但是你已经可以看到人工智能是相当愚蠢的。代码集成有什么问题吗?
如果您在我的代码中发现一个缺陷,使这些算法无法正常运行,请告诉我。Thnx。
用代码更新:
function checkWin(board,type){
for (var i=0;i<3;i++)
if (evaluateRow(board,[i,0,i,1,i,2],type) >= WIN_SCORE
||evaluateRow(board,[0,i,1,i,2,i],type) >= WIN_SCORE)
return true;
if(evaluateRow(board,[0,0,1,1,2,2],type) >= WIN_SCORE
||evaluateRow(board,[2,0,1,1,0,2],type) >= WIN_SCORE)
return true;
return false;
}
function evaluateBoard(board,type){
var moveTotal=0;
for (var i=0;i<3;i++){
moveTotal+=evaluateRow(board,[i,0,i,1,i,2],type);
moveTotal+=evaluateRow(board,[0,i,1,i,2,i],type);
}
moveTotal+=evaluateRow(board,[0,0,1,1,2,2],type);
moveTotal+=evaluateRow(board,[2,0,1,1,0,2],type);
return moveTotal;
}发布于 2013-10-16 14:47:44
问题在于您的evaluateBoard()函数。评价函数是minimax/negamax算法的核心。如果你的人工智能表现不佳,问题通常在于每次移动时董事会的评估。
对于董事会的评估,您需要考虑三件事:赢得移动,阻塞移动,和移动,导致分叉。
获胜移动
静态评估函数需要知道移动是否会导致当前玩家的胜利或损失。如果移动导致当前玩家的损失,则需要返回一个非常低的负数(低于任何常规移动)。如果移动导致当前球员获胜,则需要返回一个非常高的正数(比任何常规移动都大)。
重要的是要记住的是,这个评估必须是。,如果AI目前正在预测人类玩家将在哪里移动,那么评估必须从人类玩家的角度来看董事会。当是AI的动作时,评估必须从电脑播放器的角度来看董事会。
阻塞移动
当你运行你的评估功能,AI实际上并不认为阻止人类玩家是有益的。您的评估函数看起来就像它只是计算可用的移动次数并返回结果。相反,你需要返回一个更高的积极数字,这将有助于人工智能获胜。
要考虑阻塞,您需要弄清楚玩家是否在一个开放的行、列或对角线中有两个他们的标记,然后得分比任何其他方块都高。因此,如果轮到计算机移动,而Human在一个开放的行中有两个记号,则行中的第三个正方形需要有一个较高的正数(但不像获胜的正方形那样高)。这将使计算机优先于任何其他方。
只要考虑到赢得移动和阻挡移动,你将有一台电脑,发挥相当好。
叉动
叉子的移动会给计算机带来问题。主要的问题是这台电脑“太聪明”,而不是它自己的优点。因为它假设人类玩家每次都会做出最好的移动,它会发现它可能做出的所有动作最终都会以失败告终,所以它只会选择董事会上的第一步,因为其他任何事情都没有关系。
如果我们看看你的例子,我们可以看到这样的情况:人类玩家在左下角,电脑在中间。
| O |
---+---+---
| |
---+---+---
X | | 当Humans移动到右下角时,计算机会看到,如果它试图阻止该移动,则Humans所做的最佳移动是采取中间正方形,从而为人类带来叉和胜利(尽管由于人类容易出错,计算机也不知道这一点)。
| O |
---+---+---
| X |
---+---+---
X | O | X 因为不管是阻止还是不阻止人类获胜,计算机都会输掉,所以阻塞人类实际上会使得分降到最低(因为它会给计算机造成损失)。这意味着计算机将获得它所能得到的最好的分数--中间正方形。
你必须弄清楚处理这种情况的最佳方法是什么,因为每个人都会有不同的表现。这只是一些需要注意的事情。
发布于 2014-08-19 15:38:44
对于Tic-Tac-Toe的纯Minimax实现,人工智能不应失败。在最坏的情况下,它应该成为平局。
所谓纯Minimax,我指的是一个实现,它探索每一个可能的移动(实际上从一个移动到另一个移动),并为所述的移动和转换创建一个树(从树顶部的一个空板开始,在所有可能的第一步中分支,然后所有可能的第二步,等等)。
(还有启发式的Minimax,从一开始就不呈现树节点中的所有位置,而是只呈现一定的深度。)
树应该只有板子的位置结束游戏(X赢,O赢或平局)。这样一个分类Tic-Tac-Toe (3x3板)的树包含5477个节点(不包括顶部的全空板)。
一旦创建了这样一棵树,就可以通过简单地评估游戏的结束方式来直接对叶子进行评分:一个叶子节点的得分最高,其中包含A.I.获胜的棋盘状态、平局的0分和人类玩家获胜的棋盘状态下的最低得分。
(在启发式Minimax中,您必须创建一个“猜测”函数,该函数评估部分树的leafs,并相应地分配min/0/max分数--在此实现中,人工智能可能会在最后丢失一个机会,该机会与您的“猜测器”功能在评估部分游戏状态时的良好程度成反比)。
接下来,所有中间的,非叶节点的树是根据他们的孩子打分.显然,您会做到自下而上,就像最初一样,只有最低的非叶节点有得分子节点(叶节点),从中得到他们自己的分数。
(在Tic-Tac-Toe的上下文中,没有必要对Minimax进行启发式实现,因为用5477 +1节点呈现一棵树,然后将它们全部得分是相当便宜的。这种实现对于有很多分支(对于给定的游戏状态有很多可能的移动)的游戏非常有用,从而形成一个慢/内存占优势的完整树,比如国际象棋)。
最后,您将有一个包含所有可能的Tic-Tac-Toe游戏的数据结构,以及对人类玩家所做的任何移动做出反应的最佳动作的确切概念。因此,由于Tac Toe规则的工作方式,Minimax人工智能只会赢(如果人类玩家至少犯了一个关键错误)或平局(如果人类玩家总是做出最好的移动)。这是正确的,无论谁采取第一步。
我自己实现了这一点,它的工作就像预期的那样。
以下是一些更好的要点(我对此感到有些挣扎):
https://stackoverflow.com/questions/18777294
复制相似问题