Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Internal Iterative Deepening

Author: Robert Hyatt

Date: 10:56:28 08/12/98

Go up one level in this thread


On August 12, 1998 at 10:45:19, Roberto Waldteufel wrote:

>Hi all,
>
>I have heard of the technique of internal iterative deepening, and I wonder if
>anyone can explain the details. I already use iterative deepening at the root
>(doesn't everyone?), and I am assuming that the "internal" refers to the same
>thing at interior nodes of the main search (ie depth > 1). Does anybody know if
>this works well with PVS/Negascout type algorithms, where most of the nodes are
>searched with zero width? And what happens when you get fail high or fail low at
>depths lower than the orriginal depth passed with the node? Do you ignore this
>information and keep deepening, or are there cases when you use this added
>weaker (but cheaper) information to selectively prune the node at the full
>depth? Also, if anyone has done experiments with/without internal iterative
>deepening, what was the order of magnitude of improvement it produced?
>
>Best wishes,
>Roberto


It's an old idea, and you can find source code for it in search.c in crafty,
just look for "internal" or "deepening".

The idea is, if you reach a node where alpha is != beta+1, which means that
this should be a PV type node, and you don't have a hash table move to try,
you are in a critical part of the tree with no real good idea about move
ordering.  So, in such a case, I just recursively call search, with the same
position, but with depth-2.  Say I am at ply=5, with depth=5 (5 plies left
before qsearch takes over) and I notice this is a PV node as above.  and I
notice that I have no hash table move to try.  I simply call search and pass
it the same position, but with depth-2 (or 3 here).  But that recursive call
will have the same problem, ply=5 still, depth=3, a PV node, and no hash move.
So it calls search with depth=1.  This search does a normal 1 ply search (I
stop the internal iterative deepening if depth <= 2) and returns.  The previous
search (with depth=3) now uses this 1-ply search result by taking the move from
the PV, and then uses that as the first move to examine in the 3 ply search.
Once we finish the 3 ply search, we return and the original search now uses this
PV move in lieu of any hash table move and does the normal depth=5 search from
that point forward.

This helps significantly at times, none at all at other times.  The best case
is where an N ply search fails high, but you can't come up with a PV.  When you
start the next iteration, this will "fill in the holes".  I've seen improvements
of 10% in positions where there are fail highs, none in positions where there
are none...





This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.