Theoretical Results
With pessimal move ordering,
- alpha beta makes no reduction in search cost
With optimal move ordering
- alpha beta cuts the amount of search to the square root
- I.e. From bd to ?bd = bd/2
- Equivalently, we can search to twice the depth
With heuristics, performance is in between
alpha beta search vital to successful computer play in 2 player perfect information games