The Minimax Algorithm – Explained

 The Minimax Algorithm – Explained

 Do you want to learn more about the Minimax algorithm? We share everything about the Minimax algorithm with a complete explanation right here. 

The Minimax algorithm is a powerful strategy used in game theory and artificial intelligence to find the best possible move for a player in a game. It is widely used in games ranging from simple ones such as Tic Tac Toe to complex games such as Chess.

 

How Does It Work?

The basic idea behind the Minimax algorithm is to evaluate the possible outcomes of a move and choose the move that maximizes the player's chances of winning or minimizes the opponent's chances of winning. This algorithm works by assuming that the player and the opponent are playing optimally and considering all possible moves that can be made.

Take the example of Tic Tac Toe, a simple yet interesting two-player game played on a 3x3 board. The game involves players taking turns to place their mark (either 'X' or 'O') on an empty square on the board, with the objective of getting three of their marks in a row, either horizontally, vertically, or diagonally. The game ends when either one player wins, or the board is completely filled with no winner.

Minimax Algorithm in Tic Tac Toe

To apply the Minimax algorithm to Tic Tac Toe, we start by creating a game tree, where each node represents a possible move, and each edge represents a transition from one game state to another. For example, the root node of the tree represents the current game state (the board at any moment), and its leaf nodes represent all possible moves that the player can make.

We then assign a score to each leaf node of the tree, representing the outcome of the game if both players played optimally. For example, if the leaf node represents a game state where the player wins, we assign a score of +10; if it represents a game state where the opponent wins, we assign a score of -10; and if it represents a draw, we assign a score of 0.

Now, we work our way back up the tree, computing the scores of each non-leaf node by taking the maximum of the scores of its child nodes if it is the player's turn and the minimum of the scores of its child nodes if it is the opponent's turn. This process continues until we reach the root node of the tree, where the score of the best possible move for the player is obtained.

In Tic Tac Toe, the Minimax algorithm will always guarantee the player a win or a draw, as it considers all possible moves and assumes that the opponent is also playing optimally.

This algorithm is recursive. It works in the following way:

 Al   All current moves are considered

2.     All opponent moves for each move are considered

3.     Back to step 1

4.     This is done (theoretically) until the game ends i.e., all possible choices are considered.

While this may be possible for a simple game like tic-tac-toe, there are literally way too many choices possible in games like chess. In this case, we add the depth parameter so the algorithm stops after considering some number of moves (depth). This is necessary to add because otherwise, the computer might just think forever!

For example, Claude Shannon calculated that there are 10¹²⁰ possible games of chess. There are techniques to reduce this number such as alpha-beta pruning where a leaf node of the tree is permanently cut off if the next optimal move is worse for the computer than some other choice. Still, even the best chess engines (stockfish) at the moment ‘only’ think about 30 moves ahead on an average CPU.