Game PlayingGame Playing and AISlide 3Game Playing as SearchGame Tree RepresentationComplexity of Game PlayingGreedy Search using an Evaluation FunctionSlide 8Slide 9Minimax PrincipleSlide 11Propagating Minimax Values up the Game TreeDeeper Game TreesGeneral Minimax AlgorithmComplexity of Minimax AlgorithmSlide 16Static Board Evaluator (SBE)Slide 18Minimax Algorithm with SBEMinimax with Evaluation FunctionsSummary So FarAlpha-Beta IdeaSlide 23Alpha-Beta ExampleSlide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Effectiveness of Alpha-Beta SearchSlide 58Dealing with Limited TimeSlide 60The Horizon EffectSlide 62Book MovesMore on Evaluation FunctionsLinear Evaluation FunctionsSlide 66Learning the Weights in a Linear Evaluation FunctionExamples of Algorithms which Learn to Play WellSlide 69Non-deterministic GamesSlide 71Slide 72Slide 73Slide 74Computers can play GrandMaster ChessSlide 76Chess Rating ScaleStatus of Computers in Other Deterministic GamesSummarySlide 80Conclusion01/14/191©2001 James D. Skrentny from notes by C. DyerGame PlayingChapter 5some slides from UC-Irvine, CS Dept.01/14/192©2001 James D. Skrentny from notes by C. DyerGame Playing and AIGame playing (was?) thought to bea good problem for AI research:–game playing is non-trivialplayers need “human-like” intelligencegames can be very complex (e.g., chess, go)requires decision making within limited time–games usually are:well-defined and repeatablelimited and accessible–can directly compare humans and computers01/14/193©2001 James D. Skrentny from notes by C. DyerGame Playing and AIDeterministic Chanceadmissible, perfect infoCheckers, Chess, Go, OthelloBackgammon, Monopolynot admissible, imperfect infowhat kinds of games here?Bridge, Poker, Scrabble01/14/194©2001 James D. Skrentny from notes by C. DyerGame Playing as SearchConsider a two player board game:–e.g., chess, checkers, tic-tac-toe–board configuration: unique arrangement of "pieces"Representing board games as search problem:–states: board configurations–operators: legal moves–initial state: current board configuration–goal state: winning/terminal board configuration01/14/195©2001 James D. Skrentny from notes by C. DyerGame Tree RepresentationX X XX…OX OXOXOX…How can we handle this?What's the new aspectto the search problem?There’s an opponentwe cannot control!XOXX OXX OXOX X…OXX01/14/196©2001 James D. Skrentny from notes by C. DyerComplexity of Game PlayingAssume the opponent’s moves can bepredicted given the computer's movesHow complex would search be in this case?–worst case: O(bd) branching factor, depth–Tic-Tac-Toe: ~5 legal moves, max of 9 moves59 = 1,953,125 states–Chess: ~35 legal moves, ~100 moves per gamebd ~ 35100 ~10154 states, “only” ~1040 legal statesCommon games produce enormous search trees01/14/197©2001 James D. Skrentny from notes by C. DyerGreedy Searchusing an Evaluation FunctionAn evaluation/utility function is used to map each terminal state of the board to a number corresponding to the value of that state to the computer–positive for winning–negative for losing–0 for a draw–typical values (lost to win):- to +-1.0 to +1.001/14/198©2001 James D. Skrentny from notes by C. DyerGreedy Searchusing an Evaluation FunctionExpand the search tree to the terminal stateson each branchEvaluate utility of each terminal board configurationMake the initial move that results in the board configuration with the maximum valueM1N3O2K0L2F-7G-5H3I9J-6EDB Ccomputer's possible movesopponent'spossible movesboard evaluation from computer's perspectiveAterminal statesE3D2B-5C9A901/14/199©2001 James D. Skrentny from notes by C. DyerGreedy Searchusing an Evaluation FunctionAssuming a reasonable search space,what's the problem?This ignores what the opponent might do!Computer chooses COpponent chooses J and defeats computerM1N3O2K0L2F-7G-5H3I9J-6E3D2B-5C9computer's possible movesopponent'spossible movesboard evaluation from computer's perspectiveA9terminal states01/14/1910©2001 James D. Skrentny from notes by C. DyerMinimax PrincipleAssuming the worst (i.e., opponent plays optimally):–given there are two plays till the terminal states–high utility numbers favor the computercomputer should choose maximizing moves–low utility numbers favor the opponentsmart opponent chooses minimizing moves01/14/1911©2001 James D. Skrentny from notes by C. DyerEDB CAMinimax PrincipleThe computer assumes after it movesthe opponent will choose the minimizing moveE1D0B-7C-6A1The computer chooses the best move considering both its move and opponent’s optimal moveM1N3O2K0L2F-7G-5H3I9J-6computer's possible movesopponent'spossible movesboard evaluation from computer's perspectiveterminal states01/14/1912©2001 James D. Skrentny from notes by C. DyerPropagating Minimax Valuesup the Game TreeExplore the tree to the terminal statesEvaluate utility of the resulting board configurationsThe computer makes a move to put the board in the best configuration for it assuming the opponent makes her best moves on her turn:–start at the leaves–assign value to the parent node as followsuse minimum when children are opponent’s movesuse maximum when children are computer's moves01/14/1913©2001 James D. Skrentny from notes by C. DyerED0B CR0N4OP9Q-6S3T5U-7V-9K MFG-5H3I8JL2W-3X-5ADeeper Game TreesMinimax can be generalized to more than 2 moves Propagate/percolate values upwards in the treeterminal statesO-5K5M-7F4J9E-7B-5C3A3oppponent mincomputer maxoppponent mincomputer max01/14/1914©2001 James D. Skrentny from notes by C. DyerGeneral Minimax AlgorithmFor each move by the computer:1. Perform depth-first search to a terminal state2. Evaluate each terminal state3. Propagate upwards the minimax valuesif opponent's move, propagate up minimum value of childrenif cumputer's move, propagate up maximum value of children4. choose move with the maximum of minimax values of childrenNote:•minimax values gradually propagate upwards as DFS proceeds: i.e., minimax values propagate up in “left-to-right” fashion•minimax values for sub-tree propagate upwards “as we go,” so only O(bd) nodes need to be kept in memory at any