Editor's note: This paper was originally published in the 2000 Game Developer's Conference proceedings
Contents |
|
4. Reimplementing A*
The first stage of the plan is to reimplement A* as a depth-first search algorithm. The second stage is to implement the two move ordering techniques that we described in Section 3: transposition tables and the history heuristic.
4.1 IDA*
Korf was the first researcher to emphasize why one would want to use depth-first iterative deepening in any search framework, including heuristic searches such as A*.
The implementation will be described first. In Listing 2, we see some sample code that could be used to implement IDA*. There are similarities between this formulation and Maximize (from Listing 1). This implementation, like Minimax, is simple for a search domain that has discrete steps. For each position p, we check to see if we are at a goal node, or if the search should be cut off immediately. We use the typical condition from A* search, provided that we have an admissible heuristic for estimating the distance to the goal. If the depth (number of steps taken, g in the code and referred to as g(p) in the literature) plus the heuristic estimate to the goal (h or h(p)) is greater than the cut off for this search (fmax), then we stop searching at this node. If we are not at a goal node, nor should the search be pruned, we search all successors recursively. It is important to note that we increase the distance traveled by a step at each ply of the tree.
How does one determine fmax? A second routine usually sets this value, calling IDA* over and over again until a goal node is found. In our sample, ComputeNumberOfMoves() is a sample driver routine for IDA*, and can be seen in Listing 3. When we pass a position into the ComputeNumberOfMoves()function, we expect to get the minimum number of steps required to reach a goal node. The algorithm starts with fmax = h(startposition), and then calls the IDAStar() function, incrementing fmax until the IDAStar() function returns TRUE.
The idea of IDA* is not new, and it should not be new to you either. A previous article in Game Developermentions this in passing as something you may want to consider to improve the speed of your pathfinding.
Now, you are
probably wondering whether IDA* is any worse than A*. After all, A* only
expands each node once during a search, and the nodes near the top of the
tree are expanded many times. A* and IDA* have been shown mathematically
to search c * b^d nodes, where b is the typical number of
alternatives at each node, d is the depth to the closest solution
and c is a constant. The only difference is that the constant
c is a little larger for IDA*.
IDA* is a little slower, but
what do you gain? Well, have you seen any mention of sorting OPEN
positions on a list, or inserting entries into the CLOSED list? When you
use a depth-first iterative deepening approach, you don't have to store
either list. IDA* uses O(d) memory instead of A*, which uses O(b^d)
memory. This makes IDA* a good choice where memory is at a premium. Also
note that because you have very little state information during a search,
IDA* is very easy to save and restore if the AI time slice is
up.
4.2 Transposition Tables
If you are using IDA*, you have lost the CLOSED list. Unlike the OPEN list, the CLOSED list has other functions. The primary function of the CLOSED list in A* is the ability to detect duplicate positions within the tree. If the same node is reached by two separate paths, IDA* will blindly search through the node both times. When the first path to the node is shorter than the second path, we have wasted search effort. We would like a technique that allows us to detect duplicates, and store information about the previously attempted depth at a given node. Thus, we want to apply transposition tables to IDA*.
A transposition table in a computer chess program is implemented as a closed hash table where older and less relevant data can be overwritten with newer and more relevant data. By taking the position p and computing a hash function hash(p), one can store the fact that the node was reached in g steps and searched to a total path of size f unsuccessfully. Whenever a node is first examined in IDA*, we can quickly look in the table and determine whether or not the node has been previously searched. If it has, we can compare the stored number of steps to reach p and the current number of steps taken to reach p. If the current path to reach p is longer than the stored path, we do not search the successors of this node. This information about g for various positions is also stored in between iterations of fmax. Whenever we reach the position by a non-optimal path, one can immediately eliminate the search for all future iterations.
We can also use the transposition table to detect duplicate positions, but we can use it to tell the algorithm which successor had the most promise during a previous iteration for each position. One measure of promise is the successor leading to the smallest h value during the current level of search. The stored move is searched first on subsequent iterations, in the same manner that we search the stored move from the transposition table first in a computer chess program.
For the typical pathfinding algorithm, depending on the structure of your nodes, you may not need a large hash table. One can derive a large portion of the benefit by having a CLOSED list that is only 2-5% of the size of the typical CLOSED list generated by an A* search on the same position.
A key component of the transposition table is the entry replacement scheme. To replace entries, one would overwrite an entry in the hash table if the node in the hash table has a longer path from the start position than the node we want to write in (store the lowest g(p) instances). We want to do this because cutoffs higher up in the tree save more nodes than cutoffs lower down in the tree. Other recent research in the computer chess community has dealt with two-stage replacement schemes for transposition tables. In one experiment, half of the transposition table was reserved for the nodes closest to the root, and the other half of the transposition table was reserved for the most recently visited nodes regardless of depth. This yielded an improvement to search size at a minimal performance cost.
How much does adding a transposition table to IDA* save us? Experiments have shown that a transposition table can reduce the size of standard 15-puzzle searches by nearly 50%, with the cost of storage and access being O(1), in comparison to O(log n) searches on a data structure for a CLOSED list that doesn't lose information.
________________________________________________________