Minimax Trees: Utility Evaluation, Tree Evaluation, PruningTwo-Person Perfect Information Deterministic GameMinimaxMinimax treeMinimax Tree EvaluationSlide 6Slide 7Slide 8Slide 9Slide 10Minimax EvaluationPruning the Minimax Treea Cutsa Cut exampleSlide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23b cutsb Cut examplea-b PruningSlide 27Pruning at MAX nodePruning at MIN nodeIdea of a-b PruningUtility Evaluation FunctionUtility EvaluationSlide 33Evaluation functionsSlide 35Evaluation Functions for OrderingMinimax Trees:Utility Evaluation, Tree Evaluation, PruningCPSC 315 – Programming StudioSpring 2009Project 2, Lecture 2Adapted from slides of Yoonsuck ChoeTwo-Person Perfect Information Deterministic GameTwo players take turns making movesBoard state fully known, deterministic evaluation of movesOne player wins by defeating the other (or else there is a tie)Want a strategy to win, assuming the other person plays as well as possibleMinimaxCreate a utility functionEvaluation of board/game state to determine how strong the position of player 1 is.Player 1 wants to maximize the utility functionPlayer 2 wants to minimize the utility functionMinimax treeGenerate a new level for each moveLevels alternate between “max” (player 1 moves) and “min” (player 2 moves)Minimax treeMaxMinMaxMinMinimax Tree EvaluationAssign utility values to leavesSometimes called “board evaluation function”If leaf is a “final” state, assign the maximum or minimum possible utility value (depending on who would win)If leaf is not a “final” state, must use some other heuristic, specific to the game, to evaluate how good/bad the state is at that pointMinimax treeMaxMinMaxMin100-24-8-14-73-100-5-70-12-370412-3212823Minimax Tree EvaluationAt each min node, assign the minimum of all utility values at childrenPlayer 2 chooses the best available moveAt each max node, assign the maximum of all utility values at childrenPlayer 1 chooses best available movePush values from leaves to top of treeMinimax treeMaxMinMaxMin100-24-8-14-73-100-5-70-12-370412-321282328 -312 70 -3 -73 -14-8Minimax treeMaxMinMaxMin100-24-8-14-73-100-5-70-12-470412-321282321 -312 70 -4 -73 -14-8-3-4-73Minimax treeMaxMinMaxMin100-24-8-14-73-100-5-70-12-470412-321282321 -312 70 -4 -73 -14-8-3-4-73-3Minimax EvaluationGiven average branching factor b, and depth m:A complete evaluation takes time bmA complete evaluation takes space bmUsually, we cannot evaluate the complete state, since it’s too bigInstead, we limit the depth based on various factors, including time available.Pruning the Minimax TreeSince we have limited time available, we want to avoid unnecessary computation in the minimax tree.Pruning: ways of determining that certain branches will not be usefulGiven the assumption that players will always choose their best option, prune subtrees that cannot be their best option. CutsIf the current max value is greater than the successor’s min value, don’t explore that min subtree any more Cut example10021 -3 12 70 -4 -73 -14-3 -4-3-73MaxMaxMin Cut exampleDepth first search along path 110021 -3 12 -70 -4 -73 -14MaxMaxMin Cut example21 is minimum so far (second level)Can’t evaluate yet at top level10021 -3 12 -70 -4 -73 -14MaxMaxMin21 Cut example-3 is minimum so far (second level)-3 is maximum so far (top level)10021 -3 12 -70 -4 -73 -14MaxMaxMin-3-3 Cut example12 is minimum so far (second level)-3 is still maximum (can’t use second node yet)10021 -3 12 -70 -4 -73 -14MaxMaxMin-3-312 Cut example-70 is now minimum so far (second level)-3 is still maximum (can’t use second node yet)10021 -3 12 -70 -4 -73 -14MaxMaxMin-3-3-70 Cut exampleSince second level node will never be > -70, it will never be chosen by the previous levelWe can stop exploring that node10021 -3 12 -70 -4 -73 -14MaxMaxMin-3-3-70 Cut exampleEvaluation at second level is again -7310021 -3 12 -70 -4 -73 -14MaxMaxMin-3-3-70-73 Cut exampleAgain, can apply cut since the second level node will never be > -73, and thus will never be chosen by the previous level10021 -3 12 -70 -4 -73 -14MaxMaxMin-3-3-70-73 Cut exampleAs a result, we evaluated the Max node without evaluating several of the possible paths10021 -3 12 -70 -4 -73 -14MaxMaxMin-3-3-70-73 cutsSimilar idea to cuts, but the other way aroundIf the current minimum is less than the successor’s max value, don’t look down that max tree any more Cut exampleSome subtrees at second level already have values > min from previous, so we can stop evaluating them.1021 -3 12 70 -4 73 -14MinMinMax212170 73- PruningPruning by these cuts does not affect final resultMay allow you to go much deeper in tree“Good” ordering of moves can make this pruning much more efficientEvaluating “best” branch first yields better likelihood of pruning later branchesPerfect ordering reduces time to bm/2i.e. doubles the depth you can search to!- PruningCan store information along an entire path, not just at most recent levels!Keep along the path:: best MAX value found on this path (initialize to most negative utility value): best MIN value found on this path (initialize to most positive utility value)Pruning at MAX node is possibly updated by the MAX of successors evaluated so farIf the value that would be returned is ever > , then stop work on this branchIf all children are evaluated without pruning, return the MAX of their valuesPruning at MIN node is possibly updated by the MIN of successors evaluated so farIf the value that would be returned is ever < , then stop work on this branchIf all children are evaluated without pruning, return the MIN of their valuesIdea of - PruningWe know on this path is 21So, when we get max=70, we know this will never be used, so we can stop here10021 -312 70 -4212170Utility Evaluation FunctionVery game-specificTake into account knowledge about game“Stupid” utility1 if player 1 wins-1 if player 0 wins0 if tie (or unknown)Only works if we can evaluate complete treeBut, should form a basis for other evaluationsUtility EvaluationNeed to assign a numerical value to the stateCould assign a more complex utility value, but then the min/max determination becomes trickierTypically
View Full Document