User Tools

Site Tools

Minimax search

Minimax is a recursive algorithm for choosing the next move in a two-player game. The tree represents the possible moves in a game, each node with multiple children represents a choice. Minimax assumes that each player plays the best move, one player is trying to maximise the outcome and the other minimise it.

At each decision point in the tree the player chooses their best possible move. Recursively this is the maximum move of minimum moves of maximums of…

In this example the tree is small enough to be fully traversed. In a simple game like tic-tac-toe, values can be assigned to win, loss or draw results. But in a more complex game like chess, where it is impossible to fully traverse the decision tree, minimax has to terminate at intermediate depths and evaluate the static position. This evaluation is an estimate of the final outcome given all current information, a very basic chess static position evaluator could use the difference in total piece values.

λ minimax

The basic minimax algorithm can be dramatically improved with alpha-beta pruning.

Negamax variation

There are obvious similarities between the maximising and minimising player in the Minimax implementation. Using the relationship $max(a, b) = -min(-a, -b)$ the minimax algorithm can be simplified to the Negamax algorithm.

λ negamax

minimax_search.txt · Last modified: 2015/02/02 08:28 (external edit)