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.