Minimax algorithm

The minimax algorithm is a recursive algorithm for choosing the next move in a two-player game. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position. The player then makes the move that maximises the minimum value of the position resulting from the opponent's possible following moves. If it is A's turn to move, A gives a value to each of his legal moves. If the result of a move is an immediate win for A it is assigned positive infinity and, if it is an immediate win for B, negative infinity. The value to A of any other move is the minimum of the values resulting from each of B's possible replies. (A is called the maximizing player and B is called the minimizing player).

The above algorithm will assign a value of positive or negative infinity to any position since the value of every position will be the value of some final winning or losing position. This can be extended if we can supply a heuristic evaluation function which gives values to non-final game states without considering all possible following complete sequences. We can then limit the minimax algorithm to look only at a certain number of moves ahead. This number is called the "look-ahead" or "ply".

The algorithm can be thought of as exploring the nodes of a game tree. The effective branching factor of the tree is the average number of children of each node (i.e., the average number of legal moves in a position). The number of nodes to be explored increases exponentially with the number of plies. The number of nodes to be explored for the analysis of a game is therefore the power of plies of the branching factor. It is therefore impossible to completely analyze games such as chess using the minimax algorithm.

The performance of the naive minimax algorithm may be improved dramatically, without affecting the result, by the use of alpha-beta pruning. Other heuristic pruning methods can also be used, but not all of them are guaranteed to give the same result as the un-pruned search.