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";
});
}
}
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:
You are currently checking for a win for both players at every move. But you only need to check if the last player that moved made a win.
Use a faster data structure to maintain state: use bitmaps. One bitmap of 16 bits for the X player, and one for the O player.
Checking for a win on such bitmaps will be faster. There are 10 lines on which a win can be made: each can be represented by a bitmap with 4 bits set to 1. If an AND of such a winner-bitmap with the current X bitmap results in the winner-bitmap, you found a win for X. Also a draw can be detected if the OR of the X bitmap with the O bitmap results in all 16 bits set to 1.
You can also detect whether a board has no more possible win even when it is not full yet. This happens when both players have made a move in each possible line. Again, you can use the bitmaps for checking for this, and it would allow you to backtrack earlier with the value 0.
With a bitmap operation you can know which squares are still empty, and again with smart bit operations (see: How can I get the value of the least significant bit in a number?) you can avoid 16 iterations and only make an iteration for each free square.
The larger the board, the more probability there is that you will evaluate a board that you have already visited before (by exchange of moves). So it becomes worth it to apply memoization: maintain a dictionary (keyed by these bitmap pairs) with the earlier evaluated value.
Extending on the previous point: when reading/writing to that dictionary, first apply mirroring/rotating to one of the 8 equivalent boards that is the "least" among them (in any chosen order, like by bitmap order).
Set a maximum search depth to your minimax search. When that maximum depth is reached, and the board does not represent a win, then return a heuristic value for the board. This could be as simple as returning 0 as if it were a draw. The idea is that if you can't reach a win in like 4 moves, then it is not worth to look deeper, as it is certain (in this game) that the opponent has enough defence possibilities to counter your moves and keep it to a draw. The same reasoning applies to not losing the game in 4 moves.
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.