Minimax Trees and Tree Evaluation in Game Strategy

Minimax Trees: Utility Evaluation, Tree Evaluation, Pruning CSCE 315 Programming Studio Fall 2017 Project 2, Lecture 2 Adapted from slides of Yoonsuck Choe, John Keyser

Two-Person Perfect Information Deterministic Game Two players take turns making moves Board state fully known, deterministic evaluation of moves One 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 possible

General Strategy Player 1 wants to maximize his chance of win Player 2 wants to maximize his (minimize Player 1 s) (9 possibilities) (8 possibilities)

Minimax Tree Use Minimax tree to emulate human s forward thinking process In Chess, players think a couple of steps (e.g., 3-4 steps) ahead in contingency of opponent moves Similar idea applies to other such games

Minimax tree Max Min Max Min Minimax tree Generate a new level for each move Levels alternate between max (player 1 moves) and min (player 2 moves)

Minimax Tree Evaluation Assign utility values to leaves Sometimes called board evaluation function If a state is a leaf state where Player 1 wins (looses), assign the maximum(minimum) possible utility value Board State 1 Board State 2 Board State 3 Utility: -100 Utility: 0 Utility: +100 Otherwise, keep expanding (make the next move)

Minimax tree Max Min Max 100 Min 100 -100 -100

Minimax Tree Algorithm functionMAX-VALUE (state) ifTERMINAL-TEST (state) returnUTILITY (state) ? = foreachsinSUCCESSORS (state) v = MAX (v, MIN-VALUE (s)) returnv functionMIN-VALUE (state) ifTERMINAL-TEST (state) returnUTILITY (state) ? = foreachsinSUCCESSORS (state) v = MIN (v, MAX-VALUE (s)) returnv

Minimax Tree Evaluation At each min node, assign the minimum of all utility values at children Player 2 chooses the best available move At each max node, assign the maximum of all utility values at children Player 1 chooses best available move Push values from leaves to top of tree

Problem?? What if the node we are trying to judge is NOT a LEAF node For Chess, a LEAF node could be many levels down Could take years(!!!) to compute It would be best if there was a Oracle saying: this is promising state, go for this move The answer to this problem: Utility Function

Utility Function Create a utility function Evaluation of board/game state to determine how strong the position of player 1 is. Assume that x is Player 1 in the following Tic-Tac- Toe Example: You have all of Queen, Rooks, Knights, Bishops and some Pawns, while your opponent has only 1 Knight, you have a high chance of winning Utility function will assign a numeric value to this board state (say 90/100)

Minimax tree Max Min Max 28 -3 -8 12 70 -4 100 -73 -14 Min 23 28 21 -3 12 4 70 -4 -12 -70 -5 -100 -73 -14 -8 -24

Minimax tree Max Min -4 -3 -73 Max 28 -3 -8 12 70 -4 100 -73 -14 Min 23 28 21 -3 12 4 70 -4 -12 -70 -5 -100 -73 -14 -8 -24

Minimax tree Max -3 Min -4 -3 -73 Max 28 -3 -8 12 70 -4 100 -73 -14 Min 23 28 21 -3 12 4 70 -4 -12 -70 -5 -100 -73 -14 -8 -24

Minimax Evaluation Given average branching factor b, and depth m: A complete evaluation takes time bm A complete evaluation takes space bm Usually, we cannot evaluate the complete state, since it s too big Instead, we limit the depth based on various factors, including time available.

Utility Evaluation Function Very game-specific Take into account knowledge about game Stupid utility 1 if player 1 wins -1 if player 0 wins 0 if tie (or unknown) Only works if we can evaluate complete tree But, should form a basis for other evaluations

Utility Evaluation Need to assign a numerical value to the state Could assign a more complex utility value, but then the min/max determination becomes trickier Typically assign numerical values to lots of individual factors a = # player 1 s pieces - # player 2 s pieces b = 1 if player 1 has queen and player 2 does not, -1 if the opposite, or 0 if the same c = 2 if player 1 has 2-rook advantage, 1 if a 1- rook advantage, etc.

Utility Evaluation The individual factors are combined by some function Usually a linear weighted combination is used u = a + b + c Different ways to combine are also possible Notice: quality of utility function is based on: What features are evaluated How those features are scored How the scores are weighted/combined Absolute utility value doesn t matter relative value does.

Evaluation functions If you had a perfect utility evaluation function, what would it mean about the minimax tree?

Evaluation functions If you had a perfect utility evaluation function, what would it mean about the minimax tree? You would never have to evaluate more than one level deep! Typically, you can t create such perfect utility evaluations, though.

Pruning the Minimax Tree Since 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 useful

Cuts If the current max value is greater than the successor s min value, don t explore that min subtree any more

Cut example Max -3 Min -3 -4 -73 Max 21 -3 12 70 -4 100 -73 -14

Cut example Max Min Max -3 12 -70 -4 100 -73 -14 21 Depth first search along path 1

Cut example Max Min 21 Max -3 12 -70 -4 100 -73 -14 21 21 is minimum so far (second level) Can t evaluate yet at top level

Cut example Max -3 Min -3 Max 12 -70 -4 100 -73 -14 21 -3 -3 is minimum so far (second level) -3 is maximum so far (top level)

Cut example Max -3 Min 12 -3 Max -70 -4 100 -73 -14 21 -3 12 12 is minimum so far (second level) -3 is still maximum (can t use second node yet)

Cut example Max -3 Min -70 -3 Max -4 100 -73 -14 21 -3 12 -70 -70 is now minimum so far (second level) -3 is still maximum (can t use second node yet)

Cut example Max -3 Min -70 -3 Max -4 100 -73 -14 21 -3 12 -70 Since second level node will never be > -70, it will never be chosen by the previous level We can stop exploring that node

Cut example Max -3 Min -70 -3 -73 Max -4 100 -14 21 -3 12 -70 -73 Evaluation at second level is -73

Cut example Max -3 Min -70 -3 -73 Max -4 100 -14 21 -3 12 -70 -73 Again, can apply cut since the second level node will never be > -73, and thus will never be chosen by the previous level

Cut example Max -3 Min -70 -3 -73 Max -4 100 -14 21 -3 12 -70 -73 As a result, we evaluated the Max node without evaluating several of the possible paths

cuts Similar idea to cuts, but the other way around If the current minimum is less than the successor s max value, don t look down that max tree any more

Cut example Min 21 Max 21 70 73 Min -4 100 -14 21 -3 12 70 73 Some subtrees at second level already have values > min from previous, so we can stop evaluating them.

- Pruning Pruning by these cuts does not affect final result May allow you to go much deeper in tree Good ordering * of moves can make this pruning much more efficient Evaluating best branch first yields better likelihood of pruning later branches Perfect ordering reduces time to bm/2 i.e. doubles the depth you can search to! *Will come back to it in a bit

- Pruning Can 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 far If the value that would be returned is ever > , then stop work on this branch If all children are evaluated without pruning, return the MAX of their values

Pruning at MIN node is possibly updated by the MIN of successors evaluated so far If the value that would be returned is ever < , then stop work on this branch If all children are evaluated without pruning, return the MIN of their values

Idea of - Pruning 21 21 21 -3 70 We know on this path is 21 So, when we get max=70, we know this will never be used, so we can stop here -4 100 12 70

Refined Minimax Tree With Alpha-Beta Pruning functionTERNINAL-TEST (state, depth) ifLEAF-NODE (state) OR depth >= MAX_DEPTH returnTRUE returnFALSE functionMAX-VALUE(state, depth, alpha, beta) ifTERMINAL-TEST(state, depth)returnUTILITY(state) v = INT_MIN // minimum possible integer, emulating inf foreach s in SUCCESSORS(state) v = MAX (v,MIN-VALUE(s,depth+1,alpha, beta)) alpha = MAX (v,alpha) // update the current alpha if(v >beta) return v //prune this branch if v>beta return v

Idea of - Pruning Pruning gives the exact same result that you would have gotten without pruning It just allows you to go deeper Pruning and searching the minimax tree are independent of the particular game being studied The game influences: The utility function The branching ratio/options at any one level

Evaluation Functions for Ordering As mentioned earlier, order of branch evaluation can make a big difference in how well you can prune A good evaluation function might help you order your available moves First order the SUCCESSOR nodes on the UTILITY value This happens before completely expanding that node Then, expand DFS on the node with best value

Accounting for Time Deadline Often, real-world clock time is a factor in a game Limit time per move Limit total time allowed We might not be able to predict how far ahead we can look in a tree in a given time Different computers, board states Different amount of saving from alpha-beta pruning A non-conservative estimate might violate the time constraint A conservative estimate is likely to waste time

Dealing with Time Iterative Deepening Compute to one level, then two (repeating level 1), then three, etc. until time runs out Return the best known move so far at time limit Now, required time: O( ?=1 Wastes time in repeat of earlier levels But, can be surprising small, especially with large branching factors b Ordering from prior evaluations helps ? ??)

FAQs What kind of tree data structure for the minimax tree? You do not really need to allocate a tree. We are just referring to the recursion tree inherently being created Our game works fine without alpha-beta pruning not much delay for the AI. Why do we still need pruning? This delay would be very prominent for more complicated games (e.g., chess) Why do we need to re-order the successor nodes? Again, you may not see a difference for Kalah, but it is feature and you will get points for it. The motivation is that this gives you much more speedup in a more complicated game What type of GUI do we need? Will we just do any GUI, will we full 10% points? To get full GUI points, you need to handle the game using mouse clicks and keyboard events both