flutteralgorithmdartminimax

Minimax function not working for 4x4, 5x5, 6x6 list


I am currently trying to implement a simple tic tac toe game in flutter. I am using a minimax function to calculate the AI player moves. For the simplest 3x3 list array, the minimax function works perfectly. But when i try to use the same minimax function for 4x4,5x5, 6x6 list array(to make the game a little bit more complex and interesting), the minimax function seems to run endlessly without returning a move, no matter what i do(i added alpha-beta pruning to no avail). What am i doing wrong. Any help will be appreciated. The following are the main functions i am using:

int minimax(List<List<String>> board, bool isMaximizing, BuildContext context, int alpha, int beta) {
  // Check for terminal states
  if (checkWin(board, 'O', context)) {
    return 1;
  } else if (checkWin(board, 'X', context)) {
    return -1;
  } else if (checkDraw(board)) {
    return 0;
  }
  

  // Recursively explore the game tree
  if (isMaximizing) {
    int bestScore = -1000;
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {

        if (board[i][j].isEmpty) {
          board[i][j] = 'O';
          int score = minimax(board, false, context,  alpha, beta);

          board[i][j] = '';
          bestScore = max(score, bestScore);

          alpha = max(alpha, score);
          if (beta <= alpha) {
            break; // Prune the subtree
          }

        }
      }
    }
    return bestScore;
  } else {
    int bestScore = 1000;
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        if (board[i][j].isEmpty) {
          board[i][j] = 'X';
          int score = minimax(board, true, context,  alpha, beta,);

          board[i][j] = '';
          bestScore = min(score, bestScore);

          beta = min(beta, score);
          if (beta <= alpha) {
            break; // Prune the subtree
          }

        }
      }
    }
    return bestScore;
  }
}



bool checkWin(List<List<String>> board, String player, BuildContext context) {
  for (int i = 0; i < 4; i++) {
    if ((board[i][0] == player &&
        board[i][1] == player && board[i][2] == player && board[i][3] == player) || (board[0][i] == player &&
        board[1][i] == player && board[2][i] == player && board[3][i] == player)) {
      //Testing for winning cells so as to add colors
      if(context.read<SharedPrefProvider>().hardLevel % 2 != 0) {
        checkWinColors(board, player, i, context);
      }
      return true;
    }
  }
  if ((board[0][0] == player && board[1][1] == player && board[2][2] == player && board[3][3] == player) ||
      (board[0][3] == player && board[1][2] == player && board[2][1] == player && board[3][0] == player)) {
    //Testing for winning cells so as to add colors
    if(context.read<SharedPrefProvider>().hardLevel % 2 != 0) {
      checkWinColors(board, player, 0, context);
    }
    return true;
  }
  return false;
}


bool checkDraw(List<List<String>> board) {
  // Check if every row has every cell filled
  for (var row in board) {
    for (var cell in row) {
      if (cell.isEmpty) {
        return false; // If any cell is empty, the game is not a draw
      }
    }
  }

  // If all cells are filled, the game is a draw
  return true;
}

The following function calls the minimax function to get the index of the best AI move on the board

void makeAIMove(board) {
    int bestScore = -1000;
    int bestMoveRow = -1;
    int bestMoveCol = -1;

    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {

        if (board[i][j].isEmpty) {
          board[i][j] = 'O';

          int score = minimax(board, false, context, -1000, 1000);
          board[i][j] = '';

          if (score > bestScore) {
            
              bestScore = score;
              bestMoveRow = i;
              bestMoveCol = j;

          }else{
            
          }
        }
      }
    }

    //Returns index of the next move on the board
    if (bestMoveRow != -1 && bestMoveCol != -1) {
      setState(() {
        board[bestMoveRow][bestMoveCol] = "O";
      });

    }
  }

Solution

  • The "problem" with the 4x4 version is that the number of board states to check at the start of the game increases from roughly 9! to 16! (Here I ignore early wins, but they represent a minority). So that is from ~106 to ~1013. Add to that the work at each state, where all cells are visited to check for a draw or a win, and you get to a number of operations that is in the order of 1015. It is expected that minimax will not return soon from such a task.

    Here are a few ideas to improve the performance:

    So there are quite a few things you can do to optimise this algorithm.

    Finally (but this might not be your interest), the 4x4 game of 4-in-a-row is a draw at best play, more trivially so than with 3x3 tic tac toe. I find that applying minimax is overkill for this game. You can design a static evaluation function at search depth 1 and favour moves that maximize the difference between the number of positions you have in lines that can still be won minus the same metric of the opponent.