On internal iterative deeping

[Onno Garms]

A note on internal iterative deeping.

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 &#40;child->pv.value&#40;) <= node->old_alpha&#41;
      &#123;
        child->alpha = -ValueNode&#58;&#58;infty;
        child->ret_addr = Label&#58;&#58;after_iid_pv_research;
        // node->move still Move&#58;&#58;none
        ++node;
        ++child;
        goto recurse;
      &#125;
    after_iid_pv_research&#58;
      node->trans_move = child->pv.bestmove&#40;);      
    &#125;
    else if &#40;node->type==NodeType&#58;&#58;cut&#41;
    &#123;
      child->ret_addr = Label&#58;&#58;after_iid_cut;
      node->move = Move&#58;&#58;none;
      ++node;
      ++child;
      goto recurse;
    after_iid_cut&#58;
      if &#40;child->pv.value&#40;) > node->old_alpha&#41;
        node->trans_move = child->pv.bestmove&#40;);
    &#125;
  &#125;

See my posting on bad pruning for some comments on the coding style.

[UncombedCoconut]

A little off-topic: I've never seen this Label:: syntax before. Is this a local struct you defined at the start of the function and populated with the GCC (or ICC) && operator? Or is it an actual language extension (or pseudocode)?

[Dann Corbit]

A little off-topic: I've never seen this Label:: syntax before. Is this a local struct you defined at the start of the function and populated with the GCC (or ICC) && operator? Or is it an actual language extension (or pseudocode)?

It's C++ and those are namespace members.
You are already used to it, if you have used modern C++.
Consider:

std::cout
or:
boost::regoff_t

It probably looks more familiar that way, but it is a good idea to create your own namespaces also, to avoid name collisions.

[UncombedCoconut]

I guess it makes sense if you need them at file scope (where namespaces are allowed) to set the return address members in helper functions. You then need to call the function containing the labels at least once to initialize them. It seems like a lot of trouble and aesthetic cost for using named gotos, if there's no shortcut.

[Dann Corbit]

I guess it makes sense if you need them at file scope (where namespaces are allowed) to set the return address members in helper functions. You then need to call the function containing the labels at least once to initialize them. It seems like a lot of trouble and aesthetic cost for using named gotos, if there's no shortcut.

The named gotos (I see three -- two of which are unused at least in the snippet shown) are another thing.
Those double colon things are just member namespace disambiguation.
If you look at Stockfish code, for instance, you will see the same thing.

Here is what they are good for...
Suppose I am using someone else's big collection of stuff. That collection may use a namespace called BigCollection.
Now, if BigCollection defines a member called TotalOperationCount, it could be a problem if I made a member with the same name and there were no namespaces used. How can I tell between my version of TotalOperationCount and the BigCollection version? By creating a namespace, now the variables live in a completely separate namespace. This is especially important if you use lots of externally developed tools because they may create member objects that have the same name as one you (or someone else) happens to create. But wrapping in a namespace protects these things so that there is no collision.

[Don]

A note on internal iterative deeping.

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,

It's unclear to me what these "known" schemes are, as there is ambiguity about how to define these node types.

The chessprogramming wiki has a section on "rules for predicting node types in a PVS search"

http://chessprogramming.wikispaces.com/Node+Types

However, the rules are not very clean. For example one rule is this:

Code: Select all

The first child of a Cut-Node, and other candidate cutoff moves (nullmove, killers, captures, checks, ...) is an All-Node.

In a perfectly ordered tree I would assume that only the first child would be a cut node.

The next rule is this:

Code: Select all

A Cut-Node becomes an All-Node once the first and all candidate cutoff moves are searched.

Both of these rules of course depend completely on what your definition of a "candidate cutoff move" is.

So I'm clearly interested in how you are defining these node types as well as what others are using.


FYI Komodo distinguishes between these 2 types of nodes and appears to get some benefit from it too, but it's not clear to me if my definition is as accurate as it can be.

Of course I realize that there is no perfect definition in a practical sense and this is why we use the terminology "expected cut nodes" or "expected all node."

One solution is to assume a perfectly ordered tree and then you have a very rigid definition that is not subject to ambiguities, however if it gets classified incorrectly the entire sub tree below it can get out of sync too.

So what is your exact definition? What are others using?

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 &#40;child->pv.value&#40;) <= node->old_alpha&#41;
      &#123;
        child->alpha = -ValueNode&#58;&#58;infty;
        child->ret_addr = Label&#58;&#58;after_iid_pv_research;
        // node->move still Move&#58;&#58;none
        ++node;
        ++child;
        goto recurse;
      &#125;
    after_iid_pv_research&#58;
      node->trans_move = child->pv.bestmove&#40;);      
    &#125;
    else if &#40;node->type==NodeType&#58;&#58;cut&#41;
    &#123;
      child->ret_addr = Label&#58;&#58;after_iid_cut;
      node->move = Move&#58;&#58;none;
      ++node;
      ++child;
      goto recurse;
    after_iid_cut&#58;
      if &#40;child->pv.value&#40;) > node->old_alpha&#41;
        node->trans_move = child->pv.bestmove&#40;);
    &#125;
  &#125;

See my posting on bad pruning for some comments on the coding style.

[Dann Corbit]

Stockfish has two node types: pv nodes and non-pv nodes.
Besides this distinction, there are also boolean tags that are carried to modify the nodes: beta cuttoff and mate threat. The bounds are listed as upper, lower, exact and none.

The routine used to update history tags nodes in the history table that caused a beta cutoff as 'successful' (indicating this with a value that is the square of the depth) and then, if a move is not a capture or a promotion, it tags moves in the history table as 'unsuccessful' if they failed to cause a beta cutoff (indicating 'unsuccessful' by storing the negative of the square of the depth in the history table).

There may be some other node type distinctions in stockfish, but I am not aware of them.

[Don]

Stockfish has two node types: pv nodes and non-pv nodes.
Besides this distinction, there are also boolean tags that are carried to modify the nodes: beta cuttoff and mate threat. The bounds are listed as upper, lower, exact and none.

The routine used to update history tags nodes in the history table that caused a beta cutoff as 'successful' (indicating this with a value that is the square of the depth) and then, if a move is not a capture or a promotion, it tags moves in the history table as 'unsuccessful' if they failed to cause a beta cutoff (indicating 'unsuccessful' by storing the negative of the square of the depth in the history table).

There may be some other node type distinctions in stockfish, but I am not aware of them.

But I'm interested in cut nodes and all nodes and how to define them and stockfish does not have any opinion on this issue. I have a working definition but I am interested in knowing if there is a better way and so I'm soliciting opinions and idea, the more the merrier. I don't have any reason to believe that any particular program is doing it right or wrong either, I just want to compare what I'm doing to what others are doing.

I think I remember from the BB report that Robbo and Rybka may do this differently.

[Dann Corbit]

Stockfish has two node types: pv nodes and non-pv nodes.
Besides this distinction, there are also boolean tags that are carried to modify the nodes: beta cuttoff and mate threat. The bounds are listed as upper, lower, exact and none.

The routine used to update history tags nodes in the history table that caused a beta cutoff as 'successful' (indicating this with a value that is the square of the depth) and then, if a move is not a capture or a promotion, it tags moves in the history table as 'unsuccessful' if they failed to cause a beta cutoff (indicating 'unsuccessful' by storing the negative of the square of the depth in the history table).

There may be some other node type distinctions in stockfish, but I am not aware of them.

But I'm interested in cut nodes and all nodes and how to define them and stockfish does not have any opinion on this issue. I have a working definition but I am interested in knowing if there is a better way and so I'm soliciting opinions and idea, the more the merrier. I don't have any reason to believe that any particular program is doing it right or wrong either, I just want to compare what I'm doing to what others are doing.

I think I remember from the BB report that Robbo and Rybka may do this differently.

If you look at the code for fire:
This page:
http://www.chesslogik.com/index.htm
Click on 'Fire'
This code link:
http://users.telenet.be/chesslogik//dow ... source.rar

You will find an analysis of node types that you are interested in. For instance:

Code: Select all

C:\pgn\winboard-engines\fire>grepcarl cut *.c
  all_node.c (     70):                     if (!((trans->flags &FlagCut) == FlagCut))
  all_node.c (     99):                 v = -OppCut(Position, 1 - value, new_depth);
  all_node.c (    217):             v = -OppCutCheck(Position, 1 - value, depth - 1);
  all_node.c (    239):                     v = -OppCut(Position, 1 - value, new_depth);
  all_node.c (    249):                 v = -OppCut(Position, 1 - value, new_depth);
  all_node.c (    328):                     if (!((trans->flags &FlagCut) == FlagCut))
  all_node.c (    412):                 v = -OppCutCheck(Position, 1 - value, new_depth);
  all_node.c (    431):                     v = -OppCut(Position, 1 - value, new_depth);
  all_node.c (    446):                 v = -OppCut(Position, 1 - value, new_depth);
  cut_node.c (      1): #ifndef cut_node
  cut_node.c (      2): #define cut_node
  cut_node.c (      6): #include "cut_node.c"
  cut_node.c (     12): int MyCut(typePos *Position, int value, int depth)
  cut_node.c (    114):                 v = MyCut(Position, value, new_depth - 2);
  cut_node.c (    133):             v = MyCut (Position, value, new_depth);
  cut_node.c (    193):             b = Split(Position, NextMove, depth, value, value, NodeTypeCut, &r);
  cut_node.c (    314):     HashUpperCUT(Position, depth, v);
  cut_node.c (    318): int MyCutCheck(typePos *Position, int value, int depth)
  cut_node.c (    547):     HashUpperCUT(Position, MAX(1, depth), best_value);
exclude_node.c (    100):                 v = -OppCut(Position, 1 - value, new_depth);
exclude_node.c (    214):             v = -OppCutCheck(Position, 1 - value, depth - 1);
exclude_node.c (    236):                     v = -OppCut(Position, 1 - value, new_depth);
exclude_node.c (    246):                 v = -OppCut(Position, 1 - value, new_depth);
exclude_node.c (    413):                 v = -OppCutCheck(Position, 1 - value, new_depth);
exclude_node.c (    432):                     v = -OppCut(Position, 1 - value, new_depth);
exclude_node.c (    447):                 v = -OppCut(Position, 1 - value, new_depth);
      hash.c (     86): void HashUpperCUT(typePos *Position, int depth, int Value)
      hash.c (     96):         if (!(trans->hash ^ (Position->Dyn->Hash >> 32)) && (!trans->DepthUpper || IsCut(trans))
      hash.c (    102):             trans->flags |= FlagUpper | FlagCut;
      hash.c (    121):     trans->flags = FlagUpper | FlagCut;
      hash.c (    180):             trans->flags &= ~FlagCut;
     input.c (    903):             fprintf(log_file, "option name Split At Cut type check default true\n");
   pv_node.c (    298):                     v = -OppCutCheck(Position, -Alpha, new_depth);
   pv_node.c (    300):                     v = -OppCut(Position, -Alpha, new_depth);
root_analysis.c (    106):                     v = -OppCutCheck(Position, -Alpha, new_depth);
root_analysis.c (    108):                     v = -OppCut(Position, -Alpha, new_depth);
root_multipv.c (    133):                     v = -OppCutCheck(Position, -Alpha, new_depth);
root_multipv.c (    135):                     v = -OppCut(Position, -Alpha, new_depth);
 root_node.c (     97):                     v = -OppCutCheck(Position, -Alpha, new_depth);
 root_node.c (     99):                     v = -OppCut(Position, -Alpha, new_depth);
 root_node.c (    200):                         v = -OppCutCheck(Position, -Alpha, new_depth);
 root_node.c (    202):                         v = -OppCut(Position, -Alpha, new_depth);
       SMP.c (    220): static void SearchCutNode(typePos *Pos)
       SMP.c (    227):     Pos->wtm ? WhiteCutSMP(Pos) : BlackCutSMP(Pos);
       SMP.c (    233):         HashUpperCUT(Pos, sp->depth, sp->value);
       SMP.c (    265):     if (sp->node_type == NodeTypeCut)
       SMP.c (    267):         SearchCutNode(Pos);
SMP_search.c (     81):             v = -OppCutCheck(Position, -alpha, new_depth);
SMP_search.c (     83):             v = -OppCut(Position, -alpha, new_depth);
SMP_search.c (    179):             v = -OppCutCheck(Position, 1 - scout, depth - 1);
SMP_search.c (    193):                 v = -OppCut(Position, 1 - scout, nuovo_abisso);
SMP_search.c (    198):             v = -OppCut(Position, 1 - scout, depth - 2 + extend);
SMP_search.c (    215): void MyCutSMP(typePos *Position)

[Eelco de Groot]

I saw that Stockfish also has internal
iterative deeping outside the PV, but it seems not to use the node
classification.

That is correct, not at this point in the code for Step 9. Internal Iterative Deepening but I'd like to refer to this thread from Larry Kaufman, CUT nodes in Stockfish are mainly classified by the information in the transposition table. As Don is asking about the code in Stockfish also some suggestions from the Rainbow Serpent code are maybe illustrative, well you never know In Rainbow Serpent clone the Iterative Deepening code is changed a bit because having TT moves in CUT nodes are by definition important for the cutoffs, but also important for the singular extensions so both may be considerations when deciding on IID. The changes are from

Code: Select all

    // Step 9. Internal iterative deepening
    if (    depth >= IIDDepth[PvNode]
        &&  ttMove == MOVE_NONE
        && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
    {
        Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);

        ss->skipNullMove = true;
        search<PvNode>&#40;pos, ss, alpha, beta, d, ply&#41;;
        ss->skipNullMove = false;

        ttMove = ss->bestMove;
        tte = TT.retrieve&#40;posKey&#41;;
    &#125;

from Stockfish 2.0.1 to at the moment the following code-fragment that also has less drastic reductions than going to depth/2, just like in Onno. I'm glad to see this apparently should be possible to do without losing elo. In practice you will I think go effectively deeper than depth/2 because there should be enough information in the transposition table from the previous iterations and the difference in extra nodes needed is hopefully not so big.

I introduced some experimental extra conditions to do deeper (d -> depth - 3*ONE_PLY) secondary IID search if there is the possibility to do an exclusion search, but there is not yet a deep enough IID done to meet the requirements for it.

Code: Select all

    // Step 9. Internal iterative deepening
    if (    depth >= IIDDepth[PvNode]
        &&  ttMove == MOVE_NONE
        && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)
		|| (!SpNode && !excludedMove && &#40;ply%2 > 0 || &#40;ss-2&#41;->reduction < DEPTH_ZERO&#41;))) // &#91;Using ply%2 > 0 is unfortunately exactly wrong for sidebranches of the PV. Another danger of the asymmetries but it should not be too hard to fix this. ss->reduction is at the moment negative only if the node was singular extended. EdG&#93;
    &#123;
        Depth d = &#40;PvNode ? depth - 2 * ONE_PLY &#58; depth / 2&#41;;

        ss->skipNullMove = true;
        Value IIDValue = search<PvNode>&#40;pos, ss, alpha, beta, d, ply&#41;;
        ss->skipNullMove = false;

		if (!SpNode
			&& !excludedMove // Recursive singular extension search not allowed
			&& (&#40;ply%2 > 0&#41; || PvNode || &#40;ss-2&#41;->reduction < DEPTH_ZERO&#41;
			&& &#40;d < depth - 3 * ONE_PLY&#41;
			&& &#40;beta - IIDValue < abs&#40;beta/10&#41;))
		&#123;
			ss->skipNullMove = true;
			IIDValue = search<PvNode>&#40;pos, ss, alpha, beta, depth - 3 * ONE_PLY, ply&#41;;
			ss->skipNullMove = false;
		&#125;
		
		ttMove = ss->bestMove;
      tte = TT.retrieve&#40;posKey&#41;;
		ttValue = IIDValue;
    &#125;

Regards, Eelco