Adversarial SearchCS472/CS473 — Fall 2005Slide CS472 – Adversarial Search 1Game PlayingAn AI Favorite• structured task• clear definition of success and failure• does not require large amounts of knowledge (at firstglance)• focus on games of perfect informationSlide CS472 – Adversarial Search 2Game PlayingInitial State is the initial board/positionSuccessor Function defines the set of legal moves fromany positionTerminal Test determines when the game is overUtility Function gives a numeric outcome for the gameSlide CS472 – Adversarial Search 3Game Playing as SearchSlide CS472 – Adversarial Search 4Partial Search Tree for Tic-Tac-ToeXXXXXXXXXMAX (X)MIN (O)X XOOOXOOOOOOOMAX (X)X OX OX OXXXXXXXMIN (O)XOX XOX XOX. . . . . . . . . . . .. . .. . .. . .TERMINALXX−1 0 +1UtilitySlide CS472 – Adversarial Search 5Simplified Minimax Algorithm1. Expand the entire tree below the root.2. Evaluate the terminal nodes as wins for the minimizer ormaximizer (i.e. utility).3. Select an unlabeled node, n, all of whose children haveb een assigned values. If there is no such node, we’redone — return the value assigned to the root.4. If n is a minimizer move, assign it a value that is theminimum of the values of its children. If n is amaximizer move, assign it a value that is the maximumof the values of its children. Return to Step 3.Slide CS472 – Adversarial Search 6Another ExampleMAX3128 6421452MIN3A1A3A2A13A12A11A21A23A22A33A32A31322Slide CS472 – Adversarial Search 7Minimaxfunction MINIMAX-DECISION(game) returns an operatorfor each op in OPERATORS[game] doVALUE[op]MINIMAX-VALUE(APPLY(op,game),game)endreturn the op with the highest VALUE[op]function MINIMAX-VALUE(state,game) returns a utility valueif TERMINAL-TEST[game](state) thenreturn UTILITY[game](state)else ifMAX is to move in state thenreturn the highest MINIMAX-VALUE of SUCCESSORS(state)elsereturn the lowest MINIMAX-VALUE of SUCCESSORS(state)Slide CS472 – Adversarial Search 8Improving Minimax — α − β pruningIdea: Avoid generating the whole search treeApproach: Analyze which subtrees have no influence onthe solutionSlide CS472 – Adversarial Search 9PlayerOpponentPlayerOpponent......mnIf m is better than n for Player, never get to n in play.Slide CS472 – Adversarial Search 10α − β Searchα = lower bound on Max’s outcome; initially set to −∞β = upper bound on Min’s outcome ; initially set to +∞We’ll call α − β procedure recursively with a narrowingrange between α and β.Maximizing levels may reset α to a higher value; Minimizinglevels may reset β to a lower value.Slide CS472 – Adversarial Search 11α − β Search Algorithm1. If terminal state, compute e(n) and return the result.2. Otherwise, if the level is a minimizing level,• Until no more children or β ≤ α,– vi← α − β search on child.– If vi<β, β ← vi.• Return min(vi).3. Otherwise, the level is a maximizing level:• Until no more children or α ≥ β,– vi← α − β search on child.– If vi>α,setα ← vi.• Return max(vi).Slide CS472 – Adversarial Searc h
View Full Document
Unlocking...