improving iid

[flok]

Hi,

Afaik IID is only doing a limited search and then using the result move for ordening.
Isn't there any other usefulness to get out of it? (apart from tt)
E.g. increase alpha, or beta cut off, or whatever. My tests show that there isn't but it may very well be that my implementations were incorrect.

[PK]

If You use some sort of history move ordering, then there might be an indirect gain from IID (it basically infuses history tables, killer moves etc. with locally relevant data).

As for "increasing alpha, or beta cutoff", you would basically replace result of a deeper search with a shallower one, which does not sound good. There are pruning techniques that do exactly that, called ProbCut/Multi Cut, but they require conditions which will not blend with IID (shifted alpha-beta window or requiring that a couple of moves score well enough at reduced depth).

[hgm]

Conventional IID is oly of limited use as far as move sorting is concerned, however. It does not really help much in the case where a move causes a cutoff at reduced depth, and turns out to be a disaster at full depth. Because the cut move at low depth caused the alternative moves to be completely ignored, you then have to find an alternative at the full depth without any prior information. In anaysis I noticed that a severe drop in the PV score often causes the iteration to take 100, or even 1000 times as long as the previous one, and what happens in the root can happen in internal nodes as well. Even in a PV node, where alternative moves are always searched, the cut moves in the search tree for those moves will not be good enough to push the score below the dropped PV score, and nothing is known about alternative moves.

To make the search more robust, I use an alternative form of IID, which will always search all moves at every depth, as long as no cut move is found:

Code: Select all

Search(depth)
{
  for&#40;iterDepth=1; iterDepth<=depth; iterDepth++) &#123;
    bestScore = -INF;
    for&#40;ALL_MOVES&#41; &#123;
      MakeMove&#40;);
      for&#40;d=iterDepth; d<=depth; d++) &#123; // deepen cut moves without increasing iterDepth
        score = -Search&#40;d-1&#41;;
        if&#40;score < beta&#41; break;
      &#125;
      UnMake&#40;);
      if&#40;score >= beta&#41; return beta;
      // continue searching moves at next-higher depth as they were previously searched
    &#125;
  &#125;
&#125;

If a cut-move flunks out before the full depth of the node is reached, this effectively switches the depth back to the point where this move first became an apparent cut move, to find an alternative cut-move candidate at lowest possible cost.