Minimax Algorithm in Game Theory Set 2

The Minimax Algorithm is a type of Depth-First Search (DFS) algorithm. When evaluating game trees, it is usual to assume that the computer is attempting to maximize some score that the opponent is trying to minimize. Normally, we would consider this score to be the result of the evaluation function for a given position, so we would usually have a high positive score means a good position for the computer, a score of 0 means a neutral position and a high negative score means a good position for the opponent.

Principle of Minimax Algorithm:

The basic principle behind minimax is that a path through the tree is chosen by assuming that at its turn (max node), the computer will choose the more that will give the highest eventual static evaluation and that at the human opponent’s turn (min node), he or she will choose the move that will give the lowest static evaluation.

Minimax Algorithm:

function minimax(current node)
{
if is-leaf(current-node)
return static-evaluation(current-node);
if is-min-node(current-node)
return min(minimax(children-of(current-node)));
if is-max-node(current-node)
return max(minimax(children-of(current-node)));
}

The else part is never required as every node must be a leaf node, a min node or max node only.