首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >抽搐脚趾AI虫

问抽搐脚趾AI虫
EN

Stack Overflow用户
提问于 2013-09-13 02:24:06
回答 2查看 1.5K关注 0票数 1

我正在尝试为Tic Tac脚趾实现一个AI,它足够聪明,不会输。我尝试过两种不同的算法,但人工智能仍然会出错。

我从这个最小最大α-β剪枝算法开始。下面是一个现场演示:http://iioengine.com/ttt/minimax.htm

它运行没有错误,但如果你先从左下角,然后其他两个正方形的底部行- AI没有预见到这一点。我确信这不是minimax算法中的一个缺陷--有人能在我的源代码中看到错误吗?您可以检查演示页面以查看所有内容,但下面是主要的ai函数:

代码语言:javascript
复制
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。

用代码更新:

代码语言:javascript
复制
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;
    }
EN

回答 2

Stack Overflow用户

发布于 2013-10-16 14:47:44

问题在于您的evaluateBoard()函数。评价函数是minimax/negamax算法的核心。如果你的人工智能表现不佳,问题通常在于每次移动时董事会的评估。

对于董事会的评估,您需要考虑三件事:赢得移动,阻塞移动,和移动,导致分叉。

获胜移动

静态评估函数需要知道移动是否会导致当前玩家的胜利或损失。如果移动导致当前玩家的损失,则需要返回一个非常低的负数(低于任何常规移动)。如果移动导致当前球员获胜,则需要返回一个非常高的正数(比任何常规移动都大)。

重要的是要记住的是,这个评估必须是。,如果AI目前正在预测人类玩家将在哪里移动,那么评估必须从人类玩家的角度来看董事会。当是AI的动作时,评估必须从电脑播放器的角度来看董事会。

阻塞移动

当你运行你的评估功能,AI实际上并不认为阻止人类玩家是有益的。您的评估函数看起来就像它只是计算可用的移动次数并返回结果。相反,你需要返回一个更高的积极数字,这将有助于人工智能获胜。

要考虑阻塞,您需要弄清楚玩家是否在一个开放的行、列或对角线中有两个他们的标记,然后得分比任何其他方块都高。因此,如果轮到计算机移动,而Human在一个开放的行中有两个记号,则行中的第三个正方形需要有一个较高的正数(但不像获胜的正方形那样高)。这将使计算机优先于任何其他方。

只要考虑到赢得移动和阻挡移动,你将有一台电脑,发挥相当好。

叉动

叉子的移动会给计算机带来问题。主要的问题是这台电脑“太聪明”,而不是它自己的优点。因为它假设人类玩家每次都会做出最好的移动,它会发现它可能做出的所有动作最终都会以失败告终,所以它只会选择董事会上的第一步,因为其他任何事情都没有关系。

如果我们看看你的例子,我们可以看到这样的情况:人类玩家在左下角,电脑在中间。

代码语言:javascript
复制
   | O |
---+---+---
   |   |
---+---+---
 X |   |   

当Humans移动到右下角时,计算机会看到,如果它试图阻止该移动,则Humans所做的最佳移动是采取中间正方形,从而为人类带来叉和胜利(尽管由于人类容易出错,计算机也不知道这一点)。

代码语言:javascript
复制
   | O |
---+---+---
   | X |
---+---+---
 X | O | X  

因为不管是阻止还是不阻止人类获胜,计算机都会输掉,所以阻塞人类实际上会使得分降到最低(因为它会给计算机造成损失)。这意味着计算机将获得它所能得到的最好的分数--中间正方形。

你必须弄清楚处理这种情况的最佳方法是什么,因为每个人都会有不同的表现。这只是一些需要注意的事情。

票数 2
EN

Stack Overflow用户

发布于 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人工智能只会赢(如果人类玩家至少犯了一个关键错误)或平局(如果人类玩家总是做出最好的移动)。这是正确的,无论谁采取第一步。

我自己实现了这一点,它的工作就像预期的那样。

以下是一些更好的要点(我对此感到有些挣扎):

  • 确保用于评估板的功能运行良好,即当X和O出现双赢/平手情况时,它会正确地定位位置。在您构建Minimax树的几乎每个节点上都会使用此函数,并且当您构建它时,它的错误将导致它看起来工作,但实际上是有缺陷的代码。广泛测试此部分
  • 确保您正确地导航您的树,特别是当您正在得分中间节点(但当您正在寻找下一个移动)。一个简单的解决方案是,沿着树的一侧,生成一个哈希表,其中包含每个中间节点(非叶节点)每层树的深度。这样,您将确保得到所有节点在正确的时间,当你做自下而上的得分。
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/18777294

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档