CS 161 Recitation Notes - The Minimax Algorithm

The minimax algorithm is a way of finding an optimal move in a two player game. In the search tree for a two-player game, there are two kinds of nodes, nodes representing your moves and nodes representing your opponent's moves. Nodes representing your moves are generally drawn as squares (or possibly upward pointing triangles):

These are also called MAX nodes. The goal at a MAX node is to maximize the value of the subtree rooted at that node. To do this, a MAX node chooses the child with the greatest value, and that becomes the value of the MAX node.

Nodes representing your opponent's moves are generally drawn as circles (or possibly as downward pointing triangles):

These are also called MIN nodes. The goal at a MIN node is to minimize the value of the subtree rooted at that node. To do this, a MIN node chooses the child with the smallest value, and that becomes the value of the MIN node.

To demonstrate the minimax algorithm, I'm going use the following tree. Note that it's typical for two player games to have different branching factors at each node. The move I make could make restrictions on what moves are possible for the other player, or possibly remove restrictions. Note also that in this example, we're ignoring what the game or the probem space are in order to focus on the algorithm.

So now you've seen the whole search tree. For the rest of the diagrams, I'll only show the portion of the tree that we've already explored at that particular time. Thus, when we start the problem, all minimax sees is the start node:

It begins like a depth first search, generating the first child. Then we see this:

So far we've really seen no evaluation values. The way minimax works is to go down a specified number of full moves (where one "full move" is actually a move by you and a move by your opponent), then calculate evaluation values for states at that depth. For this example, we're going to go down one full move, which is one more level. When we generate the values for those nodes, here is what we see:

Now we have the values of the children of the min node, so it can do its work. It chooses the minimum of the two child node values, which is 3. Now we have this:

The max node at the top still has two other children nodes that we need to generate and search. We go on and generate the second node and generate its child. Since there is only one child, the min node must take it's value, and we have this:

Finally, minimax generates the third child of the top-level max node, generates its children, and evaluates them:

Now the third min node chooses the minimum of it's child node values, 1, and we have this:

Finally we have all of the values of the children of the max node at the top level, so it chooses the maximum of them, 15, and we get the final solution:

What this tells us is that we should take the move that leads to the middle min node, since it'll lead to the best possible state for us one full move down the road.