Confused by MultiPV

[Michel]

This is probably a naive question but I am wondering what the precise definition of MultiPV is. As far as I can tell there is only one principal variation at any time...

Perhaps someone can enlighten me?

Regards,
Michel

[hgm]

Good question. I think the other 'PVs' are the (unique) PVs that you would have from the positions that would occur after your second, third, etc. best move, concatenated to this move.

I don't know if there are any restrictions w.r.t. transpositions, i.e. if it is allowed that your second PV in multiPV is identical to the first one, after transposing the first two moves.

[Michel]

I think the other 'PVs' are the (unique) PVs that you would have from the positions that would occur after your second, third, etc. best move, concatenated to this move.

That makes sense. But you would have only incomplete information about these secondary PV's since you are searching them with a zero width window (basically proving that they are inferior to the real PV). Is this correct?

[hgm]

This is why multiPV is a separate mode that you have to put the engine in, and you won't automatically have multiple PVs from a normal engine. The engine will have to search all the requested PVs with an open window.

In practice, this can be done by setting the null-window of a PVS search not to the score of the best PV you found so far, but to that of the Nth (if N PVs are requested). With that window you would be proving that the remaining PVs are all worse than the N you've already got. And if you get a fail high, you would have to re-search with increased beta to get the actual score, and if it indeed turns out higher than the score of your previous Nth PV, you drop the latter, sort the newly obtained one in between the others, and now set a null window on the new Nth score, for the remaining moves.

But the first N moves you will always be searching with alpha = -INF (or what you usually take as aspiration value for alpha). In the root you cannot increase alpha after searching just one move, as you normally would. So a multiPV search is a lot more expensive than a normal search.

[bob]

This is probably a naive question but I am wondering what the precise definition of MultiPV is. As far as I can tell there is only one principal variation at any time...

Perhaps someone can enlighten me?

Regards,
Michel

What you have to do is first do a normal search and get the best move / PV. Then you exclude that move from the ply-1 move list, and search again to the same depth to find the second-best move. Then exclude that one as well, and re-search to get the 3rd best move. Repeat this enough to get as many moves as you want. It is horribly inefficient, but there is no other way to do it that is correct.

[Zach Wegner]

What you have to do is first do a normal search and get the best move / PV. Then you exclude that move from the ply-1 move list, and search again to the same depth to find the second-best move. Then exclude that one as well, and re-search to get the 3rd best move. Repeat this enough to get as many moves as you want. It is horribly inefficient, but there is no other way to do it that is correct.

No, there is another way that a couple people have reported having success with (Tony vR-W for one). That is getting an exact score for every root move individually by using an aspiration window on each one. I don't use aspiration windows (or multi PV for that matter), but it makes sense to me.

[bob]

What you have to do is first do a normal search and get the best move / PV. Then you exclude that move from the ply-1 move list, and search again to the same depth to find the second-best move. Then exclude that one as well, and re-search to get the 3rd best move. Repeat this enough to get as many moves as you want. It is horribly inefficient, but there is no other way to do it that is correct.

No, there is another way that a couple people have reported having success with (Tony vR-W for one). That is getting an exact score for every root move individually by using an aspiration window on each one. I don't use aspiration windows (or multi PV for that matter), but it makes sense to me.

That is essentially the same thing, except it is less efficient. With my approach, you only search N moves with a non-null window. With the approach you give, you have to search all moves with a non-null window which is worse.

[hgm]

Your approach does seem to search all the later moves N times with closed window, though, while my method searches them only once (also with closed window).

Of course the closed-window searches are not very expensive in comparison to the first N, but there are a lot of other moves, so it might still add up to something significant.

[bob]

Your approach does seem to search all the later moves N times with closed window, though, while my method searches them only once (also with closed window).

Of course the closed-window searches are not very expensive in comparison to the first N, but there are a lot of other moves, so it might still add up to something significant.

There is a difference. A typical position has 38 legal moves. Suppose you want the "best 10" moves.

To find the best move, you search 1 with full window, 37 with null-window.

To find the second best, you search 1 with full window, 36 with null window.

...

To find the tenth best, you search 1 with full window, 28 with null-window.

Total is 10 with full window, 323 moves searched with null-window.

Now to compare effort. I looked at a few positions from the last CCT event where we used an 8-way box. The first move searched on the final iteration that was completely finished took from 50% to 75% of the total time. With most being closer to 75 (I did not do an exhaustive comparison however so this is just a close guess).

That means that 10 of my searches above will take 10 x 75 computation units, while the remaining moves will take what is effectively 10 x 25. So that the entire process takes about 10x longer. Since you can't know which of the 38 moves are the 10 best, it would seem to me that the only alternative would be to search all 38 with a wide window, which translates into 38 * 75 computation units. 38*75 is > 10*100, so it would appear to me that the best approach was the one I described. Not the easiest to program, but the best from a search space point of view...

[jwes]

Your approach does seem to search all the later moves N times with closed window, though, while my method searches them only once (also with closed window).

Of course the closed-window searches are not very expensive in comparison to the first N, but there are a lot of other moves, so it might still add up to something significant.

There is a difference. A typical position has 38 legal moves. Suppose you want the "best 10" moves.

To find the best move, you search 1 with full window, 37 with null-window.

To find the second best, you search 1 with full window, 36 with null window.

...

To find the tenth best, you search 1 with full window, 28 with null-window.

Total is 10 with full window, 323 moves searched with null-window.

Now to compare effort. I looked at a few positions from the last CCT event where we used an 8-way box. The first move searched on the final iteration that was completely finished took from 50% to 75% of the total time. With most being closer to 75 (I did not do an exhaustive comparison however so this is just a close guess).

That means that 10 of my searches above will take 10 x 75 computation units, while the remaining moves will take what is effectively 10 x 25. So that the entire process takes about 10x longer. Since you can't know which of the 38 moves are the 10 best, it would seem to me that the only alternative would be to search all 38 with a wide window, which translates into 38 * 75 computation units. 38*75 is > 10*100, so it would appear to me that the best approach was the one I described. Not the easiest to program, but the best from a search space point of view...

You could search 10 with wide window and then search the rest with a null window based on the lowest score of the 10 and research on fail high. The big difference is with the hash table. In crafty, you clear the hash table between variations to avoid weirdness. If you search with n open windows, there is no need to clear the hash table.