How to solve Tic Tac Toe 4x4 game using Minimax Algorithm and Alpha Beta Pruning

Question

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?

Answer 1

There are several possibilities to improve performance of your program.

1. Evaluation function. It seems like currently you apply evaluaton function only when you reach the terminal game node. In games like 3x3 tic-tac-toe it is a reasonable approach because the search tree is small and leaf nodes can be reached from the starting position within short period of time. But with games that are played on the larger boards (like chess, go etc.) you cannot recurse until you reach the terminal node (it will take too much time). So you need to decide on which recursion depth to stop and try to evaluate the current position based on the tactical/strategical principles of the game. In order to do this you need to write an heuristic evaluation function which will give you the value of the position. You can then propagate this value up the search tree to determine the best move. The quality of the whole program can heavily depend on the quality of the eval function.
2. Move ordering. After you generated the list of all valid moves, sort them in descending order with respect to the evaluation function. This way the algorithm will first consider good moves which are more likely to produce high alpha-beta cutoffs causing more nodes to be pruned.
3. Iterative deepening with principal variation search. Instead of making initial call to minimax function with some fixed depth, try to call it first with depth 1, then 2, 3, ... (stop when the time per move cutoff is reached). Store the best move that was found with minimax for depth 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.
4. Opening book. If you know what are the good moves for the first couple (or maybe even dozens) of turns, you can hardcode them in the opening book. So when your program faces a position from the opening book, it will immediately retrieve the best answer. A trivial example of an opening book is to hardcode first move to the central square for the 3-by-3 tic-tac-toe game. This way your program will spend zero seconds to find the first move.
5. Transposition tables. Try to reuse the best move that was found during the minimax search for position X to determine the best move for another position Y that is symmetrical to X (meaning that Y can be obtained from X via rotations/reflections). One of the common advanced techniques for implementing transposition tables in board games programming is called Zobrist hashing.
6. Parallel algorithms. Try to parallilize your algorithm to make it run faster on machines with multiple cores.
7. Programming language. Since your question is marked with the 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.