Quiescence - Check Evaluation and Depth Control

[Cheney]

Hi,

I am at the point of building in a qsearch, read a few docs, reviewed a fair amount of posts, and I am puzzled with something going on.

Basically, what I understand is in the normal alphabeta when depth is zero, call the qsearch to playout captures until there are no captures left. This I did. I followed the model on CPWiki.

I also read about having qsearch validate check on the king and if true to then call the alphabeta with depth of 1. This is where the time to complete a search increased drastically. This is because at the end of that alphabeta, qsearch is played again, which can lead to another iteration of alphabeta, and so on. Qsearch is reaching depths around 30 ply.

Is this expected or did I do something wrong?

I am thinking the following:

1. Do not have it validate check . From what I read, this is not a good idea.

2. Validate check and if check is true then call the alphabeta but set a flag so that the alphabeta only makes a move out of check and does not call qsearch again.

3. Implement SEE. It appears SEE will not only sort the capture moves but also only play out the ones that win material. If implemented correctly, it may cut back on the ply.

4. Apply a depth control in qsearch so that it stops at a certain depth.

Thank you for reading and sharing your opinions
-Cheney

[syzygy]

Basically, what I understand is in the normal alphabeta when depth is zero, call the qsearch to playout captures until there are no captures left.

Not quite. Before playing out the captures in a particular position, first see if the static evaluation is already >= beta. If it is, then return beta (or the static evaluation value). This is called standing pat. Maybe you already do this (the CPW explains it quite well), but if you don't, there is the solution to your problem.

I also read about having qsearch validate check on the king and if true to then call the alphabeta with depth of 1. This is where the time to complete a search increased drastically. This is because at the end of that alphabeta, qsearch is played again, which can lead to another iteration of alphabeta, and so on.

Correct.

Qsearch is reaching depths around 30 ply.

I suppose 30 ply is possible in some positions (7 / 8 checking captures from both sides with 15 evasions), but it should be quite rare. Normally a long string of captures by one side should bring that side in a position where standing pat keeps it above beta.

I am thinking the following:

1. Do not have it validate check . From what I read, this is not a good idea.

Indeed not a good idea.

2. Validate check and if check is true then call the alphabeta but set a flag so that the alphabeta only makes a move out of check and does not call qsearch again.

Also not a good idea.

3. Implement SEE. It appears SEE will not only sort the capture moves but also only play out the ones that win material. If implemented correctly, it may cut back on the ply.

Good idea, but I would suggest to leave this for a later time.

4. Apply a depth control in qsearch so that it stops at a certain depth.

This is a possibility, but first make sure you have no bugs.

[Cheney]

This is called standing pat. Maybe you already do this

Thanks - yes, I believe I am doing this. I basically followed the pseudo code from CPW's site but added the check validation just before "if eval >= beta return beta;". Here's a sample:

Code: Select all

if(isMyKingChecked())
  return alphabeta(ply, 1 /*depth*/, alpha, beta);
int eval = Evaluate();
if( eval >= beta )
  return beta;
if( eval > alpha)
  alpha = eval;

7 / 8 checking captures from both sides with 15 evasions

I am hitting up to 30 ply (I believe it is more like 26) when I perform a search with a depth of 7 from a regular starting position; depth 5 does not appear to go as deep.

[Sven]

Code: Select all

if(isMyKingChecked())
  return alphabeta(ply, 1 /*depth*/, alpha, beta);
int eval = Evaluate();
if( eval >= beta )
  return beta;
if( eval > alpha)
  alpha = eval;

Does your regular alphabeta() have check extension? If yes then could it be possible that you do a "double check extension" at depth=0?

Sven

[Sven]

I also read about having qsearch validate check on the king and if true to then call the alphabeta with depth of 1.

That is basically correct.

3. Implement SEE. It appears SEE will not only sort the capture moves but also only play out the ones that win material. If implemented correctly, it may cut back on the ply.

As already mentioned, you might postpone that for later. But I'd like to correct a few points:
- SEE is mostly used to skip losing captures. Both winning *and* equal captures are kept, though.
- SEE can also be used for move ordering but several people have reported that MVV/LVA is slightly better than SEE for move ordering.
- After all, SEE is an optimization, it will not let your program explode in strength suddenly.

Thinking again about your search explosion, I'd suggest that you switch off the "check validation" again to test whether your program behaves correctly without it. How many percent of all nodes are "qsearch nodes"? If you observe much more than 80-90% QS nodes then most likely something else is wrong, maybe your QS move ordering? Are you using MVV/LVA?

Sven

[lucasart]

Chris,

I don't know what your qsearch looks like, but here are some of the common pitfalls, to wath out for:

=> the basics:
- always consider the stand pat score, except when you're in check. something like

Code: Select all

if (!in_check) {
  // consider the stand pat option when we're not in check
  if (static_eval > best_score) {
    best_score = static_eval;  // update best_score (I'm using fail soft here, it would be a little sipler in fail hard, with only alpha to update)
    if (static_eval > alpha) {
      alpha = best_score;
      if (alpha >= beta)
        return alpha;  // static eval fails high
    }
  }
}

- when you're in check, you generate all legal moves (not just captures). if there aren't any you need to return a "mated in ply" score

=> optimizations:
- SEE Pruning: when not in check, prune captures that have a < 0 SEE value (even if those captures are checks, but unless they are discovered checks perhaps, where SEE doesn't make sense). Without that you'll find positions where your qsearch will take forever to calculate: it really prunes a lot (and makes some mistakes too, but the ratio gain/pain is largely favorable).
- sort the captures by MVV/LVA or SEE. They score about equally (in terms of minimizing the number opf nodes), but MVV/LVA is faster to calculate, so in the end it seems to be the best tradeoff for captures in the qsearch (though use SEE in the search, where the tradeoff quality/speed is more geared towards quality, as the subtree is larger).
- do not generate under promotions, they are completely useless (and harmful as they inflate the tree) in a qsearch. However they are useful in the normal search.
- at depth zero, generate (non capturing) checks. What I do is only direct checks with pieces (not pawns), because the code to generate them was easier to write. In combination with a hash table, this means that the depth to enter in your hash table entries is going to be (depth < 0 ? -1 : 0), watch out for that too!

[ZirconiumX]

I also read about having qsearch validate check on the king and if true to then call the alphabeta with depth of 1. This is where the time to complete a search increased drastically. This is because at the end of that alphabeta, qsearch is played again, which can lead to another iteration of alphabeta, and so on. Qsearch is reaching depths around 30 ply.

Is this expected or did I do something wrong?

Some people do evaluate check. How they do it is implementation-specific. Some have a move-evasion generator that is used. Others rely on the fact that non-legal moves get taken back, and simply increment depth by one (like Fruit). The one that you are using attempts to catch checkmates, which I'd say isn't worth the effort. But one thing that seems to be common is to not evaluate stand-pat when in check.

1. Do not have it validate check . From what I read, this is not a good idea.

Bad idea. A QSearch must know about check. I'd say have a look at Fruit's QS which is quite simple about checks.

2. Validate check and if check is true then call the alphabeta but set a flag so that the alphabeta only makes a move out of check and does not call qsearch again.

This defeats the point of Alpha-Beta, where optimal moves are searched for.

3. Implement SEE. It appears SEE will not only sort the capture moves but also only play out the ones that win material. If implemented correctly, it may cut back on the ply.

It will reduce branching factor, if not ply. I'd recommend you add this to your todo list, as (on Stockfish) SEE can be used for pruning in the main search.

4. Apply a depth control in qsearch so that it stops at a certain depth.

Some people have done that, but it defeats the point of QSearch - because your engine will still have a horizon effect.

Matthew:out

[Cheney]

Thank you again

If you would like to see the code, I will post the alphabeta with the qsearch maybe that will help.

In the alphabeta, I do not have check validation except to make sure a move made is legal and does not leave a king in check. By "extension", if I understand that correctly where I woudl extend a ply when in check, I am not extending this one additional ply.

At any ply, when all moves are made, before returning alpha, I do have a 50 move validation plus a checkmate/stalemate validation based on if no moves were valid.

At this time, in my basic alphabeta, I am not sorting. I have made separeate alphabetas to learn about sorting; I have one that moves the PV first when retaining PVs between iterations; I have another where I tried using the heruistics[64,64] move tables but that is not sinking in yet .

In the qSearch, I created a move generator for captures. So far, it orders only on attackers(LVA) - it generates captures for pawns first, knights, and so on. There is no analysis on what that piece is is being captured, which I would believe would be MVV/LVA.

[Sven]

Thank you again

If you would like to see the code, I will post the alphabeta with the qsearch maybe that will help.

In the alphabeta, I do not have check validation except to make sure a move made is legal and does not leave a king in check. By "extension", if I understand that correctly where I woudl extend a ply when in check, I am not extending this one additional ply.

At any ply, when all moves are made, before returning alpha, I do have a 50 move validation plus a checkmate/stalemate validation based on if no moves were valid.

At this time, in my basic alphabeta, I am not sorting. I have made separeate alphabetas to learn about sorting; I have one that moves the PV first when retaining PVs between iterations; I have another where I tried using the heruistics[64,64] move tables but that is not sinking in yet .

In the qSearch, I created a move generator for captures. So far, it orders only on attackers(LVA) - it generates captures for pawns first, knights, and so on. There is no analysis on what that piece is is being captured, which I would believe would be MVV/LVA.

You need to order moves to get an acceptable tree size. In qsearch it is also crucial to start with capturing the queen, if possible, since that will already avoid most variants where a queen goes wild all over the board. Only moving the PV first is by far insufficient since most nodes are non-PV nodes. Implement MVV/LVA everywhere (full-width search + qsearch), and you will see how your search tree shrinks drastically. One of many possible examples would be an implementation like this, including only MVV/LVA for captures and promotions:

Code: Select all

static inline int mvvLva(PieceType movingPiece, PieceType capturedPiece, PieceType promotionPiece)
{
    return 64 * capturedPiece + 8 * promotionPiece - movingPiece;
}

static void evaluateMoves(Board const & b, MoveList & moveList)
{
    uint nMoves(moveList.size());
    for &#40;uint i = 0; i < nMoves; i++) &#123;
        MoveListEntry & m = moveList&#91;i&#93;;
        PieceType capturedPiece = b.piece&#40;m.to&#40;)) + Pawn * &#40;m.to&#40;) == b.epTarget&#40;));
        if &#40;capturedPiece + m.prPiece&#40;) > NoPiece&#41; &#123;
            m.setValue&#40;mvvLva&#40;b.piece&#40;m.from&#40;)), capturedPiece, m.prPiece&#40;)));
        &#125;
    &#125;
&#125;

static Move * nextMove&#40;MoveList & moveList, uint i&#41;
&#123;
    if &#40;i >= moveList.size&#40;)) &#123;
        return 0;
    &#125;
    int bestValue = moveList&#91;i&#93;.value&#40;);
    for &#40;uint j = i + 1; j < moveList.size&#40;); j++) &#123;
        if &#40;moveList&#91;j&#93;.value&#40;) > bestValue&#41; &#123;
            bestValue = moveList&#91;j&#93;.value&#40;);
            moveList.swap&#40;i, j&#41;;
        &#125;
    &#125;
    return &&#40;moveList&#91;i&#93;);
&#125;

// move loop within search function
&#123;
    // ...
    generateAllCaptures&#40;b, moveList&#41;;
    evaluateMoves&#40;b, moveList&#41;;
    for &#40;Move * pMove = nextMove&#40;moveList, i&#41;; pMove != 0; pMove = nextMove&#40;moveList, ++i&#41;) &#123;
        Move const & m = *pMove;
        b.makeMove&#40;m&#41;;
        // ...
    &#125;
    // ...
&#125;

"nextMove()" fetches the next move from the move list with the i-th highest move evaluation by comparing all move list entries behind i with the i-th and, if finding a better value, swapping them with the i-th entry. This avoids completely sorting the whole move list even if only the first move will actually be tried (and causes a beta cutoff). But this is an optimization that can also be postponed for later since it only has an effect on NPS but not on the tree size.

Combine this with your existing PV-based ordering and, as a next step, killer moves (the latter not in qsearch), and your tree will already be a lot smaller than before. This shows the relative importance of ordering captures as compared to ordering quiet moves, even though a strong engine needs to do the latter as well. A further improvement that has already been mentioned is to lower the priority of "losing captures" (e.g. queen takes defended knight) within full-width search, and to even skip them completely in qsearch.

Sven

[Cheney]

Thanks Sven

I did go ahead and complete the MVV/LVA by adding a "sortscore" member to captures (actually, all moves). For captures, I basically subtracted the captured piece's value from the attacker's value. I wrote a heap sort to sort these and immediately saw a decrease in qsearch nodes plus cut 20 seconds off the search time which is what was alarming me to begin with.

I played a little more with implementing this in the regular search and that is where I am at now - trying to spot the differences in nodes visited, cut, and possibly enhancing sorting.

I read somewhere about selecting a move instead of a full sort. This is what you are referring to with the nextmove, correct? I had something like this with the history heruistic but I am also trying to grasp that as well. I'll try selective move out

As for killer, I am not there yet. I was thinking about TT since I have the Zobrist hash working but the TT I tried was not making sense either... but that is another day and thread

I'll continue on this path with the sorting and your suggestions, thanks for your input and guidance