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?
Principal Variation Search and MultiPV
Moderator: Ras
-
- Posts: 982
- Joined: Fri Mar 10, 2006 4:29 pm
- Location: Germany
- Full name: Jörg Oster
Principal Variation Search and MultiPV
Jörg Oster
-
- 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
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].Joerg Oster wrote: ↑Wed Oct 06, 2021 11:57 pm In my opinion, [1] is unnecessarily complicated and expensive.
What do you think?
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
-
- Posts: 28395
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Principal Variation Search and MultiPV
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).
In PVS you would always set beta = alpha after alpha gets adjusted (and re-search if score > alpha).
-
- 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
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
-
- Posts: 28395
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Principal Variation Search and MultiPV
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".
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".
-
- Posts: 982
- Joined: Fri Mar 10, 2006 4:29 pm
- Location: Germany
- Full name: Jörg Oster
Re: Principal Variation Search and MultiPV
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
-
- Posts: 982
- Joined: Fri Mar 10, 2006 4:29 pm
- Location: Germany
- Full name: Jörg Oster
Re: Principal Variation Search and MultiPV
Yes, and there is also no rule that all lines have to be searched to the same depth.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".

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
-
- Posts: 28395
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Principal Variation Search and MultiPV
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.
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.
-
- Posts: 1784
- Joined: Wed Jul 03, 2019 4:42 pm
- Location: Netherlands
- Full name: Marcel Vanthoor
Re: Principal Variation Search and MultiPV
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.
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.
-
- Posts: 2703
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Principal Variation Search and MultiPV
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
https://www.ct800.net