I was just reading a webpage from 2004 that looks to have been created as part of somebody's master thesis. I'm intrigued by the author's section on Quiescence Searching where he says the following (emphasis mine):
Since the depth of the min-max search is limited, problems can occur at the frontier. A move that may seem great may actually be a disaster because of something that could happen on the very next move. Looking at all these possibilites would mean increasing the ply by 1, which is not the solution, as we would need to extend it to arbitrarily large depths. The goal is thus to search the tree until "quiescent" positions are found - i.e ones that don't affect the current positions too much (most maneuvers in chess result in only slight advantages or disadvantages to each player, not big ones at once). Hence, looking at higher depths is important only for significant moves - such as captures. Consider for example a move in which you capture the opponent's knight with your queen. If that is the limit of your min-max search, it seems to be a great move - you receive points for capturing the opponent's knight. But suppose that in the very next move your opponent can capture your queen. Then the move is clearly seen as bad, as trading a queen for a knight is to your disadvantage. Quiescence searching will be able to detect that by looking at the next move. Again, it doesn't need to do this for every move - just for ones that affect the score a lot (like captures).
One important caveat in the quiescence searching algorithm is that it should only look at moves that became available because of the current move being made. Consider the following situation. Your bishop is threatened by an opponent's pawn, and you have the ability to capture the opponent's knight with a different pawn. Suppose the algorithm is looking only 1 ply ahead, and is examining some non-capturing move. It won't notice that the bishop can be captured in the next turn. But what happens when it's examining the knight-capturing move with quiescence. It will see that the opponent can take your bishop, which will even out the piece possession, making the move not seem as good. So it's highly likely that the algorithm would pick a move other than capturing the knight, thus needlessly losing the bishop in the next turn. To prevent this, the algorithm must look at ONLY those moves available because of its own move. Since the opponent's "pawn captures bishop" was available regardless of whether you capture the knight or not, it should be ignored.
I've not seen anywhere else add this caveat about only searching newly available moves, and I'm not quite convinced by the provided example. Is this something that should actually be used in quiescent search, or is the author of this page incorrect in this stipulation?
To me none of it sounds correct. For example every move changes the situation on the board and any previously non dangerous move can become dangerous. And most new moves are innocuous unless they capture the moving piece but then it's included anyway because it is a capture.
If you want to improve Qsearch then find a way to include forks and skewers. Or at least check before entering Qsearch that there are no forks and skewers.
Or try the following idea that no one will comment on no matter how many times I post about it.
In Qsearch allow each side a single non capture move at any node in the search line. Then all such one move threats will be found and 99.99% of Qsearch oversights will be avoided. Depth will be reduced but regained in the Qsearch itself.
That was my impression too. It seemed interesting because I see a lot of discussion about how the majority of a search is spent in the Quiescent Search, and the strategy discussed on that page seemed like it would severely limit the number of nodes that are explored. However, the example really doesn't make sense to me, especially the referenced image. If anything, it seems to indicate a need to consider all captures, not just ones made available due to the prior move (surely Bxe7 is better than Ngxe7 because of the threat to the bishop on b4, but this could be missed at depth 1 if the quiescent search does not look at moves that were possible before the prior move). Maybe the author thinks that a quiescent search is only performed after captures?
In regards to your suggestion, it sounds interesting. My immediate reaction is that the cost of evaluating the extra nodes might not overcome the benefit of identifying two-move tactics better. Regardless, it will be a little bit before my engine is at a place where testing that would be feasible, but I'll keep it in mind to try out.
I'm about 2 weeks into development of my engine, and it can reasonably evaluate to a depth of 6 if I limit the Quiescent Search extension to 5 ply. It also doesn't quite implement UCI yet, which makes testing it a bit tedious, so that's my next step. That was what I had initially started with, but then I realized it would be way easier to add the interface once I had some idea of what it's connecting to. I was just looking into Quiescent Search more because it was reporting a mate in 2 rather than 3 for a particular position where the mate would have been identified in the QSearch (but it was reported properly after the first move was made), and that's when I found the page I linked to which suggested something that I hadn't seen elsewhere. It didn't answer any questions that I had, but it raised some new ones.
I think that for orthodox Chess it is well established now that the best way to search for quiescence is by searching all captures with SEE >= 0. Bad captures (SEE < 0) can be pruned.
There are other chess variants, though (especially those with very mobile pieces), where the above prescription leads to a disastrous search explosion. So that you would not spend 95% of the time in QS, but something like 99.999%. In other words, you might not even be able to finish a one-ply search (+QS) before the cold-turkey timeout occurs. In such variants better selectivity is needed.
Focusing on new moves would be a useful method in that case. Even though existing moves (which apparently struck out in an earlier turn,or you would not have reached the current node) can get an improved score because of what happened since then (e.g. the piece they can capture might have lost its protection in an earlier trade), this is relatively unlikely. So pruning these causes fewer errors than pruning the new moves.
Note that moves can be new not only because the preceding (opponent ply), but also because of your own ply before that. The opponent's move enables recapture or pin enforcement, your own move enabled discovered attacks and plunder.
In the AI of the Interactive Diagram, which should be able to play arbitray chess variants, QS is a relative notion. Recapture of a higher-valued or unprotected piece is always searched. Non-new captures take a full ply, and are thus only searched in the full-width search. The search works with fractional plies, however, and a node is considered QS (so it can stand pat) when the remaining depth is less than 1 ply. An equal or HxL recapture of a protected piece would take half a ply, just as any other new capture. This way non-trivial exchanges get into view more slowly, without the risk fo a search explosion.
