Confused by MultiPV

[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...

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.

Which 10 do you search with wide window? How do you know one of the best 10 is not ranked last at the root?

If you don't clear hash tables, the scores interact and don't make a lot of sense. The second-best move can return a higher score than the best move, for example, because some scores from the best move get grafted into the tree for the second-best...

And searching with open windows doesn't solve the hashing issue at all. I already search each best move with an "open window" and the hash table causes interaction between the different best moves... That problem remains and can't be eliminated except by clearing things.

[Dann Corbit]

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.

Which 10 do you search with wide window? How do you know one of the best 10 is not ranked last at the root?

If you don't clear hash tables, the scores interact and don't make a lot of sense. The second-best move can return a higher score than the best move, for example, because some scores from the best move get grafted into the tree for the second-best...

And searching with open windows doesn't solve the hashing issue at all. I already search each best move with an "open window" and the hash table causes interaction between the different best moves... That problem remains and can't be eliminated except by clearing things.

What about one pass over the hash table that clears the pv status from each node (so that all nodes look like non-pv nodes)?

[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...

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.

Which 10 do you search with wide window? How do you know one of the best 10 is not ranked last at the root?

If you don't clear hash tables, the scores interact and don't make a lot of sense. The second-best move can return a higher score than the best move, for example, because some scores from the best move get grafted into the tree for the second-best...

And searching with open windows doesn't solve the hashing issue at all. I already search each best move with an "open window" and the hash table causes interaction between the different best moves... That problem remains and can't be eliminated except by clearing things.

What about one pass over the hash table that clears the pv status from each node (so that all nodes look like non-pv nodes)?

The problem is the "score". the scores get grafted from one branch to another. It is not a problem, except that end users used to complain that the scores were non-reproducible. I explained that if you re-search the same position a bunch of times, the hash information bleeds into each PV.

The bottom line is that multi-PV is problematic no matter what you do, because alpha/beta is not intended to produce anything other than the best move... As far as "clearing the status" I have no way of marking a hash entry as PV or non-PV. And even if I could identify PV hash entries (and I am not sure what that would be) those are not the only nodes that influence the scores along any branch.

[hgm]

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...

The alternative I was discussing is actually the algorithm I presented above (let's call it MPVS). Not to search 38 moves with open window. And your numbers confirm that a significant (although not dramatic) savings are possible. It would only take 10 x 75 + 1 x 25 < 10 x 100 by nearly 25%.

Of course the calculation above does assume I know which 10 moves to search. This is why you do ID. You search the best 10 moves of the previous MPVS iteration. If the search is not stable, and the ranking of the last iteration would be completely different than in the previous one, your calculation would also not fly: for each PVS search you do, you would get many fail highs, which would trigger many re-searches with open window. This would lead to an even more disastrous collapse of performance than with MPVS, as you would repeatedly search the same move with open window, only to see it be superseded by the true (quasi-)best move later. With MPVS you would search each move only once with open window.

(Beware: you might not consider MPVS to be alpha-beta, as your concept of te latter is much more restricted than mine.)

[bob]

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...

The alternative I was discussing is actually the algorithm I presented above (let's call it MPVS). Not to search 38 moves with open window. And your numbers confirm that a significant (although not dramatic) savings are possible. It would only take 10 x 75 + 1 x 25 < 10 x 100 by nearly 25%.

Of course the calculation above does assume I know which 10 moves to search. This is why you do ID. You search the best 10 moves of the previous MPVS iteration. If the search is not stable, and the ranking of the last iteration would be completely different than in the previous one, your calculation would also not fly: for each PVS search you do, you would get many fail highs, which would trigger many re-searches with open window. This would lead to an even more disastrous collapse of performance than with MPVS, as you would repeatedly search the same move with open window, only to see it be superseded by the true (quasi-)best move later. With MPVS you would search each move only once with open window.

(Beware: you might not consider MPVS to be alpha-beta, as your concept of te latter is much more restricted than mine.)

If your only goal is to write a multi-PV search, I would do it far differently than a normal search. For example, search the first move to get a lower bound on the best move. Now search the remainder of the moves on a null-window. When one fails high, put it aside as a "good move". You will most likely wind up with less than "n" of these fail high moves. You have now found the best P moves, one you have the score for, the others you do not. So you can do a simple open-window search on those to get their values. Now you are missing N-P moves left to find. You can do that by removing the best P so far, and repeating the process. But no matter what you do, to find N best rather than the best by itself, you are going to do at least N-1 times as much work as normal, which kills performance. Some commercial engines cheat and don't really give the N best... just something pretty close, by merging previous iteration scores with the current best move, which is wrong.

[hgm]

I fully agree that it is more expensive than normal search, and thus will take more time. Calling that a drop of performance is a bt unfair to the engine: it is don a more difficult task, and per PV it delivers, it is likely to need less time (because the PVs can exploit each other's hash entries). So you might as well call it an increase in performance. It is just not possible to sensibly compare two different tasks like they were the same.

If people want multiple PVs, they will have to pay the price. But they most likely want it for a reason, and the price might be well worth it.

If you want to do something really funny, try to make your engine play "veto Chess", which is perfectly normal Chess, except that you have the right on any turn to veto the opponent's move (which you presumably only do when he plays its best move).

[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.

Which 10 do you search with wide window? How do you know one of the best 10 is not ranked last at the root?

You search the 10 that had the highest scores from the previous iteration, of course.

If you don't clear hash tables, the scores interact and don't make a lot of sense. The second-best move can return a higher score than the best move, for example, because some scores from the best move get grafted into the tree for the second-best...

And searching with open windows doesn't solve the hashing issue at all. I already search each best move with an "open window" and the hash table causes interaction between the different best moves... That problem remains and can't be eliminated except by clearing things.

I believe that most ot the hash problems occur when combining shallow searches with deep hash entries. The multiple open window is essentially similar to the single PV search, so I don't see why the hash table would cause more problems.

[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...

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.

Which 10 do you search with wide window? How do you know one of the best 10 is not ranked last at the root?

You search the 10 that had the highest scores from the previous iteration, of course.

What does that have to do with the best 10 for the _current_ iteration? Any move can become best in the current iteration, and some of the best 10 from the previous iteration may well not be in the best 10 for this iteration.

If you don't clear hash tables, the scores interact and don't make a lot of sense. The second-best move can return a higher score than the best move, for example, because some scores from the best move get grafted into the tree for the second-best...

And searching with open windows doesn't solve the hashing issue at all. I already search each best move with an "open window" and the hash table causes interaction between the different best moves... That problem remains and can't be eliminated except by clearing things.

I believe that most ot the hash problems occur when combining shallow searches with deep hash entries. The multiple open window is essentially similar to the single PV search, so I don't see why the hash table would cause more problems.

Here's the original complaint: "Bob, why is it that when I do a multi-pv annotate, the scores you show can't be reproduced with a normal search? Also, why is the score for the nth move sometimes higher than the score for the move given as best?" Crafty would work just fine without the clear operation, but the scores suddenly are not consistent. The best can be lower than #4, etc, because of how hash entries graft information from one search to the next and change the scores...

Note that the scores can not be called "wrong"... just "inconsistent"...

[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...

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.

Which 10 do you search with wide window? How do you know one of the best 10 is not ranked last at the root?

You search the 10 that had the highest scores from the previous iteration, of course.

What does that have to do with the best 10 for the _current_ iteration? Any move can become best in the current iteration, and some of the best 10 from the previous iteration may well not be in the best 10 for this iteration.

If you don't clear hash tables, the scores interact and don't make a lot of sense. The second-best move can return a higher score than the best move, for example, because some scores from the best move get grafted into the tree for the second-best...

And searching with open windows doesn't solve the hashing issue at all. I already search each best move with an "open window" and the hash table causes interaction between the different best moves... That problem remains and can't be eliminated except by clearing things.

I believe that most ot the hash problems occur when combining shallow searches with deep hash entries. The multiple open window is essentially similar to the single PV search, so I don't see why the hash table would cause more problems.

Here's the original complaint: "Bob, why is it that when I do a multi-pv annotate, the scores you show can't be reproduced with a normal search? Also, why is the score for the nth move sometimes higher than the score for the move given as best?" Crafty would work just fine without the clear operation, but the scores suddenly are not consistent. The best can be lower than #4, etc, because of how hash entries graft information from one search to the next and change the scores...

[bob]

I fully agree that it is more expensive than normal search, and thus will take more time. Calling that a drop of performance is a bt unfair to the engine: it is don a more difficult task, and per PV it delivers, it is likely to need less time (because the PVs can exploit each other's hash entries). So you might as well call it an increase in performance. It is just not possible to sensibly compare two different tasks like they were the same.

If people want multiple PVs, they will have to pay the price. But they most likely want it for a reason, and the price might be well worth it.

If you want to do something really funny, try to make your engine play "veto Chess", which is perfectly normal Chess, except that you have the right on any turn to veto the opponent's move (which you presumably only do when he plays its best move).

I don't like the "increase in performance". I have seen users play a real game using multi-PV mode, not knowing they are killing the program, because that lops off plies compared to what the normal search would reach.

best-2 is bad in that every iteration takes 2x as long. Moving the EBF from 2.0 to 4.0. In an exponential problem, that is murder...