UoL CS Notes
Menu

Alpha - Beta Pruning

COMP111 Lectures

If you know half way through a calculation that it will succeed or fail, then there is no point in doing the rest of it. This removes redundant information.

graph TD
subgraph max1[MAX]
A0
end
subgraph MIN
A1
A2
A3
end
subgraph max2[MAX]
A11
A12
A13
A21
A22
A23
A31
A32
A33
end
A0[>= 3, then just 3] -->|A1| A1[3]
A0 -->|A2| A2[<= 2]
A0 -->|A3| A3[<= 14, then <= 5, then 2]
A1 -->|A11| A11[3]
A1 -->|A12| A12[12]
A1 -->|A13| A13[8]
A2 -->|A21| A21[2]
A2 .->|A22| A22[x]
A2 .->|A23| A23[x]
A3 -->|A31| A31[14]
A3 -->|A32| A32[5]
A3 -->|A33| A33[2]

From the example we can see from the subparagraph for MIN that the MAX value can only get larger than three. Hence, we can make assumptions and ignore paths based on what we have found already.

This can be seen on the path A21. As there is such a low value we don’t have to search the other items in the tree as we already have a greater value on A1.

The essence is that we can prune redundant states.

Cutoffs and Heuristics

As it is not always possible to explore the full tree to evaluate the move you can cut off the end of the tree to speed up calculation at the cost of getting potentially lower quality moves.

  • Problem
    • Utilities are defines only at terminal states
  • Solution
    • Evaluate the pre-terminal leaf states using heuristic evaluation function rather than using the actual utility function.

Cutoff Value

Instead of $\text{MiniMaxV}(s)$ we compute $\text{CutOffV}(s)$.

Assume that we con compute a function $\text{Evaluation}(s)$ which gives us a utility value for any state $s$ which we do not want explored (every cutoff state).

Then define $\text{CutOffV}(s)$ recursively:

\[\text{CoV}(s)= \begin{cases} \text{Utility}(s) & s\ \text{is terminal}\\ \text{Evaluation}(s) & s\ \text{is CutOff} \\ \max_{n\in\text{Succ}(s)}\text{CoV}(n) & s\ \text{is}\max\\ \min_{n\in\text{Succ}(s)}\text{CoV}(n) & s\ \text{is}\min \end{cases}\]

In this definition $\text{CutOffV}$ has been shortened to $\text{CoV}$.

How good this is depends crucially on how good the heuristic evaluation function is.

Summary

  • Minimax algorithm (with $\alpha - \beta$ pruning) fundamental for game playing.
  • Not efficient enough for games such as chess, go, etc.
  • Evaluation function are needed to replace terminal states by cutoff states.
  • Various approaches to define evaluation function.
  • Most successful approach: machine learning. Evaluate position using experience from previous games.