Why is MultiPV so slow?

[Sesse]

Later moves tend to be worse. Worse, means more fail-lows. More fail-lows means more time spent to resolve them. So it's not unusual to have the later moves being more costly to search and absorbing a disproportionate part of the "nodes budget".

Hm. So a problem is that the engine spends a disproportional amount of time aborting its searches because its goal is to find the Nth best move as quickly as possible, not just score some move? So it would be better if I did the IDP+MultiPV myself, not caring much which order moves are searched in?

[mar]

Multi-PV with N moves should not take more than N times as much time as a single-move search. If it does, it is not properly implemented.

Yes, I always thought the natural way to do multi-pv is to search n PV moves the rest with null window around the worst pv score to see if it beats
the previous ones.
Works well for me at least.

No idea what SF does that their multiPV is so slow.

[Ovyron]

If you want a quick approximation for all moves, and the bad moves not hurting too much the search of the better ones, you need to reduce the searched depth of bad moves, according to eval and/or move number.

Yes, I suggested Decreasing MultiPV.

In practice, though, using that and adjusting yourself to less depth per position (to compensate for lost time in extra moves) doesn't work, because ironically, the positions that benefit from MultiPV are the ones that benefit the most from a deeper search, so just reaching high depth in the second best move (sometimes a higher depth that on the best move, since you'll move the first move to investigate it anyway) is more effective, and you never ask for what's the third move unless the second one overtakes the first one (so the position is complex and exploring the alternatives is worth it; for the majority of positions the best move is clear and any search on the alternatives is wasted.)

So I have abandoned MultiPV entirely, it seems to provide a function for users that don't have time for interaction and just want some move list. The main problem is when in the position you're in, your MultiPV list, to whatever value you set it to, is missing the best move. Then you're wasting all the time examining alternative moves to best, but you don't know it, because the best isn't even on your radar.

[Ferdy]

So, of course I get why MultiPV is much slower than a regular single-PV search; you can't use the cutoffs and have to research suboptimal moves to score them.

But still, the slowdown seems extreme. Right now, I'm searching the same position on Stockfish 11 on very similar hardware (basically two-socket Haswell/Broadwell servers). Single-PV is at depth 52. Multi-PV, with 29 candidate moves, is still working on depth 31!

This depends on the search depth, it is fast at lower depths.

A more controlled test: I took the same position and ran to depth 20 with single-threaded Stockfish twice, once with single-PV and once with multi-PV 100 (which then should become 29 in practice, I suppose), with restarts in-between. Single-PV finished in 1086 ms, multi-PV finished in roughly 58 seconds—so not only do I get zero benefit from sharing analysis between the lines, I actually get _more_ than even the 29x slowdown I would assume as worst case?

I suppose the main benefit of multipv is, you can see the moves in order of score or strength. You want it fast, then decrease the search depth or time.

Another test; I took the same position, added all 29 moves in turn and ran each of those positions at depth 20 (so, overall a deeper search than what I'd expect full multi-PV would do, which would be 19). That completed in roughly 48 seconds, so still faster than automating essentially the same thing with multi-PV. I can't figure out what the story is. Is there something I'm missing? Does multi-PV also make the tree wider deeper in the search, not just at the root?

That is actually an interesting test. Searching each move individually - given that you want all legal moves searched and order them later, you get the same result as in doing multipv all. It would be interesting to try on different positions and depths and see which is faster.

[koedem]

I haven't implemented multi PV in my engine so I might be completely wrong but couldn't one reason why it is so slow be that the TT gets trashed from all the different bounds?
In single PV mode if the eval is somewhat stable all bounds for all positions will be around that eval, either as upper or lower bound.
Now if you search very bad moves all your bounds stored in the TT will be way off.

[Sesse]

Note that I have a different need for MultiPV from what a typical chess player would; I want to communicate to the viewer (on analysis.sesse.net) the score for every possible move. Typical use cases are “why can't he just capture that piece?” and “is this a situation where the player needs to find an only-move, or will nearly whatever work to hold the draw?”. Somewhat lower depth for really bad moves would be acceptable, but it's not a goal in itself.

FWIW, I already expose the hash table so that you still get stuff when querying outside the PVs, but the cutoffs can make the scores hard to interpret.

[Sesse]

For future reference: I tried integrating manual multi-PV in my scripts, and it was markedly slower than just regular multi-PV. I have no idea why it didn't work this time; perhaps it was the different position, perhaps these things pan out very differently with many threads, perhaps the hash size mattered. I don't know. But at least there wasn't a simple win as I'd hoped =)

[EroSennin]

Another test; I took the same position, added all 29 moves in turn and ran each of those positions at depth 20 (so, overall a deeper search than what I'd expect full multi-PV would do, which would be 19).

Why does it stop at 19?

[Ferdy]

For future reference: I tried integrating manual multi-PV in my scripts, and it was markedly slower than just regular multi-PV. I have no idea why it didn't work this time; perhaps it was the different position, perhaps these things pan out very differently with many threads, perhaps the hash size mattered. I don't know. But at least there wasn't a simple win as I'd hoped =)

I run a similar test, mpv (multipv) all vs spv (singlepv) per move. Using mpv is faster after a test of a single position at 4 different search depths.

[d]1r4k1/3n1pp1/1q2pb1p/1pp5/8/1QNP2P1/1P1NPPKP/R7 w - - 3 20
Artemiev-Caruana after 19... Rb8

There are 49 legal moves that were seached, in mpv and spv.



Plot data, time is in sec.

Code: Select all

search_depth = [12, 20, 24, 28]
    mpv_time = [2, 49, 187, 677]
    spv_time = [6, 72, 238, 901]

Analyzing engine:

Code: Select all

Engine: Stockfish 11
Threads: 4
Hash: 256 MB
EGT: None

System:

Code: Select all

CPU: i7-2600K, 3.4 Ghz, 4-cores, 8 threads
RAM: 12 GB
OS: Win10

[Ferdy]

Position where searching moves individually is faster than multipv.

[d]8/1Q3r2/3k4/6p1/6P1/3p1P2/2qb2K1/3R4 w - - 13 55



Plot data:

Code: Select all

search depth = [20, 36, 46]
mpv time = [2, 20, 30]
spv time = [2, 5, 9]