Nov 4, 2022
Dynamic Tic-Tac-Toe using React-Typescript with MiniMax
Implementation of Tree and the MiniMax Algorithm in the making of Dynamic Tic-Tac-Toe
First of all in the past week, I feel kinda frustated to find an algorithm that can produce the best move for a computer bot in tic-tac-toe game. Then, after all the searched and all of the read I think we could make an unbeatable computer bot in tic-tac-toe game.
How Does The Intelligence works?
Before we dive deeper into the code, first of all we need to know what the minimax is. So, The Minimax algorithm is a recursive algorithm for choosing a best move, by maximizing value in the player side and minimizing value in the opponent side. Minimax have been used for a computer bot in 2 player games such as chess, tic-tac-toe, Go and so on.
As you can see, there are three possibilities for Player O to make a move from the diagram above. So Player O will maximizing the return value below, on the other hand Player X will minimizing the return value. From the illustration above, this Tic-Tac-Toe game will return +1 if the Player O wins, but if the player X wins it will return -1, and if it’s tie it will return 0.
How Does The Dynamic tic-tac-toe work ?
In the past week I challenged my self to build a Tic-Tac-Toe more than 3x3 squares, then I found a solution for myself to use a tree data structure to build it. It means each node of the tree will backtracking the value up to the root, so this solution aims to determine is there any crossing line from the start point. For better explanation, let’s see the visualization in the diagram below:
The Diagram shows that this solution will be using a recursive function that produce a tree node until it meets the constraints and then backtracking the value up +1 to the root of the tree. The constraints such as if the current coordinate meets the square boundaries, meets the empty space or meet the symbol which is not equal the current symbol, then it will return the current value up to the parent node.
Let’s check the code right now!
As you can see in the snippet code above, this solution works on any n * n Square. This approach is better than checking each winning combination from an array that holds a winning combinations. The getLines() function will be invoked when user click the square and its return value will be use as a parameter to determine the winner of the game.
Whenever a user clicks the square, the game will calculates the game status despite the game mode is player vs player or player vs computer. The tie counter use react ref because the tie counter value doesn’t need to be visible to the user screen, so we don’t need any useless re-render at all from react and it only dispatch the board when the computer best move has been filled to the newboard variable.
The max symbol value obtained from the length of the row square, so if it’s 4x4 squares, to win the game player must have at least 4 square that forming a line either it is a horizontal, a vertical or a diagonal line. After the winner has been decided then save the score results into the local storage and reset the tie counter to zero, so the game back to the initial state.
Let’s Dive into The MiniMax Code!
This miniMax function will backtracking up the score and the coordinate into the root of the tree. On each depth, if the current player is the maximizing player returns the max value and it works opposite if the player is the minimizing player.
The depth parameter in the minimax function used to limit the decision tree when the square is larger than 3x3, otherwise your browser will be crashed because the calculation is very large and I think it is useless to calculate every possible move when the player make a move in the first turn.
Could Minimax be more efficient ?
From what I have read and heard, minimax could be optimized to reduce computation time, it called alpha beta pruning. It cuts the branch of the tree that don’t need to be computed because it already has a better move available. For that I think it will be another story, you can check out the explanation here.
Conclusions
I have enhanced a Tic-Tac-Toe game a little bit so it can be played in n*n square and the minimax Algorithm could run in more than 3x3 square.
If you want to learn more the about the Minimax algorithm you can check out this great tutorial and if you want to see rest of the code you can find it in here.
I hope this could be useful for you, happy coding cheers 🍺!
