Efficient algorithm for kbest mode?
Moderators: bob, hgm, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Efficient algorithm for kbest mode?
Any ideas on how you can efficiently implement kbest mode?
Regards,
Gijsbert
Regards,
Gijsbert

 Posts: 870
 Joined: Sun Nov 19, 2006 8:16 pm
 Location: Russia
Re: Efficient algorithm for kbest mode?
You have to find all (k1)best moves from a root movelist, and find the best from rest.
Re: Efficient algorithm for kbest mode?
Not enough, because you should take care of the fact that in all inner nodes every player will only be able to chose the kth 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 alphabeta where the alpha bound is adjusted to be at least the kthbest value you have found so far, and where you can do a betacut only when the kth best value is >= beta. I may give this variant a try some day, maybe.
Regards!
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 alphabeta where the alpha bound is adjusted to be at least the kthbest value you have found so far, and where you can do a betacut only when the kth best value is >= beta. I may give this variant a try some day, maybe.
Regards!
Re: Efficient algorithm for kbest mode?
There is only _one_ way to do it correctly:gwiesenekker wrote:Any ideas on how you can efficiently implement kbest mode?
Regards,
Gijsbert
generate the complete ply1 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 secondbest move. Repeat K1 times to find the best K moves. It will be slow.

 Posts: 3041
 Joined: Fri May 26, 2006 1:00 am
 Location: WY, USA
 Full name: Michael Sherwin
Re: Efficient algorithm for kbest mode?
I have been working on an upper level 'max' search.bob wrote:There is only _one_ way to do it correctly:gwiesenekker wrote:Any ideas on how you can efficiently implement kbest mode?
Regards,
Gijsbert
generate the complete ply1 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 secondbest move. Repeat K1 times to find the best K moves. It will be slow.
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.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.
Re: Efficient algorithm for kbest mode?
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 kbest moves, you would have to search the first kmoves with an open window (INF,INF or whatever other aspiration windows you use). Say the worst of the kbest 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 kbest moves.gwiesenekker wrote:Any ideas on how you can efficiently implement kbest mode?
Regards,
Gijsbert
Re: Efficient algorithm for kbest mode?
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
Regards,
Gijsbert
Re: Efficient algorithm for kbest mode?
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 kbest moves with the bound (INF,w). If you fail high, then you do the usual "PVS style" research (s,INF).Pradu wrote: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 kbest moves, you would have to search the first kmoves with an open window (INF,INF or whatever other aspiration windows you use). Say the worst of the kbest 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 kbest moves.
You could go totally overkill and instead of searching failhighs with (s,INF) when the scout search fails high, you could research it with (s, next worst score in your kbest) and continue until you have to search (new s,INF).
 Zach Wegner
 Posts: 1922
 Joined: Wed Mar 08, 2006 11:51 pm
 Location: Earth
 Contact:
Re: Efficient algorithm for kbest mode?
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 kbest.
It seems to make sense to me, but I've never tried it. I never had any use for kbest.
Re: Efficient algorithm for kbest mode?
Some also "lie" about it.gwiesenekker wrote: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
One shortcut. During the search (last iteration depth) you will get the score for move 1. Then you continue searching and you might get a failhigh 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 Nbest moves accurately... And the hash table can make this interesting as well, in that researching 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...