Adversarial SearchGame Playing An AI Favorite • structured task, often a symbol of “intelligence” • clear definition of success and failure • does not require large amounts of knowledge (at first glance) • focus on games of perfect information • multiplayer, chanceGame Playing Initial State is the initial board/position Successor Function defines the set of legal moves from any position Terminal Test determines when the game is over Utility Function gives a numeric outcome for the game For chess, only win, lose, draw. Backgammon: +192 to -192.x Partial Search Tree for Tic-Tac-Toe x x x x x x x x x x x o o o o o o o o o o o o o o o x x x x x x x x x x x x x x x x x x x o … … … … … … … MIN(O) MAX(X) MIN(O) TERMINAL UTILITY MAX(X) 0 +1 -1Game Playing as Search 1A3A2A322AAAAAAAAA12128461451113212223313233MAXMINTwo PlySimplified Minimax Algorithm 1. 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 maximizer move, assign it a value that is the maximum of the values of its children. Return to Step 3.Another Example 1A3A2A322AAAAAAAAA12128461451113212223313233MAXMINAccording to minimax, which action to take? A=A1 B=A2 C=A3Another Example 1A3A2A3332222AAAAAAAAA12128461451113212223313233MAXMINMinimax function MINIMAX-DECISION(game) returns an operator for each op in OPERATORS[game]do VALUE[op]←MINIMAX-VALUE(APPLY(op,game),game) end return the op with the highest VALUE[op] function MINIMAX-VALUE(state,game) returns a utility value if 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) else return the lowest MINIMAX-VALUE of SUCCESSORS(state)Improving Minimax: Pruning Idea: Avoid generating the whole search tree Approach: Analyze which subtrees have no influence on the solution Search  = best choice (highest) found so far for max, initially -  = best choice (lowest) found so far for min , initially +Features of Evolution mnPlayer Opponent .. .. Player Opponent If m is better than n for Player, never get to n in play.Search Algorithm Search Space Size Reductions Worst 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 Decisions Problem: 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 Functions Minimax 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 Minimax Evaluation 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 well 1 1 2 2...nnw f w f w f  Design Issues for Heuristics Minimax Search: search to a constant depth What are problems with constant search depth?Backgammon Board 123457089101112624232220251918171615141321• 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 - Rules123457089101112624232220251918171615141321White 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 Backgammon MAXDICEMINDICEMAXTERMINAL… … … … … … … … … … … … … … … … … … 1/181,21/361,16,56,66,56,61/181,21/361,1CExpectiminimax Expectiminimax(n) = Utility(n) for n, a terminal state for n, a Max node for n, a Min node for n, a chance node expectiminimax( )ss Succ(n) maxexpectiminimax( )ss Succ(n) min()( )*expectiminimax( )s Succ nP s sEvaluation function 1.32.12.1.9.9.111A2A432233114440.92120.1.9.9.111A2A112020303030404040State 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 the world 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 Go Large 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 AI Early 1950's Shannon and Turing both had programs that (barely) played legal chess (500 rank). 1950's Alex Bernstein's system, (500 + ε) 1957 Herb Simon claims that a computer chess program would be world chess champion in 10