CheckersGuy wrote:Hey guys,
I have implemented QuiesceneSearch but I it didn't seem to help my engine nor did it hurt my engine in any way. I just wonder if my implementation is correct if that's not the case there is probably a bug somewhere else. (I am using failSort implementation of PVS)
Here is the implementation I am using:
Code: Select all
public static int quiesceneSearch(Board board, int alpha, int beta){
final int standpat =board.color*GameEvaluation.evaluate(board);
if(standpat>=beta)
return beta;
if(alpha<standpat)
alpha=standpat;
ArrayList<Move> jumpers = MGenerator.getCaptures(board);
for (Move move : jumpers) {
board.makeMove(move);
int value = -quiesceneSearch(board, -beta, -alpha);
board.undoMove(move);
if(value>beta)
return beta;
if(value>alpha)
alpha=value;
}
return alpha;
}
And I got another question about Sorting the MoveList: Should I use ShellSort instead of insertionSort (which I am currently using). I tested insertionsSort vs SelectionSort and saw almost no difference. I concluded that there arent many moves that need to be swaped. When does ShellSort outperform InsertionSort ?
I did a 15second search and my algorithm spend around 25% of that time sorting the moves.
Hi Robin,
testing for a cutoff should always be done like this:
Code: Select all
if(value>=beta)
return beta;
where you do "value > beta" instead within the move loop. The reason should be obvious (the current node will have no impact on the root if it is proven that the score returned from the current node will not improve alpha of the parent node).
Another point is that you mentioned you are using the fail-soft algorithm. In that case you should - for consistency - also do so in quiescence search, and therefore return "value" resp. "standpat" instead of "beta" in case of a cutoff. I hope you do so already in your full-width search, otherwise you are not really using fail-soft.
Sorting the move list should not take 25% of overall runtime. On the other hand, since you are in a very early stage of engine development (I derive that from the fact that you are currently adding quiescence search) I would not care too much about performance aspects at this point. Especially everything that can only change performance by a constant factor could be postponed, unless that factor is so huge and the risk of doing the change is so low that you would classify that as "low hanging fruits". In the given case I would plan to optimize that later. Nevertheless I can tell you how many engine programmers solve that: the easiest way, often also the one that performs best, is to always select the next best move when you actually need one. Since good move ordering will lead to about 80-90% cutoffs on the first move (or even more), this will basically reduce the ordering effort to O(n) since you usually go only once through the move list to find the one with the best ordering score. That move will be swapped with the move at position "i", where moves no. 1 until i-1 have already been searched and did not produce a cutoff.
I can't say why adding QS to your engine does not lead to an improvement. But typically the problems are not only in the search algorithm. There may be a problem in move ordering or even in the evaluation. You will have to debug it!
