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 $b$ and a depth $m$

A complete evaluation takes time $b^{m}$
a complete evaluation takes space $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:

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.