verminox wrote:In the early version of my engine, all i did at leaf nodes that are not quiet was something like SEE. I just recursively found the least valuable attacker on the move square and got the result of the exchange. However, I realised many flaws with this method. For example, exchanges need not necessarily be on the same square, and checks/promotions can't be extended in this way.
I've read a lot about quiescence search and realised it's importance but I don't really get why it has to be a whole new routine (function). Both the
CPWiki and
Wikipedia show quiescence search as a completely different routine, just as it were a whole new component of the search.
From what I understand, quiescence searching just means "at a leaf node, if the last move was not quiet, then search further". From this, I deduced the following logic:
Code: Select all
search(alpha, beta, depth)
{
if( depth == 0 )
{
if( is_quiet(last_move) )
return static_eval();
else
depth = 1;
}
foreach ( move in legal_moves )
{
/* standard alpha-beta, perform the move and search to (depth-1) */
}
}
In this way, all violent leaf nodes will get searched one ply deeper. If the node at the next ply was quiet, the score is returned from the general AB-search or else that particular node is extended even further.
Is there much else to quiescence search? Are there things to do in the quiescence search that you would not do in a normal alpha-beta search? What is wrong with my logic?
It's mainly just semantics. The classic quiescence search is a search than contains only captures and each side can consider a non-move as option. This of it as just another move, except that you evaluate the position and stop searching when you choose that option. Sometimes this is called "standing pat."
Example: I do a 7 ply search and now I'm in quies. On the 8th ply, I have 3 captures, QxP, RxN and NxP. I have 4 options here, play one of the 3 capture moves, or stop searching (after calling the evaluator.)
The search chooses which is best, doing nothing, or making one of those captures. Each possibility is explored (but the doing nothing option is explored only by calling the static evaluation function.)
Since there is a good chance all 3 captures are blunders, the search might choose to score the position and stop searching. But of course one of those captures may be advantageous too, but the search will figure that out for you.
The assumption of such a "stand pat" search is that if it's your turn to move, you can do no worse than scoring the position as is, but you might very well do better by trying a capture. That assumption is not always true of course, but you have to stop searching somewhere.
That is the short version. In practice, some program explore other moves, such as non-capture checks and so on. If a capture puts a king in check, you might choose to look at out of check moves (but some program don't bother to do this in order to save time.) If you ignore checks, you can simply apply the same stand pat logic and try just captures or stop. Just because you are in check doesn't mean you lose, most of the time you have a safe response.
