Trying to create an unbeatable Tic Tac Toe game with a dependable Artificial Intelligence took me hours of scrolling through tutorials, watching videos, and banging my head against the desk. Consequently, if you are embarking on a similar journey, I would like to provide you with an introduction to the Minimax algorithm.
This algorithm, like a professional chess player, anticipates a few steps ahead of time and places itself in the shoes of its adversary. After that, it continues to play ahead until it reaches a terminal arrangement of the board (terminal state), which results in a tie, play tic tac toe a win, or a loss for the player. As soon as the game reaches a terminal state, the AI will assign an arbitrary positive score (+10) to the winner, a negative score (-10) to the loser, and no score (zero) to the tie.
While this is going on, the algorithm is evaluating the moves that will lead to a terminal state based on which player is in the lead. When it is the AI's turn, it will choose the move with the highest possible score, and when it is the human player's turn, it will choose the move with the lowest possible score. Minimax is able to avoid losing to the human player by employing this strategy.
Try it out for yourself in the following game, which should be played in a Chrome browser if possible. Generally speaking, the Minimax algorithm can be described as a recursive function that performs the following functions:
return a numerical value If a terminal state (+10, 0, -10) is discovered, the program terminates.
go through all of the available spots on the board and call the minimax function on each one that is still available (recursion)
The best value is selected after evaluating the returning values from function calls
If you are unfamiliar with the concept of recursion, I recommend that you watch this video from Harvard's CS50 program.
Implementing the Minimax's thought process in code and seeing it in action in the following two sections will allow you to fully comprehend its reasoning.
Code's Minimax value
For the purposes of this tutorial, you will be working on a near-final state of the game, as depicted in figure 2. Minimax evaluates every state of the game (hundreds of thousands at a time), so being close to the end of the game makes it easier to follow up with minimax's recursive calls (9).
Assume that the artificial intelligence (AI) is represented by X and the human player by O in the following figure. You should define the Ti Tac Toe board as an array of nine items in order to make working with it more convenient. Each item will have a value that corresponds to its index. This will come in handy at a later time. To avoid having to recreate the board from scratch, we'll just define the board that contains the X and Y moves that are already present on the board (origBoard). Afterwards, declare the aiPlayer and huPlayer variables and assign them to the values "X" and "O," respectively.
Aside from that, you'll need a function that searches for winning combinations and returns true if it comes across one, as well as one that lists the indexes of the positions that are currently available on the board.
Let's get into the meat of the matter by defining the Minimax function, which takes two arguments: newBoard and player, as shown below. In the following step, you must locate the indexes of the available spots on the board and assign them to a variable named availSpots.
