Minimax Algorithm

Vocabulary flashcards covering the minimax algorithm, depth-first game tree search, pseudocode functions, and time and space complexity analysis.

Minimax Algorithm

An algorithm that computes the minimax decision from the current state by performing a complete depth-first exploration of the game tree.

Backed Up Values

The minimax values that are passed back up through the tree as recursion unwinds after reaching the leaf nodes.

Minimax Algorithm Pseudocode (Figure 5.3)

An algorithm for calculating minimax decisions that returns the action leading to the best utility under the assumption that the opponent plays to minimize utility.

$$\arg\max_{a \in S} f(a)$$

A mathematical notation that computes the element $a$ of set $S$ that has the maximum value of $f(a)$.

Time Complexity of Minimax

$O(b^m)$, where $m$ is the maximum depth of the game tree and $b$ represents the legal moves at each point.

Space Complexity of Minimax

$O(bm)$ for an algorithm that generates all actions at once, or $O(m)$ for an algorithm that generates actions one at a time, where $m$ is the maximum depth and $b$ is the number of legal moves.