Quiescence node explosion

[sandermvdb]

I've just implemented quiescence search which is initiated at the leaf-nodes when the last move is a capture or a pawn-queen-promotion. The q-search searches ONLY new captures and promotions and does this until the position is quite. The problem is that it really slows-down my engine which is caused by a node explosion, see numbers below (100 > Q-nodes than AB-nodes...):

Time 50569ms
AB-nodes 2489055
Q-nodes 194697863
Evaluated 47588278
NPS 941k
TT 865710/1623347 (34% hits)
TT-usage 38%
Q-TT 20020274/174677589 (10% hits)
Q-TT-usage 100%
Depth 10/42

This is if I do a search using 10 plies, AB-pruning, Transposition-table and a really simple evaluation function. As you can see, the q-search results in a max-depth of 42... I've verified this at ply 6 which seems to give a correct max-depth.

I've read that some people stop the q-search at a certain depth, but then you will run in the horizon-effect again?
I've also read that you can only investigate winning captures, but isn't a capture always a winning move?

Tx!

[hyatt]

I've just implemented quiescence search which is initiated at the leaf-nodes when the last move is a capture or a pawn-queen-promotion. The q-search searches ONLY new captures and promotions and does this until the position is quite. The problem is that it really slows-down my engine which is caused by a node explosion, see numbers below (100 > Q-nodes than AB-nodes...):

Time 50569ms
AB-nodes 2489055
Q-nodes 194697863
Evaluated 47588278
NPS 941k
TT 865710/1623347 (34% hits)
TT-usage 38%
Q-TT 20020274/174677589 (10% hits)
Q-TT-usage 100%
Depth 10/42

This is if I do a search using 10 plies, AB-pruning, Transposition-table and a really simple evaluation function. As you can see, the q-search results in a max-depth of 42... I've verified this at ply 6 which seems to give a correct max-depth.

I've read that some people stop the q-search at a certain depth, but then you will run in the horizon-effect again?
I've also read that you can only investigate winning captures, but isn't a capture always a winning move?

Tx!

Do you have a stand-pat option first? In most positions one side is so far ahead that no captures need to be searched, the static eval is good enough to terminate the search with a beta cutoff...

[H.G.Muller]

It seems your Quiescence Search is badly flawed. Normal numbers when searching all captures are about 7 times as many QS nodes as full-width nodes.

One common reason for QS explosion is poor move ordering, in particular failing to capture the most valuable piece first. This allows the Queens to go on plunder raids. But this usually only happens in special positions. (But the result can be very dramatic, like the search depth falling back from 10-11 plys to 2-3 ply.)

So you probably have a problem with stand pat, like Bob says. If you don't cut off the branch immediately when the static evaluation is above beta, but start to search moves in that case, you will typically get results like this. If the eval is not above beta, it is also very important to raise alpha to the eval before searching any captures.

'Bad captures' are captures that lose material after you acted out the optimal exchange on that square. The capture itself of course always gains material, but if it is QxP, and is followed by PxQ because the P was protected, then it is likely that playing the move will make you end up one Queen down. So many engines prune such moves in QS. But even without such pruning, you should never get results like you are seeing.

[sandermvdb]

No I did not implement a stand-pat check. Does this mean that for every node in the quiescence search tree you check if a cutoff is possible?
I've implemented it as follows and really hope this is ok because now I have about the same number of q-nodes as ab-nodes which saved a lot of time!!

//old fashioned alpha-beta pruning
short score = chessBoard.calculateScore();
if (chessBoard.isWhiteToMove) {
if (score >= beta) {
return score;
}
} else
if (score <= alpha) {
return score;
}

[H.G.Muller]

You should also adapt alpha (or beta, as you don't seem to use negamax) when you do not take the cutoff.

Code: Select all

short score = chessBoard.calculateScore();
if (chessBoard.isWhiteToMove) {
  if (score >= beta) {
    return score;
  }
  if(score > alpha) alpha = score;
} else {
  if (score <= alpha) {
    return score;
  }
  if(score > beta) beta = score;
}

This assumes in the end you return alpha (or beta). If you keep a separate variable bestScore you should make sure you update that too. (So that when no capture is available, or all lose material, you will return the score of the static eval.)