flutterdartartificial-intelligenceminmax

Why is Min Max playing the first available move it can find as best move?


The Minimax algorithm only selects the first available move as the best move when none of its pieces are threatened. On an 8x8 board, when it is the bot's turn to play and the Minimax algorithm is called to determine the best move, the bot chooses the first available move, provided that no piece is under threat. This behavior has become predictable because I can now anticipate what the bot will play.

I have also tried increasing the search depth, and I believe this could be contributing to the issue. When increasing the depth from 2 to 4, I noticed that the maxEval is always 9999. Additionally, at depth 3, I observed that the bot attempts to play the minimizing player's piece as the best move.

I need help resolving this behavior.

This is the Min Max method

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

This is how I call and play the best move

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 < 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);

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

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

          // Update best move
          if (eval > bestEval) {
            bestEval = eval;
            bestMovePrev = i;
            bestMoveIndex = move;
          }
        }
      }
    }
    print("BBB The best max is $bestEval prev is $bestMovePrev and index is $bestMoveIndex");
    //Restored state to original State before making best move
    piecesPos = List.from(defaultState);

    // Play the best move
    if (bestMovePrev != -1 && bestMoveIndex != -1) {
      //makeMove(piecesPos, bestMovePrev, bestMoveIndex);
      recentlyCrowned = false;
      if(animatePieceMovement){performMultitakeAnim = true;}
      if(!vsComputer){
        undoMove = List.from(piecesPos);
        saveMovesState.add(undoMove);
      }
      //Allow to check for Win, loose and draw.
      checkForWinLooseDraw = true;
      //MakeMove
      makeBotMove(bestMovePrev, bestMoveIndex);
    }
  }

This is the code for the evaluateBoard method

int evaluateBoard(List<String> piecesPos) {
    // Implement the evaluation function
    // This function should return a score based on the current state of the board
    // For example, the difference in the number of pieces between the two players
    int totalMyPiece = 0;
    int totalOppPiece = 0;

    //Piece Weight
    for (int i = 0; i < piecesPos.length; i++) {
      if (piecesPos[i][0] == "W"){
        totalOppPiece = totalOppPiece + 10;
      }else
      if(piecesPos[i][0] == "Q"){
        totalOppPiece = totalOppPiece + 20;
      }else
      if (piecesPos[i][0] == "B"){
        totalMyPiece = totalMyPiece + 10;
      }else
      if(piecesPos[i][0] == "O"){
        totalMyPiece = totalMyPiece + 20;
      }
    }
    // center control
    for(int b = 0; b < centerControlArea.length; b++){
      if (piecesPos[centerControlArea[b]][0] == "W" || piecesPos[centerControlArea[b]][0] == "Q"){
        totalOppPiece = totalOppPiece + 3;
      }
    }
    // Threats (pieces under attack)
    totalOppPiece = totalOppPiece - squaresWithTakes_OPP.length * 5;

    // center control
    for(int b = 0; b < centerControlArea.length; b++){
      if (piecesPos[centerControlArea[b]][0] == "B" || piecesPos[centerControlArea[b]][0] == "O"){
        totalMyPiece = totalMyPiece + 3;
      }
    }
    // Threats (pieces under attack)
    totalMyPiece = totalMyPiece - squaresWithTakes.length * 5;

    print("VVV $totalMyPiece");
    print("VVV $totalOppPiece");

    return totalMyPiece - totalOppPiece;
  }

Solution

  • I had to save the board state for each move made when Minimax was called and analyze them individually. This allowed me to track the moves and notice that the board state was not being updated correctly. I’ve now resolved the issue. The problem was related to how I was passing my board state (piecesPos). I was retrieving and passing the wrong board state, which caused Minimax to make incorrect or suboptimal moves. Thank you all for your contributions; it is greatly appreciated.

    Renaming to piecesPosCopy and using piecesPos

    This was getting the actual board state to use when min max is called.

    int minMax(List<String> piecesPosCopy, 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
                performMultitakeAnim = false;
                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
                performMultitakeAnim = false;
                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;
        }
      }