Minimax

In artificial intelligence, minimax is a game strategy for two-player games.

• Assumption: the other player always plays its best move.
• Decision: play a move that minimises the payoff that could be gained by the other player.

To make a correct minimax decision, each player needs to know the payoff of each move, so we need to compute the minimax value for the internal nodes. Starting from the terminal node’s parents, we compute minimax values for non-terminal states. Max states will always pick the highest valued child, and min states will always pick the lowest valued child (because utility function is wrt max).

This is done recursively. We sent the minimax values back up the tree.

$$U(s)=\{\begin{array}{llc}U(s)& & \text{if }s\text{ is a terminal}\\ \min (U(c):c\text{ is a child of }s)& & \text{if }s\text{ is a min node}\\ \max (U(c):c\text{ is a child of }s)& & \text{if }s\text{ is a max node}\end{array}$$

so the value $U(s)$ that labels each state $s$ is the value that max will achieve in that state if both max and min play their best move.

Extensions

Problem: to evaluate all options, we have to traverse the entire game tree. This is an exhaustive DFS, so the time complexity is $\mathcal{O}(b^d)$. We can use node pruning techniques like alpha-beta pruning to reduce the search size, because it’s not necessary to examine the entire tree to make correct minimax decisions.

For a non-zero sum or multiple player game, then we have to generalise minimax:

• Terminals may have utility tuples.
• Node values are also utility tuples.
• Each player maximises its own component.
• This can give rise to cooperation and dynamic competition.

Expectimax is a similar search method that computes the average score, which is especially useful for probabilistic games.