All time spent in quiescent search - why?

[mike_bike_kite]

I have quite a simple chess program. It does an ID search with quiescence with moves done in MVV - LVA order. Everything seems OK but I'm now seeing that the depth in the ID isn't going very deep at all (to save embarrassment I won't say how deep) but the quiescence search (the bit that does all the takes) just goes on and on, sometimes to a depth of 30.

In a given situation it will try the most likely takes first ie pawn x queen before queen x pawn but the problem is it will still attempt these other takes and this is leading to some very deep (and pointless) searches.

I also do a stand pat score with alpha beta cut off before attempting any jumps.

Any ideas?

(I'd appreciate it if you could make your explanations as simple as possible)

[Evert]

I also do a stand pat score with alpha beta cut off before attempting any jumps.

Any ideas?

I assume you meant captures rather than jumps.
Print out one of those long and pointless variants and check that there isn't a point when it should have taken the stand-pat cutoff but didn't. It sounds to me like that is what is happening.
Also check that the move ordering is correct and you're not accidentally sorting in MVA/LVV order (in other words, have the ordering exactly opposite of what you want).

[mike_bike_kite]

Captures yes - I used to play a lot of checkers and the terminology has seeped across

Test position = e5 d4 d6 Nf3 Nf6 Bg5 Be7 Nc3 h6 which leaves white to move with a lot of possible exchanges.

I have a single routine which returns the moves in the order they should be tried (MVV - LVA plus a few other small hints). The move order for white in the above position is the following:

Code: Select all

Move scores at depth 2
   Bg5xf6 (10157) = 170 (in 16ms)
   Pd4xe5 (10077) = 141 (in 62ms)
   Bg5xh6 (9841) = -57 (in 63ms)
   Nf3xe5 (9597) = -154 (in 78ms)
   Bg5-e3 (273) = 57 (in 859ms)
   Bg5-d2 (267) = 24 (in 641ms)
   Bg5-h4 (253) = 23 (in 2547ms)
   Bg5-c1 (251) = -500000 (in 719ms)
Best move Bg5xf6

The MVV-LVA score is shown in brackets while the score returned by the search is shown after the "=" sign. The move Bg5xf6 gets that score because all captures are given a 10000 score to place them in front of normal moves, the victim - attacker score is even in this case, a bonus is given because the attacker is moving from a square that was attacked by a pawn. The score -500000 is a time out score but please note I'm getting the time out when the ID is set at level 2 - something tells me that I'm not gong to be challenging Kasparov just yet.

Here is one continuation with a lot of jumps:
Pd4xe5 Nf6xe4 Bg5xe7 Ne4xc3 Be7xd8 Nc3xd1 Bd8xc7 Pd6xe5 Bc7xb8 Nd1xf2 Bb8xa7 Nf2xh1 Nf3xe5 Ra8xa7 Ne5xf7 Ra7xa2 Nf7xh8 => -693

I haven't worked out how to tell if the stand pat score but I'm working on that now. It sounds like that could be the culprit. Any other ideas welcome of course

Thanks for the quick reply!

[mike_bike_kite]

I found this in the log which shows the computer exchanging a bishop for a pawn (bad) but it doesn't appear to mind. This is obviously wrong but I'm not sure what is correct. I did try comparing the stand pat score against the best so far score 2 levels below (I was guessing) but that suddenly made it start looking 50 moves ahead and it was obviously ignoring everything.

Code: Select all

 Bg5xh6 Pg7xh6 . => -193 (lev=2 bsf=-2000000 AB=2000000) BETTER

The above is part of the log and shows a move bishop takes pawn and then is retaken by another pawn. The "." stands for a stand pat position and this should recognise that it's lost 2 pawns. I'd of thought this would trigger an alpha beta cut off but this isn't the case.

Code: Select all

Bg5xh6 Pg7xh6                            # BxP PxB
.                                        # stand pat evaluation
=> -193                                  # score returned is approx -2 pawns
lev=2                                    # currently at level 2 
bsf=-2000000                             # current best so far score is -2m
                                         # this is the minimum score for white
                                         # as no moves have been tried yet at this level
AB=2000000                               # best score so far at level below
                                         # this is min score for black so this is 1st move

BETTER                                   # the move is the best move so far but only because 1st move

What should I be comparing against and under what conditions should I give up on that line of search. I have an initial score for each level (+/-2m), I have the best score so far for each level and I have the current score to work with.

[Evert]

I found this in the log which shows the computer exchanging a bishop for a pawn (bad) but it doesn't appear to mind. This is obviously wrong but I'm not sure what is correct. I did try comparing the stand pat score against the best so far score 2 levels below (I was guessing) but that suddenly made it start looking 50 moves ahead and it was obviously ignoring everything.

I don't really follow everything you just said, but how do you handle the stand pat?
The correct way to do it is to calculate the static score at the top of the search function (before even generating moves), which should be used to raise alpha. If it causes a beta cutoff you return the static score immediately before trying any captures.

[Don]

I have quite a simple chess program. It does an ID search with quiescence with moves done in MVV - LVA order. Everything seems OK but I'm now seeing that the depth in the ID isn't going very deep at all (to save embarrassment I won't say how deep) but the quiescence search (the bit that does all the takes) just goes on and on, sometimes to a depth of 30.

In a given situation it will try the most likely takes first ie pawn x queen before queen x pawn but the problem is it will still attempt these other takes and this is leading to some very deep (and pointless) searches.

I also do a stand pat score with alpha beta cut off before attempting any jumps.

Any ideas?

(I'd appreciate it if you could make your explanations as simple as possible)

There are several issues that perhaps come to mind.

1. The option to stand pat means you stop looking at captures. Its' not a null move.
2. If score >= beta stop searching before generating or looking at captures.
3 You search will explode like crazy if the move ordering is not good.

Make sure your move ordering is correct. Generate captures of higher piece before lower piece and when it's a even generate capture BY lower valued piece first. i.e. PxQ before QxQ but QxN before PxR

You can get a huge reduction by not generating losing captures but this requires a see() function. There is a shortcut that will help a lot however:

If capture is a down-capture, and the captured piece is defended by a pawn, skip it.

This rule picks up a subset of the cases that see() does.

[tpetzke]

i.e. PxQ before QxQ but QxN before PxR

why QxN before PxR ?

QxN will probably have a SEE of 0 or worse
PXR will have a SEE of 400 or better

why should I perform the queen capture first. Also in a MVV order the rook comes before the knight, it should be removed first.

It somehow does not look right capturing the knight first

Thomas...

[Don]

i.e. PxQ before QxQ but QxN before PxR

why QxN before PxR ?

QxN will probably have a SEE of 0 or worse
PXR will have a SEE of 400 or better

why should I perform the queen capture first. Also in a MVV order the rook comes before the knight, it should be removed first.

It somehow does not look right capturing the knight first

Thomas...

I got it backwards, sorry. I probably meant QxR before PxN which for many people is counter-intuitive and why I wished to state an example. It has been discussed many times on this forum why a bigger downcapture should be tried before a small up-capture and even why this should be done despite the SEE score, except in cases where QxR actually is losing.

[tpetzke]

ok, makes sense now. Thanks

It seems this is then what I do. (searching captures in decreasing victim order, for multiple attacks to the same victim take the least valuable attacker first. If a capture might be losing verify via SEE and if SEE indicates a value < 0 skip it).

Thomas...

[hgm]

Something seems wrong here:

[d]rnbqk2r/ppp1bpp1/3p1n1p/4p1B1/3PP3/2N2N2/PPP2PPP/R2QKB1R w KQkq - 0 6

Pd4xe5 Nf6xe4 Bg5xe7 Ne4xc3 Be7xd8 Nc3xd1 Bd8xc7 Pd6xe5 Bc7xb8 Nd1xf2 Bb8xa7

Upto d6xe5 everything makes sense, because both sides have been capturing equal value on each move. White took the lead each time, so that black had to recapture and could not afford to stand pat without incurring a loss. After the recapture it was neutral again, so that white had to try something to see if he could do better.

But after Bxb8 Nxf2 black did not equalize, and captured a Pawn after losing a Knight. So white is at +2 here by standing pat, which should be above beta, and thus cause an immediate cuttoff. So it should never get to searching Bxa7.

[d]rBb1k2r/pp3pp1/7p/4p3/8/5N2/PPP2nPP/R3KB1R w KQkq - 0 11

Kxf2 is another move that should have been searched before Bxa7, and should also have produced a beta cutoff, if the stand pat had not done that already.