Is there a standard in implementing MultiPV in regular engines?

[Laskos]

Although most engines supporting MultiPV option will show a similar thing in say MultiPV=4 mode, it seems there are very many practical ways to implement it. I naively imagined that to get the best move, one has to search by aspirating window, then, skipping the best move, one finds by aspirating window the second best move and so on. After all of these, one orders them by score in MultiPV output. I also naively imagined that by definition, the quality of 4x more time spent MultiPV=4 chosen move is higher than the quality of 1x MultiPV=1 move. Well, I played 1,000 games matches of engine MultiPV=4 at 40s+0.4s versus MultiPV=1 at engine at 10s+0.1s for regular AB several engines, and the diversity of what I get is both confusing me and shows that they are all showing a bit different notion of MultiPV.

MultiPV=4 at 40s+0.4s versus MultiPV=1 at 10s+0.1s

SF_dev: 0 +/- 15 Elo
Komodo 13.02: -40 +/- 15 Elo
Andscacs 0.95: +70 +/- 15 Elo
Houdini 1.5a: +110 +/- 15 Elo

In case of MCTS MultiPV as used in Leela and Komodo MCTS, it would be simply playing the same engine at 4x time control, or about +250 Elo points or so, but the issue that they show different MultiPV was settled.

With my results, it seems only Andscacs and Houdini behave as I expected, although there are differences even between these two engines. SF_dev shows that the quality of 4x MultiPV=4 move is about equal to simply the best move at 1x time, a bit unexpected. And Komodo 13.02 shows something even weirder, after spending 4 times more time in MultiPV=4 mode, the quality of its best move is below that of 1x time used by regular engine.

All in all, it seems there is no standard way to compute and display MultiPV even for AB engines, never mind when we have AB and MCTS kinds.

[hgm]

For multi-PV you only have to make alpha follow the score of the Nth-best move, instead of that of the best move, in the root. In Fairy-Max I don't do multi-PV by a fixed number, but rather by a score margin. Then it is even simpler; you just set alpha = bestScore - margin in the root, every time you increase bestScore. (Aspiration can be done on top of that; a fail low would be defined by not enough moves ending above the aspirated alpha, or (in the margin case) the best move not being 'margin' better than the aspirated alpha.)

[elcabesa]

Although most engines supporting MultiPV option will show a similar thing in say MultiPV=4 mode......

The way you describe multiPV or the one proposed my h.g.m. are ok to produce multiPV.
That said I don't know how much engines are optimized for playing in multiPV mode, just think at time management that is optimized to choose when stopping the search. I don't think it will work in a the correct way. it's more probable that MultiPV has been tested in infinite time mode and can have bugs when returning bestMove.

[Laskos]

For multi-PV you only have to make alpha follow the score of the Nth-best move, instead of that of the best move, in the root. In Fairy-Max I don't do multi-PV by a fixed number, but rather by a score margin. Then it is even simpler; you just set alpha = bestScore - margin in the root, every time you increase bestScore. (Aspiration can be done on top of that; a fail low would be defined by not enough moves ending above the aspirated alpha, or (in the margin case) the best move not being 'margin' better than the aspirated alpha.)

Yes, this makes sense too. I think both "approaches" would predict that for MultiPV=N, we should have a better best move for N x time MultiPV=N vs 1 x time MultiPV=1. It seems to not be the case with SF and Komodo. I thought that there is a well established way of implementing MultiPV, with N moves searched roughly to the same quality, which is "surely better than 1/N time spent on best move".

[Laskos]

Although most engines supporting MultiPV option will show a similar thing in say MultiPV=4 mode......

The way you describe multiPV or the one proposed my h.g.m. are ok to produce multiPV.
That said I don't know how much engines are optimized for playing in multiPV mode, just think at time management that is optimized to choose when stopping the search. I don't think it will work in a the correct way. it's more probable that MultiPV has been tested in infinite time mode and can have bugs when returning bestMove.

I think I can partly eliminate at least the time control bias, by playing at fixed time. But it won't change much, I guess. About bugs when returning bestMove, I don't know, but how one can check the quality of the move presented other than games?

[hgm]

..., which is "surely better than 1/N time spent on best move".

Why would this be "surely better"? I can imagine that the search of the other moves have trees that virtually have no overlap with that of the best move, and just overwrite the hash table with info that is useless for the next turn.

If the bestmove returned after a multi-PV search is not the first move of the PV with the highest score this should surely count as an engine bug. In principle this can be tested by comparing that bestmove with the PV.

[Laskos]

..., which is "surely better than 1/N time spent on best move".

Why would this be "surely better"? I can imagine that the search of the other moves have trees that virtually have no overlap with that of the best move, and just overwrite the hash table with info that is useless for the next turn.

If the bestmove returned after a multi-PV search is not the first move of the PV with the highest score this should surely count as an engine bug. In principle this can be tested by comparing that bestmove with the PV.

I am not sure I understand that. In the regular search the first move of the PV is reduced and pruned less than the second and higher. In MultiPV=N, N moves are reduced and pruned less. So, N times MultiPV=N should be better than 1 time MultiPV=1 mode, or I am missing something?

[hgm]

You mean all the other moves have to be searched only once, rather than N times? But it is not the same search. Normally they would only have to be proven worse than the PV move, but in multi-PV they would have to be proven worse than the Nth-best move. Which has a lower score, so that this requires a better refutation, which would take more time to find.

[Ovyron]

I hold that if it is known what depth the user wants in advance, that this MultiPV strategy is best:

Say, MultiPV=4 Depth 24:

-Engine searches up to Depth 23 at Single PV
-Engine displays Depth 24's score for main move
-Now Engine switches to MultiPV and resolves 2nd, 3rd and 4th move at Depth 24.

Because it makes no sense to slow down the search before this depth, I think this strategy would outperform all Multi-PV implementations out there (from A/B engines.)

I know this works because back when Rybka had a Randomizer, I'd use it to search for alternative moves automatically (by asking it to play again on same position), and this was faster than MutiPV or Exclude moves, and you could set a window so if you got a repeated move, the rest weren't worth considering.

[Laskos]

Although most engines supporting MultiPV option will show a similar thing in say MultiPV=4 mode......

The way you describe multiPV or the one proposed my h.g.m. are ok to produce multiPV.
That said I don't know how much engines are optimized for playing in multiPV mode, just think at time management that is optimized to choose when stopping the search. I don't think it will work in a the correct way. it's more probable that MultiPV has been tested in infinite time mode and can have bugs when returning bestMove.

I think I can partly eliminate at least the time control bias, by playing at fixed time. But it won't change much, I guess. About bugs when returning bestMove, I don't know, but how one can check the quality of the move presented other than games?

I partly corrected for time control management issues by playing at fixed time per move:

MultiPV=4 at 2s/move versus MultiPV=1 at 0.5s/move

SF_dev, Andscacs 0.95, Houdini 1.5a all came to the same +140 +/- 15 Elo points difference. Komodo 13.02 is the only one coming at -20 +/- 15 difference. It seems Komodo does MultiPV differently (and is weaker as the best move choice goes). Now I understand better in the sense that "Komodo is a bit buggy in MultiPV mode", the first three engines came as I expected from a naive intuition.