purcell%loki.edsg@HAC2ARPA.HAC.COM (ed purcell) (11/19/88)
Some observations on the request of quintus!ok@unix.sri.com (16 Nov 88)
for references on the term ``iterative deepening'':
In his IJCAI85 paper on the IDA* (Iterative Deepening A*) search
algorithm for state-space problem graphs, Rich Korf of UCLA
acknowledges early chess-playing programs as the first implementations
of the idea of progressively deeper searches. (The history of
progressively deeper look-ahead searches for game trees is somewhat
reminiscent of the history of alpha-beta pruning -- these clever
algorithms were both implemented early but not immediately published
nor analyzed until many years later.)
The closely-related term ``progressive deepening'' also has been around
awhile; for example, this term is used in the 2nd edition (1984) of Pat
Winston's textbook ``An Introduction to AI.''
The contributions of Korf's IJCAI85 paper on IDA* are in the
re-formulation and analysis of progressively deeper depth-first search
for state-space graphs, using a heuristic evaluation function instead
of a fixed depth bound to limit node expansions.
It is interesting that Korf is now investigating the re-formulation of
minimax/alpha-beta pruning for state-space graphs.
Ed Purcell
purcell%loki.edsg@hac2arpa.hac.com
213-607-0793