Courses/CS 460/Fall 2005/Notes for Dec 3

From CSWiki

Contents 1 Minimax trees 2 Alpha-beta pruning 3 The A* algorithm

Last week we mentioned minimax. Here is a brief discussion of minimax and the alpha-beta heuristic. Below that we include a brief discussion of the A* algorithm, which really belongs with our discussion last week of breadth-first and depth-first search.

See Chandy, which has a nice (and also brief) discussion, from which this is derived. The preceding site includes pseudo-code. The preceding site also includes the following copyright notice. Since I'm linking to figures on that site, here is that notice. (I don't know whether a link without the copyright notice would violate copyright.)

© 1994, K. Mani Chandy. All rights reserved. Reproduction of all or part of this work is permitted for educational or research use provided that this copyright notice is included in any copy.

The preceding copyright notice applies to the Chandy site, not to this one, which is covered by the http://cs.calstatela.edu/~wiki/skins/common/images/gnu-fdl.png copyright. This page does not include any text or figures copied from Chandy's site. It includes links to figures on Chandy's site. In other words, Chandy's copyright notice applies to the figures from Chandy's site that appear in your browser when you access this page.

It isn't clear to me what the legal obligations are here. This page does not include anything from Chandy's site. It simply refers to figures that appear on that site. It does that in much the same way as it might refer to the George Washington monument. This page also tells your browser how to access those figures and to display them in a context that makes the text on this page more useful. It needn't have done that. It might have provided a link to Chandy's site and suggested that the reader look at the figures there while reading the text here.

[edit] Minimax trees

Consider the following figure: http://www.cs.caltech.edu/~vhuang/cs20/c/research/gfx/_19960_figure17.gif

The figure is intended to represent a game tree. It represents the possible game states after two black moves and one white move from some current position. (Note that there is an assumption that one can evaluate a game state and assign a value to it.)

The figure presumes that black wants to maximize and that white wants to minimize. If the bottom nodes were final nodes of the game, we might represent a black win as +100 and a white win as -100.

If one had such a game tree (and having a tree that is large enough to be useful is a big assumption), one could determine what black's optimum move is. (The top of the tree represents the state of the game at which it is black's turn to move.)

To find black's best move, simply start at the bottom of the tree and work your way up, selecting the maximum or minimum move as appropriate. Thus the 6 at the right of the tree above the three nodes with values 4, 6, and 3 represents black's best move at that point since black wants to maximize. The 1 shown in the parent of that node is white's best move since white wants to minimize. Working upwards, we find that black's best move is to select the middle (5) move.

Note that we are assuming that the opponent will make his best move. If we thought the opponent could be tricked, it might be better for black to select the node to the left since there is a chance for black to end up with 9 at the bottom of that branch of the tree. On the other hand, if black did select that node, white might select the node to the left, and black would be left with 4 instead of the 5, which he could have guaranteed for himself.

[edit] Alpha-beta pruning

Alpha-beta pruning is a way to reduce the number of branches that must be searched when doing a minimax evaluation. Consider the same game tree again. http://www.cs.caltech.edu/~vhuang/cs20/c/research/gfx/_19960_figure26.gif

We are evaluating the tree from left to right. Suppose that we have already evaluated the left-most branch to the point that we know that white can assure a 4 by taking the left most branch. We know that after looking all the way down the tree along the left-most path. Consider how we proceed with the middle branch below that internal 4 node for white.

We see that black can get at least a 6 by taking the left-most branch below the node labelled 6. Since we know that white wants to minimize, we know that even if black could do better than a 6 white would select the 4 node. So there is no point in evaluating the other nodes below the 6. That's why those nodes are crossed out. We don't even have to look at them. It turns out that those nodes wouldn't have improved black's score. But even were there a way for black to score better than 6 at that move, white would not have given black the opportunity to do so since white already knows a way to minimize the parent node to 4.

Note that both nodes below the internal 9 node must be explored. The first move is 3. If the other move were also less than 4, selecting that node would have been better for white than to select the 4 node. It is only after we see that black could score 9 that we know that that node is not good for white. But by that time, we have looked at both nodes under the internal 9 node.

Similarly, once we know that black can assure a 5 at the topmost node, there is no point in evaluating any but the first node at the far right. The first subnode of the far-right 1 node tells us that white can minimize that node to at most 1. Even if white could do better (and reduce that far-right node further), black would not give white that opportunity since black can guarantee a 5 at the top node by selecting the middle node.

[edit] The A* algorithm

The A* algorithm is not related to minimax. It is on this page only because this is the final page of the term.

Last week we spoke about depth-first and breadth-first search. You can think of A* as best-first search. It is a variant of breadth-first search.

As we discussed in class, breadth-first search keeps a queue of nodes to be expanded. Because it is breadth-first, the queue is ordered by the length of the path that one took to get to that node.

With the A* algorithm whenever you reach a new node, compute the following.

1. the "cost" to get to that node. This is often called g(n). In breadth-first search, this would be the length of the path from the starting point to that node. In general, each step may not be equally costly. So the cost to get to a node may not be the same as the number of steps to get there.
2. an estimate of the cost to get from that node to the goal. This is often called h(n). For A* to be useful, one must have some way to estimate that cost. If one doesn't have such an estimate, A* becomes very much like breadth-first.

If one has g(n) and h(n) for each node, then the estimated cost to go from the starting point through that node to the goal is f(n) = g(n) + h(n) Order the nodes for further exploration according to f(n), lowest-valued nodes first. In other words, one keeps a priority queue of nodes ordered by their f(n) values. Whenever a new node is encountered, insert that new node into the queue in the appropriate place according to its f(n) value.

If one takes g(n) to be the length of the path to the current node and h(n) to be some constant C (meaning that we have no way to estimate how costly it will be to get from the current node to the goal), then A* will be exactly breadth-first.