Efficient algorithm for k-best mode?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
gwiesenekker

Efficient algorithm for k-best mode?

Post by gwiesenekker » Sat Nov 17, 2007 10:27 pm

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

Regards,
Gijsbert

Aleks Peshkov
Posts: 870
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: Efficient algorithm for k-best mode?

Post by Aleks Peshkov » Sat Nov 17, 2007 11:44 pm

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

Ratta

Re: Efficient algorithm for k-best mode?

Post by Ratta » Sun Nov 18, 2007 12:04 am

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!! 8-) ), 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
Posts: 20566
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Efficient algorithm for k-best mode?

Post by bob » Sun Nov 18, 2007 6:15 am

gwiesenekker wrote: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
Posts: 3041
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Efficient algorithm for k-best mode?

Post by Michael Sherwin » Sun Nov 18, 2007 7:32 am

bob wrote:
gwiesenekker wrote: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.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: Efficient algorithm for k-best mode?

Post by Pradu » Sun Nov 18, 2007 9:11 am

gwiesenekker wrote: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

Re: Efficient algorithm for k-best mode?

Post by gwiesenekker » Sun Nov 18, 2007 10:02 am

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
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: Efficient algorithm for k-best mode?

Post by Pradu » Sun Nov 18, 2007 10:21 am

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

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Efficient algorithm for k-best mode?

Post by Zach Wegner » Sun Nov 18, 2007 1:55 pm

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
Posts: 20566
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Efficient algorithm for k-best mode?

Post by bob » Sun Nov 18, 2007 4:31 pm

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

Post Reply