What is the algorithm for multivariation mode?

[Kirk]

Is it just a matter of saving the moves as they move down the stack with lower evaluations? I notice that the same initial move is disregarded if it moves down the stack if it is only the whole line that changes the eval.

Thanks

[hgm]

In Fairy-Max the only difference between multiPV mode and normal mode is that in the root I set the lower window limit (alpha) to (s - margin) whenever it finds a new move with score s. Normally you would set it to s, and then any subsequent move that is worse would fail low. So you would not have a score for that move (just an upper limit), and no PV (as the move that refuted it would not likely be the best reply). The engine never reports such fail lows, as there is really nothing to report. Only with scores above alpha there is an exact score and a PV to report.

But when alpha was set to (s - margin), all subsequent moves that score less than margin lower than the best so far will score above alpha, and thus not fail low. Which means you also get scores and PVs for those, and then you report those to the GUI.

That is really all. The situation is really very much like when you started with what later turns out to be a non-best move. Then, when you get to the better move, the engine will report a second score and PV, but now a higher one. But it still reports multiple PVs iin that case. By not raising alpha as aggressively, you can also find scores and PVs better than alpha (but worse than the best score).

If you want to set a limit on the number of PVs, say 4, you would set alpha to the 4th-best score. (In Fairy-Max I use a user-adjustable margin in stead of a fixed number, as I am not interested in a 2nd or 3rd move when it loses a Rook compared to the best.)

[Sven]

Is it just a matter of saving the moves as they move down the stack with lower evaluations? I notice that the same initial move is disregarded if it moves down the stack if it is only the whole line that changes the eval.

Thanks

HGM already described his solution, which is correct in my view.

The underlying idea is that normally (i.e., without "multivariation mode" or "MultiPV") the search returns the best move only (and its score) while the only thing you know about all other moves at the root is that they are not better than the best move - but you don't know which of them is second best, which is third and so on. The reason lies in the nature of the alpha-beta algorithm which is used to discard moves as early as possible whenever it is clear that searching them would be wasted. To discard those moves happens by refuting them with any move of the opponent that turns out to be sufficient for that purpose - not necessarily the best refutation but just one that is sufficient. That causes almost random scores for all refuted moves, implying also a random order among them.

The latter also applies for all refuted moves at the root node. Continuing until the "best refutation" is found would be required to know which of the non-optimal moves is second, third etc., and that leads to solutions like the one described by HGM which somehow makes the window wider and causes less refutations to occur.

But that takes longer and is therefore not used for a competition.

Sven

[Rebel]

I never looked at "MultiPV", the manipulations with the windows are clear to me but the question I have is: when implementing this as Winboard (my engine is sort of) will it automatically work with wb2uci as well?