MultiPV implementation

[dav1312]

Following the conversation that happened on Discord about MultiPV I decided to open a formal discussion here on GitHub.
There are currently 3 ways to implement MultiPV:

1. Equal amount of resources for all moves (current)
   • Useful if you really want to analyze all moves equally, but it drastically reduces the quality of the evaluation by wasting valuable resources on bad moves.
2. Return the value for each root move (Fake/free MultiPV)
   • This doesn't cost nearly as many resources as the other two methods. It doesn't change the behavior of the engine compared to using just 1 line, and it can provide some insight into what the engine is "thinking" about the moves when performing a regular search. I suspect this is how many (non-power) users already assume that MultiPV works. Not changing the engine's behavior can be a problem if the user actually wants to force the engine to search for other moves.
3. Adjust amount of resources for each line ([RFC] Adjust rootDepth on MultiPV lines. #2152)
   • This is a middle ground between the other two implementations. Adjusting the resources based on various factors such as line number, evaluation, or winning chances compensates for the issue of wasting resources. There are a lot of users who use the engine in the browser in popular websites that I'm sure are unaware of the strength penalty that comes with using a lot of lines or, if they are aware, don't reduce them because they want to see more options than just the best move. This method ensures that the user doesn't need to change anything, the engine decides for them how to spend the resources.

[vdbergh]

2. is bad I think. Evals outside the window are totally unreliable.

[jhellis3]

I've been testing a few things locally. What I came up with was -2 depth at root for pvIdx > 0 and allowing TT on PvNodes when pvIdx > 0 and it is our move with a lower bound.

The combination of these two things means that we are able to use the previous iteration's main line results to very efficiently skip work on trivial transpositions. These transpositions currently waste a great deal of resources because they are going to have the same score as the main line, and are first in line for multiPV while contributing nothing useful. Taking the TT cutoff for our own moves with a lower bound is safe because it is either a fail high, which if large enough will promote to mainline and be resolved as ususal, or it has BOUND_EXACT which means it was searched as a PvNode at a greater depth than our current search.

At the same time, it preserves the spirit of multiPV in that all of our opponents moves are disallowed from taking nonPV cutoffs/reductions.

I think this was worth ~48 Elo at an STC of 18+0.18, MPV=4 for both. I can push a branch and test on fishtest if this is something people are interested in...

[jhellis3]

Here is the patch: jhellis3@2236edb

[mstembera]

In SMP different threads often find different moves. get_best_thread() is the function that then picks one of them. We could output all of them in MultiPV w/o spending any additional resources. As a bonus this happens most often in positions where multiple moves are close which is when most people care about MultiPV.

[bftjoe]

Another idea:

If number of threads >= multipv, have each thread search different moves at root. could partly use existing searchmoves infrastructure to handle this, with possible optimization for searchmoves of only 1 move. Leftover threads could just search best move or be equally distributed between all multipv moves.

[dubslow]

Seems that part of the problem is that we're not sure what users want, which is a key piece of data to make a good choice. I can think of at least two broadly different user bases, the casuals who use browsers (e.g. lichess or chesscom), and the "power" users of correspondence. Soliciting from feedback from at least the latter if not the former would be useful.

It would also be good to perhaps explore the options in more detail. The "overkill" way would be to implement all the choices, make it selectable via UCI and thence solicit feedback from power users or browser users. However, maintainers have a history of disdaining option overload, so mayhaps this would need to be a branch outside (but tracking) master.

That said, for browser users at least, using a fake/free/pseudo mode is likely to be a clear improvement.

Also, if I interpret jhellis3 correctly (not sure I do), that sounds like a straight, direct improvement to the current "equal time" strategy, and so quite separately from the question of what other modes are good, improving the current mode is certainly worth a fishtest.

[jhellis3]

Fishtest result for aforementioned patch can be found here: https://tests.stockfishchess.org/tests/view/663e5d163a2f9702074bc16a

[PGG106]

Just as i said on Discord, i'm not sure STC gains from an option that should be turned off in regular game playing anyway make for a good argument for any type of tweak.
MultiPV is an "analysis" tool that comes with a clear and understood impact on strength (given the same amount of time per search at least), users should be aware of this and if they aren't it's not really an issue with the feature itself.
Any form of "multiPV reduction" will bridge the gap in strength, sure, but how do we measure if the tweak doesn't defeat the point of multipv?
You can reduce the depth of the secondary lines all the way down to 0 and gain Elo, and so what? How do we establish that -2 is ok but -20 isn't? how are we sure that "-2" in itself is acceptable when there's no clear way to measure "analysis" performance, with analysis being the only realistic usecase for multipv?
tldr: If an end user doesn't want to lose Elo to multipv they should just turn it off, Elo gains tweaks are meaningless for a feature that shouldn't actively care about Elo at all.

[bftjoe]

I disagree that it is a clear and understood impact when chess.com defaults to multipv 3 for analysis. I highly doubt that most people using this tool know what impact this has on analysis strength.

[PGG106]

That points to a need to better educate the end user, "acting behind Their back" by changing the default behaviour of multipv (to in practice do less multipv) is a non solution imo, I just don't think the default behaviour of a function like multipv should try to go out of their way to account for misuage by ignorant end users

[Craftyawesome]

Default is comparatively unimportant compared to what and how to add an alternative IMO, but worth discussing at least.
Whether the default is traditional multipv or not, whatever the option is named could help quite a bit. Something like "Fast MultiPV" or "Smart MultiPV" would both hint power users that something could have changed and hint novices that something about multipv is worth an option.
Also not sure I would call it "less multipv". AFAIK searching every line to equal depth isn't inherent to the definition of multipv, just that equal depth is how it is traditionally and usually done.

[Craftyawesome]

You could also argue for a variant of 1 with something like a node limit, since sometimes other moves take more nodes to resolve the same depth. I suspect this is actually a decent portion of multipv elo loss.

IMO 2 would be nice to have if you can keep it as decent as leela's output. It also makes the most sense, since it considers the secondary moves the right amount for maximum elo and naturally looks at bad moves less. But I haven't seen this done well in an AB, and there are concerns like out of window searches mentioned above.

3 could be trying to simulate 2 if 2 can't work directly (maybe search at the adjusted depth but with new window? Would be some level of elo loss though)

Personally I don't see much of an appeal between "minimal elo loss with usable mpv" and "full search", but if someone does want it you may want to use some UCI option to control the balance between it.

[bftjoe]

One thing to consider is that stockfish/uci support setting a maximum thinking time/nodes/depth/etc but not a minimum. Support for a minimum would be interesting/useful.

[joergoster]

Maybe this is of some interest: https://github.com/joergoster/Stockfish/releases/tag/mpv1
The corresponding branch https://github.com/joergoster/Stockfish/tree/simpleMultiPV