How to implement MultiPV

[ZirconiumX]

I have been working on a Fruit derivative (Toga is getting old) in my spare spare spare time. I have decided to implement MultiPV - so I ask: How do I implement MultiPV?

Matthew:out

[hgm]

In the root, don't set alpha to the score of the best move, but the score of the Nth-best move, each time you find a new move with a score above alpha. (Or use a threshold in centi-Pawn, and set alpha to bestScore minus that threshold).

That is really all. (Except that you have to output the lines somehow.) In Fairy-Max it was a 3-character change (not counting the interface code for setting the threshold).

[ZirconiumX]

I presume N means the maximum number of lines (?)

So you are saying:

Code: Select all

RootSearch()
{
 stuff...
 MultiPV loop {
  Move loop {
   search_move()
   if (score > alpha)
    alpha = this_loop_best_score;
  }
 }
}

Matthew:out

[bob]

In the root, don't set alpha to the score of the best move, but the score of the Nth-best move, each time you find a new move with a score above alpha. (Or use a threshold in centi-Pawn, and set alpha to bestScore minus that threshold).

That is really all. (Except that you have to output the lines somehow.) In Fairy-Max it was a 3-character change (not counting the interface code for setting the threshold).

Simplest solution would seem to be to search all the moves and get the best one, then remove that from the list, and search again with a normal search, which will now produce the 2nd best move. Repeat for N total searches.

This is what I do to annotate games, when someone asks crafty to "show the best 5 moves" or whatever...

[hgm]

I presume N means the maximum number of lines (?)

Indeed. But what I am saying is:

Code: Select all

RootSearch()
{
 stuff...
  Move loop {
   search_move()
   if (score > alpha)
    alpha = score - margin;
    PrintOrSavePV();
  }
}

[ZirconiumX]

Mr. Muller,

This is UCI we are talking about, where that system is not bulletproof if not of the other moves are >= alpha; leading to the engine having one PV where it needs, say, 4.

Matthew:out

[hgm]

Well, this is why it says PrintOrSavePV. When you don't have enough PVs to print, you save the new one untill you have, and print the complete group then. You can also calculate the margin from what you already have in store. E.g. if N=4 and you already have 4 PVs in store, and the sores are 0, -0.01, -0.03 and -0.05 w.r.t. the best, you obviouslly don't need to set the new alpha to lower than bestScore-0.05.

Note that even in UCI you must be able to print a number of PVs smaller than the requested one, because there is no guarantee that a Chess position has a minimum number of moves. Having only a single legal move is actually quite common.