7

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

3 Answers 3

7

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.

7
  • wow this answer is great! Thank you very much. Would this ordering also help in alpha-beta search? Dec 10, 2019 at 17:23
  • I just did that and it reduced the amount of checked nodes by a factor of 5. Dec 10, 2019 at 17:30
  • Glad I could help! And yes, alpha/beta benefits (quite a lot) from move ordering techniques. In fact, I assumed you were aware of them when writing my answer. As I said, searching A before B makes it more likely to create a beta cutoff. The same principle applies to normal alpha/beta search: if you search the good moves first, alpha/beta will be more efficient. The actual ordering mechanisms are usually more complicated than MVV/LVA, but core idea is the same. Dec 10, 2019 at 18:13
  • I will also go ahead and implement iterative deepening which should be a huge improvement. Just one last question on that. Basicaly the last principal variation line is only included in the first called node, right? Basically only for the left-most nodes in the alpha-beta tree. Dec 10, 2019 at 18:16
  • I'm not entirely sure what you mean by "the principal variation line is only included in the first called node," but the basic idea of iterative deepening is that after each iteration, you can order the nodes using the previous iteration. This means that the first move of the principal variation of the previous iteration will be searched first, along with the other moves, in descending order of value. Dec 10, 2019 at 18:41
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.

10
  • So I got a pretty good result when limiting it to a depth of 2. Is this allowed? Dec 9, 2019 at 19:03
  • @FinnEggers - if you are happy with the results you may certain do that without anyone elses approval.
    – yobamamama
    Dec 9, 2019 at 19:06
  • Okay thank you! Should I include things like move-ordering and hashing also for the Quiescence Search? Dec 9, 2019 at 19:07
  • @FinnEggers -- Now you are getting past my experience with this sort of programming. I would expect that the Quiescent search would be more of the normal search method just to verify no funny surprises could happen. On a philosophical bent, why don't programmers then do a quiescent search on the results of the quiescent search just done .... ad infinitum. At some point you have to say this is what I can do and just stop.
    – yobamamama
    Dec 9, 2019 at 19:09
  • 1
    That is your call. It would simplify and speed up that part of the search. I would think you still need to look at checks. Be embarassing to have a mate in one and not check because it was not a capture.
    – yobamamama
    Dec 9, 2019 at 19:16
2

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.

1
  • I added my code. Thank you for the link! It looks promising allthough there are some aspects that I did not include in my program like checkmate etc. the game ends if the king is taken. this is much simpler to implement. I could implement that those moves are forbidden when actually playing but they are allowed when searching Dec 10, 2019 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.