CSCE 315 Lecture 16

« previous | Monday, February 27, 2012 | next »

Minimax Trees

Create a utility function to evaluate the game state to determine how strong the position of player 1 is.

Player 1 wants to maximize the utility function, Player 2 wants to minimize the utility function

Generate a new level for each move
Each move alternates between max (player 1 moves) and min (player 2 moves)

Tree Evaluation

Assign utility values to leaves

If "final" state, assign maximum utility value (player 1 wins) or minimum utility value (player 2 wins)
If not "final", evaluate utility value

At each min value, assign the minimum of all possible children utility values (player 2 chooses best move)

At each max node, assign max of children.

Given an average branching factor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} and a depth Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m}

A complete evaluation takes time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b^m}
a complete evaluation takes space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle bm}

We can only look a certain distance ahead: limit the depth based on various factors, or prune the tree. :D

Pruning

Does not affect final result (may allow you to go deeper in the tree)
Store information along an entire path (recursively evaluate pruning and store values for later

α Cuts

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

We are at a max node, so we want to choose the "max" move. Evaluate the tree using a depth-first... We find the first subtree (chooses min of it's children) provides a value of -3. Halfway through evaluation, we find that the next subtree (also chooses min), could possibly provide a minimum value of -70. Since -3 is greater than -70, we can stop evaluating that entire branch.

β Cuts

If the current min value is less than the successor's max value, don't explore that max subtree any more.

We are at a min node, so we want to choose the "min" move. blah blah blah. We get 21 from the first max node, halfway throgh we get a value of 60 from the second max node. We can stop evaluating that second node.

Utility Function

Assign numerical values to lots of individual factors:

a = # of player 1's pieces - # of player 2's pieces
b = 1 if player 1 has queen and player 2 does not, -1 if opposite, or 0 if same
c = 2 if player 1 has a 2-rook advantage, 1 if a 1-rook advantage, etc.

Use a weighted combination:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u = \alpha a + \beta b + \chi c}

Evaluation Function

Perform one move only
Evaluate board at that level
Recursively evaluate branches in order from best first move to worst first move (or vice-versa if at a min node). This should probably be done with a heap.