Principal Variation Search and MultiPV

Discussion of chess software programming and technical issues.

Moderator: Ras

Joerg Oster
Posts: 982
Joined: Fri Mar 10, 2006 4:29 pm
Location: Germany
Full name: Jörg Oster

Principal Variation Search and MultiPV

Post by Joerg Oster »

It looks like there are 2 possible ways to implement a MultiPV search with PVS.

[1] Search the first PV line with an open/aspiration window.
Then, search all remaining moves with a zero window.
Repeat for all requested PV lines.
As a consequence, even PV moves, except for the 1st one, will be searched with a zero window first.

[2] Search ALL requested PV lines with an open/aspiration window consecutively, and only after the last one,
search the remaining moves with a zero window.

[1] is how it's implemented in Stockfish and probably other engines, too.
In my opinion, this is unnecessarily complicated and expensive.


What do you think?
Jörg Oster
User avatar
emadsen
Posts: 441
Joined: Thu Apr 26, 2012 1:51 am
Location: Oak Park, IL, USA
Full name: Erik Madsen

Re: Principal Variation Search and MultiPV

Post by emadsen »

Joerg Oster wrote: Wed Oct 06, 2021 11:57 pm In my opinion, [1] is unnecessarily complicated and expensive.
What do you think?
I agree it requires more complex code. Though it may perform better. I don't know, I've never compared the performance of [1] and [2].

I do [3] for its simplicity:

[3] Do a single root search with a wide enough alpha / beta window to get MultiPV=n exact scores. After each iteration (ply), store the best score and MultiPV score (the nth best). Search ply + 1 with an aspiration window of (nth best score - 100) to (best score + 100). If that fails high or low, then search with an infinite window. Note that failing low means the nth best score == alpha, not best score == alpha.

Very simple and works well. Though, as I said earlier, I've never compared the performance of [1], [2], and [3].

Another benefit of [3] is it simplifies the implementation of UCI_LimitStrength. A single root search gives MultiPV=n exact scores. Randomly selecting a move among the best to nth best within a defined alpha / beta window (narrow == strong, wide == weak) simulates patzer play.
Erik Madsen | My C# chess engine: https://www.madchess.net
User avatar
hgm
Posts: 28395
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Principal Variation Search and MultiPV

Post by hgm »

My engines do multi-PV through a centi-Pawn margin, rather than by requesting a specific number of PVs. (I would not be much interested in the second-best move if it loses a Rook compared to the best...) The implementation is totally trivial: instead of setting alpha to bestScore I set it to bestScore - MPVmargin (in the root). If I wanted a specific number N of lines, I would have to keep track of the Nth-best score, and set alpha equal to that after each update.

In PVS you would always set beta = alpha after alpha gets adjusted (and re-search if score > alpha).
User avatar
emadsen
Posts: 441
Joined: Thu Apr 26, 2012 1:51 am
Location: Oak Park, IL, USA
Full name: Erik Madsen

Re: Principal Variation Search and MultiPV

Post by emadsen »

hgm wrote: Thu Oct 07, 2021 5:13 pm My engines do multi-PV through a centi-Pawn margin, rather than by requesting a specific number of PVs.
That's not true for UCI engines, nor for the GUIs I use. While the wording could be clarified, the UCI spec says MultiPV = n means send n PVs. It's based on lines not eval margin. The Hiarcs and Shredder GUIs implement MultiPV as lines.
Erik Madsen | My C# chess engine: https://www.madchess.net
User avatar
hgm
Posts: 28395
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Principal Variation Search and MultiPV

Post by hgm »

Yet another reason to avoid UCI. My engines are of course WB.

BTW, the UCI spec should be interpreted as the maximum number of lines to send. Otherwise it could not be complied with in positions where there is only a single legal move. So GUIs must be able to handle the case where an engine sends fewer lines than they requested. And of course in UCI engines are free to implement any engine-defined option they want. There is no rule that forbids you to have an option "multi-PV margin".
Joerg Oster
Posts: 982
Joined: Fri Mar 10, 2006 4:29 pm
Location: Germany
Full name: Jörg Oster

Re: Principal Variation Search and MultiPV

Post by Joerg Oster »

emadsen wrote: Thu Oct 07, 2021 5:40 pm
hgm wrote: Thu Oct 07, 2021 5:13 pm My engines do multi-PV through a centi-Pawn margin, rather than by requesting a specific number of PVs.
That's not true for UCI engines, nor for the GUIs I use. While the wording could be clarified, the UCI spec says MultiPV = n means send n PVs. It's based on lines not eval margin. The Hiarcs and Shredder GUIs implement MultiPV as lines.
Indeed, users/testers request n pv lines either per GUI or per command line, via setoption name MultiPV value n.

However, playing games in multipv mode is quite a corner case.
I tested the implementation of [2] in Stockfish here https://tests.stockfishchess.org/tests/ ... 036ac7fcdf
Not sure the test result is due to the best move being worse than in the default implementation.
It might also be caused by a time-management issue. But it's probably not worth further investigation.

Thanks for your input.
Jörg Oster
Joerg Oster
Posts: 982
Joined: Fri Mar 10, 2006 4:29 pm
Location: Germany
Full name: Jörg Oster

Re: Principal Variation Search and MultiPV

Post by Joerg Oster »

hgm wrote: Thu Oct 07, 2021 6:30 pm Yet another reason to avoid UCI. My engines are of course WB.

BTW, the UCI spec should be interpreted as the maximum number of lines to send. Otherwise it could not be complied with in positions where there is only a single legal move. So GUIs must be able to handle the case where an engine sends fewer lines than they requested. And of course in UCI engines are free to implement any engine-defined option they want. There is no rule that forbids you to have an option "multi-PV margin".
Yes, and there is also no rule that all lines have to be searched to the same depth. :D
I don't quite understand why that hasn't changed over the years. It's not very reasonable
to search all lines, even very inferior ones, to the same depth.
Jörg Oster
User avatar
hgm
Posts: 28395
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Principal Variation Search and MultiPV

Post by hgm »

I think it hasn't changed because engines can pretty much do as they like. The UCI specs are only intended to specify how they should communicate to the GUI. Not how the engine should work internally. Communicating PVs of unequal depth is sort of standard procedure in multi-PV mode for most engines.

If multi-PV mode is used with "go depth N" it would make sense to search all lines to the specified depth. But with "go infinite" it is up to the engine to decide how fast it deepens each line.
User avatar
mvanthoor
Posts: 1784
Joined: Wed Jul 03, 2019 4:42 pm
Location: Netherlands
Full name: Marcel Vanthoor

Re: Principal Variation Search and MultiPV

Post by mvanthoor »

I've been reading this thread, but to be honest, don't really understand it yet, how you can get multiple PV's by manipulation of the alpha/beta values. In my understanding, a PV is the line with the best moves for each side. In multi-PV, you get the "normal" PV, and then the one with the second best move for the side to move, and then one starting with the third best move, etc...

So I was thinking to implement it as such. Assume I want 3 PV's.
- Do iterative deepening to depth 1; get the PV (of one move).
- Do iterative deepening to depth 1 again, but now exclude the best move from the previous PV.
- Do iterative deepening to dpeht 1 again, but now exclude the two best moves (in the movelist) of the previous runs.

Now you have the three PV's for depth 1, and so...
- Do iterative deepening to depth 2: get the PV.
- Do iterative deepening to depth 2: skip the best move from the previous run.
- Do iterative deepening to depth 3: skip the two best moves (in the movelist) from the previous runs.

And so on.
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL
User avatar
Ras
Posts: 2703
Joined: Tue Aug 30, 2016 8:19 pm
Full name: Rasmus Althoff

Re: Principal Variation Search and MultiPV

Post by Ras »

hgm wrote: Thu Oct 07, 2021 5:13 pmI would not be much interested in the second-best move if it loses a Rook compared to the best...
I would because I like to see how much worse the lines are. Like in, "I have good two moves, but all others will lose the game." And sure, if there are fewer legal moves than requested PV lines, the engine returns fewer. That's how e.g. Stockfish does it.
Rasmus Althoff
https://www.ct800.net