Chess: quiescence search dominating runtime

Question

I have implemented an alpha-beta search with quiescence search for my chess engine. However, in most positions, the quiescence search is taking 80-90% of the total execution time, as indicated by my profiler. Do I have a bug with my pruning?

I have included both the alpha-beta routine and the quiescence routine.

My quiescence search is based directly on this pseudocode.

// Perform the alpha-beta search.
func ab(b *dragontoothmg.Board, alpha int16, beta int16, depth int8, halt chan bool, stop *bool) (int16, dragontoothmg.Move) {
    nodeCount++

    if *stop {
        return alpha, 0
    }

    found, tableMove, tableEval, tableDepth, tableNodeType := transtable.Get(b)
    if found && tableDepth >= depth {
        if tableNodeType == transtable.Exact {
            return tableEval, tableMove
        } else if tableNodeType == transtable.LowerBound {
            alpha = max(alpha, tableEval)
        } else { // upperbound
            beta = min(beta, tableEval)
        }
        if alpha >= beta {
            return tableEval, tableMove
        }
    }
    if depth == 0 {
        //return eval.Evaluate(b), 0
        return quiesce(b, alpha, beta, stop), 0
    }

    alpha0 := alpha
    bestVal := int16(negInf) 
    moves := b.GenerateLegalMoves()
    var bestMove dragontoothmg.Move
    if len(moves) > 0 {
        bestMove = moves[0] // randomly pick some move
    }
    for _, move := range moves {
        unapply := b.Apply(move)
        var score int16
        score, _ = ab(b, -beta, -alpha, depth-1, halt, stop)
        score = -score
        unapply()
        if score > bestVal {
            bestMove = move
            bestVal = score
        }
        alpha = max(alpha, score)
        if alpha >= beta {
            break
        }
    }

    if *stop {
        return bestVal, bestMove
    }

    var nodeType uint8
    if bestVal <= alpha0 {
        nodeType = transtable.UpperBound
    } else if bestVal >= beta {
        nodeType = transtable.LowerBound
    } else {
        nodeType = transtable.Exact
    }
    transtable.Put(b, bestMove, bestVal, depth, nodeType)
    return bestVal, bestMove
}

func quiesce(b *dragontoothmg.Board, alpha int16, beta int16, stop *bool) int16 {
    nodeCount++
    if *stop {
        return alpha
    }
    var standPat int16
    found, _, evalresult, _, ntype := transtable.Get(b)
    if found && ntype == transtable.Exact {
        standPat = evalresult
    } else {
        standPat = eval.Evaluate(b)
        transtable.Put(b, 0, standPat, 0, transtable.Exact)
    }
    if standPat >= beta {
        return beta
    }
    if alpha < standPat {
        alpha = standPat
    }
    moves := b.GenerateLegalMoves()
    if len(moves) == 0 { // TODO(dylhunn): What about stalemate?
        return negInf
    }
    for _, move := range moves {
        if !isCapture(move, b) {
            continue
        }
        unapply := b.Apply(move)
        score := -quiesce(b, -beta, -alpha, stop)
        unapply()
        if score >= beta {
            return beta
        }
        if score > alpha {
            alpha = score
        }
    }
    return alpha
}

func isCapture(m dragontoothmg.Move, b *dragontoothmg.Board) bool {
    toBitboard := (uint64(1) << m.To())
    return (toBitboard&b.White.All != 0) || (toBitboard&b.Black.All != 0)
}

Answer 1

If I read your code correctly, you are searching all captures. What you can do to save work, is to prune the hopeless captures move. It turns out that it is quite common that moves are so bad that it is safe to skip them, so the technique is quite safe.

For example, take a look at this position:

FEN: rnbqkbnr/pppppppp/8/8/8/8/1PP1PPP1/RNBQKBNR w KQkq - 0 1

There are three captures:

• Rxa7
• Qxd7+
• Rxh7

Let us assume the engine first tries the capture move with the queen. Black has four ways to capture back, but any of these moves will likely result in a cutoff.

For instance, black plays Bxd7. Now white has two captures in the resulting position, Rxa7 or Rxh7.

Here, most engines will recognize that white has already fallen back in material (in comparison to beta) that even capturing a pawn will not help. So, both of this rook captures are unlikely to result in a cutoff.

Here, your current search would still continue to search these moves. Detecting such cases and skipping these moves will save a lot of work.

There are further optimizations. For example, strong engines with static exchange evaluation will immediately see that Qxd7 will win one pawn but will loose the queen. As this is a bad trade, the engine can immediately skip this move. The same goes for the other two rook captures.

As always, there is a trade-off, though. If you prune too aggressively, you will eventually prune good moves, too. In general, I would recommend to spend more time in the normal search, not in the quiescence search, so aggressive pruning should be fine.