algorithm - Minimax 算法没有按预期工作

Question

我目前正在使用 C# 开发针对 AI 的西洋跳棋游戏。我尝试使用 minimax 算法来实现 AI。尽管我的功能有效，但它选择的 Action 根本不符合逻辑。我用很多游戏和算法测试了它，当有很多更好的选择时，它只会选择不好的 Action 。我不认为这是由于地平线问题，因为它的移动会产生直接后果，例如在没有捕获任何对手棋子的情况下丢失棋子。关于代码的 Som 注释:

• 我的函数采用一个 8x8 二维枚举 Pieces 数组，代表棋盘。
• BlackPlayer 是一个 bool 值，属于同一个类中的函数。
• MyPiece(currentPiece) 函数检查 currentPiece 是否与 AI 颜色相同。
• 由于捕获在西洋跳棋中是强制性的，因此函数首先检查 gameState 是否包含任何捕获 Action 。如果不是检查正常移动。
• 我使用 alpha-beta 修剪来提高效率。

• 我使用 CloneGameState(gameState) 函数复制二维数组，这样代表游戏的原始数组就不会改变。

  public int Minimax (Pieces[,] gameState, int depth, bool is_maximizing, int alpha, int beta)
  {
      //Base Case - Return the board value 
      if (depth == 3)
          return HeuristicEvaluation(gameState);
  
      Move[] possibleMoves;
      int bestValue;
      bool currentSide;
  
      if (is_maximizing)
      {
          bestValue = int.MinValue;
          currentSide = BlackPlayer;
      }
      else
      {
          bestValue = int.MaxValue;
          currentSide = !BlackPlayer;
      }
  
      // check forced moves
      int moveCount = rules.GetCaptureMoves(gameState,out possibleMoves, currentSide);
      // if no forced moves get normal moves 
      if (moveCount < 1)
          moveCount = rules.GetNormalMoves(gameState,out possibleMoves, currentSide);
  
      // traverse moves
      for (int i = 0; i < moveCount; i++)
      {
          Pieces[,] newGameState = ApplyMove(CloneGameState(gameState), possibleMoves[i]);
          int newStateValue = Minimax(newGameState, depth + 1, !is_maximizing,alpha, beta);
  
          if (is_maximizing)
          {
              if (newStateValue > bestValue)
              {
                  bestValue = newStateValue;
                  if (depth == 0)
                      bestMove = possibleMoves[i];
                  if (newStateValue > alpha)
                      alpha = newStateValue;
                  if (alpha >= beta)
                      return bestValue;
              }
          }
          //Evaluation for min
          else
          {
              if (newStateValue < bestValue)
              {
                  bestValue = newStateValue;
                  if (newStateValue < beta)
                      beta = newStateValue;
                  if (alpha >= beta)
                      return bestValue;
              }
          }
      }
      return bestValue;
  }
  

启发式函数:

public int HeuristicEvaluation(Pieces[,] gameState)
{
    int stateValue = 0;

    //use loops to check each piece 
    for (int j = 0; j < 8; j++)
    {
        int i = 0;
        if (j % 2 == 1)
            i++;

        for (; i < 8; i += 2)
        {
            Pieces currentPiece = gameState[i, j];

            if (currentPiece != Pieces.empty)
            {

                // if the current piece is mine
                if (MyPiece(currentPiece))
                {
                    // check if my piece is a king
                    if (currentPiece == Pieces.whiteKing || currentPiece == Pieces.blackKing)
                        stateValue += 80;
                    // my piece is a man
                    else
                    {
                        stateValue += 30;
                        // row values, closer to king zone higher the value 
                        if (currentPiece == Pieces.blackMan)
                        {
                            // black goes in reverse direction
                             int y = 7-j;
                             stateValue += y;
                        }
                        else
                             stateValue += j; 
                    }
                    // pieces on the edge are safe from capture
                    if (i == 0 ||i == 7 || j== 0 ||j ==7)
                    {
                        stateValue += 10;
                    }

                }

                // point reduction for enemy pieces
                else
                {
                    if (currentPiece == Pieces.whiteKing || currentPiece == Pieces.blackKing)
                        stateValue -= 80;
                    else
                    {
                        stateValue -= 20;

                        // row values, closer to king zone higher the value 
                        if (currentPiece == Pieces.blackMan )
                        {
                            // black goes in reverse direction
                            int y = 7-j;
                            stateValue -= y;
                        }
                        else
                            stateValue -= j;
                    }
                    // pieces on the edge cant be captured
                    if (i == 0 || i == 7 || j == 0 || j == 7)
                    {
                        stateValue -= 10;
                    }
                }
            }
        }
    }
    return stateValue;
}

Answer 1

首先，我想指出您的函数 Maximizer 和 Minimizer 可以合并到一个函数 Minimax(Pieces, gameState, depth, bool is_maximizing) 中，因为它们的逻辑几乎相同，除了一对的代码行。因此，您将调用 Minimax 并将 is_maximizing 设置为 true，而不是调用 Maximizer。而不是调用 Minimizer，只需调用 Minimax 并将 is_maximizing 设置为 false。这将有助于避免重复，并使您的代码更具可读性。

第一点导致我们在算法中犯了一个错误。在 Minimize 函数中递归调用自身，而您应该调用 Maximize 函数。

另一点是您在给定位置处理所有有效移动的方式。您不必将捕获 Action 的处理与非捕获 Action 分开。原因再次是处理两种类型移动的逻辑是相同的。我建议创建两个函数 - GenerateValidMoves() 和 SortValidMoves()。 GenerateValidMoves() 函数将生成给定位置中所有有效移动的列表。生成移动列表后，调用 SortValidMoves() 对列表进行排序，以便捕获移动位于列表的开头，然后是非捕获移动。

这是极小极大的简化伪代码:

Minimax(color, board, depth, is_max):
    if ((depth == DEPTH_CUTOFF) or IsTerminalNode()):
        return EvalBoard()
    best_score = is_max ? -infinity : infinity
    valid_moves = GenerateValidMoves(board, color)
    for curr_move in valid_moves:
        clone_board = board.clone()
        clone_board.make_move(curr_move)
        int curr_score = Minimax(opposite_color, clone_board, depth + 1, !is_max)
        if (is_max) {
            if (curr_score > best_score) {
                best_score = curr_score
                best_move = curr_move
            }
        } else {
            if (curr_score < best_score) {
                best_score = curr_score
                best_move = curr_move
            }
        }
    return best_score