All time spent in quiescent search - why?

[Don]

I suspect he has the stand pat rule wrong somehow.

Essentially you can STOP searching if the score before generating any moves is >= beta, but even if that is not the case you STILL have the option to STOP searching if you don't like any of the captures.

So the FIRST move you should try is the "stand pat" move, in other words NO move and treat this as if it were a searched subtree - a fully searched move that returned the stand pat score and can be accepted if it's "better" than the other real captures. Which also means that it can update alpha if appropriate.

My guess is that this is what you have been missing. You can stand pat if it gives you a beta cutoff, but you can also stand pat even if it doesn't (if that is better than trying other moves.)

Don

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.

[bob]

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)

Couple of things that I use.

(1) use SEE and do not search captures with SEE < 0, as those are generally bad.

(2) use MVV/LVA ordering, so that you get rid of the queens and rooks first, since they tend to go on feeding forays and drive the search deeper as the queens eat away on opposite sides of the board.

(3) qsearch is always going to be a major part of the tree, because of the exponential shape the tree has. You ALWAYS get to the qsearch at the end of every normal branch you search, and then you add on captures. It only takes a couple to make the q-search examine 90% of the total nodes searched.

[lucasart]

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)

could you show us your quiescent search function ? it's hard to say what you're doing wrong otherwise. the slightest thing can be dramatic... i have experience these problems before, so i know the story

[lucasart]

(2) use MVV/LVA ordering, so that you get rid of the queens and rooks first, since they tend to go on feeding forays and drive the search deeper as the queens eat away on opposite sides of the board.

That's interesting ! I naively used SEE ordering for captures and promotions, whether in the search or in the qsearch. Does it really make a big difference on the qsearch ?

[bob]

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!

How do you compute the scores? for MVV/LVA, I use a very simple formulation:

score = (captured << 7) - moving_piece;

I use the << 7 because a pawn = 100. That makes the captured piece dominate the value.

For RxQ I would get score = 900 * 128 - 500 = 114700
for PxQ I would get score = 900 * 128 - 100 = 115100
for QxP I would get score = 100 * 128 - 900 = 11900

sorted into descending order, I get PxQ, RxQ, QxP. The captured piece dominates, the value of the capturing piece inversely affects the score...

Next, are you doing "stand pat" correctly? First thing you do in quiesce() is compute the static eval. If it is >= beta, or <= alpha, you return instantly and don't look at any captures. Otherwise, you set alpha = the stand-pat score you just computed, and search captures that appear reasonable. Then you return the best score you saw, which will often be the stand-pat score if there are no good captures.

[bob]

(2) use MVV/LVA ordering, so that you get rid of the queens and rooks first, since they tend to go on feeding forays and drive the search deeper as the queens eat away on opposite sides of the board.

That's interesting ! I naively used SEE ordering for captures and promotions, whether in the search or in the qsearch. Does it really make a big difference on the qsearch ?

It makes a difference. Sometimes large, sometimes not, but it is significant...

[Don]

(2) use MVV/LVA ordering, so that you get rid of the queens and rooks first, since they tend to go on feeding forays and drive the search deeper as the queens eat away on opposite sides of the board.

That's interesting ! I naively used SEE ordering for captures and promotions, whether in the search or in the qsearch. Does it really make a big difference on the qsearch ?

Use see() for move ordering is perfectly legit, but if your tree is exploding I would suspect that it is wrong.

I think most program uses see only for pruning bad moves and it's understood that MVVLVA is slightly superior to see() for move ordering, not by much but by a little. This is definitely counter-intuitive. But it's a huge win to pruning losing captures in quies.

[sje]

First thing you do in quiesce() is compute the static eval. If it is >= beta, or <= alpha, you return instantly and don't look at any captures.

If the stand pat score is less than or equal to alpha, it might still be improved by some gainer (capture/promotion) move.

A better test at the start of a quiescence node would be:

Code: Select all

if (&#40;stand_pat_score + best_possible_gain&#40;position&#41;) <= alpha&#41; then return alpha;

And for each quiescence node move:

Code: Select all

if (&#40;stand_pat_score + best_possible_gain&#40;move&#41;) <= alpha&#41; then skip_move;

[mike_bike_kite]

How do you compute the scores? for MVV/LVA, I use a very simple formulation:

score = (captured << 7) - moving_piece;

I use the << 7 because a pawn = 100. That makes the captured piece dominate the value.

For RxQ I would get score = 900 * 128 - 500 = 114700
for PxQ I would get score = 900 * 128 - 100 = 115100
for QxP I would get score = 100 * 128 - 900 = 11900

sorted into descending order, I get PxQ, RxQ, QxP. The captured piece dominates, the value of the capturing piece inversely affects the score...

Each move at a given level is assigned a MVV/LVA score. The scoring method is now similar to your own ie

• Jumps -> 10000 + victim * 1000 - attacker * 100
  if from square attacked by pawn -> +20
  if to square attacked by pawn -> -20
  prefer centre squares over edge -> range 0-30
  castling -> +40
  checking the opponent -> +70
  moving pawns near to promotion -> range 40-90
  killer mover -> +500
  minor pieces to centre -> range 0-30

This MVV/LVA score is shown in brackets after the moves for the given position. So for the first move below the MVV/LVA score is calculated as 10000 + 3*1000 - 3*100 +/- other things for centre and squares being defended:

Code: Select all

   Move (MVV/LVA order) = actual score (time)
   Bg5xf6 (12557) = 297 (in 16ms)
   Pd4xe5 (10877) = 316 (in 203ms)
   Bg5xh6 (10561) = -5 (in 15ms)
   Nf3xe5 (10317) = -59 (in 16ms)
   Bg5-e3 (273) = 120 (in 78ms)
   Bg5-d2 (267) = 122 (in 110ms)
   Bg5-h4 (253) = 321 (in 171ms)
   Bg5-c1 (251) = 119 (in 94ms)
   Bg5-f4 (153) = -295 (in 0ms)
   Pd4-d5 (117) = -250 (in 16ms)
   Bf1-b5 (97) = 592 (in 62ms)
   Nc3-d5 (37) = 118 (in 172ms)
   Bf1-d3 (33) = -98 (in 16ms)
   Bf1-c4 (33) = -59 (in 15ms)
   Bf1-e2 (27) = -98 (in 0ms)
   Pg2-g4 (27) = -209 (in 63ms)
   Pg2-g3 (27) = -162 (in 16ms)
   Pb2-b4 (27) = -195 (in 0ms)
   Pb2-b3 (27) = -177 (in 15ms)
   Nf3-d2 (27) = -318 (in 0ms)
   Nc3-e2 (27) = -203 (in 31ms)
   Nc3-b5 (27) = -159 (in 16ms)
   Ph2-h3 (21) = -140 (in 16ms)
   Pa2-a3 (21) = -151 (in 15ms)
   Ph2-h4 (13) = -186 (in 32ms)
   Pa2-a4 (13) = -176 (in 15ms)
   Nf3-h4 (13) = -254 (in 16ms)
   Nc3-a4 (13) = -208 (in 15ms)
   Nf3-g1 (5) = -312 (in 16ms)
   Nc3-b1 (5) = -265 (in 31ms)
   Rh1-g1 (0) = -179 (in 16ms)
   Ke1-e2 (0) = -186 (in 0ms)
   Ke1-d2 (0) = -267 (in 0ms)
   Qd1-c1 (0) = -202 (in 16ms)
   Qd1-b1 (0) = -212 (in 0ms)
   Qd1-d2 (0) = -167 (in 15ms)
   Qd1-d3 (0) = -204 (in 16ms)
   Qd1-e2 (0) = -176 (in 0ms)
   Ra1-b1 (0) = -161 (in 0ms)
   Ra1-c1 (0) = -161 (in 15ms)
   Bf1-a6 (-109) = -100 (in 32ms)

Next, are you doing "stand pat" correctly? First thing you do in quiesce() is compute the static eval. If it is >= beta, or <= alpha, you return instantly and don't look at any captures. Otherwise, you set alpha = the stand-pat score you just computed, and search captures that appear reasonable. Then you return the best score you saw, which will often be the stand-pat score if there are no good captures.

I doubt it. I don't really have alpha and beta values stored separately. I just store best scores for each level, setting it to a minimum value before starting a search and then storing the best scores as they come in. I do do alpha beta cut offs but I use the scoring mentioned. With the stand pat scores I do this before trying any moves and then treat the score returned as a normal move - which means it can produce an alpha cut off.

My results are better now in that I'm getting past a depth 2 search but sadly I'm only getting a depth 3 search now. The quiescent search used to go to depths of 30 but now is reaching around 20.

I've been attempting to understand these posts, change my code, debug and post back but I've been a little overwhelmed! I've decided to try and respond to each question individually where I can.

[Aleks Peshkov]

I don't really have alpha and beta values stored separately. I just store best scores for each level, setting it to a minimum value before starting a search and then storing the best scores as they come in. I do do alpha beta cut offs but I use the scoring mentioned. With the stand pat scores I do this before trying any moves and then treat the score returned as a normal move - which means it can produce an alpha cut off.

I doubt you treat alpha-beta (even minimax correctness is questionable) properly.