Algorithms in a Nutshell

AlphaBeta | 219

Path Finding

in AI

Recall that ALPHABETAis based on NEGMAX, the MINIMAXvariant that seeks to

maximize the negative score of the opposing player at each level. ALPHABETA

ensures that non-productive nodes are not searched. To explain the way ALPHA-

BETAprunes the game tree, Figure 7-22 presents a three-ply search of Figure 7-17

that expands 66 nodes (whereas the corresponding MINIMAXgame tree would

require 156 nodes).

Figure 7-21. AlphaBeta two-ply search

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use