Efficient algorithm for k-best mode?

[Alessandro Scotti]

In Hamsters, I use the (first) approach described by Pradu.

[bob]

In Hamsters, I use the (first) approach described by Pradu.

same result. The best K moves must be searched with a wide window, which kills performance...

[Michael Sherwin]

Any ideas on how you can efficiently implement k-best mode?

Regards,
Gijsbert

There is only _one_ way to do it correctly:

generate the complete ply-1 move list, and search it to a fixed depth and print the best move. Remove the best move, and search again to find the best move. This is the second-best move. Repeat K-1 times to find the best K moves. It will be slow.

I have been working on an upper level 'max' search.

i = iteration depth

search i moves deep to find the best move and opponents responce

(this is when played a max node) play the moves

repeat i times (a max node, inc ply by two, another max node, etc)

on any max node scoring less than the root node see if it is best so far and save it if it is

get the second best root move and play its max node if it is better than best sofar

quit when best sofar is better than the next best move and go to next iteration depth (i++).

This is the simplest version. The version that I am working on is a little more complicated.

Hint, hint!

This algorithm (or something similar) can be used to make a very interesting k-best searcher. Sure, some tactics are sacrificed at the root, but the tactics do not narrow with depth (except on the last search) and it can go very deep. Much deeper than standard alpha/beta search. And if the goal is an analysis search that you can direct or have time to let run, then it will pay dividends.

[jwes]

In Hamsters, I use the (first) approach described by Pradu.

same result. The best K moves must be searched with a wide window, which kills performance...

I have been thinking about this. With your way, you search move 1 with a wide window and all the other moves with a zero window at plies 1...n, then the same with move 2, and on to move k. Pradu's method searches moves 1...k with a wide window and all the other moves with a zero window at ply 1 and then plies 2...n. So your method and Pradu's method search the same number of times with open windows, *but* your method searches all the other moves k times per ply while Pradu's searches them once per ply.
It seems like Pradu's method should be much faster.

ps, I know that Pradu probably did not invent his method.

[bob]

In Hamsters, I use the (first) approach described by Pradu.

same result. The best K moves must be searched with a wide window, which kills performance...

I have been thinking about this. With your way, you search move 1 with a wide window and all the other moves with a zero window at plies 1...n, then the same with move 2, and on to move k. Pradu's method searches moves 1...k with a wide window and all the other moves with a zero window at ply 1 and then plies 2...n. So your method and Pradu's method search the same number of times with open windows, *but* your method searches all the other moves k times per ply while Pradu's searches them once per ply.
It seems like Pradu's method should be much faster.

ps, I know that Pradu probably did not invent his method.

If you read what he is doing, the net result is pretty similar. No way you can just search N moves once. You find the best move, and you don't know that until you have searched _all_ mvoes once. Now how to find the second-best? If you pick the right second-best move first for the next search, you still have to search the rest to make sure none are better. Whether you search for fail-highs and then resolve later or not turns out to be pretty similar in search space, because if you put off a re-search, you take a chance the important stuff form the hash table will be overwritten and the later re-search will be less efficient than if you do it "right now"...

The real problem lies in the fact that the first move is far harder to search than the rest, assuming the first move is actually the best move. And to find the best K moves, you have to absorb that performance hit K times, which is expensive...

[Dann Corbit]

In Hamsters, I use the (first) approach described by Pradu.

same result. The best K moves must be searched with a wide window, which kills performance...

I have been thinking about this. With your way, you search move 1 with a wide window and all the other moves with a zero window at plies 1...n, then the same with move 2, and on to move k. Pradu's method searches moves 1...k with a wide window and all the other moves with a zero window at ply 1 and then plies 2...n. So your method and Pradu's method search the same number of times with open windows, *but* your method searches all the other moves k times per ply while Pradu's searches them once per ply.
It seems like Pradu's method should be much faster.

ps, I know that Pradu probably did not invent his method.

If you read what he is doing, the net result is pretty similar. No way you can just search N moves once. You find the best move, and you don't know that until you have searched _all_ mvoes once. Now how to find the second-best? If you pick the right second-best move first for the next search, you still have to search the rest to make sure none are better. Whether you search for fail-highs and then resolve later or not turns out to be pretty similar in search space, because if you put off a re-search, you take a chance the important stuff form the hash table will be overwritten and the later re-search will be less efficient than if you do it "right now"...

The real problem lies in the fact that the first move is far harder to search than the rest, assuming the first move is actually the best move. And to find the best K moves, you have to absorb that performance hit K times, which is expensive...

Is this method actually cheaper than simply searching every depth +1 node with full window (but the subsequent node with normal pvs)?

[hgm]

I am not even sure what is asked here. From the answer given by Maurizio (which I think is absolutely correct) it seems that this is for a variant where you are allowed to veto k-1 moves. But rom other answers, it seems they just want to know an exact score for the first k moves in the root.

Logiclly, that latter would require what Maurizio suggests only in the root: alpha is updated to be the score of the kth best move so far. And so as a logical consequence, the first k moves are searched with alpha = -INF. Obviously clever aspirating can save you a lot of work here. The PVS analog would, in each new iteration, first search the k-th move with open window, then search all other moves with a null window at the score you find (to prove they are all worse), do the usual re-searches if one of them fails high, to adjust the null-window upward if the fail high was confirmed with open window, and then search the best k-1 moves with the best value found so far as aspiration.

[bob]

In Hamsters, I use the (first) approach described by Pradu.

same result. The best K moves must be searched with a wide window, which kills performance...

I have been thinking about this. With your way, you search move 1 with a wide window and all the other moves with a zero window at plies 1...n, then the same with move 2, and on to move k. Pradu's method searches moves 1...k with a wide window and all the other moves with a zero window at ply 1 and then plies 2...n. So your method and Pradu's method search the same number of times with open windows, *but* your method searches all the other moves k times per ply while Pradu's searches them once per ply.
It seems like Pradu's method should be much faster.

ps, I know that Pradu probably did not invent his method.

If you read what he is doing, the net result is pretty similar. No way you can just search N moves once. You find the best move, and you don't know that until you have searched _all_ mvoes once. Now how to find the second-best? If you pick the right second-best move first for the next search, you still have to search the rest to make sure none are better. Whether you search for fail-highs and then resolve later or not turns out to be pretty similar in search space, because if you put off a re-search, you take a chance the important stuff form the hash table will be overwritten and the later re-search will be less efficient than if you do it "right now"...

The real problem lies in the fact that the first move is far harder to search than the rest, assuming the first move is actually the best move. And to find the best K moves, you have to absorb that performance hit K times, which is expensive...

Is this method actually cheaper than simply searching every depth +1 node with full window (but the subsequent node with normal pvs)?

Yes. Because you only end up searching K (or slightly) more moves with a full-window, otherwise you search them all, and that is way more expensive.

Simple explanation:

Say the first move takes 50% of the time, and the remaining N-1 moves take the remaining 50%, and we assume perfect move ordering so that it can be solved without a lot of mathematical gyrations. Let's call the total time used to search the entire list one time as "T"

To find the first best move requires time T (total time of the search). To find the second best, we spend .5*T + (N-1) / N * T. To find the best 5, you end up with 5 * .5T to search the actual best moves, plus roughly .5 * T to search the rest of the moves. Or about 5T.

If you search them one at a time with wide windows. you end up with N * T, which is much larger than 5*T...

[jwes]

I pretty much agree with all you said. The two methods do nearly the same work except your method searches all the moves that always fail low k times and the other method searches them once (per ply). It is very expensive doing a k-best search with any method, but the other way does do significantly less work.

[bob]

I pretty much agree with all you said. The two methods do nearly the same work except your method searches all the moves that always fail low k times and the other method searches them once (per ply). It is very expensive doing a k-best search with any method, but the other way does do significantly less work.

Not quite. Suppose a bad move is ordered first? it is not one of the best K moves, but it introduces big overhead. This is highly sensitive to move ordering for that reason. There are other reasons why you can't just pick the best K and pass over the rest just once, but it is more complex...