Efficient algorithm for k-best mode?

[diep]

oh well there is a fast way to get the n best moves, though that doesn't always 100% work as you could have bad luck.

For every movelist m at iteration depth d, there is a bound b that exactly has the property that k moves are better than or equal to b.

So MTD type search here is total superior in case k is a tad bigger.

Of course in itself this is total useless, as users want to know which of the k best moves is the best, which asks for more refinements (and let's you move to something else than MTD especially in case k=2), but that wasn't the original question.

If you misguess bound b, then this search is gonna be very very expensive.

Vincent

[bob]

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.

What was asked so far as I know was what is the most efficient way to find the "best K" moves, not scores for the first K moves. "most efficient" is a misnomer as there is nothing efficient about it, however.

[hgm]

OK, I see. In the root, I suppose. Efficiency is a relative notion: if finding the best k moves takes less than k times the time to find the single best move, one could argue that it is more efficient than normal alpha-beta or PVS.

So you need no scores, that makes it even easier than I thought. If your search is quite stable, the PVS philosopy seems attractive. In that case I would use MTD(f): iterate towards a situation where the null window has k moves failing high and the rest failing low. If you have k+N moves failing high, but the null window for the next iteration just below the lower bound of the k-th, and search the move with the lowest lower bound.

[rjgibert]

Devising an algorithm to find the k-best might be interesting, but is perhaps not the most practical.

Why not an algorithm that returns all the moves that are within say a quarter pawn of the best move? Who cares about the kth best move if it evaluates as 5 pawns worse than the best move? likewise about the 2nd best move for that matter.

By returning all the moves that are within a reasonable delta of best, a much simpler and more efficient algorithm is possible. It would return the best move and its score and all the moves within some delta of the best move without returning their exact scores. That should be easy to do without too much loss of efficiency. Ideal for MTD(f) type search without the researches.

In addition to being easier, it would also have greater practical value. Looking for the k-best moves seems too anal to me and in many positions, utterly pointless.

Just my 2 cents.

[Dann Corbit]

Devising an algorithm to find the k-best might be interesting, but is perhaps not the most practical.

Why not an algorithm that returns all the moves that are within say a quarter pawn of the best move? Who cares about the kth best move if it evaluates as 5 pawns worse than the best move? likewise about the 2nd best move for that matter.

By returning all the moves that are within a reasonable delta of best, a much simpler and more efficient algorithm is possible. It would return the best move and its score and all the moves within some delta of the best move without returning their exact scores. That should be easy to do without too much loss of efficiency. Ideal for MTD(f) type search without the researches.

In addition to being easier, it would also have greater practical value. Looking for the k-best moves seems too anal to me and in many positions, utterly pointless.

Just my 2 cents.

Your idea sounds very good to me.
Perhaps the answer is that there *are* no other good moves.
For example, suppose that one move wins and all other moves draw.
What is the answer to "Give me the top three moves?"
I would answer:
1. Winning move
2. NULL
3. NULL

[Daniel Mehrmann]

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

Pradu gives the most logical answer here and he's one of my best school-boys. Using the bounds and doing a pvs after you filled all wanted k-moves is the best way for a very small search-tree.

For example what i do in 3 k-move search:
I'll search the first three moves with INF INF window. After that, i know my upperbound and set it up to the lowest score from the k-moves. Now i perform a pvs and if i must do a re-search i'll take in a first run the score of the best k-move and if it still hit the score i open my upperbound to INF.
If the search is finished don't forget to set the upperbound to the new lowest score.

Best,
Daniel

ps: Just a little hint: What do you think will happen if you store your results in a hashtable with "exact" score.

[OliverBr]

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

Ahh, this shouldn't happen actually. If you make a clean (loss free) hash table should only use hash scores from the same depth. Then you can research as often you want, it won't alternate the result.

Of course, other information than score can be used from different depth, especially moves for sort.

[bob]

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

Ahh, this shouldn't happen actually. If you make a clean (loss free) hash table should only use hash scores from the same depth. Then you can research as often you want, it won't alternate the result.

Of course, other information than score can be used from different depth, especially moves for sort.

Why would you want to do a crippled hash implementation like that and give up the potential benefit. For example, doing it that way, you need 26 plies to solve fine #70, where most of us get it 4-8 plies sooner. I prefer the benefit this grafting offers, rather than trying to cripple the feature...

Do you _really_ want to ignore a 12 ply table result because you only have 2 plies of real search left? And give up that potential accuracy that might let you see something important that the normal search depth would miss (again, fine 70 is an example of how this could change the game outcome negatively if this is done...).

[jwes]

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

Ahh, this shouldn't happen actually. If you make a clean (loss free) hash table should only use hash scores from the same depth. Then you can research as often you want, it won't alternate the result.

Of course, other information than score can be used from different depth, especially moves for sort.

Why would you want to do a crippled hash implementation like that and give up the potential benefit. For example, doing it that way, you need 26 plies to solve fine #70, where most of us get it 4-8 plies sooner. I prefer the benefit this grafting offers, rather than trying to cripple the feature...

Do you _really_ want to ignore a 12 ply table result because you only have 2 plies of real search left? And give up that potential accuracy that might let you see something important that the normal search depth would miss (again, fine 70 is an example of how this could change the game outcome negatively if this is done...).

Crafty does this in annotate mode.

[bob]

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

Ahh, this shouldn't happen actually. If you make a clean (loss free) hash table should only use hash scores from the same depth. Then you can research as often you want, it won't alternate the result.

Of course, other information than score can be used from different depth, especially moves for sort.

Why would you want to do a crippled hash implementation like that and give up the potential benefit. For example, doing it that way, you need 26 plies to solve fine #70, where most of us get it 4-8 plies sooner. I prefer the benefit this grafting offers, rather than trying to cripple the feature...

Do you _really_ want to ignore a 12 ply table result because you only have 2 plies of real search left? And give up that potential accuracy that might let you see something important that the normal search depth would miss (again, fine 70 is an example of how this could change the game outcome negatively if this is done...).

Crafty does this in annotate mode.

Annotate is not playing real games. If I don't clear the hash table scores (leaving the best move for better ordering of course) then it sometimes happens that the second best (or third best or whatever) move has a _better_ score than the first move searched. And that caused too many questions. Even now, this happens on infrequent occasions as not searching that first move changes the shape of the tree that is searched when it is excluded... and that can change the scores just as easily...

But I would not consider doing that for the real case of playing an actual game, where every bit of performance and accuracy counts...