Alpha-Beta Pruning Example includes Alpha-Beta Pruning Idea (Some of the branches of the game tree won't be taken if playing against a smart opponent, Use pruning to ignore those branches), Alpha-Beta Search Example. | Alpha-Beta Pruning Example Alpha-Beta Pruning Idea Some of the branches of the game tree won't be taken if playing against a smart opponent. Use pruning to ignore those branches. While doing DFS of game tree, keep track of: alpha at maximizing levels (computer’s move) highest SBE value seen so far (initialize to -infinity) is lower bound on state's evaluation beta at minimizing levels (opponent’s move) lowest SBE value seen so far (initialize to +infinity) is higher bound on state's evaluation Alpha-Beta Pruning Idea Beta cutoff pruning occurs when maximizing if child’s alpha >= parent's beta Why stop expanding children? opponent won't allow computer to take this move Alpha cutoff pruning occurs when minimizing if parent's alpha >= child’s beta Why stop expanding children? computer has a better move than this Alpha-Beta Search Example minimax(A,0,4) alpha initialized to -infinity Expand A? Yes since there are successors, no cutoff test for root B N -5 W -3 H 3 I 8 P O 4 D C G F Call Stack A A α=- max 9 X -5 E 0 J Q -6 L K R 0 S 3 M 2 T 5 U -7 V -9 A Alpha-Beta Search Example beta initialized to +infinity minimax(B,1,4) Expand B? Yes since A’s alpha >= B’s beta is false, no alpha .
