quiescence search
Andrew Tridgell
I'm wondering how other people handle check in a quiescence search.
In KnightCaps quiesce() search I test for check (just a simple bit
test) and if the player on the move is in check I modify the
search in two ways:
1) the player is not allowed to "sit" and take the current evaluation
2) all check evasion moves are generated using the same check
evasion routine I use for the main search. This is instead of
the normal capture and promotion move generation.
Today I was told by David Blackman (author of Desperado) that
you only need to account for check in a quiesce search if all
moves by the opponent in this line of the quiesce search have
been check, otherwise you ignore the check, or perhaps allow the
player to sit. The reasoning is that if the quiesce search does
lead to mate you will end up sitting at a earlier move if there
has been a non-checking move.
I'm not totally convinced this is correct, so I took a quick
look at Crafty and found that (as far as I can see) it doesn't
take account of check at all in the quiesce search. This really
surprised me, but may explain why the quiesce node counts in Crafty
are generally less than in KnightCap.
Whats going on? I'm interested in knowing both what the "correct"
way to handle check in quiesce is, and also why its correct!
Andrew
Robert Hyatt
Andrew Tridgell (Andrew....@anu.edu.au) wrote:
: I'm wondering how other people handle check in a quiescence search.
: In KnightCaps quiesce() search I test for check (just a simple bit
: test) and if the player on the move is in check I modify the
: search in two ways:
: 1) the player is not allowed to "sit" and take the current evaluation
: 2) all check evasion moves are generated using the same check
: evasion routine I use for the main search. This is instead of
: the normal capture and promotion move generation.
: Today I was told by David Blackman (author of Desperado) that
: you only need to account for check in a quiesce search if all
: moves by the opponent in this line of the quiesce search have
: been check, otherwise you ignore the check, or perhaps allow the
: player to sit. The reasoning is that if the quiesce search does
: lead to mate you will end up sitting at a earlier move if there
: has been a non-checking move.
correct... if you dig up the source for a 9.x version of crafty,
you'll see this. the reason is that if there is one non-checking
move, your opponent can stand pat. and you can't use the remainder
of the quiescence search to force mate or win anything more than you
have already won, because he'll just stick at that position...
: I'm not totally convinced this is correct, so I took a quick
: look at Crafty and found that (as far as I can see) it doesn't
: take account of check at all in the quiesce search. This really
: surprised me, but may explain why the quiesce node counts in Crafty
: are generally less than in KnightCap.
: Whats going on? I'm interested in knowing both what the "correct"
: way to handle check in quiesce is, and also why its correct!
: Andrew
Correct, eh? :)
That's relative. I've done a lot of work to extend in the basic search.
and, as a result, I've done a lot of work to avoid doing anything that
is unsafe in the q-search. One quick example is that of making the
assumption that the best move in a given position is a capture. The
result is the "lean and mean" q-search you see in Crafty... winning and
even captures only, no checks or anything else.
Why?
simple and fast. the code to extend on checks is not hard to write. I
did it in Cray Blitz, I did it in Crafty prior to 10.x, but it is
expensive. One trick is to note that after you enter the q-search, and
you play one non-checking move with wtm, then there is *never* any sense
in looking at checking moves after that, because you can't ever force
mate since btm can stand pat (not in check at some point, remember). Same
for btm. This will save a good bit of time. But it's not nearly as fast
as searching captures only.
this depends on a pretty deep basic search. In blitz, I typically see
8-9 plies with Crafty when it's searching, and with the extensions in
search, I've seen enough mates in 10 announced that it is no longer a
novelty at all. I remember a case early in the development of Crafty
where I logged in and ICC was buzzing with "did you see that?" and so
forth. "that" was a mate in 11 announcement against a GM. It was a
novelty. It's not any longer.
The gain in Crafty is that the q=search is *very* fast, which means the
regular search probes deeper than it did with a q-search loaded up with
checks, and the overall effect is better play. Even on test suites like
Win At Chess, where you'd think the qsearch checks would find mates that
a regular search can't...
I won't begin to claim this is "correct"... I do claim it "works"... :)
one nice thing, however, is Quiesce() is about 75 lines of code, including
the futility cutoffs, move ordering and everything (excluding comments.)
In general, it works flawlessly as bugs are rare in code that small. Search()
can be arbitrarily complicated (as mine is in places) with internal iterative
deepening at key places where there's no move ordering after a fail high
for example, or null-move searches, or razoring, or other things.
My philosophy in Cray Blitz was always "the quiescence search is *not* there
to win material or mate the opponent, it is there to be sure that after all
the trick extensions in the basic search have been tried, there is not some
simply overloaded piece or something that will lose something." If you depend
on the q-search to win stuff, it will make mongo errors, because it can't find
non-capturing moves like pins, forks, skewers, mate threats and the like. Since
it is stupid, I don't trust it, and give it just as little responsibility as I
can. I then invest all my time in the regular search, and try to make it
extend where it should, avoid extending where it shouldn't, and try to resolve
all tactical issues before calling "simpleton Quiesce()"... The bottom line
is more nodes in the basic search, fewer nodes in the quiescence search, and
since the error-prone part of the search is searching fewer nodes, I'm happy.
Jon Dart
I have tried taking checks out of the qsearch in Arasan but so far I
am not happy with it .. test scores went down, not up. I think this
is one case where your mileage might vary, depending on other things
in the program. Ditto with razoring .. my experiments show that it
makes some searches way faster, but sometimes it extends finding the
correct move out another ply or two, and overall it's not good. So
"try before you buy".
--Jon
In article <5j2me5$8...@juniper.cis.uab.edu>,
Robert Hyatt
Jon Dart (jd...@shell3.ba.best.com) wrote:
: I have tried taking checks out of the qsearch in Arasan but so far I
: am not happy with it .. test scores went down, not up. I think this
: is one case where your mileage might vary, depending on other things
: in the program. Ditto with razoring .. my experiments show that it
: makes some searches way faster, but sometimes it extends finding the
: correct move out another ply or two, and overall it's not good. So
: "try before you buy".
Razoring is almost guaranteed to fail on test problems. Because it will
add roughly one ply to the depth needed to find sacrificial combinations.
Of course, how many sacrificial combos do you find in a real game? Probably
none, most of the time. That's where razoring shines, because then it may
get you another ply, that helps out positionally.
As always there are tradeoffs... just beware of only using tactical
chess suites as the main measure of effectiveness. I'd be happy to
compare something like WAC results with you however, so you can see
whether your version of razoring was doing better or worse than what
I am doing... I run it regularly just for speed comparisons when I
am optimizing rather than modifying...
: --Jon
: >