Quiescence node explosion

Code, algorithms, languages, construction...

Quiescence node explosion

Postby sandermvdb » Wed Jun 01, 2016 4:05 pm

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!
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: Quiescence node explosion

Postby hyatt » Wed Jun 01, 2016 6:58 pm

sandermvdb wrote: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...
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: Quiescence node explosion

Postby H.G.Muller » Wed Jun 01, 2016 7:38 pm

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.
H.G.Muller
 
Posts: 179
Joined: Sun Jul 14, 2013 10:00 am

Re: Quiescence node explosion

Postby sandermvdb » Wed Jun 01, 2016 7:44 pm

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;
}
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: Quiescence node explosion

Postby H.G.Muller » Thu Jun 02, 2016 8:47 am

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.)
H.G.Muller
 
Posts: 179
Joined: Sun Jul 14, 2013 10:00 am


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: Bing [Bot] and 2 guests