Adversarial Search and Game PlayingTopicsWhy study gamesGame-Playing AgentTypes of gamesSlide 6Typical caseNimNIM(2,2)Perfect Two-Player GameGame Tree for NIM(2,2)How to play a gameOptimal PlayMinimax TreeMinimax procedureMin-Max Game Tree for NIM(2,2)Minimax ExampleSlide 18Evaluation functionEvaluation function examplesGame treesSlide 22Partial Game Tree for Tic-Tac-ToeIssuesAdaptive SearchSlide 26Alpha-Beta ProcedureAlpha-beta pruningSlide 29Alpha-beta exampleSlide 31Slide 32Alpha-Beta ExampleSlide 35Effectiveness of alpha-betaSome examples….CheckersChinook vs. TinsleyChinookChessMan vs. MachineSlide 47Several versions of the story…Reversi/OthelloOthelloGo: On the One SideGo: And on the OtherPerspective on Games: ProPerspective on Games: ConOther GamesSummaryAdditional ResourcesThe GameDraw the game treeTry this for your Game TreeAdversarial Search and Adversarial Search and Game PlayingGame PlayingRussell and Norvig: Chapter 6CMSC 421 – Fall 2003TopicsGame playingGame treesMinimaxAlpha-beta pruningExamplesWhy study gamesClear criteria for successOffer an opportunity to study problems involving {hostile, adversarial, competing} agents.Historical reasonsFunInteresting, hard problemsGame-Playing AgentGame-Playing Agentenvironmentagent?sensorsactuatorsEnvironmentTypes of gamesperfect informationimperfect informationdeterministicchanceTypes of gameschess, checkers, go, othellobackgammon, monopolybridge, poker, scrabbleperfect informationimperfect informationdeterministicchanceTypical case2-person gamePlayers alternate moves Zero-sum: one player’s loss is the other’s gainPerfect information: both players have access to complete information about the state of the game. No information is hidden from either player.No chance (e.g., using dice) involved Examples: Tic-Tac-Toe, Checkers, Chess, Go, Nim, OthelloNot: Bridge, Solitaire, Backgammon, ...NimGame: start with a punch of piles of tokensAt each turn, a player may pick up one or two tokensThe player who picks up the last token LOSESNIM(2,2)Try the following case:pile 1 pile 2Perfect Two-Player GamePerfect Two-Player Game Two players MAX and MIN take turn (with MAX playing first) State space Initial state Successor function Terminal test Score function, that tells whether a terminal state is a win (for MAX), a loss, or a draw Perfect knowledge of states, no uncertainty in successor function ~UtilityGame Tree for NIM(2,2)drawn on the boardHow to play a gameA way to play such a game is to:Consider all the legal moves you can makeCompute the new position resulting from each moveEvaluate each resulting position and determine which is bestMake that moveWait for your opponent to move and repeatKey problems are:Representing the “board”Generating all legal next boardsEvaluating a positionOptimal Play2 7 18MAXMIN2 7 18212 7 182 122 7 182 12This is the optimal playMinimax TreeMAX nodeMIN nodef valuevalue computed by minimaxMinimax procedureApply the evaluation function at each of the leaf nodes “Back up” values for each of the non-leaf nodes until a value is computed for the root nodeAt MIN nodes, the backed-up value is the minimum of the values associated with its children. At MAX nodes, the backed up value is the maximum of the values associated with its children. Pick the operator associated with the child node whose backed-up value determined the value at the rootMin-Max Game Tree for NIM(2,2)drawn on the boardMinimax ExampleMinimax Example0 5 -3 25-2 32-3 033 -501 -350 1-55 3 2-35But in general the search tree is too big to make it possible to reach the terminal states!Examples:• Checkers: ~1040 nodes• Chess: ~10120 nodesEvaluation functionEvaluation function or static evaluator is used to evaluate the “goodness” of a game position.Contrast with heuristic search where the evaluation function was a non-negative estimate of the cost from the start node to a goal and passing through the given nodeThe zero-sum assumption allows us to use a single evaluation function to describe the goodness of a board with respect to both players. f(n) >> 0: position n good for me and bad for youf(n) << 0: position n bad for me and good for youf(n) near 0: position n is a neutral positionf(n) = +infinity: win for mef(n) = -infinity: win for youEvaluation function examplesExample of an evaluation function for Tic-Tac-Toe: f(n) = [# of 3-lengths open for me] - [# of 3-lengths open for you] where a 3-length is a complete row, column, or diagonalAlan Turing’s function for chessf(n) = w(n)/b(n) where w(n) = sum of the point value of white’s pieces and b(n) = sum of black’sMost evaluation functions are specified as a weighted sum of position features:f(n) = w1*feat1(n) + w2*feat2(n) + ... + wn*featk(n) Example features for chess are piece count, piece placement, squares controlled, etc. Deep Blue has about 6000 features in its evaluation functionGame treesProblem spaces for typical games are represented as treesRoot node represents the current board configuration; player must decide the best single move to make nextStatic evaluator function rates a board position. f(board) = real number withf>0 “white” (me), f<0 for black (you)Arcs represent the possible legal moves for a player If it is my turn to move, then the root is labeled a "MAX" node; otherwise it is labeled a "MIN" node, indicating my opponent's turn. Each level of the tree has nodes that are all MAX or all MIN; nodes at level i are of the opposite kind from those at level i+1Minimax procedureCreate start node as a MAX node with current board configuration Expand nodes down to some depth (a.k.a. ply) of lookahead in the gameApply the evaluation function at each of the leaf nodes “Back up” values for each of the non-leaf nodes until a value is computed for the root nodeAt MIN nodes, the backed-up value is the minimum of the values associated with its children. At MAX nodes, the backed up value is the maximum of the values associated with its children. Pick the operator associated with the child node whose backed-up value determined the value at the rootPartial Game Tree for Tic-Tac-Toe•f(n) = +1 if the position is a win for X.•f(n) = -1 if the position is a win for O.•f(n) = 0 if the position is a draw.IssuesIssues Choice of the horizon Size of memory needed Number of nodes