Editor's note: This paper was originally published in the 2000 Game Developer's Conference proceedings

Contents

1. Introduction 3.1 Game Trees and Minimax Search 3.2 Iterative Deepening 4.0 Reimplementing A* 4.3 The History of Heuristic

3.2 Iterative Deepening

One method that most practitioners employ is to search the tree to a fixed depth, k ply from the root node, and use approximate minimax value at that level. However, the nature of the pruning algorithms (such as NegaScout and MTD(f)) yield game trees that can vary widely in size at the same nominal depth. Computer chess has real time limits, and if one exceeds those time limits, the game is lost, so having an algorithm that can generate a rational decision at any time is very important. Thus, a technique called iterative deepening Scott 1969] is used.

The idea is that the algorithm should be limited to exploring a small search depth k by forcing evaluations of nodes once they reach that depth. Once that search is done, the limit k can be moved forward by a step s, and the search can be repeated to a depth of k+s. In chess programs, k and s usually equal 1. Thus, the program does a 1-ply search before doing a 2-ply search, which occurs before the 3-ply search et cetera.

Scott noted that there is no way of predicting how long an ab search will take, since it depends heavily on the move ordering. However, by using iterative deepening, one can estimate how long a (k+1)-ply search will take, based on the length of the preceding k-ply search. Unfortunately, the prediction may be far off the accurate value. In some cases, a real time constraint (such as a time control in a chess game) may necessitate aborting the current search. Without iterative deepening, if a program has not finished a search when the time constraint interrupts the search, the program may play a catastrophic move. With iterative deepening, we can use the best move from the deepest search that was completed.

Other benefits were explored by Slate and Atkin in their Chess 4.5 program [Slate 1977]. They discovered that there were many statistics that could be gathered from a search iteration, including the principal variation. The principal variation of a k-ply search is a good starting place to look for a principal variation of a (k+1)-ply search, so the principal variation from the k-ply search is searched first at depth (k+1). This improves the ordering of the moves in the (k+1)-ply search. Usually, the number of bottom positions explored for all of the searches up to depth d with iterative deepening is significantly smaller than attempting a d-ply search without iterative deepening.

3.3 Transposition Tables

Specific information about a search can be saved in a transposition table [Greenblatt 1967].
In the minimax algorithm given in Listing 1, all of the information about a node can be accumulated including the best score, the best move from that position, the depth it was searched to. All of this information is commonly stored into one transposition table entry. Transposition tables are normally constructed as closed hash tables, with hashing functions that are easy to update (such as a number of XOR operations) as one traverses the tree. The transposition table information can be used in two main ways: duplicate detection and move ordering.

Why would we need to detect duplicates in a game tree? In reality, the game tree is a graph; some of the positions appear in multiple places within the tree. Thus, it makes sense that each position should only be explored once if the information obtained is sufficient to terminate the search. The transposition table assists in finding and eliminating these duplicated positions.

The same position in the game will always hash to the same location in the transposition table. What if the information stored in the table is the same position as the current node, and the stored result of a search of that position is at least as deep as the search we are attempting to execute? If we have an exact minimax value in the hash table for a search that is at least as deep as the one to be executed, we can use the result from the hash table and prune the entire search.

Most of the time, the duplicate detection will fail to completely eliminate the search, and we can exploit the transposition table to improve our move ordering. In the games we are studying, the best move from a previous search depth is likely to be the best move at the current search depth. Thus, we can obtain the previous best move from the transposition table, and search the previous best move before all others. In general, the move ordering benefits of combining iterative deepening and the transposition table are at least as important to the node count as the duplicate detection property, depending on the application chosen.

3.4 The History Heuristic

The transposition table only offers move ordering information about a single move in the move list. The history heuristic [Schaeffer 1989] is a useful technique for sorting all other moves. In the game of chess, a 64 by 64 matrix is used to store statistics. Each time a move from a square startsq to a square endsq is chosen as a best move during the search, a bonus is stored in the matrix at the location [startsq,endsq]. The size of this bonus depends on the depth at which the move was successful at. A bonus that varies exponentially based on the depth of the subtree under that position has been found to work well in practice. Moves with higher history values are more likely to be best moves at other points in the tree; thus, moves are sorted based on their current history values. This makes a dynamic ordering for all possible legal moves in cases where no ordering information exists.

In the programs that the author is aware of, both move ordering techniques are used. The transposition table move is always used first, since it yields specific information about that node from a previous search. Once the transposition table move has been searched, the remaining moves are sorted by the history heuristic.

3.5 Another Method Of Searching A Game Tree - SSS*

Stockman [1979] introduced the SSS* algorithm, a variant to the depth-first search algorithms for determining the minimax value. Initially, it was believed that the algorithm dominated in the sense that SSS* will not search a node if did not search it. A problem with SSS* is that a list structure (the OPEN list) must be maintained, which could grow to b^d/2 elements, where b is the branching factor and d is the depth of the tree to be searched. At the time, this space requirement was considered to be too large for a practical chess-playing program. Even if the space requirement was not a problem, maintaining the OPEN list slowed down the algorithm to make it slower than in practice.

Although versions of SSS* eventually managed to become faster than for game trees [Reinefeld 1994a], it has been recently discovered that SSS* can be implemented as a series of null-window calls, using a transposition table instead of an OPEN list [Plaat 1996]. The research showed that the drawbacks of SSS* are not true. However, it is also important to note that the benefits also disappear: SSS* is not necessarily better than when dynamic move reordering is considered. When all of the typical enhancements are used, SSS* can be outperformed by NegaScout and MTD(f).

In game-tree search, a depth-first search algorithm generates results faster than a best-first search algorithm. A* is also a best-first search algorithm. Is there a better single-agent search algorithm than A*, that uses a depth-first iterative deepening formulation?

________________________________________________________

4.0 Reimplementing A*