Decreasing Depth in MultiPV?

[Ovyron]

I'm working with CFish that seems to have this code for the MultiPV loop:

Code: Select all

    for (int pvIdx = 0; pvIdx < pos->multiPV && !Signals.stop; pvIdx++) {
      pos->pvIdx = pvIdx;
      if (pvIdx == pvLast) {
        pvFirst = pvLast;
        for (pvLast++; pvLast < rm->size; pvLast++)
          if (rm->move[pvLast].tbRank != rm->move[pvFirst].tbRank)
            break;
        pos->pvLast = pvLast;
      }

      pos->selDepth = 0;

For example, if one sets MultiPV to 4 and Depth to 24 and one makes it play a move, this will make Stockfish search for a main move to Depth 24, then for a second best move to Depth 24, then a third one to Depth 24, a fourth one to Depth 24, and it'll finally play the move with the best score.

But it does it at every depth (say, in the previous iteration it built a PV for all 4 moves up to Depth 23), what changes would I need to do so that it goes directly to the main move's Depth 24 (without building a PV for the other 3 moves) and only then it builds a PV for the other 3?

If you know what depth you're interested in (24 in this case) I think this would be faster than Stockfish's current behavior (because I don't care about PVs and scores below this depth, Stockfish can save time running in SinglePV to reach Depth 24 faster).

Note that this would be the same behavior as letting it reach Depth 24 and then use searchmoves to exclude the best move 3 times ending with 4 PVs at Depth 24, which would be faster than current behavior because the hash has contents from the main PV that can help build the rest of the lines faster.

----------------

The next question would be (which is the thread's title), what changes would I need to do so that every MultiPV line is built at a lower Depth than the main one? Like, 1st move is searched to Depth 24, the 2nd best at Depth 23, the 3rd best at Depth 22, and the 4th best at Depth 21? With the condition that if a move returns a score equal or better than one ranked before, it is searched to one depth more? (so, if 2nd best at Depth 23 is now as good or better than 1st best then you make it reach Depth 24 and so on.)

The idea is that this would be guaranteed to save time, specially in positions where non-best moves are much worse so with the time saved the user could permit a higher depth that currently is prohibitive due to the slow way Stockfish runs MultiPV.

(Note: depth 24 is just an example, the depth number would come from where the user tells the engine to play a move at some depth)

[Ovyron]

Got it working. Looks like this way you can set it to play at some high MultiPV and force it to play a move once the score of the next PV is poor. I just hope this is useful and not a waste of time.

[hgm]

I don't get it. If you search the moves one by one to full depth, you would not know that the second move is poor before you already have searched it to completion. Or do you want to save time by refraining from searching the 3rd and 4th move in that case.

For that reason I usually control multi-PV not by a number but by a score marging, in my engines. Then it only spends significant time on the acceptable moves at any depth.

[Ovyron]

Multi-PV was designed for analysis. In analysis, you don't know at what depth you'll stop it, that's why it's called Infinite Analysis.

If you know at what point you'll stop the analysis, say, Depth 30, then there's much faster methods to get to know the top N moves than leaving it on MultiPV to Depth 30, mainly, analyze best move to Depth 30, then exclude it from analysis and let the second one to reach Depth 30 (which will do it faster thanks to hash contents from the 1st PV), and then the third one to Depth 30, and so on.

I discovered this before ever using searchmoves to exclude best ones, because one of the Rybka versions had a thing called "Randomizer", where if you asked it to play a move on the board, it'd remember that it had played it, so if you asked for another one, it'd exclude what it had played from analysis, and would play the second best move (it also used a score margin, so if you got the best move again, you knew all the best moves were already shown.)

At the time Rybka had extremely good hash management (later on it was discovered it lost Rybka elo on games, so it was separated to a "Preserve Analysis" option), so what would happen in positions in where, say, 4 moves were within the score margin, is that you'd make Rybka play a move to some depth with Randomizer on, then takeback the move, and make it play again, 3 other times, until it'd play the first move again.

And Rybka would play the other 3 moves instantly! Or really quickly. So this was a much faster method than using MultiPV 4, where the other 3 moves slow down the search of the main move so it can't reach the wanted depth as fast.

The truth is that people that use MultiPV don't really care about the scores of the secondary moves at low depth, only at the final iteration, so it makes no sense to slow down the search with them until the final iteration. But this wanted depth is only known in play mode where the user can specify a depth at which MultiPV should play.

The new idea is that if the secondary moves are really worse than the main move, the user doesn't care about their scores at this depth either, so the user can get top move at Depth 30, second best at Depth 29, third best at Depth 28, and fourth best at Depth 27, and so on.

With the time saved not having to slow down the main move and not having to reach a depth as high for secondary moves, I'd expect that this MultiPV could play at the same level as normal MultiPV in a much faster time, so the user can afford to do the same 1 depth higher (in this case Depth 31.) Or maybe this is unsound and MultiPV needs to reach the wanted depth on all PVs to reach this level, I don't really have time to run both in parallel to compare, but it'll be evident if I notice a drop in quality (like when official Stockfish under-performs compared to some branch.)

[hgm]

If you know at what point you'll stop the analysis, say, Depth 30, then there's much faster methods to get to know the top N moves than leaving it on MultiPV to Depth 30, mainly, analyze best move to Depth 30, then exclude it from analysis and let the second one to reach Depth 30 (which will do it faster thanks to hash contents from the 1st PV), and then the third one to Depth 30, and so on.

I don't understand why that should in general be faster. On the contrary, there is every reason to expect it to be slower. I frequenly encounter situations where during iteration the engine frequently switches between moves, and each switch takes a lot of time, because it suddenly has to search a tree that was abandoned many iterations earlier, and has not been improved since. Deepening such muves simultaneously makes that they can always rely on the info from one ply less still to be there, where they were also both searched.

Also, in every single-PV search with exclusion, the engine has to prove all other moves worse than the one it finally comes up with. If you take the best N moevs from the same iteration it only has to do that one time. If you search them one by one, it would have to do that N times.

[Ovyron]

I don't understand why that should in general be faster.

Because in general the best move in the position will be included in the secondary lines, so the transposition table will have data from when the main PV was built that will help build the secondary lines faster, and those that don't benefit will not be slowed down.

Note that for this you need what I called "good hash management". To know if your engine does, put it to analyze, to say, Depth 20. Stop the search, and restart it. If it has it it'll display the PV line already searched instantly up to Depth 20 and continue from there, as if you never stopped it. Play its move and let it analyze the resulting position to Depth 20. Jump back to the original position and make it analyze to Depth 21. It should reach it instantly with the PV from the next move and the already known eval and continue from there, as if you didn't play any move or analyzed a different position.

If while doing this you see at any point the engine analyzing anything below Depth 19, it has bad hash management (because it's researching what it already knew but forgot).

Back when I helped to implement good hash management for Stockfish (which costs elo so it was dropped later), I put Zappa Mexico II's behavior as an example:

[d]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -

Analysis starts normally

8/17 0:00 +0.10 1.d4 d5 2.Bf4 e6 3.e3 Bb4+ 4.c3 Bd6 5.Bxd6 Qxd6 (69.999) 372
8/20 0:00 +0.10 1.d4 d5 2.Bf4 e6 3.e3 Bb4+ 4.c3 (124.151) 377
9/21 0:00 +0.22 1.d4 Nf6 2.e3 d5 3.Nf3 Ne4 4.Bb5+ c6 (284.209) 395
9/21 0:00 +0.22 1.d4 Nf6 2.e3 d5 3.Nf3 Ne4 4.Bb5+ (318.440) 391
10/23 0:01 +0.08 1.d4 Nf6 2.e3 d5 3.Nf3 e6 4.Bb5+ c6 (521.354) 406
10/31 0:02 +0.08 1.d4 Nf6 2.e3 d5 3.Nf3 e6 4.Bb5+ (1.161.967) 404
11/31 0:04 +0.21 1.d4 Nf6 2.e3 d5 3.Nf3 Ne4 4.Bb5+ c6 (1.872.939) 400
11/31 0:05 +0.21 1.d4 Nf6 2.e3 d5 3.Nf3 Ne4 4.Bb5+ c6 (2.250.098) 402
12/33 0:08 +0.20 1.d4 Nf6 2.Bf4 d5 3.e3 e6 4.Nf3 Bb4+ 5.c3 (3.616.944) 410
12/33 0:12 +0.20 1.d4 Nf6 2.Bf4 d5 3.e3 e6 4.Nf3 Bb4+ 5.c3 (4.991.335) 407

If one stops the analysis, and restarts it, the engine reaches current depth with known score immediately.

12.00 0:00 +0.20 1.d4 Nf6 2.Bf4 d5 3.e3 e6 4.Nf3 Bb4+ 5.c3 Bd6 6.Ne5 (12)

If one forces a move, the engine reaches immediately depth -1, with known score, and continues from there to the next depth.

[d]rnbqkbnr/pppppppp/8/8/3P4/8/PPP1PPPP/RNBQKBNR b KQkq -

11.00 0:00 +0.20 1...Nf6 2.Bf4 d5 3.e3 e6 4.Nf3 Bb4+ 5.c3 Bd6 6.Ne5 (12)
12.00 0:00 +0.19 1...Nf6 2.Bf4 d5 3.e3 e6 4.Nf3 Bb4+ 5.c3 Bd6 6.Ne5 (13)
12/34 0:02 +0.19 1...Nf6 2.Bf4 d5 3.e3 e6 4.Nf3 Bb4+ 5.c3 Bd6 6.Ne5 (1.047.929) 394

If one goes back a move, the engine reaches immediately depth +1 with known score and the same line.

[d]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -

13.00 0:00 +0.19 1.d4 Nf6 2.Bf4 d5 3.e3 e6 4.Nf3 Bb4+ 5.Nbd2 O-O 6.c3 (14)
13/35 0:19 +0.29 1.e4 e5 2.Nf3 Nf6 3.Nc3 Bb4 4.Bc4 d6 5.Ng5 O-O (8.067.399) 423
13/35 0:19 +0.29 1.e4 e5 2.Nf3 Nf6 3.Nc3 Bb4 4.Bc4 d6 5.Ng5 O-O (8.241.862) 422

The engine should not do this dumbly, an improvement would be found if at earlier depth a better move is known, specially when one refutes the variation and backtracks to the root, a move with a score of >refutation would be shown at the earliest depth.

If the engine is unable to do this it'd be unable to benefit from the main PV filling the hash. Unfortunately Zappa Mexico II does not implement excludemoves so to show what I mean I'd need to dig up the old Stockfish PA that doesn't forget and is able to exclude moves, but the end of the project died with Jeremy Bernstein's Stockfish Persistent Hash, and nowadays CFish without learning or good hash management outperforms it, so I don't know how would it perform if good hash management was added back.

[bob]

The issue is simpler.

If you do a normal search to depth=24, you get a score and refute all the other moves. How to get the second best move? Easiest and fastest approach is to edit the ply-1 move list, remove the best move you found, and research starting at ply=1. Why re-search? You have now completely changed the tree, and you need all those early iterations to guide the search / move ordering to find the best move from the remaining set of ply-1 moves. Once you find the second-best move, rinse and repeat until you have the N best moves. If you start at depth=24 to find the second best move, it will take MUCH longer than what everyone is doing here. IE suppose you start the NORMAL search at depth=24. It will kill performance and might kill the program in a real game when it can't even search the first move in the time allotted.

So there is really a good reason to start over for each new best move. It is all about performance. You might THINK it would go faster by just starting at depth=24, but it won't. Slate/Atkin were the first to use iterated search that I know about. We all thought it was silly to search a tree, then re-search it to depth+1, etc. Doing redundant work. But we all tested and realized that the depth D search really helps to order the depth D+1 search. And with alpha/beta, move ordering is by far the most important part of searching. Anything else is a distant second place.

[Ovyron]

If you do a normal search to depth=24, you get a score and refute all the other moves.

For this to work you have to exclude the move right as its PV at Depth 24 is known, you don't let iteration 24 finish but instead jump directly to analyzing the second best move to Depth 24. You only let the iteration finish on the last move you're interested in (in the case of MultiPV=4, just let iteration 24 complete for the fourth move.)

Okay, let me dig up Rybka Randomizer and actually show what I'm talking about.

[d]rnbqkb1r/pp2pppp/2p2n2/3p4/2PP4/5N2/PP2PPPP/RNBQKB1R w KQkq -

Rybka 2.3.2a MutiPV 4

10 0:03 +0.19 4.Nc3 dxc4 5.e3 Be6 6.Be2 Qd6 7.Ne5 (833.924) 223
10 0:03 +0.16 4.g3 dxc4 5.Bg2 Bf5 6.Ne5 Qa5+ 7.Bd2 Qd8 (697.112) 215
10 0:04 +0.06 4.cxd5 cxd5 5.Nc3 Nc6 6.e3 e6 7.Bd3 Bd6 (934.794) 225
10 0:04 +0.03 4.Qb3 dxc4 5.Qxc4 Be6 6.Qb4 Qb6 7.Qxb6 axb6 8.Nc3 (974.724) 224
-----
11 0:07 +0.17 4.g3 dxc4 5.Bg2 Be6 6.O-O Nbd7 7.Qc2 Nb6 (1.684.360) 231
11 0:08 +0.11 4.cxd5 cxd5 5.Nc3 Nc6 6.Bf4 Ne4 7.Qb3 e6 8.Ne5 (1.873.621) 234
11 0:06 +0.06 4.Nc3 dxc4 5.b3 cxb3 6.Qxb3 Qb6 7.Qa4 Bf5 8.Nh4 Bg4 (1.476.287) 239
11 0:08 -0.04 4.Qb3 dxc4 5.Qxc4 Be6 6.Qb4 Qb6 7.Qxb6 axb6 8.Nc3 Na6 (1.939.444) 233
-----
11 0:07 +0.17 4.g3 dxc4 5.Bg2 Be6 6.O-O Nbd7 7.Qc2 Nb6 (1.684.360) 231
11 0:08 +0.11 4.cxd5 cxd5 5.Nc3 Nc6 6.Bf4 Ne4 7.Qb3 e6 8.Ne5 (1.873.621) 234
11 0:06 +0.06 4.Nc3 dxc4 5.b3 cxb3 6.Qxb3 Qb6 7.Qa4 Bf5 8.Nh4 Bg4 (1.476.287) 239
11 0:11 +0.03 4.Qc2 dxc4 5.e3 Na6 6.Qxc4 Qb6 7.Nc3 Be6 8.Qa4 (2.536.345) 233
-----
11 0:07 +0.17 4.g3 dxc4 5.Bg2 Be6 6.O-O Nbd7 7.Qc2 Nb6 (1.684.360) 231
11 0:08 +0.11 4.cxd5 cxd5 5.Nc3 Nc6 6.Bf4 Ne4 7.Qb3 e6 8.Ne5 (1.873.621) 234
11 0:06 +0.06 4.Nc3 dxc4 5.b3 cxb3 6.Qxb3 Qb6 7.Qa4 Bf5 8.Nh4 Bg4 (1.476.287) 239
11 0:11 +0.05 4.Nbd2 g6 5.e3 Bg7 6.Bd3 Na6 7.Qb3 O-O (2.564.661) 233
-----
12 0:20 +0.16 4.Nc3 dxc4 5.e3 b5 6.Be2 Nbd7 7.O-O e6 8.e4 (4.951.453) 246
12 0:14 +0.14 4.g3 g6 5.Bg2 Bg7 6.O-O O-O 7.c5 b6 8.Nc3 (3.370.906) 233
12 0:17 +0.12 4.cxd5 cxd5 5.Nc3 Nc6 6.g3 g6 7.Bg2 Bg7 8.O-O O-O (3.924.278) 235
12 0:21 0.00 4.Nbd2 g6 5.e3 Bg7 6.Bd3 Na6 7.Qb3 Qb6 8.a3 (5.196.348) 247
-----
12 0:20 +0.16 4.Nc3 dxc4 5.e3 b5 6.Be2 Nbd7 7.O-O e6 8.e4 (4.951.453) 246
12 0:14 +0.14 4.g3 g6 5.Bg2 Bg7 6.O-O O-O 7.c5 b6 8.Nc3 (3.370.906) 233
12 0:17 +0.12 4.cxd5 cxd5 5.Nc3 Nc6 6.g3 g6 7.Bg2 Bg7 8.O-O O-O (3.924.278) 235
12 0:29 +0.08 4.Bd2 dxc4 5.e3 b5 6.b3 cxb3 7.axb3 Bf5 8.Be2 Nbd7 9.O-O (6.876.178) 235
-----
13 0:35 +0.17 4.g3 g6 5.Bg2 Bg7 6.O-O O-O 7.c5 b6 8.cxb6 axb6 9.Nc3 (8.257.481) 235
13 0:43 +0.08 4.Bd2 dxc4 5.e3 b5 6.b3 cxb3 7.axb3 Bf5 8.Nc3 Nbd7 9.Nh4 Be6 (10.053.775) 238
13 0:32 +0.06 4.Nc3 dxc4 5.e3 b5 6.Be2 Nbd7 7.O-O e6 8.e4 b4 (7.455.281) 237
13 0:40 +0.06 4.cxd5 cxd5 5.Nc3 Nc6 6.g3 g6 7.Bg2 Bg7 8.O-O O-O 9.Ne5 (9.597.425) 241
-----
14 0:52 +0.14 4.g3 g6 5.Bg2 Bg7 6.O-O O-O 7.c5 b6 8.cxb6 axb6 9.Nc3 Na6 (12.282.860) 239
14 1:20 +0.12 4.cxd5 cxd5 5.Nc3 Nc6 6.g3 g6 7.Bg2 Bg7 8.O-O O-O 9.Ne5 Bf5 (18.965.898) 242
14 1:14 +0.10 4.Nc3 dxc4 5.e3 b5 6.a4 b4 7.Na2 Be6 8.Nxb4 Qd6 9.Bd2 Ne4 (17.271.681) 238
14 1:09 +0.09 4.Bd2 g6 5.Nc3 Bg7 6.e3 O-O 7.Qb3 Qb6 8.Qxb6 axb6 9.cxd5 cxd5 10.Ne5 Rd8 (16.232.958) 238
-----
15 2:05 +0.15 4.Nc3 dxc4 5.e3 b5 6.a4 b4 7.Na2 Be6 8.Nxb4 Qb6 9.Bd2 a5 10.Nc2 (30.354.456) 248
15 2:19 +0.14 4.Bd2 g6 5.Nc3 Bg7 6.e3 O-O 7.Qb3 Qb6 8.Be2 Bf5 9.Nh4 Be6 (33.447.848) 245
15 1:39 +0.12 4.g3 g6 5.Bg2 Bg7 6.O-O O-O 7.c5 b6 8.cxb6 axb6 9.Nc3 Nbd7 10.Bf4 (23.696.866) 243
15 1:53 +0.12 4.cxd5 cxd5 5.Nc3 Nc6 6.e3 g6 7.Bd3 Bg7 8.O-O O-O 9.Qb3 Na5 10.Qb4 (27.627.821) 248
best move: Nb1-c3 time: 2:31.110 min n/s: 249.141 nodes: 36.765.695

15 is the depth wanted and it finishes it in 2:31.110.

*Clears hash*

*Turns on Randomizer*

*Asks for it to play a move up to Depth 15*

11.00 0:01 +0.27 4.e3 g6 5.Nc3 Bg7 6.Bd3 O-O 7.O-O Na6 (443.856) 312
12.01 0:02 +0.18 4.e3 g6 5.Nc3 Bg7 6.Bd3 O-O 7.O-O Na6 8.cxd5 (619.924) 309
13.01 0:03 +0.21 4.e3 g6 5.Nc3 Bg7 6.Bd3 O-O 7.O-O Na6 8.cxd5 Nxd5 9.Nxd5 Qxd5 10.e4 (976.576) 310
14.01 0:04 +0.17 4.e3 g6 5.Nc3 Bg7 6.Bd3 O-O 7.O-O Na6 8.cxd5 Nxd5 9.Nxd5 Qxd5 10.e4 Qd8 (1.450.919) 309
15.01 0:09 +0.25 4.e3 g6 5.Nc3 Bg7 6.Bd3 O-O 7.O-O Na6 8.cxd5 Nxd5 9.e4 Ndc7 10.Be2 (2.890.333) 303
best move: e2-e3 time: 0:10.594 min n/s: 308.370 nodes: 3.171.942

*Takes back e3, asks for another move*

12.01 0:01 +0.18 4.g3 dxc4 5.Bg2 Be6 6.O-O Na6 7.Ng5 Bg4 8.Qa4 h6 9.Nf3 Qd6 (420.095) 269
13.01 0:03 +0.17 4.g3 dxc4 5.Bg2 Be6 6.O-O Na6 7.Ng5 Bg4 8.Qa4 h6 9.Nf3 Qd6 (852.130) 272
14.01 0:04 +0.15 4.g3 dxc4 5.Bg2 Be6 6.O-O Na6 7.Ng5 Bg4 8.Qa4 h6 9.Nf3 Qd6 (1.218.051) 256
15.01 0:12 +0.08 4.g3 dxc4 5.Bg2 Nbd7 6.O-O Nb6 7.a4 a5 8.Nc3 g6 9.b3 cxb3 10.Qxb3 Bg7 (3.627.472) 301
best move: g2-g3 time: 0:13.250 min n/s: 301.168 nodes: 3.892.838

*Takes back g3, asks for another move*

11.00 0:00 +0.09 4.c5 b6 5.cxb6 axb6 6.Nc3 Bf5 7.Nh4 Be6 8.Bf4 Nbd7 9.Qd3 (210.191) 352
12.01 0:01 +0.06 4.c5 b6 5.cxb6 axb6 6.Nc3 Bf5 7.Nh4 Be6 8.Bf4 Nbd7 9.Qd3 (463.725) 303
12.03 0:02 +0.09 4.Nc3 dxc4 5.Ne5 Be6 6.e4 Nbd7 7.Nxc4 b5 8.Ne3 Nb6 (886.410) 326
13.01 0:06 +0.10 4.Nc3 dxc4 5.Ne5 Be6 6.e4 Nbd7 7.Nxc4 b5 8.Ne3 b4 9.d5 (2.010.872) 332
14.01 0:08 +0.10 4.Nc3 dxc4 5.e3 b5 6.a4 b4 7.Na2 Be6 8.Nxb4 Qd6 9.Bd2 Ne4 (2.917.088) 337
15.01 0:14 +0.09 4.Nc3 dxc4 5.e3 b5 6.a4 b4 7.Na2 Be6 8.Nxb4 Qd6 9.Bd2 Nbd7 10.Ng5 (4.893.954) 344
best move: Nb1-c3 time: 0:17.500 min n/s: 347.260 nodes: 5.924.454

*Takes back Nc3, asks for final move and lets iteration end*

11.00 0:01 +0.08 4.Nbd2 g6 5.e3 Bg7 6.Bd3 O-O 7.Qb3 Na6 8.O-O Qb6 (297.099) 218
12.01 0:03 +0.03 4.Nbd2 g6 5.e3 Bg7 6.Bd3 O-O 7.Qb3 Na6 8.O-O Qb6 (855.970) 270
12.02 0:03 +0.11 4.Bd2 dxc4 5.e3 b5 6.a4 Be6 7.Be2 Qb6 8.O-O Nbd7 9.Qc2 (864.864) 267
13.01 0:03 +0.11 4.Bd2 dxc4 5.e3 b5 6.a4 Be6 7.Be2 Qb6 8.O-O Nbd7 9.Qc2 (872.204) 264
14.01 0:07 +0.09 4.Bd2 dxc4 5.e3 b5 6.a4 Be6 7.Be2 Qb6 8.O-O Nbd7 9.Qc2 (1.956.655) 284
15.01 0:13 +0.07 4.Bd2 dxc4 5.e3 Be6 6.Nc3 Qb6 7.Ne5 Nbd7 8.Nxc4 Qc7 9.a4 O-O-O 10.Be2 (3.713.282) 285
15.03 0:30 +0.08 4.cxd5 cxd5 5.Nc3 Nc6 6.e3 g6 7.Bd3 Bg7 8.O-O O-O 9.Qb3 Na5 10.Qb4 (9.300.487) 312
best move: c4xd5 time: 0:30.532 min n/s: 312.406 nodes: 9.300.498

Lines:

15.01 0:09 +0.25 4.e3 g6 5.Nc3 Bg7 6.Bd3 O-O 7.O-O Na6 8.cxd5 Nxd5 9.e4 Ndc7 10.Be2 (2.890.333) 303
15.01 0:12 +0.08 4.g3 dxc4 5.Bg2 Nbd7 6.O-O Nb6 7.a4 a5 8.Nc3 g6 9.b3 cxb3 10.Qxb3 Bg7 (3.627.472) 301
15.01 0:14 +0.09 4.Nc3 dxc4 5.e3 b5 6.a4 b4 7.Na2 Be6 8.Nxb4 Qd6 9.Bd2 Nbd7 10.Ng5 (4.893.954) 344
15.03 0:30 +0.08 4.cxd5 cxd5 5.Nc3 Nc6 6.e3 g6 7.Bd3 Bg7 8.O-O O-O 9.Qb3 Na5 10.Qb4 (9.300.487) 312

Times:
0:10.594
0:13.250
0:17.500
0:30.532

Total time taken: 71.876 seconds

Difference:
MultiPV=4 took 2:31.110
Excluding the best move took 1:11.876 seconds
Suggested strategy saved 1 minute 20 seconds.

Note: My last MultiPV change suggestion was a success and made it into Stockfish 10, though that one didn't depend on good hash management...

[bob]

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

It even looks like you don't get the SAME 4 best moves???

This is not quite the approach I had described...

[mar]

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

EEDIT: more realistic depth 21 results:
mpv1, depth 22 started at 56215ms (0:56)
mpv4, depth 22 started at 106316ms (1:46)

so at depth 20 the mpv-1 search was unlucky because the PV changed; still not so bad I guess