Depth-limited Negamax Search

  • We want an approximate value for a position, and will tolerate an approximately best move

  • For 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 search

    • Imagine further that in some earlier state t at the same level you had found a score of 2

    • Then your opponent (parent) would never let you get to s: they would avoid it

    • So there's no point in searching s any further

alpha-beta search tree

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 with

  • Note that alpha-beta never changes the answer: it only prunes states that provably don't matter

Last modified: Sunday, 18 October 2020, 10:51 PM