1CS 1571 Intro to AIM. HauskrechtCS 1571 Introduction to AILecture 12Milos [email protected] Sennott SquareAdversarial search CS 1571 Intro to AIM. HauskrechtAnnouncements• Homework assignment 4 is out– Programming and experiments – Simulated annealing + Genetic algorithm– Competition Course web page:http://www.cs.pitt.edu/~milos/courses/cs1571/2CS 1571 Intro to AIM. HauskrechtSearch reviewSearch• Path search• Configuration searchOptimality• Finding a path versus finding the optimal path• Finding a configuration satisfying constraints versus finding the best configurationCS 1571 Intro to AIM. HauskrechtGame search• Game-playing programs developed by AI researchers since the beginning of the modern AI era– Programs playing chess, checkers, etc (1950s)• Specifics of the game search:– Sequences of player’s decisions we control– Decisions of other player(s) we do not control• Contingency problem: many possible opponent’s moves must be “covered” by the solutionOpponent’s behavior introduces an uncertainty in to the game– We do not know exactly what the response is going to be• Rational opponent – maximizes it own utility (payoff) function3CS 1571 Intro to AIM. HauskrechtTypes of game problems• Types of game problems:– Adversarial games:• win of one player is a loss of the other– Cooperative games:• players have common interests and utility function– A spectrum of game problems in between the two:we focus on adversarial games only!!Adversarial games Fully cooperative gamesCS 1571 Intro to AIM. HauskrechtExample of an adversarial 2 person game: Tic-tac-toe• Player 1 (x) moves firstWinLoss Draw4CS 1571 Intro to AIM. HauskrechtGame search problem• Game problem formulation:– Initial state: initial board position + info whose move it is– Operators: legal moves a player can make– Goal (terminal test): determines when the game is over– Utility (payoff) function: measures the outcome of the game and its desirability• Search objective: – find the sequence of player’s decisions (moves) maximizing its utility (payoff)– Consider the opponent’s moves and their utilityCS 1571 Intro to AIM. HauskrechtGame problem formulation (Tic-tac-toe)Objectives:• Player 1:maximize outcome• Player 2:minimize outcomeUtility:1-1 0Initial stateTerminal (goal) statesOperators5CS 1571 Intro to AIM. HauskrechtMinimax algorithmHow to deal with the contingency problem?• Assuming that the opponent is rational and always optimizes its behavior (opposite to us) we consider the best opponent’s response • Then the minimax algorithm determines the best move MAXMIN31282 4 614523223CS 1571 Intro to AIM. HauskrechtMinimax algorithm. ExampleMAXMAXMIN436 2219 3515 4 7 56CS 1571 Intro to AIM. HauskrechtMinimax algorithm. ExampleMAXMAXMIN436 2219 3515 4 7 5CS 1571 Intro to AIM. HauskrechtMinimax algorithm. ExampleMAXMAXMIN436 2219 3515 4 7 547CS 1571 Intro to AIM. HauskrechtMinimax algorithm. ExampleMAXMAXMIN436 2219 3515 4 7 546CS 1571 Intro to AIM. HauskrechtMinimax algorithm. ExampleMAXMAXMIN436 2219 3515 4 7 54648CS 1571 Intro to AIM. HauskrechtMinimax algorithm. ExampleMAXMAXMIN436 2219 3515 4 7 54642CS 1571 Intro to AIM. HauskrechtMinimax algorithm. ExampleMAXMAXMIN436 2219 3515 4 7 5464299CS 1571 Intro to AIM. HauskrechtMinimax algorithm. ExampleMAXMAXMIN436 2219 3515 4 7 5464293CS 1571 Intro to AIM. HauskrechtMinimax algorithm. ExampleMAXMAXMIN436 2219 3515 4 7 54642932555710CS 1571 Intro to AIM. HauskrechtMinimax algorithmCS 1571 Intro to AIM. HauskrechtComplexity of the minimax algorithm• We need to explore the complete game tree before making the decision1-1 0Complexity:mb?11CS 1571 Intro to AIM. HauskrechtComplexity of the minimax algorithm• We need to explore the complete game tree before making the decision• Impossible for large games – Chess: 35 operators, game can have 50 or more moves1-1 0Complexity:)(mbOmbCS 1571 Intro to AIM. HauskrechtSolution to the complexity problemTwo solutions:1. Dynamic pruning of redundant branches of the search tree– identify a provably suboptimal branch of the search tree before it is fully explored– Eliminate the suboptimal branchProcedure: Alpha-Beta pruning2. Early cutoff of the search tree– uses imperfect minimax value estimate of non-terminal states (positions)12CS 1571 Intro to AIM. HauskrechtAlpha beta pruning• Some branches will never be played by rational players since they include sub-optimal decisions (for either player)CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 513CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54≥CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=4≤14CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54≤6≥4=!!CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=6≥4=4≥15CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=6≥4=4≥2≥CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=6≥4=4≥2=2≤16CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=6≥4=4≥2=2≤!!CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=6≥4=4≥2=2≤5≥17CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=6≥4=4≥2=2≤5=5≤CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=6≥4=4≥2=2≤5=5≤7≥!!18CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=6≥4=5≥2=2≤5=5=7≥CS 1571 Intro to AIM. HauskrechtAlpha beta pruning. ExampleMAXMAXMIN436 2219 3515 4 7 54=6≥4=5=2=2≤5=5=7≥nodes that were never explored !!!19CS 1571 Intro to AIM. HauskrechtAlpha-Beta pruningGOALGOALCS 1571 Intro to AIM. HauskrechtUsing minimax value estimates• Idea:– Cutoff the search tree before the terminal state is reached– Use imperfect estimate of the minimax value at the leaves• Evaluation functionHeuristic evaluationfunctionMAXMINCutoff level464293255574320CS 1571 Intro to AIM. HauskrechtDesign of evaluation functions• Heuristic estimate of the value for a sub-tree• Examples of a heuristic functions:– Material advantage in chess, checkers• Gives a value to every piece on the board, its