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(iterDepth = 1; iterDepth <=depth; iterDepth++) {
    alpha = startAlpha;
    PV = "";
    for(ALL_MOVES) {
      MakeMove(move);
      score = -Search(-beta,-alpha, iterDepth-1);
      UnMake();
      if(score > alpha) {
        alpha = score;
        PV = CONCATENATE(move, returnedPV);
        if(ply == 1) { // root code
          PRINT(PV);
          alpha -= multiPvMargin; // <-- re-open window.
        }
        if(score >= beta) {
          alpha = beta;
          break;
        }
      }
    }
  }
  returnedPV = PV;
  return alpha;
}

[CDiddy]

Thanks all for the wealth of ideas.