I made a Tic Tac Toe game, using Minimax and Alpha Beta Pruning. I wanted to make a computer AI for Tic Tac Toe (10x10) game, but Its game tree size was ridiculously large.
My code is such that, I just need to change two variables to change board Size + Cells needed in a row to win. Example:
boardSize = 3 // This is for 3x3 tic tac toe
boardSize = 4 // This is for 4x4 tic tac toe
boardSize = 10 // This is for 10x10 tic tac toe
and
winStreak = 3 // Need to make 3 cells in a row to win
winStreak = 4 // Need to make 4 cells in a row to win
I hope you got it.
So, I changed my plan to make Tic Tac Toe from 10x10 to 3x3, and it worked fine.
Then I change boardSize = 4
and winStreak = 3
making it (4x4) tic tac toe game.
Now, I thought Minimax with Alpha Beta Pruning will be enough to solve 4x4, but was surprised to see, it is not.
When I make the first move (human), the minimax algorithm searches for 5-10 minutes, then the browser tab just crash. It is unable to make even the first move.
How Can I improve its speed? People are even able to solve chess using Minimax + Alpha Beta Pruning, but what is wrong with my code?
My full code is of around 200-300 lines, so I will just write pseudo code.
humanMakeMove();
Minimax(); // Bot calls Minimax function to make a move
function Minimax(board, player) {
if (checkResult() != 0) // 0 = Game is on
return checkResult(); // 1 = Win, 0.5 = Draw, -1 = Lose
availableMoves = getAvailableMoves();
for(i = 0; i < availableMoves.length;i++)
{
move = availableMoves[i];
removeMoveFromAvailableMovesArray(move);
if (player == "X")
score = Minimax(board, "O");
else
score = Minimax(board, "X");
board[i] = "-"; // "-" means empty space
if (depth of tree is on first level && score == 1)
return maxScore; //Alpha Beta Pruning is applied here, if we get score of 1, then we don't need to search more.
}
}
What else optimization I can apply to make the code run faster?
There are several possibilities to improve performance of your program.
k
and use it as your first candidate in minimax for depth k + 1
. Furthermore, you can store not only the best move, but the whole sequence of best moves which is called principal variation. So after you found principal variation for depth k
, feed it to the minimax call on depth k + 1
and it often will produce a lot of good alpha-beta cutoffs.Javascript
tag, I assume that you're using this language to implement the algorithm. Javascript is not considered the best language in terms of performance. So if you are familiar with languages like C, C++ or Java, rewriting the program in one of them can give a considerable performance boost.Finally, your phrase
People are even able to solve chess using Minimax + Alpha Beta Pruning
is not true strictly speaking, because chess is not a solved game yet. But there exist chess programs that can beat human players easily (using minimax with alpha-beta pruning and many other more advanced techniques). So the fact that program can beat expert players and world champion doesn't mean it is playing perfectly.