1Foundations of Artificial IntelligenceAdversarial SearchCS472 – Fall 2007Thorsten JoachimsGame PlayingAn AI Favorite• structured task• clear definition of success and failure• does not require large amounts of knowledge (at first glance)• focus on games of perfect informationGame PlayingInitial State is the initial board/positionSuccessor Function defines the set of legal moves from any positionTerminal Test determines when the game is overUtility Function gives a numeric outcome for the gameGame Playing as SearchxPartial Search Tree for Tic-Tac-Toexxxxxxxxxxxoooooooooooooooxxxxxxxxxxxxxxxxxxxo…………………MIN(O)MAX(X)MIN(O)TERMINALUTILITYMAX(X)0+1-1Simplified Minimax Algorithm1. Expand the entire tree below the root.2. Evaluate the terminal nodes as wins for the minimizer or maximizer (i.e. utility). 3. Select an unlabeled node, n, all of whose children have been assigned values. If there is no such node, we're done ---return the value assigned to the root.4. If n is a minimizer move, assign it a value that is the minimum of the values of its children. If n is a maximizermove, assign it a value that is the maximum of the values of its children. Return to Step 3.2Another Example1A3A2A3332222AAA AAA AA A121284614511 13212223313233MAXMINMinimaxfunction 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) then return UTILITY[game](state)else if MAX is to move in state then return the highest MINIMAX-VALUE of SUCCESSORS(state)elsereturn the lowest MINIMAX-VALUE of SUCCESSORS(state)Improving Minimax: PruningIdea: Avoid generating the whole search treeApproach: Analyze which subtrees have no influence on the solutionαβ−Features of EvolutionmnPlayerOpponent....PlayerOpponentIf m is better than n for Player, never get to n in play.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 narrowing range between and .Maximizing levels may reset to a higher value;Minimizing levels may reset to a lower value.αβ−αβ∞∞αβ−αβαβ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 - search on a child-If • Return min3. Otherwise, the level is a maximizing level:• Until no more children or– search on a child.– If •Returnβα≤()iυmax,αβ≥, set iiυααυ>←iυαβ←−()iυiυαβ←−,.iiυββ υ<←αβ−3Search Space Size ReductionsWorst Case: In an ordering where worst options evaluated first, all nodes must be examined.Best Case: If nodes ordered so that the best options are evaluated first, then what?The Need for Imperfect DecisionsProblem: Minimax assumes the program has time to search to the terminal nodes.Solution: Cut off search earlier and apply a heuristic evaluation function to the leaves.Static Evaluation FunctionsMinimax depends on the translation of board quality into single, summarizing number. Difficult. Expensive.• Add up values of pieces each player has (weighted by importance of piece).• Isolated pawns are bad.• How well protected is your king?• How much maneuverability to you have?• Do you control the center of the board?• Strategies change as the game proceeds.Design Issues for Heuristic MinimaxEvaluation Function: Need to be carefully crafted and depends on game! What criteria should an evaluation function fulfill?Linear Evaluation Functions••This is what most game playing programs use• Steps in designing an evaluation function:1. Pick informative features.2. Find the weights that make the program play well11 2 2...nnwf wf wf+++Design Issues for Heuristics MinimaxSearch: search to a constant depthWhat are problems with constant search depth?4Backgammon Board1234570891011 1262423222025 19 18 17 16 15141321• Goal: move all of your pieces off the board before your opponent does.• Black moves counterclockwise toward 0.• White moves clockwise toward 25.• A piece can move to any position except one where there are two or more of the opponent's pieces.• If it moves to a position with one opponent piece, that piece is captured and has to start it's journey from the beginning.Backgammon - Rules• If you roll doubles you take 4 moves (example: roll 5,5, make moves 5,5,5,5).• Moves can be made by one or two pieces (in the case of doubles by 1, 2, 3 or 4 pieces)• And a few other rules that concern bearing off and forced moves.Backgammon - Rules1234570891011 1262423222025 19 18 17 16 15141321White has rolled 6-5 and has 4 legal moves: (5-10,5-11), (5-11,19-24), (5-10,10-16) and (5-11,11-16).Game Tree for BackgammonMAXDICEMINDICEMAXTERMINAL………………………………………………1/181,21/361,16,56,66,56,61/181,21/361,1CExpectiminimaxfor n, a chance nodefor n, a Min nodefor n, a Max nodefor n, a terminal stateUtility(n)Expectiminimax(n) =expectiminimax( )s∈s Succ(n) maxexpectiminimax( )s∈s Succ(n) min()( )*expectiminimax( )sSuccnPs s∈Σ5Evaluation function1.32.12.1 .9.9.111A2A432233114440.92120.1 .9.9.111A2A11202030 303040 4040State of the Art in Backgammon• 1980: BKG using two-ply (depth 2) search and lots of luck defeated the human world champion.• 1992: Tesauro combines Samuel's learning method with neural networks to develop a new evaluation function (search depth 2-3), resulting in a program ranked among the top 3 players in the world.State of the Art in Checkers• 1952: Samuel developed a checkers program that learned its own evaluation function through self play.•1990: Chinook (J. Schaeffer) wins the U.S. Open. At theworld championship, Marion Tinsley beat Chinook.•2005: Schaeffer et al. solved checkers for “White Doctor”opening (draw) (about 50 other openings).State of the Art in GoLarge branching factor makes regular search methods inappropriate.Best computer Go programs ranked only “weak amateur”.Employ pattern recognition techniques and limited search. $2,000,000 prize available for first computer program to defeat a top level player.History of Chess in AIEarly 1950's Shannon and Turing both had programs that (barely) played legal chess (500 rank).1950's Alex Bernstein's system, (500 + ε)1957