Q-checks was once a pain for me because it was a huge hit in new code for very little gain. But in the end, I accepted that the gain was good enough. However, getting there had these hurdles, which could be true with you now:
1. The q-check code was never executed, even when it had to be. This depends on how you decide its execution. In my case, it was based on the remaining depth. I was counting on the fact that there would be at least -1 depth at qsearch. But this is not always true, since the some reduction code at search gets this to -2.
2. The q-check code generated checking captures. This resulted in capture moves being tried twice since qsearch already generates captures first.
bob wrote:I also have one more run with plain null-move R=3, since the adaptive null move (R=2~3) tapered R off near the leaves due to the danger of overlooking a serious threat, and the q-search checks are partially intended to help with that.
This is IMO the most important aspect of doing checks in qsearch. IIRC using adaptive null move along with qsearch checks was a definite loss for me.
Also, as Gary brings up, delta pruning is an important topic to consider. I try noncapture checks after all the captures are tried. IMO you pretty much have to delta prune checks as well, because any captures you try that happen to be checks will be subject to delta pruning (unless you check for this...). Not delta pruning checks can lead to big branching factors too.
bob wrote:I also have one more run with plain null-move R=3, since the adaptive null move (R=2~3) tapered R off near the leaves due to the danger of overlooking a serious threat, and the q-search checks are partially intended to help with that.
This is IMO the most important aspect of doing checks in qsearch. IIRC using adaptive null move along with qsearch checks was a definite loss for me.
Also, as Gary brings up, delta pruning is an important topic to consider. I try noncapture checks after all the captures are tried. IMO you pretty much have to delta prune checks as well, because any captures you try that happen to be checks will be subject to delta pruning (unless you check for this...). Not delta pruning checks can lead to big branching factors too.
I just wrote a new Quiesce() function called QuiesceChecks(). This is always called from Search() rather than the normal QUiesce(). It was easier to write this way for testing, whether I will combine QueseceChecks with Quiesce will depend on how much complexity that adds. QuiesceChecks() does behaves identically to Quiesce() until all the normal captures (SEE >= 0) have been searched. But rather than returning at that point, I then generate checking moves only (non-capturing checks since capturing checks came out in the normal capture generation) and I repeat the same loop again (and again, checking moves with SEE < 0 are not tried), trying each move, except this time I know to always call QuiesceEvasions() since I know I am in check, where in the capture search above I call QuiesceEvasions() only if the capture gives check.
In any case, after trying any move that leaves the opponent in check, I go to QuiesceEvasions() which is a simplified version of the normal search. It uses the pre-existing GenerateCheckEvasions() (a legal check-escape generator) and does a normal search, but only calling Quiesce() after each move is made. There is no stand-pat option in this code of course.
It significantly reduces the depth needed to solve many problems in WAC. It reduces (but less significantly) the time required to solve those, although on occasion it might actually take longer. But the net effect in games is actually very minimal.
CThinker wrote:Q-checks was once a pain for me because it was a huge hit in new code for very little gain. But in the end, I accepted that the gain was good enough. However, getting there had these hurdles, which could be true with you now:
1. The q-check code was never executed, even when it had to be. This depends on how you decide its execution. In my case, it was based on the remaining depth. I was counting on the fact that there would be at least -1 depth at qsearch. But this is not always true, since the some reduction code at search gets this to -2.
2. The q-check code generated checking captures. This resulted in capture moves being tried twice since qsearch already generates captures first.
Both are already handled. In my Search(), where I used to call Quiesce() if depth is <= 0, I now always call QuiesceChecks() instead. I have a special GenerateChecks() function that only generates direct checks and discovered checks, excluding any capture moves at all. Since the normal capture search has already generated all possible capture moves including those that deliver check.
after the first 400 games, R=3 looked to be worse. After another 3,000 games, it has moved slightly ahead (again error bars overlap so it is not better in any absolute sense) What a difference the extra 3,000 games made, compared to the decision one might have made after 400. The cluster is currently completing about one game per second since there are 128 at a time going on. It will take around 24 hours to finish the entire set unless we get A/C back up today and power up the other 128 processors.
gladius wrote:Tord mentioned a while back that Glaurung tapers the search more gradually than a hard q-search cutoff.
Yes: The last 7 plies of the main search are tapered, and becomes gradually more and more like a qsearch (except at PV nodes, where the search is completely full-width all the way to depth=0). Here is how it works:
The first N moves at all nodes are always searched. The number N depends on the remaining depth; it is smaller when the remaining depth is small. After the first N moves, only the following classes of moves are searched (the "threat move" is defined to be the move that refuted the null move at the current node):
Captures, checks, check evasions, and passed pawn pushes. All of these are searched, even when they have SEE < 0.
Moves where the moving piece is the piece captured by the threat move.
Moves which defend the destination square of the threat move, if the destination square is empty or the value of the piece on the destination square is smaller or equal to the value of the capturing piece in the threat move.
Moves with non-negative SEE value which block the ray of the threat move.
Moves with high history scores. The threshold depends on the remaining depth.
Most programmers don't like this scheme, because it sounds "too risky". I don't quite understand what they mean. It is not intuitively obvious to me why a gradual transition to the qsearch should be more risky than a sharp limit.
Tord
I do not think that most programmers tried it but I guess that the main reason is that most programmers do not use it is that they had no time to implement it or they do not know what you do(Glaurung is open source but it does not mean that most programmers studied it).
My comment about most programmers finding my scheme too risky was not based on the popularity of the technique in other programs, but on the reactions I invariably get when I describe it here and elsewhere. With a few exceptions, people instantly reject the idea as being far too risky, without even considering to try it.
Most programmers don't like this scheme, because it sounds "too risky". I don't quite understand what they mean. It is not intuitively obvious to me why a gradual transition to the qsearch should be more risky than a sharp limit.
I didn't used to know either. Now that I have filled my program with similar risky things I am starting to get an inkling. When you do funky pruning like that (or reductions of a similar type) your program begins to play more brilliant and more dumb moves. Even if you can find a risky system that improves your overall results in whatever testing mechanism you use, it can be quite annoying when some weak program mates you in 5 in some endgame (which would not happen if you were not doing risky pruning). I am willing to put up with that kind of thing, and it sounds like Tord is willing to put up with analogous annoyances as long as his average engine performance is improved. But to many falling for simple combos or sequences is simply unacceptable, even if it happens infrequently.
If it does happen, it happens so infrequently that I have never even seen it. I have never seen Glaurung miss a mate in 5 in a practical endgame. If anything, it seems to find endgame mates far faster than most programs of comparable strength. The few simple mates it doesn't find quickly are usually those involving zugzwang, but even for these positions, it is no slower (and often faster) than other null move pruners. The common form of tactical mistake in Glaurung's games is missing perpetual check draws, but this is not because of the super qsearch (which actually should help it spot most such draws more quickly, because all checks and check evasions are searched in the super qsearch), but because I extend checks by only half a ply, and not by a full ply like most others.
Tactically, my seven plies of super qsearch appear to be very solid and safe, both in test suites and in practical play. It also appears to work extremely well in the endgame. If it has any disadvantages, they are probably to be found in positional play in the opening and middle game. I am not sure whether this is a problem. My program does make lots of ugly antipositional moves, but I am not sure to what extent this is a search problem. I believe that the problems are usually caused by my rather bad evaluation function, but I could be wrong.
gladius wrote:Tord mentioned a while back that Glaurung tapers the search more gradually than a hard q-search cutoff.
Yes: The last 7 plies of the main search are tapered, and becomes gradually more and more like a qsearch (except at PV nodes, where the search is completely full-width all the way to depth=0). Here is how it works:
The first N moves at all nodes are always searched. The number N depends on the remaining depth; it is smaller when the remaining depth is small. After the first N moves, only the following classes of moves are searched (the "threat move" is defined to be the move that refuted the null move at the current node):
Captures, checks, check evasions, and passed pawn pushes. All of these are searched, even when they have SEE < 0.
Moves where the moving piece is the piece captured by the threat move.
Moves which defend the destination square of the threat move, if the destination square is empty or the value of the piece on the destination square is smaller or equal to the value of the capturing piece in the threat move.
Moves with non-negative SEE value which block the ray of the threat move.
Moves with high history scores. The threshold depends on the remaining depth.
Most programmers don't like this scheme, because it sounds "too risky". I don't quite understand what they mean. It is not intuitively obvious to me why a gradual transition to the qsearch should be more risky than a sharp limit.
Tord
I truly believe this is the way to go. I have not implemented it in my program Gaviota just because my development goes at the speed of snail and I always had other priorities. However, my intuition tells me that a gradient will be better that an abrupt transition to quies(). In fact, something that I do is to take into account different things at different levels in the quies(). First two plies checks, then none, and at one point quies() become even more selective taking into account only recaptures.
It is not your elaborate scheme, but it is a start.
Zach Wegner wrote:Also, as Gary brings up, delta pruning is an important topic to consider. I try noncapture checks after all the captures are tried. IMO you pretty much have to delta prune checks as well, because any captures you try that happen to be checks will be subject to delta pruning (unless you check for this...). Not delta pruning checks can lead to big branching factors too.
Delta pruning is the same as futility pruning, isn't it? I never futility prune checks (neither in the main search nor in the quiescence search), and it doesn't seem to hurt my branching factor much. Futility pruning of checks doesn't make sense at all, IMHO.
