The minimax algorithm

The minimax algorithm is used in Artificial Intelligence to determine an optimal move for a player in a two-player game. It assumes that the other player is playing optimally.

There are two types of players:

• the maximizer
• the minimizer

You are the maximizer, and your opponent is the minimizer. Your goal at the node representing your move (called the max node) is to maximize the value at that node. Your opponent’s goal at the node representing his/her move (called the min node) is to minimize the value at that node. The minimax algorithm does a depth-first search of the game tree.

Suppose that the maximizer takes the first turn, the minimizer takes the second turn, ​and so on. The following illustration demonstrates the algorithm.

Remember that in a real game, ​the game tree may be an n-ary tree with many layers.

Complex games

Complex games have complex game trees as the players have a wide range of options to choose from at every level. The minimax algorithm takes a long time to run on such trees as its running time is dependent on the branching factor of the tree. There may be cases where heuristics need to be used to evaluate terminal values.