## Depth Limits, αβ Pruning

## Depth-limited Negamax Search

We want an

*approximate*value for a position, and will tolerate an*approximately*best moveFor chess, we use "piece value" as a heuristic approximation.

Heuristic should look at both sides, so subtract on-move value from opponent (zero-sum)

But just doing this right away might not be the best plan. Let's look ahead some fixed depth and use negamax to combine heuristic values

## Chess In n Moves

Imagine chess but after n moves whoever is "ahead on points" (material value) is the winner

Chess in one move: always take the queen if possible

But as n gets larger, game looks more and more like chess

Depth-limited heuristic search converges on true value of position (theorem, with caveats)

## Alpha-Beta Pruning

Generalization of Win Pruning. Hard to explain:

Imagine you find a forced score of 3 for some state

*s*in the middle of the searchImagine further that in some earlier state

*t*at the same level you had found a score of 2Then your opponent (parent) would never let you get to

*s*: they would avoid itSo there's no point in searching

*s*any further

## Alpha-Beta Implementation

"Alpha-Beta window" keeps track of best score for side not on move (alpha) and side on move (beta)

Prune when computed score exceeds beta

Game is zero-sum. On recursion, flip and negate the window: (alpha, beta) → (-beta, -alpha)

Window starts with (-max, max). When searching, keep bumping alpha up as better moves are found

## Effectiveness of Alpha-Beta

Depends on move ordering: a good move for the side on move will "close the window" a lot, so want to try good moves first

With optimal move ordering, will effectively

*double the depth*of the search by pruning; runtime of depth-4 without = runtime of depth-8 withNote that alpha-beta

*never changes the answer*: it only prunes states that provably don't matter