dart - Minimax Implementation with Heuristic: Unexpectedly Poor Performance - Stack Overflow

IT技术

更新时间：2025-04-113

admin管理员组
文章数量:1402839

I'm implementing the Minimax algorithm for a two-player board game using Dart. My approach involves two nested for loops to simulate the maximizing and minimizing players' turns. I've also developed a heuristic evaluation function that considers several key factors to assess the board state. These factors include:

Pawn Count: Weighting the number of pawns each player possesses.

King Count: Prioritizing the acquisition of king pieces.

Center Control: Evaluating the degree to which a player controls the center of the board.

Threatened Pieces: Penalizing positions where a player's pieces are under threat.

Piece Mobility: Rewarding positions with greater piece movement options.

My intention is to create a Minimax implementation that can play reasonably well, aiming for at least a 50% win rate against a basic opponent. While the code executes without errors, the AI's performance is significantly below my expectations. It often makes seemingly poor moves, failing to capitalize on obvious advantages and falling into simple traps.

This method is used to call the minMax and find the best move to play:

void playBestMove(List<String> piecesPosCopy, int depth) {
    int bestEval = -9999;
    int bestMovePrev = -1;
    int bestMoveIndex = -1;
    // Save the current state before call
    List<String> defaultState = List.from(piecesPos);

    for (int i = 0; i < piecesPosCopy.length; i++) {
      if (piecesPosCopy[i][0] == "B" || piecesPosCopy[i][0] == "O") {
        List<int> possibleMoves = getPossibleMoves(piecesPosCopy, i);
        for (int move in possibleMoves) {
          // Save the current state
          List<String> saveState = List.from(piecesPosCopy);

          // Make the move
          makeMove(piecesPosCopy, i, move);

          // Evaluate the move
          int eval = minMax(piecesPosCopy, depth - 1, false, -9999, 9999);

          // Restore the state
          piecesPosCopy = List.from(saveState);

          // Update best move
          if (eval > bestEval) {
            bestEval = eval;
            bestMovePrev = i;
            bestMoveIndex = move;
          }
        }
      }
    }
    //Restored state to original State before making best move
    piecesPos = List.from(defaultState);

    // Play the best move
    if (bestMovePrev != -1 && bestMoveIndex != -1) {
      //MakeMove
      makeBotMove(bestMovePrev, bestMoveIndex);
    }
  }

This is the minmax code

int minMax(List<String> piecesPos, int depth, bool isMaximizing, int alpha, int beta) {
    // Base case: if depth is 0 or the game is over, return the evaluation
    if (depth == 0 || isGameOver(piecesPos)) {
      return evaluateBoard(piecesPos);
    }

    if (isMaximizing) {
      int maxEval = -9999; // Initialize to a very low value
      for (int i = 0; i < piecesPos.length; i++) {
        if (piecesPos[i][0] == "B" || piecesPos[i][0] == "O") {
          List<int> possibleMoves = getPossibleMoves(piecesPos, i);
          for (int move in possibleMoves) {
            // Save the current state
            List<String> saveState = List.from(piecesPos);

            // Make the move
            makeMove(piecesPos, i, move);

            // Recursive call
            int eval = minMax(piecesPos, depth - 1, false, alpha, beta);

            // Restore the state
            piecesPos = List.from(saveState);

            // Update maxEval
            maxEval = max(maxEval, eval);
            alpha = max(alpha, eval);

            // Alpha-Beta Pruning
            if (beta <= alpha) {
              break;
            }
          }
        }
      }
      return maxEval;
    } else {
      int minEval = 9999; // Initialize to a very high value
      for (int i = 0; i < piecesPos.length; i++) {
        if (piecesPos[i][0] == "W" || piecesPos[i][0] == "Q") {
          List<int> possibleMoves = getPossibleMoves(piecesPos, i);
          for (int move in possibleMoves) {
            // Save the current state
            List<String> saveState = List.from(piecesPos);

            // Make the move
            makeMove(piecesPos, i, move);

            // Recursive call
            int eval = minMax(piecesPos, depth - 1, true, alpha, beta);

            // Restore the state
            piecesPos = List.from(saveState);

            // Update minEval
            minEval = min(minEval, eval);
            beta = min(beta, eval);

            // Alpha-Beta Pruning
            if (beta <= alpha) {
              break;
            }
          }
        }
      }
      return minEval;
    }
  }