I am currently trying to implement a basic chess engine and got to the following point:
I have got Alpha-Beta Pruning implemented and extended it with a transposition table. To further increase stability I implemented Quiescence Search and this is where I ran into problems.
The result clearly looked better but the required time for this was out of this world.
I was using Alpha-Beta pruning with a depth of 6 half-moves. Each evaluation was carried out by Quiescence Search. Without limiting the allowed depth of the Quiescence Search, my program ran for multiple minutes without any result. I limited the depth of the Quiescence Search 10 half-moves and got to the following result for the second move:
visited nodes: 6915527
quiescent nodes: 104313894
>>> 79502 ms <<<
Without Quiescence Search (the listed quiescent nodes are the leafs of the main tree)
visited nodes: 8472808
quiescent nodes: 4978606
>>> 9227 ms <<<
You can see that the Quiescence Search takes up most of the time.
What could I do to improve the time my engine needs?
private double alphaBetaSearch(double alpha, double beta, int currentDepth) {
_visitedNodes ++;
long zobrist = _board.zobrist();
double transposition = transpositionLookUp(zobrist, currentDepth);
if(!Double.isNaN(transposition)){
return transposition;
}
List<Move> allMoves = _board.getAvailableMoves();
if(currentDepth == _depth || allMoves.size() == 0 || _board.isGameOver()){
double val = Quiesce(alpha, beta,quiesce_depth );
transpositionPlacement(zobrist, currentDepth, val);
return val;
}
orderer.sort(allMoves,currentDepth,zobrist,_transpositionTable_pv);
for (Move m : allMoves) {
_board.move(m);
double score = -alphaBetaSearch(-beta, -alpha, currentDepth + 1);
_board.undoMove();
if (score >= beta) {
transpositionPlacement(zobrist, m);
return beta;
}
if (score > alpha) {
transpositionPlacement(zobrist, m);
alpha = score;
if (currentDepth == 0) {
_bestMove = m;
}
}
}
transpositionPlacement(zobrist, currentDepth, alpha);
return alpha;
}
private double Quiesce(double alpha, double beta, int depth_left) {
_quiesceNodes ++;
_evaluatedNodes ++;
double stand_pat = evaluator.evaluate(_board) * _board.getActivePlayer();
if(depth_left == 0){
return stand_pat;
}
if( stand_pat >= beta)
return beta;
if( alpha < stand_pat )
alpha = stand_pat;
List<Move> allMoves = _board.getAvailableMoves();
for(Move m:allMoves){
if(m.getPieceTo() * m.getPieceFrom() < 0){
_board.move(m);
double score = -Quiesce( -beta, -alpha, depth_left-1);
_board.undoMove();
if( score >= beta )
return beta;
if( score > alpha )
alpha = score;
}
}
return alpha;
}