Chess engine: Quiescence Search increases required time by a factor of 20

Question

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;
}

Answer 1

Because you said

Without limiting the allowed depth of the Quiescence Search, my program ran for multiple minutes without any result

I'm assuming that you haven't implemented any capture ordering in your quiescence search.

When you don't do this, you allow your computer to calculate rather silly situations very deeply. For instance, say I have one capture: my queen takes your (defended) pawn. This is obviously a bad choice, and we want your computer to recognize this quickly.

You could simply recapture (choice A), but you have another capture available (choice B) your bishop takes my pawn. Say for the sake of example that these are the only two available captures. You now have two options for searching these moves:

First B, then A

If you search B first, my queen might have the option to take another piece (now that it has moved to a different square). You'll call the quiescence function again (maybe your bishop can now take another piece) and after that, maybe my queen can take yet another piece. You're calling the quiescence function over and over again. It'll have to end at some point, but when you're doing this for every leaf node, this takes time.

First A, then B

If you search A first, I will no longer have a queen with which to take pieces, meaning I am substantially less likely to have to have more captures available, meaning your quiescence search will likely stop here. Then, when you inevitably search B, you will be much more likely to create a beta cutoff because capturing the queen with a pawn was given a very high value.

---

Hopefully this illustrates the importance of move ordering in quiescence search.

The way we typically do this is with MVV/LVA, which stands for "most valuable victim, least valuable attacker," which does exactly what it sounds like. For each capture, compute the value of the victim minus the value of the attacker, then search the largest captures first. This should massively reduce your qsearch times.

All this being said, limiting your qserach is sometimes a legitimate thing to do, (is it actually useful to see the 10th capture in a row?) but first you should see how the capture ordering shakes out, then make a decision.

Hope it helps.

Answer 2

I am speculating that you have too many quiet positions to continue with the quiescence checking, especially at that extra depth. You will have to limit the number of extra quiescent moves you check or get a faster computer; or be willing to wait longer for an answer.

Answer 3

The point of a quiescence search(QSearch) is to get a better static evaluation. By the number of nodes your searching, it seems that your just extending your main search function. By limiting your QSearch to only captures, promotions and maybe checks, you should greatly reduce the QSearch.

An interesting observation is that QSearch is the function mainly used to call the evaluation function. This is the most time consuming function, so the QSearch would account for the most time used.

https://web.archive.org/web/20201106232751/members.home.nl/matador/Inside%20Rebel.pdf is a useful reference.

Note: By providing some code, it would be easier to suggest a better answer.