Efficient algorithm for k-best mode?

[gwiesenekker]

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

Regards,
Gijsbert

[Aleks Peshkov]

You have to find all (k-1)-best moves from a root move-list, and find the best from rest.

[Ratta]

Not enough, because you should take care of the fact that in all inner nodes every player will only be able to chose the k-th best move.
For instance, in the chess variant where one move can be refused (and i guess you are willing to implement this, and it is cool!! ), it may be a good move capturing a knight with your queen if the knight is defended by "only" one pawn, because you will be able to prevent your opponent from capturing your queen.
I never tried to implement this, but i think that it can be done with a plain alpha-beta where the alpha bound is adjusted to be at least the kth-best value you have found so far, and where you can do a beta-cut only when the k-th best value is >= beta. I may give this variant a try some day, maybe.
Regards!

[bob]

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.

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

[Pradu]

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

Regards,
Gijsbert

You can still use alphabeta techniques to some extent. If you are using PVS or some other kind of scout search and say you wanted the first k-best moves, you would have to search the first k-moves with an open window (-INF,INF or whatever other aspiration windows you use). Say the worst of the k-best moves had a score w. Then you search the rest of the moves assuming the current bounds are (w,w+1) and if you fail high (returned score s) you can research with the window (s, INF <or whatever other upperbound you use>) and update the worst of your k-best moves.

[gwiesenekker]

As I found out this method is (very) slow, which was the reason why I posted this question. Commercial chess programs seem be be able to generate this information quite efficiently, the score and the PV of the second best move seems to be right as well.

Regards,
Gijsbert

[Pradu]

You can still use alphabeta techniques to some extent. If you are using PVS or some other kind of scout search and say you wanted the first k-best moves, you would have to search the first k-moves with an open window (-INF,INF or whatever other aspiration windows you use). Say the worst of the k-best moves had a score w. Then you search the rest of the moves assuming the current bounds are (w,w+1) and if you fail high (returned score s) you can research with the window (s, INF <or whatever other upperbound you use>) and update the worst of your k-best moves.

Another possible enhancement... for this one you have to experiment to see if it is indeed better. When you start a new iteration and finish searching the first move. Search the rest of the k-best moves with the bound (-INF,w). If you fail high, then you do the usual "PVS style" research (s,INF).

You could go totally overkill and instead of searching fail-highs with (s,INF) when the scout search fails high, you could research it with (s, next worst score in your k-best) and continue until you have to search (new s,INF).

[Zach Wegner]

What I have heard works pretty well from a couple of people (you get a pretty much constant branching factor) is using a separate aspiration window on every move. That is, every iteration, you obtain an exact score for each move, and on the next iteration, search with an aspiration window around this value.

It seems to make sense to me, but I've never tried it. I never had any use for k-best.

[bob]

As I found out this method is (very) slow, which was the reason why I posted this question. Commercial chess programs seem be be able to generate this information quite efficiently, the score and the PV of the second best move seems to be right as well.

Regards,
Gijsbert

Some also "lie" about it.

One short-cut. During the search (last iteration depth) you will get the score for move 1. Then you continue searching and you might get a fail-high on move N. Once you resolve it, you at least have moves 1 and N resolved. But what I have seen from at least one professional program is this:

Save each score/PV as they change. When you finish, sort the list from high to low and print it out. Even if some of the PVs came from the previous iteration. Even if you are not certain that these are the best N.

there is only one correct way, which was the way I explained. Nothing else will work to produce the N-best moves accurately... And the hash table can make this interesting as well, in that re-searching a move after having already searched all moves at this depth can produce a score that is better than the best move because of how the hash table grafts scores from one part of the tree onto another...