GPliGame Playingα-βPruningαβPruning Introduction to Artificial IntelligenceHadi Moradi12.α-βpruning: search cutoff Pruning: eliminating a branch of the search tree from consideration without exhaustive examination of each node Does it work? Yes, it roughly cuts the branching factor from b to √b li i d bl f l khdhiiresulting in double as far look-ahead than pure minimax2α-βpruning: example≥ 6MAX6MIN61283α-βpruning: example≥ 6MAX6≤ 2MIN6128 24α-βpruning: example≥ 6MAX6≤ 2≤ 5MIN6128 2 55α-βpruning: example≥ 6MAXSelected move6≤2≤5MIN6≤2≤56128256612825α-βpruning: general principlePlayerOpponentmα= 6OpponentIf α> v then MAX will chose m so prune tree under n Similar for βfor MIN6Playerβ7Opponentnv= 2Properties of α-β8The α-βalgorithm//the leaf node (terminal state)()9The α-βalgorithm (cont.)//the leaf node (terminal state)10Remember Minimax: Recursive implementationp11Complete: Yes, for finite state-spaceOptimal: YesTime complexity: O(bm)Space complexity: O(bm) (= DFSDoes not keep all nodes in memory.)More on the α-βalgorithm: ttf Miistart from Minimax12The α-βalgorithmNote: These are bothLocal variables. At theStart of the algorithm,lhWe initialize them toα= -∞and β= +∞13A Walk Through Examplepα: Best choice so far for MAXMAXα= -∞β+α: Best choice so far for MAXβ: Best choice so far for MINβ= +∞…MINMAX145 10 4 2 8 7In Max-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞V= -∞β…MINMax-Value loopsover theseMAX5104 287155 10 4 2 8 7In Max-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞v= -∞β…MINα= -∞β= +∞MAX5104 287165 10 4 2 8 7In Min-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= -∞β= +∞v= -∞…MINα= -∞β= +∞v= +∞v= +∞MAX5104 287175 10 4 2 8 7In Min-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= -∞β= +∞v= -∞…MINα= -∞β= +∞v= +∞v= +∞Min-Value loopsover theseMAX5104 287185 10 4 2 8 7α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= -∞β= +∞v= -∞…MINα= -∞β= +∞v= +∞α= -∞β= +∞MAX5104 287195 10 4 2 8 7Utility(state) =5In Min-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= -∞β= +∞v= -∞…MINα= -∞β= +∞v= 5v= 5MAX5104 287205 10 4 2 8 7In Min-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞β…MINα= -∞β= 5v= 5v= 5MAX5104 287215 10 4 2 8 7In Min-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞β…MINα= -∞β= 5v= 5α= -∞β= 5v= 5MAX5104 287225 10 4 2 8 7α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞v= -∞…MINα= -∞β= 5v= 5α= -∞β= 5MAX5104 287235 10 4 2 8 7Utility(state) =10In Min-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞β…MINα= -∞β= 5v= 5 <10MAX5104 287245 10 4 2 8 7α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞v= -∞…MINα= -∞β= 5v= 5α= -∞β= 5MAX5104 287255 10 4 2 8 7Utility(state) =4In Min-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= -∞β= +∞v= -∞…MINα= -∞β= 5v= 5 >4MAX5104 287265 10 4 2 8 7In Min-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= -∞β= +∞v= -∞…MINα= -∞β= 5v= 4MAX5104 287275 10 4 2 8 7In Min-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= -∞β= +∞v= -∞…MINα= -∞β= 4v= 4MAX5104 287285 10 4 2 8 7α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= -∞β= +∞v= 4…MINMAX5104 287295 10 4 2 8 7α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= 4β= +∞v= 4…MINMAX5104 287305 10 4 2 8 7In Max-Value:α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞v= -∞β…MINα= 4β= +∞v= 4MAX5104 287315 10 4 2 8 7α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞v= -∞β…MINα= 4β= +∞v= +∞MAX5104 287325 10 4 2 8 7α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞v= -∞β…MINMAX5104 2874335 10 4 2 8 7α= 4β= +∞v= +∞α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞v= -∞β…MINMAX5104 2874345 10 4 2 8 7α= 4β= +∞α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞v= -∞β…MINα= 4β= +∞v= 2MAX5104 287355 10 4 2 8 7α: Best choice so far for MAXβ: Best choice so far for MINMAXα= -∞β= +∞v= -∞β…MINα= 4β= +∞v= 2MAX5104 287365 10 4 2 8 7α: Best choice so far for MAXβ: Best choice so far for MINMAXβα= 4β= +∞v= 4 >2…MINMAX5104 287375 10 4 2 8 7Another way to understand the algorithm From: http://yoda.cis.temple.edu:8080/UGAIWWW/lectures95/seh/ l hbt ht larch/alpha-beta.html For a given node N, α is the value of N to MAXβ is the value of N to MIN38Alpha/Beta pruning - example (4)A move (max)B move (min)A move (max)87 3 916 24 1 135 39265212397 2398 7 3 9 1 6 2 4 1 1 3 5 3 9 2 6 5 2 1 2 3 9 7 2Alpha/Beta pruning - example (4)A move (max)B move (min)A move (max)87 3 916 24 1 135 39265212397 2408 7 3 9 1 6 2 4 1 1 3 5 3 9 2 6 5 2 1 2 3 9 7 2State-of-the-art for deterministic games41Chess As An ExampleCh b iChess basics 8x8 board, 16 pieces per side, average branching factor of 38factor of 38 Rating system based on competition 500 --- beginner/legal 1200 --- good weekend warrier 2000 --- world championship level2500+ ---grand master2500 grand master time limited moves important aspects: position, material42Sketch of Chess History First discussed by Shannon, Sci. American, 1950 Initially, two approaches human-like brute force search 1966 MacHack ---1100 --- average tournament player 1970’s discovery that 1 ply = 200 rating points43 hash tables quiescence searchSketch of Chess History Chess 4.x reaches 2000 (expert level), 1979 Belle 2200, 1983special purpose hardwarespecial purpose hardware 1986 --- Cray Blitz and Hitech 100,000 to 120 000 position/sec using special120,000 position/sec using special purpose hardware44Deep Blue History 1985, Hsu build BLSI move generator (using DARPA funding!)g) Anantharaman combined with chess program leading to 50K moves/second
View Full Document
Unlocking...