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

Question

我已经实现了 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;  }}我已经将我的代码“翻译”成英文，所以可能有错别字。我相当确定问题出在某个地方，但是如果您需要其他代码，那么我会更新问题。同样，我的玩家可以创造优势，但由于某种原因它不会做出最后的胜利。我感谢您的帮助！

Answer 1

假设您的 Minimax 玩家处于可以证明它可以保证获胜的位置。通常有许多不同的方式仍然可以保证最终获胜。有些招式可能是立竿见影的，有些招式可能会不必要地拖延比赛……只要不是真正愚蠢的招式突然让对手获胜（或平局），它们都是胜利，它们都有相同的博弈论价值（Integer.MAX_VALUE在您的代码中）。

您的 Minimax 算法不区分这些移动，而只是播放恰好是您gameState.children列表中第一个的移动。这可能是一场快速、浅薄的胜利，也可能是一场缓慢、非常深刻的胜利。

有两种简单的方法可以让您的 Minimax 算法优先考虑快速获胜而不是缓慢获胜：

1. 最好的选择（因为它还有许多其他优点）是使用Iterative Deepening。您可以查看详细信息，但基本思想是首先进行深度限制为 1 的 Minimax 搜索，然后进行深度限制为 2 的另一个搜索，然后深度限制为 3，依此类推。您的一次搜索证明获胜，您可以终止搜索并玩该获胜动作。这将使您的算法始终更喜欢最短的胜利（因为那些是最先找到的）。

2. 或者，您可以修改您的heuristicValue()函数以合并搜索深度。例如，您可以Integer.MAX_VALUE - depth在获胜位置返回。这将使更快的胜利实际上具有稍大的评估。