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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With