MiniMax 算法的一个非常有趣的问题。什么可能导致这种行为?

A very interesting problem with the MiniMax algorithm. What could cause this behaviour?

我已经实现了 MiniMax 算法(带有 alpha-beta 修剪),但是它的行为方式很有趣。我的玩家将创造巨大的领先优势,但是当需要做出最后的、获胜的一步时,它并没有采取那一步,而是继续拖延比赛。

这是我的极小极大函数:

// Game states are represented by Node objects (holds the move and the board in that state)
//ValueStep is just a pair holding the minimax value and a game move (step) 

private ValueStep minimax(Node gameState,int depth,int alpha,int beta) {

  //Node.MAXDEPTH is a constant
  if(depth == Node.MAXDEPTH || gameOver(gameState.board)) {
      return new ValueStep(gameState.heuristicValue(),gameState.step);
  }

  //this method definately works. child nodes are created with a move and an 
  //updated board and MAX value
  //which determines if they are the maximizing or minimizing players game states.
  gameState.children = gameState.findPossibleStates();

  if(state.MAX) { //maximizing player
      ValueStep best = null;

      for(Node child: gameState.children) {

          ValueStep vs = new ValueStep(minimax(child,depth+1,alpha,beta).value,child.move);

          //values updated here if needed
          if(best==null || vs.value > best.value) best = vs;

          if(vs.value > alpha) alpha = vs.value;

          if(alpha >= beta) break;
      }

      return best;

  } else { //minimizing player
      ValueStep best = null;

      for(Node child: gameState.children) {

          ValueStep vs = new ValueStep(minimax(child,depth+1,alfa,beta).value,child.move);

          if(best==null || vs.value < best.value) best = vs;

          if(vs.value < beta) beta = vs.value;

          if(alpha >= beta) break;
      }

      return best;
  }

}

起初我以为问题出在我的评估函数上,但如果是,我找不到它。在这个游戏中,两个玩家都有一个分数,我的函数只是根据分数差计算启发式值。 这是:

public int heuristicValue() {

       //I calculate the score difference here in this state and save it in 
       //the variable scoreDiff. scoreDiff will be positive if I am winning 
       //here, negative if im loosing.

        //"this" is a Node object here. If the game is over here, special
        //heuristic values are returned, depending on who wins (or if its a 
        //draw) 
        if(gameOver(this.board)) {
            if(scoreDiff>0) {
                return Integer.MAX_VALUE;  
            } else if(scoreDiff==0) {
                return 0;
            } else {
                return Integer.MIN_VALUE;
            }
        }

        int value = 0;
        value += 100*scoreDiff; //caluclate the heuristic value using the score differerence. If its high, the value will be high as well 

      return value;
  }

我已经 "translated" 将我的代码翻译成英文,所以可能会有拼写错误。我相当确定问题出在某个地方,但如果您需要其他代码,那么我会更新问题。同样,我的玩家可以创造优势,但由于某种原因它不会做出最后的致胜棋。 感谢您的帮助!

假设您的 Minimax 玩家处于可以证明可以保证获胜的位置。通常会有许多不同的方式来保证最终的胜利。有的走法可能是速胜,有的走法可能会把比赛拖到不必要的地步……只要不是真正愚蠢的走法突然让对方赢(或平),都是赢,而且都是一样的博弈论价值(Integer.MAX_VALUE 在你的代码中)。

您的 Minimax 算法不区分这些着法,而只是着手恰好是 gameState.children 列表中第一个的着法。这可能是一场快速而肤浅的胜利,也可能是一场缓慢而深刻的胜利。

有两种简单的方法可以让您的 Minimax 算法优先考虑快赢而不是慢赢:

  1. 最好的选择(因为它还有许多其他优点)是使用迭代深化。您可以查看详细信息,但基本思想是首先进行深度限制为 1 的 Minimax 搜索,然后进行深度限制为 2 的另一个搜索,然后深度限制为 3,等等。您的其中一项搜索证明是胜利,您可以终止搜索并执行该获胜步骤。这将使您的算法始终更喜欢最短的胜利(因为最先找到)。
  2. 或者,您可以修改 heuristicValue() 函数以合并搜索深度。例如,您可以 return Integer.MAX_VALUE - depth 中奖位置。那会让更快的胜利实际上有稍微大的评价。