About implementing MultiPV

[Kempelen]

1. how did you find the first 3 "best moves"? Not with a normal alpha.

Define "normal alpha". This obviously depends on if you are doing PVS or alpha-beta, if you do asipration or not.

For me, "normal" would be -INFINITY when you don't do aspiration, and score_of_previous_iteration - lowerMargin when you do. Of course you would use the score of the 3rd move in the multi-PV case.

2. Once you find the first "best 3" you absolutely set alpha "artificially low". Why? Because you are setting it _lower_ than the actual score for the third-best move, once you actually find the real 3rd best move.

Why on Earth would I do that? Once I actually find the real 3rd best move, alpha is of course set to the score of that. Why would you set it lower? Both in alpha-beta and PVS one usully increases alpha, when one finds a move with a better score.

Let me make it simpler.

There are 4 moves, A, B, C and D. A, B and D are the real best 4.

Once you have searched A, B and C, C is the 3rd best so far, and you are searching with its score as alpha. But D is the _real_ 3rd best move and has a higher score. So while searching all moves
after C, you are using C's score as alpha, and it is lower than the real 3rd best move's score.

So again, how is this supposedly superior to what I am currently doing?

Maybe I am confused also, but I agree with H.G.
why? As I understand the proposed system work like a normal root move search: first we try 1st move and its score it sets as new alpha, then we search the 2nd move and if is score is better than new alpha, we set that move as new best and its score as new alpha, then try again with 3nd and so on. The only difference with multiPV is that 3 first moves are -Infinite as alpha and after third is like a normal search as I have described. In both cases we are searching for "best moves than a previous one"

[hgm]

There is a simpler (and more efficent) approach.

Generate the ply-1 move list and search it normally, using aspiration and anything else you normally use. This produces the best move. Now remove that best move from the ply-1 move list and search again using normal aspiration and everything. This gives you the second-best move. Repeat until you have as many moves as you want. This avoids a full-search on every root move.

You are asking how this is inefficient. Isn't that obvious? You repeatedly search the later moves again and again, with ever lower null window. First at the score of the best move, then with the score of the second best, then with the score of the third best.

And if your ordering was not perfect, and the frst move you search at every stage (possiby after exclusion of some moves) was not the best remaining move, you get _exactly_ the effect you describe as a disadvantage of what I do: PVS wil put the null window for the remaining moves at the score of the first move you search, and not at the score of the best move yet to come. So in that iteration you will search a number of moves with an "artificially low" null window, until you stumble on the true best remaining move, which fails high on that window, and will have to be researched. That is not any different from what I have to do.

Basically, what you describe is speculatively searching all remaining moves with an artificially high alpha in the hope that the first move in line to search will not be the best remaining move, and some later move will fail high against that window. If that is a gamble that pays off, then why don't you do it in a single-PV search as well? If in iteration n-1 the score of the best move is S, set an aspiration window {S+margin, S+margin+1} above the expected score for iteration n, to cheaply detect which of the later moves is going to fail high, and thus avoid having to search move 2, 3, ... of your list with alpha at the "artificially low score" of the PV move in the new iteration?

[bob]

1. how did you find the first 3 "best moves"? Not with a normal alpha.

Define "normal alpha". This obviously depends on if you are doing PVS or alpha-beta, if you do asipration or not.

For me, "normal" would be -INFINITY when you don't do aspiration, and score_of_previous_iteration - lowerMargin when you do. Of course you would use the score of the 3rd move in the multi-PV case.

2. Once you find the first "best 3" you absolutely set alpha "artificially low". Why? Because you are setting it _lower_ than the actual score for the third-best move, once you actually find the real 3rd best move.

Why on Earth would I do that? Once I actually find the real 3rd best move, alpha is of course set to the score of that. Why would you set it lower? Both in alpha-beta and PVS one usully increases alpha, when one finds a move with a better score.

Let me make it simpler.

There are 4 moves, A, B, C and D. A, B and D are the real best 4.

Once you have searched A, B and C, C is the 3rd best so far, and you are searching with its score as alpha. But D is the _real_ 3rd best move and has a higher score. So while searching all moves
after C, you are using C's score as alpha, and it is lower than the real 3rd best move's score.

So again, how is this supposedly superior to what I am currently doing?

Maybe I am confused also, but I agree with H.G.
why? As I understand the proposed system work like a normal root move search: first we try 1st move and its score it sets as new alpha, then we search the 2nd move and if is score is better than new alpha, we set that move as new best and its score as new alpha, then try again with 3nd and so on. The only difference with multiPV is that 3 first moves are -Infinite as alpha and after third is like a normal search as I have described. In both cases we are searching for "best moves than a previous one"

That's not what is happening. Let me run thru both choices for clarity.

In Crafty, at depth N I search normally. The first move will initially be the best move, and about 85% of the time it remains best. All the rest of the moves are searched with a null-window fail-soft search (fail soft means that I store HT entries with scores outside the alpha/beta bound, whatever gets backed up). I save it, remove it from the move list, and re-start the search with normal aspiration. Now, since the first move is missing, we find another "best move" which is initially the first move left in the list. And often this is really the second best move due to the move ordering by node count at the root. Most of the remaining moves (assuming this one is best) get dismissed instantly with hash hits or shallow searches. I repeat for the 3rd, and 4th etc.

The alternative is to do a normal search, but once you get a score for the best move, you artificially lower alpha enough to pick up the 2nd best (and other) moves. If you don't lower it enough, everythying fails low and you get nothing and have to do it again. If you lower it too far, other moves will fail high and have to be evaluated, just because their score is > alpha. Any search where alpha != beta-1 is very expensive to do. Once you get 3 best moves, you can set alpha to the smallest of the 3 scores, so that only moves that are better will fail high.

The issue is searching the 2nd, 3rd moves in the list with the offset alpha value just to get 3 "best moves". And then expending significant effort to prove that they are the best.

I see no way this is more efficient than what I am doing at present. The interesting case is not the one where the first 3 root moves really are best, but the case where the best N moves are scattered throughout the move list,

My preference for the way I do things in Crafty is simplicity.

Some sample data:

Code: Select all

               19->  52.81  -0.17   18. ... Bc7 19. Rac1 f5 20. Nd2 Kh8
                                    21. Kh1 Rac8 22. e4 Nf6 23. exf5 Qd7
                                    24. Nc4 Qxf5 25. Qe2 e4 26. dxe4 Qxe4+
                                    27. Qxe4 Nxe4 28. Bd4
               20     1:25  -0.15   18. ... Bc7 19. Rac1 f5 20. Nd2 Kh8
                                    21. Kh1 Rac8 22. e4 Nf6 23. exf5 Qd7
                                    24. Nc4 Qxf5 25. Qe2 Rfe8 26. Rfe1
                                    Rcd8 27. Nxe5 Bxe5 28. Bxe5 Rxd3
               20->   1:29  -0.15   18. ... Bc7 19. Rac1 f5 20. Nd2 Kh8
                                    21. Kh1 Rac8 22. e4 Nf6 23. exf5 Qd7
                                    24. Nc4 Qxf5 25. Qe2 Rfe8 26. Rfe1
                                    Rcd8 27. Nxe5 Bxe5 28. Bxe5 Rxd3

If you notice, the first (best) move takes about 35 seconds to complete, the remainder of the moves take 4 seconds. If we remove this move from the list, we repeat this process again with roughly the same time required. There are some efficiency issues related to choosing one of these algorithms:

(1) once you find the best move, remove it from the list, and start back over at depth 1 and find the best move and build up good move ordering information to help the search;

(2) at the final ply, lower alpha to force other best moves to pop to the top of the list, without good move ordering information which makes the search less efficient. Very similar to the idea of just starting at depth N rather than using an iterated search.

This appears to be the primary reason I was seeing better performance with the current way I do things, assuming you believe that an iterated search approach is better.

In this same light, many use the idea that when a move fails low at the root, you should completely re-start the search at depth 1 to find a new best move using something better than just starting a blind/deep search. Since the fail low hash entry should stick around, the old best move will fail low on each iteration and not become the best move again.

Complex topic, lots to test. I've been experimenting with the fail-low-at-root -> restart idea as well. It has some advantages...

[jwes]

OK, one more time.

You search at depth N and find that the three best moves are A=+100, B=+50 and C=0. All other moves are < 0 and fail low.

Now you start the search at depth N and find A=100, B=30, C=0, D=150. So after a full search at N+1 you now have D, A, B as the three best moves. But unfortunately, after move D there is a move E with a score of +120. How will you ever pick that one up since it will fail low on the +150 alpha value from D? Your list ends up incomplete, and wrong...

You can't take unsafe shortcuts unless you are willing to accept the error that can produce...

You obviously set the value for the zero-window search to the lowest of the pv values, in this case 30, since this gives the answer you want, which is whether any of the remaining moves are better than any of the pv moves you have found.

A math question.

Which is preferable:

(1) searching all root moves with a normal search, to pick up the best. Then re-searching the remaining root-moves with a normal search to pick up the second-best, etc... or

(2) Searching all moves with an artificially lowered alpha value?

The answer might be surprising...

In any iteration, the first move takes the majority of the time, and the rest rip by quickly. If you lower alpha by any amount, artificially, the rest of the moves no longer "fly by".

It is clear that you would find the answer suprising. I have tried it and searching n open windows in 1 search is significantly faster than doing n searches, even ignoring that you feel you need to clear the hash table between searches to avoid hash inconsistencies.
Let me try to illustrate this with a very simple example: There are thirty moves, you want 3 PVs, the top three moves have a value on .8, .5. and .3, and they never change. Your method searches the first move with an open window, and 29 moves with a zero window with alpha of .8, then the second move with an open window, and 28 moves with a zero window with alpha of .5, then the third move with an open window, and 27 moves with a zero window with alpha of .2.
The other method searches the first three moves with open windows and 27 moves with a zero window with alpha of .2. The difference between the two methods is that your method unnecessarily searches 29 moves with a zero window with alpha of .8 and 28 moves with a zero window with alpha of .5

Funny, because I just finished some experiments with the "annotate" code in Crafty, which does exactly what I explained. I tried several alternative approaches, and overall, the current approach was faster. Not in every position, to be sure. But _overall_. And it would be easy for anyone to run a similar test since the annotate.c code is pretty short, and what is going on is well-documented.

You need to change iterate and searchroot also.

Which I did, BTW. But annotate.c has the comments about how it currently picks up the best N replies.

Is that version available or will it be soon?

Which "version"? The one where I tried the alternative way to obtain the N-best moves? Yes, as I wanted a real "multi-PV" approach that works both for annotating games as well as analyzing games. However, I suspect it will continue to use the current approach, of searching N moves, then N-1 moves, etc. But the changes will be moved into iterate.c...

As far as clearing the hash, why? Too many other things get changed anyway to expect perfect consistency.

Don't ask me. You wrote long ago that human players liked the analysis better. As of 23.2, crafty clears the hash in annotate before each search.

Did I say otherwise? I had played with it recently due to a couple of requests via email. Got me to thinking and I spent some time, with the idea that I could also make the "multi-PV" a part of iterate.c so that it would work for normal games (if desired) as well as for annotation.

BTW, exactly how do you guarantee that you only search the first 3 moves with an open window, and all the rest with null? Is your root move ordering perfect? What if the 3rd best move is the last one? It's not quite so simple.

I oversimplified to try to keep the example short. If a move fails high, you open the window and re-search just as in a normal search.

There is another efficiency issue. If you search with an artificial alpha (lower than optimal), the search is not as efficient. The higher alpha, the better. More moves fail low easier (with less effort) because suddenly getting the score up to alpha is difficult.

What is this "artificial alpha" you are talking about? The alpha used for all the zero-window searches is the same alpha you use for the zero-window searches on your last search.

Simple answer. When you find, using your approach, the 3rd best move, you have to continue searching to see if there is another move that is better than this move, correct? That means you need to set alpha to a value that represents the current 3rd best move, which will be lower than the alpha for the real 3rd best move. This is _exactly_ the same issue in my current code, and it is the reason that neither approach is superior to the other. They have to do the same thing.

The difference between the two methods is that your method searches each non-pv move n times rather than once. I can't see how your method can be faster.

[bob]

OK, one more time.

You search at depth N and find that the three best moves are A=+100, B=+50 and C=0. All other moves are < 0 and fail low.

Now you start the search at depth N and find A=100, B=30, C=0, D=150. So after a full search at N+1 you now have D, A, B as the three best moves. But unfortunately, after move D there is a move E with a score of +120. How will you ever pick that one up since it will fail low on the +150 alpha value from D? Your list ends up incomplete, and wrong...

You can't take unsafe shortcuts unless you are willing to accept the error that can produce...

You obviously set the value for the zero-window search to the lowest of the pv values, in this case 30, since this gives the answer you want, which is whether any of the remaining moves are better than any of the pv moves you have found.

A math question.

Which is preferable:

(1) searching all root moves with a normal search, to pick up the best. Then re-searching the remaining root-moves with a normal search to pick up the second-best, etc... or

(2) Searching all moves with an artificially lowered alpha value?

The answer might be surprising...

In any iteration, the first move takes the majority of the time, and the rest rip by quickly. If you lower alpha by any amount, artificially, the rest of the moves no longer "fly by".

It is clear that you would find the answer suprising. I have tried it and searching n open windows in 1 search is significantly faster than doing n searches, even ignoring that you feel you need to clear the hash table between searches to avoid hash inconsistencies.
Let me try to illustrate this with a very simple example: There are thirty moves, you want 3 PVs, the top three moves have a value on .8, .5. and .3, and they never change. Your method searches the first move with an open window, and 29 moves with a zero window with alpha of .8, then the second move with an open window, and 28 moves with a zero window with alpha of .5, then the third move with an open window, and 27 moves with a zero window with alpha of .2.
The other method searches the first three moves with open windows and 27 moves with a zero window with alpha of .2. The difference between the two methods is that your method unnecessarily searches 29 moves with a zero window with alpha of .8 and 28 moves with a zero window with alpha of .5

Funny, because I just finished some experiments with the "annotate" code in Crafty, which does exactly what I explained. I tried several alternative approaches, and overall, the current approach was faster. Not in every position, to be sure. But _overall_. And it would be easy for anyone to run a similar test since the annotate.c code is pretty short, and what is going on is well-documented.

You need to change iterate and searchroot also.

Which I did, BTW. But annotate.c has the comments about how it currently picks up the best N replies.

Is that version available or will it be soon?

Which "version"? The one where I tried the alternative way to obtain the N-best moves? Yes, as I wanted a real "multi-PV" approach that works both for annotating games as well as analyzing games. However, I suspect it will continue to use the current approach, of searching N moves, then N-1 moves, etc. But the changes will be moved into iterate.c...

As far as clearing the hash, why? Too many other things get changed anyway to expect perfect consistency.

Don't ask me. You wrote long ago that human players liked the analysis better. As of 23.2, crafty clears the hash in annotate before each search.

Did I say otherwise? I had played with it recently due to a couple of requests via email. Got me to thinking and I spent some time, with the idea that I could also make the "multi-PV" a part of iterate.c so that it would work for normal games (if desired) as well as for annotation.

BTW, exactly how do you guarantee that you only search the first 3 moves with an open window, and all the rest with null? Is your root move ordering perfect? What if the 3rd best move is the last one? It's not quite so simple.

I oversimplified to try to keep the example short. If a move fails high, you open the window and re-search just as in a normal search.

There is another efficiency issue. If you search with an artificial alpha (lower than optimal), the search is not as efficient. The higher alpha, the better. More moves fail low easier (with less effort) because suddenly getting the score up to alpha is difficult.

What is this "artificial alpha" you are talking about? The alpha used for all the zero-window searches is the same alpha you use for the zero-window searches on your last search.

Simple answer. When you find, using your approach, the 3rd best move, you have to continue searching to see if there is another move that is better than this move, correct? That means you need to set alpha to a value that represents the current 3rd best move, which will be lower than the alpha for the real 3rd best move. This is _exactly_ the same issue in my current code, and it is the reason that neither approach is superior to the other. They have to do the same thing.

The difference between the two methods is that your method searches each non-pv move n times rather than once. I can't see how your method can be faster.

Simple. I do an iterated search for _each_ "best-n move". Which establishes move ordering and such to make the search as efficient as it can be. If you just blindly start looking for the 2nd best move at depth N, where a different move was actually best, then move ordering is broken. IE the very reason iterated search is effective in the first place...

[bob]

There is a simpler (and more efficent) approach.

Generate the ply-1 move list and search it normally, using aspiration and anything else you normally use. This produces the best move. Now remove that best move from the ply-1 move list and search again using normal aspiration and everything. This gives you the second-best move. Repeat until you have as many moves as you want. This avoids a full-search on every root move.

You are asking how this is inefficient. Isn't that obvious? You repeatedly search the later moves again and again, with ever lower null window. First at the score of the best move, then with the score of the second best, then with the score of the third best.

You apparently miss the key point. At depth N, I do a normal search (PVS) to find the best move. I remove it from the move list and then do a normal search again. Starting from depth 1 (as always) to build up move ordering information for the final depth-n search to find the 2nd best move. I repeat for the remaining N (of best-N) moves, using the iterated search approach to make each one of the best-N searches as efficient as possible. I don't just start at depth N each time searching N-1 moves, then N-2 moves. I restart at depth=1 for each new depth-N best move...

[quoite]

And if your ordering was not perfect, and the frst move you search at every stage (possiby after exclusion of some moves) was not the best remaining move, you get _exactly_ the effect you describe as a disadvantage of what I do: PVS wil put the null window for the remaining moves at the score of the first move you search, and not at the score of the best move yet to come. So in that iteration you will search a number of moves with an "artificially low" null window, until you stumble on the true best remaining move, which fails high on that window, and will have to be researched. That is not any different from what I have to do.[/quote]

Again, note that I don't suffer from the same problem, restarting at depth=1 for each different "best move" at least uses the iterated approach to improve move ordering, as opposed to starting "cold" at depth=N with the search trying to find a different best move.

Basically, what you describe is speculatively searching all remaining moves with an artificially high alpha in the hope that the first move in line to search will not be the best remaining move, and some later move will fail high against that window. If that is a gamble that pays off, then why don't you do it in a single-PV search as well? If in iteration n-1 the score of the best move is S, set an aspiration window {S+margin, S+margin+1} above the expected score for iteration n, to cheaply detect which of the later moves is going to fail high, and thus avoid having to search move 2, 3, ... of your list with alpha at the "artificially low score" of the PV move in the new iteration?

Again, that is not exactly what I am doing. See my explanation above.

[jwes]

1. how did you find the first 3 "best moves"? Not with a normal alpha.

Define "normal alpha". This obviously depends on if you are doing PVS or alpha-beta, if you do asipration or not.

For me, "normal" would be -INFINITY when you don't do aspiration, and score_of_previous_iteration - lowerMargin when you do. Of course you would use the score of the 3rd move in the multi-PV case.

2. Once you find the first "best 3" you absolutely set alpha "artificially low". Why? Because you are setting it _lower_ than the actual score for the third-best move, once you actually find the real 3rd best move.

Why on Earth would I do that? Once I actually find the real 3rd best move, alpha is of course set to the score of that. Why would you set it lower? Both in alpha-beta and PVS one usully increases alpha, when one finds a move with a better score.

Let me make it simpler.

There are 4 moves, A, B, C and D. A, B and D are the real best 4.

Once you have searched A, B and C, C is the 3rd best so far, and you are searching with its score as alpha. But D is the _real_ 3rd best move and has a higher score. So while searching all moves
after C, you are using C's score as alpha, and it is lower than the real 3rd best move's score.

So again, how is this supposedly superior to what I am currently doing?

Maybe I am confused also, but I agree with H.G.
why? As I understand the proposed system work like a normal root move search: first we try 1st move and its score it sets as new alpha, then we search the 2nd move and if is score is better than new alpha, we set that move as new best and its score as new alpha, then try again with 3nd and so on. The only difference with multiPV is that 3 first moves are -Infinite as alpha and after third is like a normal search as I have described. In both cases we are searching for "best moves than a previous one"

That's not what is happening. Let me run thru both choices for clarity.

In Crafty, at depth N I search normally. The first move will initially be the best move, and about 85% of the time it remains best. All the rest of the moves are searched with a null-window fail-soft search (fail soft means that I store HT entries with scores outside the alpha/beta bound, whatever gets backed up). I save it, remove it from the move list, and re-start the search with normal aspiration. Now, since the first move is missing, we find another "best move" which is initially the first move left in the list. And often this is really the second best move due to the move ordering by node count at the root. Most of the remaining moves (assuming this one is best) get dismissed instantly with hash hits or shallow searches. I repeat for the 3rd, and 4th etc.

The alternative is to do a normal search, but once you get a score for the best move, you artificially lower alpha enough to pick up the 2nd best (and other) moves. If you don't lower it enough, everythying fails low and you get nothing and have to do it again. If you lower it too far, other moves will fail high and have to be evaluated, just because their score is > alpha. Any search where alpha != beta-1 is very expensive to do. Once you get 3 best moves, you can set alpha to the smallest of the 3 scores, so that only moves that are better will fail high.

The issue is searching the 2nd, 3rd moves in the list with the offset alpha value just to get 3 "best moves". And then expending significant effort to prove that they are the best.

I see no way this is more efficient than what I am doing at present. The interesting case is not the one where the first 3 root moves really are best, but the case where the best N moves are scattered throughout the move list,

My preference for the way I do things in Crafty is simplicity.

What you do is use the 3 values from the previous ply for aspiration windows for the first 3 moves and the lowest of the three values as alpha for zero-window searches for the rest of the moves.

Some sample data:

Code: Select all

               19->  52.81  -0.17   18. ... Bc7 19. Rac1 f5 20. Nd2 Kh8
                                    21. Kh1 Rac8 22. e4 Nf6 23. exf5 Qd7
                                    24. Nc4 Qxf5 25. Qe2 e4 26. dxe4 Qxe4+
                                    27. Qxe4 Nxe4 28. Bd4
               20     1:25  -0.15   18. ... Bc7 19. Rac1 f5 20. Nd2 Kh8
                                    21. Kh1 Rac8 22. e4 Nf6 23. exf5 Qd7
                                    24. Nc4 Qxf5 25. Qe2 Rfe8 26. Rfe1
                                    Rcd8 27. Nxe5 Bxe5 28. Bxe5 Rxd3
               20->   1:29  -0.15   18. ... Bc7 19. Rac1 f5 20. Nd2 Kh8
                                    21. Kh1 Rac8 22. e4 Nf6 23. exf5 Qd7
                                    24. Nc4 Qxf5 25. Qe2 Rfe8 26. Rfe1
                                    Rcd8 27. Nxe5 Bxe5 28. Bxe5 Rxd3

If you notice, the first (best) move takes about 35 seconds to complete, the remainder of the moves take 4 seconds. If we remove this move from the list, we repeat this process again with roughly the same time required. There are some efficiency issues related to choosing one of these algorithms:

(1) once you find the best move, remove it from the list, and start back over at depth 1 and find the best move and build up good move ordering information to help the search;

(2) at the final ply, lower alpha to force other best moves to pop to the top of the list, without good move ordering information which makes the search less efficient. Very similar to the idea of just starting at depth N rather than using an iterated search.

This appears to be the primary reason I was seeing better performance with the current way I do things, assuming you believe that an iterated search approach is better.

In this same light, many use the idea that when a move fails low at the root, you should completely re-start the search at depth 1 to find a new best move using something better than just starting a blind/deep search. Since the fail low hash entry should stick around, the old best move will fail low on each iteration and not become the best move again.

Complex topic, lots to test. I've been experimenting with the fail-low-at-root -> restart idea as well. It has some advantages...

When I tried this, I found it best to re-start the search only on large fail-lows (+3,+M).

[hgm]

Simple. I do an iterated search for _each_ "best-n move".

So your point is that you start iterating from low depth every time you get to work on a new move? From what you said so far it was not clear that you did that.

I still don't see how that would help, however. The only thing the iterations before the last tell you is which move is most likely to be next in line. The way I do it I already have that information from the previous iteration, because each iteration gives me the N best moves at that iteration.

So by the time you start the final iteration for the third-best move, you would still have to start searching the most-likely candidate (the best from the previous iteration with two moves excluded) with an "artificially low" alpha (your lower aspiration bound), and figure out at full depth if that move does not fail low, or (if it does) if there is a later move that does not fail low, to pick up that move as a new 3rd best.

That is exactly the same as what I would be doing after having found the 2nd-best move. Difference is that I would have not done any redundant null-window searches at the score of the 2nd-best on all remaining moves. These searches make your algorithm quadratically expensive. Look what happens if you want to have PVs on all 40 moves. You would do 40*39/2 = 780 null-window searches at full depth, and 40 open-(aspirated)-window searches. I would just do the 40 open-window searches.

[bob]

Simple. I do an iterated search for _each_ "best-n move".

So your point is that you start iterating from low depth every time you get to work on a new move? From what you said so far it was not clear that you did that.

In that case, sorry for the confusion. When I said a "full search on the N-1 moves" that is what I meant. In annotate.c, I actually generate the move list for the root, then call iterate to find the best move within some fixed time limit. I then remove that move from the list, and call iterate again, except that this time I use a forced depth limit so that every "best move" is searched to the same depth. I repeat this until I find N best moves (I am working on adding a cutoff for this as it is stupid to do this when a move is an obvious re-capture and every other move is -3.00 (or worse) less than the obvious move. Yet existing annotate.c will still find those N best moves.

I still don't see how that would help, however. The only thing the iterations before the last tell you is which move is most likely to be next in line. The way I do it I already have that information from the previous iteration, because each iteration gives me the N best moves at that iteration.

And you may well be right there. The problem I ran into was that when finding all those "best" moves, I clobbered the hash table so that the next iteration took longer than it should have. And the bigger "N" was, the worse this appeared to be.

So by the time you start the final iteration for the third-best move, you would still have to start searching the most-likely candidate (the best from the previous iteration with two moves excluded) with an "artificially low" alpha (your lower aspiration bound), and figure out at full depth if that move does not fail low, or (if it does) if there is a later move that does not fail low, to pick up that move as a new 3rd best.

That is exactly the same as what I would be doing after having found the 2nd-best move. Difference is that I would have not done any redundant null-window searches at the score of the 2nd-best on all remaining moves. These searches make your algorithm quadratically expensive. Look what happens if you want to have PVs on all 40 moves. You would do 40*39/2 = 780 null-window searches at full depth, and 40 open-(aspirated)-window searches. I would just do the 40 open-window searches.

Don't forget the re-searches assuming you don't always start at -infinity.