1

我正在尝试为井字游戏实现一个人工智能，它足够聪明，不会输。我尝试了两种不同的算法，但人工智能仍然会出错。

我从这个minimax alpha-beta pruning algorithm开始。这是一个现场演示：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;
    }

如果您更熟悉 negamax，我也尝试过。我直接从这个页面中提取了逻辑。这是一个现场演示：http: //iioengine.com/ttt/negamax.htm

一旦你达到胜利状态，它就会冻结，但你已经可以看到人工智能非常愚蠢。代码集成有问题吗？

如果您在我的代码中发现阻止这些算法正常运行的缺陷，请告诉我。谢谢。

用代码更新：

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;
    }
4

2 回答 2

2

The problem lies in your evaluateBoard() function. The evaluation function is the heart of a minimax/negamax algorithm. If your AI is behaving poorly, the problem usually lies in the evaluation of the board at each move.

For the evaluation of the board, you need to take into consideration three things: winning moves, blocking moves, and moves that result in a fork.

Winning Moves

The static evaluation function needs to know if a move results in a win or a loss for the current player. If the move results in a loss for the current player, it needs to return a very low negative number (lower than any regular move). If the move results in a win for the current player, it needs to return a very high positive number (larger than any regular move).

What is important to remember is that this evaluation has to be relative to the player whose turn the AI is making. If the AI is currently predicting where the Human player will move, then the evaluation must look at the board from the point of view of the Human player. When it's the AI's turn move, the evaluation must look at the board from the point of view of the Computer player.

Blocking Moves

When you run your evaluation function, the AI actually doesn't think blocking the Human player is beneficial. Your evaluation function looks like it just counts the number of available moves and returns the result. Instead, you need to return a higher positive number for moves that will help the AI win.

To account for blocking, you need to figure out if a player has 2 of their tokens in an open row, column, or diagonal, and then score the blocking square higher than any other square. So if it is the Computer's turn to move, and the Human player has 2 tokens in an open row, the 3rd square in the row needs to have a high positive number (but not as high as a winning square). This will cause the computer to favor that square over any others.

By just accounting for Winning moves and Blocking moves, you will have a Computer that plays fairly well.

Forking Moves

Forking moves cause problems for the Computer. The main problem is that the Computer is 'too smart' for it's own good. Since it assumes that the Human player will always make the best move every time, it will find situations where all moves that it could make will eventually end in a loss for it, so it will just pick the first move on the board it can since nothing else matters.

If we go through your example, we can see this happen: Human player plays bottom left, Computer plays top middle.

   | O |
---+---+---
   |   |
---+---+---
 X |   |

When the Human player makes a move to the bottom right corner, the Computer sees that if it tries to block that move, the best move the Human player would make is to take the middle square, resulting in a fork and a win for the Human (although this won't happen even time since Humans are fallible, the Computer doesn't know that).

   | O |
---+---+---
   | X |
---+---+---
 X | O | X

Because the computer will lose whether it blocks or doesn't block the Human from winning, blocking the Human will actually bubble up the lowest possible score (since it results in a loss for the Computer). This means that the Computer will take the best score it can - the middle square.

You'll have to figure out what is the best way to handle such situations, since everyone would play it differently. It's just something to be aware of.

于 2013-10-16T14:47:44.257 回答
1

对于井字游戏的纯 Minimax 实现，AI 永远不会输。在最坏的情况下，它应该进入平局。

纯粹的极小极大，我的意思是探索每一个可能的移动（实际上是从一个移动到另一个移动）并为所述移动和过渡创建一个树（从树顶部的一个空板开始，分支到所有可能的第一步，然后是所有可能的第二步，等等）。

（还有启发式 Minimax，您不会从一开始就渲染树节点中的所有位置，而只会渲染一定的深度。）

这棵树的叶子应该只有结束游戏的棋盘位置（X 胜、O 胜或平局）。这样一棵用于分类井字游戏（3x3 棋盘）的树包含 5477 个节点（不包括顶部的全空棋盘）。

一旦创建了这样的树，就可以通过简单地评估游戏的结束方式来直接对叶子进行评分：包含 AI 获胜的棋盘状态的叶子节点得分最高，平局得分为 0，具有人类棋盘状态的节点得分最低玩家赢了。

（在启发式 Minimax 中，您必须创建一个“猜测”函数，该函数评估部分树的叶子并相应地分配 min/0/max 分数 - 在此实现中，AI 有可能最终会失败，并且该机会与您的“猜测者”功能在评估部分游戏状态方面的好坏成反比。）

接下来，树的所有中间非叶节点都根据它们的子节点进行评分。显然，您将自下而上地进行此操作，因为最初，只有最低的非叶节点具有得分的子节点（叶节点），从中得出自己的分数。

（在井字游戏的上下文中，对 Minimax 进行启发式实现是没有意义的，因为渲染具有 5477 + 1 个节点的树，然后对它们全部进行评分是相当便宜的。这种实现对于以下游戏很有用有很多分支（对于给定的游戏状态有很多可能的移动），因此会形成一个缓慢/内存占用的完整树 - 例如国际象棋））

最后，您将拥有一个包含所有可能的井字游戏的数据结构，并准确了解响应人类玩家所做的任何动作的最佳动作是什么。因此，由于井字游戏规则的运作方式，Minimax AI 只会赢（如果人类玩家至少犯了一个严重错误）或平局（如果人类玩家总是做出最好的举动）。无论谁先采取行动，这都是正确的。

我自己实现了这个，它按预期工作。

以下是一些更好的观点（我有点挣扎）：

  • 确保您用来评估棋盘的函数运行良好，即当 X 和 O 出现获胜/平局情况时，它可以正确识别。在您构建 Minimax 树的几乎每个节点时，都会使用此函数，并且将其排除故障将导致看似有效但实际上有缺陷的代码。广泛测试这部分

  • 确保您正确导航您的树，尤其是在您对中间节点进行评分时（以及在您搜索下一步要进行的操作时）。一个简单的解决方案是在树旁边制作一个哈希表，其中包含每个树深度级别的每个中间节点（非叶节点）。这样，当您进行自下而上评分时，您将确保在正确的时间获得所有节点。

于 2014-08-19T15:38:44.803 回答