Decreasing Depth in MultiPV?

[Ovyron]

How will that work? After completing the first move (NOT necessarily the best move) if you start on the second best move with a +/- infinity alpha/beta bound, how can the search be efficient?

I didn't make up what I posted, it was actual output from Rybka 2.3.2a, did it look efficient to you?

You did lots of pruning on this move on previous iterations, but now, suddenly, you can't due to the a/b window. So the search should take a LONG time in most positions.

But it doesn't! Believe me, I used Rybka Randomizer for almost two years, because it was better than MultiPV, and I really missed it once Rybka 3 was released, as I was forced to use MultiPV to make Persistent Hash work, and it was clearly less efficient.

Even worse, you do not yet have the BEST move since the depth=24 search can always change its best move as it goes through them...

This is MultiPV in Play Mode at fixed depth, you don't need a BEST MOVE at any point but the very end, where you just play the one with the best score (what to do in tied scores is for debate, MultiPV plays the first one found but Rebel used to play the last scored). This is only problematic in Infinite analysis (where the wanted depth isn't known so this is useless) and timed games (where you have to play a move at a given time.)

I do something entirely different in Cheng, very simple actually and it seems to work well (I bet others do the same as well, the "lazy" approach):

- disable aspiration window if MultiPV > 1
- only do zw search to make sure it beats current worst MultiPV move as soon as I have searched first MultiPV moves (reserarching alpha, infinity if fails high to prove it makes it into k-best)

In the above position (rnbqkb1r/pp2pppp/2p2n2/3p4/2PP4/5N2/PP2PPPP/RNBQKB1R w KQkq -)

My results (1 thread, 4G hash):
depth 20 finished in 41 seconds in multiPV-1 mode
depth 20 finished in 55 seconds in multiPV-4 mode

Perhaps my search/aspiration window is crap, but I still wonder what Rybka does that it's so much slower in mpv-4 mode

Right, if this is all caused by really poor MultiPV from Rybka, a correct one might be as fast as the different strategy. I might need to dig up Stockfish PA and repeat the experiment.

[hgm]

I typically implement multi-PV by adding a few statements in the code that prints a newly found PV (and is thus only executed in the root). Normally alpha-beta would set alpha = bestScore just before this (after a score > alpha was found). The extra statements just lower alpha. As I control multi-PV with a score margin, it just sets alpha = bestScore - margin, making sure the following moves are either proven to fall below the window, or produce an exact score.

If I had wanted to control the multi-PV by the number of PVs, I would have had to insert code here that keeps track of the Nth-largest score (which no doubt would require an array that keeps the N best scores found so far), and sets alpha equal to that. (Or to -INF when no N moves have been searched yet.)

[Dann Corbit]

What a fantastic idea. Thank you for sharing it

[bob]

I typically implement multi-PV by adding a few statements in the code that prints a newly found PV (and is thus only executed in the root). Normally alpha-beta would set alpha = bestScore just before this (after a score > alpha was found). The extra statements just lower alpha. As I control multi-PV with a score margin, it just sets alpha = bestScore - margin, making sure the following moves are either proven to fall below the window, or produce an exact score.

If I had wanted to control the multi-PV by the number of PVs, I would have had to insert code here that keeps track of the Nth-largest score (which no doubt would require an array that keeps the N best scores found so far), and sets alpha equal to that. (Or to -INF when no N moves have been searched yet.)

Does this not kill the search efficiency? IE if you search each root move with an open window, that would seem to be much worse than searching all to get #1 best, then removing that and searching all to get #2 best. By starting the search over, you get much better move ordering on the second best search, etc. I don't do an N-best in the normal search, but I do do this in the "annotate" code where it plays through a game and makes comments about moves that are worse than the best by some user-specified margin. And you can also say "for such (or all) positions, give the best N moves with scores and PVs." When I did this, I initially tried to search to final depth, then for each root move, reset alpha and beta back to their original values. This would really wreck the search time since the 2nd best had to be searched as if nothing has happened so far, rather than using the previous result from a search that failed low but did store some move ordering help.

In any case, I'm not planning on doing a true multi-PV search anytime soon since the annotate command can be used for the same thing. And since multi-PV slows things down so badly, annotating a PGN game seems more usable, since it can be done without human intervention.

[Ovyron]

I think I need to explain to bob the idea step by step...

Current behavior:

1-User sets MultiPV to 4 and Depth to 4. Forces the engine to play a move.

2-Engine gets best move to Depth 1.
3-Engine gets second best move to Depth 1.
4-Engine gets third best move to Depth 1.
5-Engine gets fourth best move to Depth 1.

6-Engine gets best move to Depth 2.
7-Engine gets second best move to Depth 2.
8-Engine gets third best move to Depth 2.
9-Engine gets fourth best move to Depth 2.

10-Engine gets best move to Depth 3.
11-Engine gets second best move to Depth 3.
12-Engine gets third best move to Depth 3.
13-Engine gets fourth best move to Depth 3.

14-Engine gets best move to Depth 4.
15-Engine gets second best move to Depth 4.
16-Engine gets third best move to Depth 4.
17-Engine gets fourth best move to Depth 4.

In the process of doing that, the move ordering changes as moves score better than ones ranked before them, and fifth best moves might join in and replace the fourth one that drops.

Improved Strategy:

1-User sets MultiPV to 4 and Depth to 4. Forces the engine to play a move.

2-Best move is shown at Depth 4 (goes from Depth 1 to 4) - as soon as its score is known instead of looking at alternative moves at this depth you jump to 3.
3-Second best is shown at Depth 4 (goes from Depth 1 to 4 faster thanks to the transposition table being now full of useful content) - as soon as its score is known instead of looking at alternative moves at this depth you jump to 4.
4-Third best is shown at Depth 4 (goes from Depth 1 to 4 faster thanks to the transposition table being now full of useful content) - as soon as its score is known instead of looking at alternative moves at this depth you jump to 5.
5-Fourth best is shown at Depth 4 (goes from Depth 1 to 4 faster thanks to the transposition table being now full of useful content) - this time you let Depth 4 finish to see if a move can refute any of the four best.

What often happens is that at the last moment the engine will switch from move A to move B in the last iteration, however it'll have move A in hash so it'll reach high depth for Move A and get the second best instantly. If the top 3 moves transpose it'll get the best move and the other 2 will appear instantly, etc.

So that's how Rybka Randomizer is able to show 4 best moves in half the time of MultiPV.

Decreasing Depth (what this thread is about):

1-User sets MultiPV to 4 and Decreasing Depth to 6. Forces the engine to play a move.

2-Best move is shown at Depth 6 (goes from Depth 1 to 6) - as soon as its score is known instead of looking at alternative moves at this depth you jump to 3.
3-Second best is shown at Depth 5 (goes from Depth 1 to 5 faster thanks to the transposition table being now full of useful content) unless it has a score equal or better than Best (if it does we let it reach Depth 6) - as soon as its score is known instead of looking at alternative moves at this depth you jump to 4.
4-Third best is shown at Depth 4 (goes from Depth 1 to 4 faster thanks to the transposition table being now full of useful content.) If the score is better than Best we let it reach Depth 6. If the score is better than Second Best we let it reach Depth 5, if at Depth 5 the score is better than Best we let it reach Depth 6 - as soon as its score is known instead of looking at alternative moves at this depth you jump to 5.
5-Fourth best is shown at Depth 3 (goes from Depth 1 to 3 faster thanks to the transposition table being now full of useful content) If the score is better than Best we let it reach Depth 6. If the score is better than Second Best we let it reach Depth 5, if at Depth 5 the score is better than Best we let it reach Depth 6. If the score is better than Third best we let it reach Depth 4, if at Depth 4 the score is better than Second Best we let it reach Depth 5, if at Depth 5 the score is better than Best we let it reach Depth 6 - this time you let this last Depth finish to see if a move can refute any of the four best.

That's it. Now try this with MultiPV=8 and Depth 28. Current behavior is prohibitive because it's way too slow, improved Strategy will not help much by the 5th move that is so bad it'll not be speed up by the contents in the hash, but Decreasing Depth will be so quick to give you the moves ranked and the scores of those depths so quick that you can afford to try Depth 29 or Depth 30 instead, which will give a much better analysis in the same time.

(in other words, MultiPV performs so poorly because it spends too much time analyzing poor moves)