Informed vs uninformed; min-max; alpha-beta

Informed vs uninformed search

Min-max algorithm

Min-max is a game-tree search for two-player, zero-sum games (chess, tic-tac-toe). MAX tries to maximise the utility and MIN (the opponent) tries to minimise it. The algorithm generates the game tree to some depth, evaluates the leaf nodes with a utility function, and backs the values up: MAX nodes take the maximum of their children, MIN nodes take the minimum. At the root MAX picks the move with the highest backed-up value (it assumes the opponent plays optimally).

Example (leaf values shown at the bottom):

                 MAX  [5]
              /          \
         MIN [5]        MIN [0]
         /     \         /     \
    MAX[5]   MAX[9]  MAX[2]   MAX[0]
     / \      / \      / \      / \
    3   5    6   9    1   2    0  -1

• MAX nodes: max(3,5)=5, max(6,9)=9, max(1,2)=2, max(0,-1)=0.
• MIN nodes: min(5,9)=5, min(2,0)=0.
• Root MAX: max(5,0)=5, so MAX chooses the left move.

Time complexity O(b^m), space O(b·m) (depth-first), where b = branching factor and m = depth.

How alpha-beta differs from min-max

Alpha-beta pruning gives the same result as min-max but skips branches that cannot affect the final decision. It keeps two values: α = best (highest) value found so far for MAX, β = best (lowest) value found so far for MIN. A branch is pruned when α ≥ β.

In the example above: in the left MIN node, the first MAX child gives 5, so β = 5. In the second MAX child the first leaf is 6, which is already ≥ β, so MIN will never choose this child and the leaf 9 is pruned. In the right MIN node, the first MAX child gives 2, so this MIN node is worth at most 2, which is ≤ α = 5 (MAX already has 5 on the left); its second child (leaves 0, -1) is pruned. Only 5 of the 8 leaves are examined, yet the answer is still 5.