Some engines do internal iterative deeping only in the PV. However you
can argue (almost prove mathematically) that there are
parametrizations of internal iterative deeping that make internal
iterative deeping useful on cut nodes.
Using known schemes, I classified nodes as PV, CUT, or ALL by using
their position in the search tree only. I do not consider the
relationship between evaluation and alpha/beta for this
classification.
Then I wrote statistics how many nodes of each type there are and how
many children they have. This shows that the classification scheme
works well. CUT nodes have very few children, ALL nodes have many.
Look at a CUT node. As search depth increases, the costs of searching
a child increase (over all thresholds). However only one move must be
searched for a cutoff. This means that the value of move ordering
increases.
Suppose you do move ordering by searching at some fixed depth d. For
any such depth d there is a depth d' such that for a search at depth
d' or more move ordering at depth d pays of.
In practice it seems that internal iterative deeping on CUT nodes pays
off for d'=d+2. In other words I found iid_reduction==2 a useful value.
Consequently I implemented internal iterative deeping at CUT nodes
(but not at ALL nodes). I saw that Stockfish also has internal
iterative deeping outside the PV, but it seems not to use the node
classification. I have no idea what is better, try it out.
Here is my IID
Code: Select all
// internal iterative deeping
// ------------------------------------------------------------
if (SearchInnerRc::iid_enable
&& node->ret_addr != Label::after_veri_search
&& node->depth>=SearchInnerRc::iid_min_depth
&& node->trans_move==Move::none)
{
child->depth = node->depth - SearchInnerRc::iid_reduction;
child->height = node->height;
child->alpha = node->old_alpha;
child->beta = node->beta;
child->type = node->type;
if (node->type==NodeType::pv)
{
child->ret_addr = Label::after_iid_pv;
node->move = Move::none;
++node;
++child;
goto recurse;
after_iid_pv:
if (child->pv.value() <= node->old_alpha)
{
child->alpha = -ValueNode::infty;
child->ret_addr = Label::after_iid_pv_research;
// node->move still Move::none
++node;
++child;
goto recurse;
}
after_iid_pv_research:
node->trans_move = child->pv.bestmove();
}
else if (node->type==NodeType::cut)
{
child->ret_addr = Label::after_iid_cut;
node->move = Move::none;
++node;
++child;
goto recurse;
after_iid_cut:
if (child->pv.value() > node->old_alpha)
node->trans_move = child->pv.bestmove();
}
}