Implementing Multi pv

[bob]

No. You get the score for the BEST move. And if it wasn't ordered first, you will get a score for one or more moves that came before that one. But you can't be sure those are in the "ten best" until you have done the whole search. Pass 1 looks at all moves and finds the best. Pass 2 looks at the remaining 14 and finds the best. Etc. This is usually more efficient than trying to get a real score for EACH root move (by setting alpha back to -infinity after you get a score back). Because with that approach, you will spend a lot of effort and have to search every last root move with an open window to get the N best...

You would only need to search the first N moves (the N best from the previous iteration) with an open window, then verify that the remaining moves are all worse than the current Nth best.

I don't know what would be most efficient, but doing N repeated searches, each further search excluding one more move, does not immediately strike me as the best way to do it.

I tried several approaches to this when I did my "annotate" option years ago. The normal annotate mode simply suggests a different move if it has a better score than what was actually played. But I also added an "n-best" option to show the best N moves as well. The re-searching is not as bad as you would think, thanks to the trans/ref table. And since the "annotate" stuff is generally done in an "offline" manner, my approach was a lot simpler in terms of code.

[hgm]

In Shokidoki I have a code section in Search() that isonly activein the root, to printf the PV. To addmulti-PV I just added a statement there to lower alphe:

Code: Select all

int Search(int startAlpha, int beta, int depth)
{
  static char *returnedPV;
  for&#40;iterDepth = 1; iterDepth <=depth; iterDepth++) &#123;
    alpha = startAlpha;
    PV = "";
    for&#40;ALL_MOVES&#41; &#123;
      MakeMove&#40;move&#41;;
      score = -Search&#40;-beta,-alpha, iterDepth-1&#41;;
      UnMake&#40;);
      if&#40;score > alpha&#41; &#123;
        alpha = score;
        PV = CONCATENATE&#40;move, returnedPV&#41;;
        if&#40;ply == 1&#41; &#123; // root code
          PRINT&#40;PV&#41;;
          alpha -= multiPvMargin; // <-- re-open window.
        &#125;
        if&#40;score >= beta&#41; &#123;
          alpha = beta;
          break;
        &#125;
      &#125;
    &#125;
  &#125;
  returnedPV = PV;
  return alpha;
&#125;

[CDiddy]

Thanks all for the wealth of ideas.