Path: utzoo!attcan!uunet!convex!killer!osu-cis!tut.cis.ohio-state.edu!bloom-beacon!HAC2ARPA.HAC.COM!purcell%loki.edsg
From: purcell%loki.edsg@HAC2ARPA.HAC.COM (ed purcell)
Newsgroups: comp.ai.digest
Subject: iterative deepening for game trees, state-space graphs
Message-ID: <8811190350.AA00801@loki.edsg>
Date: 19 Nov 88 03:50:27 GMT
Sender: daemon@bloom-beacon.MIT.EDU
Organization: The Internet
Lines: 27
Approved: ailist@ai.ai.mit.edu

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