56 Minimax

• Minimax value of a node is the utility of the terminal state to which both players play optimally from that node.
• So the process of a two player game is that one player (called player Max) is to maximise its utility whereas its opponent (called player Min) is to minimise the utility of Max.

Implementing Minimax

function minimax_value(state) returns its minimax value
    if state is a terminal state then
        return utility of the state
 
    if the agent to act in state is Max then
        return max_value(state)
 
    if the agent to act in state is Min then
        return min_value(state)

function max_value(state) returns the minimax value v
    initialize v = -∞
 
    for each successor of state do
        v = max(v, minimax_value(successor))
 
    return v

function min_value(state) returns the minimax value v
    initialize v = +∞
 
    for each successor of state do
        v = min(v, minimax_value(successor))
 
    return v

Summary

• Deterministic, zero-sum games
  • Tic tac toe, chess, go, etc.
  • The first player maximises its own utility and the other minimises the utility of the first player.
• Minimax search :
  • A state space search tree.
  • Players alternate turns.
  • Compute each node’s minimax value, i.e. the best achievable utility against an optimal adversary.

Computational Complexity of Minimax

• How efficient is minimax
  • DFS(exhaustive)
  • Time: $O(b^m)$, $b$ is branching factor (i.e., how many successors a node may have), $m$ is maximum depth of the tree.
  • Space : $O(bm)$