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
Quiescence - Check Evaluation and Depth Control
Moderators: hgm, Rebel, chrisw
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Quiescence - Check Evaluation and Depth Control
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.Cheney wrote: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.
Correct.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.
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.Qsearch is reaching depths around 30 ply.
Indeed not a good idea.I am thinking the following:
1. Do not have it validate check . From what I read, this is not a good idea.
Also 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.
Good idea, but I would suggest to leave this for a later time.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.
This is a possibility, but first make sure you have no bugs.4. Apply a depth control in qsearch so that it stops at a certain depth.
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: Quiescence - Check Evaluation and Depth Control
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:This is called standing pat. Maybe you already do this
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;
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.7 / 8 checking captures from both sides with 15 evasions
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Quiescence - Check Evaluation and Depth Control
Does your regular alphabeta() have check extension? If yes then could it be possible that you do a "double check extension" at depth=0?Cheney wrote: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;
Sven
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Quiescence - Check Evaluation and Depth Control
That is basically correct.Cheney wrote:I also read about having qsearch validate check on the king and if true to then call the alphabeta with depth of 1.
As already mentioned, you might postpone that for later. But I'd like to correct a few points:Cheney wrote: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.
- 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
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Quiescence - Check Evaluation and Depth Control
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
- 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!
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
}
}
}
=> 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!
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Quiescence - Check Evaluation and Depth Control
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.Cheney wrote: 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?
Bad idea. A QSearch must know about check. I'd say have a look at Fruit's QS which is quite simple about checks.
1. Do not have it validate check . From what I read, this is not a good idea.
This defeats the point of Alpha-Beta, where optimal moves are searched for.
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.
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.
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.
Some people have done that, but it defeats the point of QSearch - because your engine will still have a horizon effect.
4. Apply a depth control in qsearch so that it stops at a certain depth.
Matthew:out
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: Quiescence - Check Evaluation and Depth Control
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.
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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Quiescence - Check Evaluation and Depth Control
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:Cheney wrote: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.
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 (uint i = 0; i < nMoves; i++) {
MoveListEntry & m = moveList[i];
PieceType capturedPiece = b.piece(m.to()) + Pawn * (m.to() == b.epTarget());
if (capturedPiece + m.prPiece() > NoPiece) {
m.setValue(mvvLva(b.piece(m.from()), capturedPiece, m.prPiece()));
}
}
}
static Move * nextMove(MoveList & moveList, uint i)
{
if (i >= moveList.size()) {
return 0;
}
int bestValue = moveList[i].value();
for (uint j = i + 1; j < moveList.size(); j++) {
if (moveList[j].value() > bestValue) {
bestValue = moveList[j].value();
moveList.swap(i, j);
}
}
return &(moveList[i]);
}
// move loop within search function
{
// ...
generateAllCaptures(b, moveList);
evaluateMoves(b, moveList);
for (Move * pMove = nextMove(moveList, i); pMove != 0; pMove = nextMove(moveList, ++i)) {
Move const & m = *pMove;
b.makeMove(m);
// ...
}
// ...
}
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
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: Quiescence - Check Evaluation and Depth Control
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
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