🚀 go-pugleaf

>>>>> On 22 Jan 93 07:34:07 GMT, lim@toadflax.cs.ucdavis.edu (Lloyd Lim) said:

> In article <C15r40.D1r@sju.edu> tmoody@sju.edu (T. Moody) writes:
>>
>>My real problem is with (b).  Levy and Newborn say
>>something about searching at a given level and storing lots of positions
>>in a hash table before moving to the next level.  Is this the only way
>>to do it?  I don't know a thing about hash tables and, from what I have
>>read it looks like it's over my head.
>>
>>So my question is, can iterative deepening be usefully (if not
>>optimally) accomplished without using hash tables?

> Iterative deepening is commonly used with transposition (hash) tables,
> but it doesn't require them.  Iterative deepening just means increasing
> the search depth by one each time (i.e. - searching to a depth of 1,
> then 2, then 3, ...).  You don't need to use transposition tables.
> They are just used to speed things up, because many of the same nodes
> are encountered again when you search to depth n+1.

One the the more expensive routines in a chess programs is the
move generation function.  The transposition table limits the
number of times that move generation is called to once per position.
I agree that a transpositon table is not necessary to do iterative
deepening, but even shallow chess trees can involve thousands
of positions.

The transposition table is can also speed up the search by giving
a score for a position that my have been generated in a parallel
branch of the tree.

Jon Vander Hill
jon@cas.org