Page 1 of 1
Check-extension in QS
Posted: Fri Apr 03, 2015 7:37 pm
by hgm
What is the consensus on check extensions during QS? In most of my engines, when I accidentally get checked by any of the captures, I usually search all evasions, also the non-capture evasions, i.e. extend to a d=1 search.
Is that really worth it, or could you just as well stand pat when in check, assuming that one of the non-capture evasions will keep you at the current eval? You will miss tactics where he can fork King + hanging piece through a capture (or that the check actually is a mate). But there could be lots of that through non-capture checks, which you would miss anyway. The chances that he could have such a fork by capturing anything should be slim. (I am talking now about the QS phase where you would not search non-capture checks in the parent node. Searching those would obviously not make sense if the opponent would be allowed to stand pat in the face of these.)
E.g. positions like the following:
[d]5rk1/5ppp/8/8/3Q4/2B5/8/8 b
If just before the horizon black in this position plays h6, Qxg7# would get him mated, but standing pat in the face of check would keep him unaware of that. But if he would be aware, he would play g6 just before the horizon, instead of h6. Then Qg7# would mate him just as much as before, but would not be searched in QS, and thus would look like a defense. So forcing black to search on after the capture check doesn't bring a thing if you don't allow searching the same non-capture check. He will just start to 'defend' by preventing the mating move is a capture. (Would be better eval-wise as well.)
Re: Check-extension in QS
Posted: Fri Apr 03, 2015 8:10 pm
by cdani
In Andscacs I prune captures that don't recover material balance even if they provoke check. It's bad for finding mate quicker but is good for elo at least for it.
Also when in check I prune evasions that captures something (i.e. checker) but SEE is bad.
Re: Check-extension in QS
Posted: Fri Apr 03, 2015 8:36 pm
by Bloodbane
A long time ago my program could stand pat when in check. I fixed that and gained about 5 elo. To me it seems wrong to assume
anything when in check as the position is very volatile. By the same logic I don't do any sort of pruning or reductions when in check in the main search. Also, I am not aware of any reasonable program which can stand pat in check while in QS.
daniel jose wrote:
In Andscacs I prune captures that don't recover material balance even if they provoke check. It's bad for finding mate quicker but is good for elo at least for it.
Same here. Interestingly not pruning captures/checks which are also discovered checks when they have SEE < 0 (because SEE is meaningless for discovered checks) loses serious amounts of elo (10 or so).
Re: Check-extension in QS
Posted: Fri Apr 03, 2015 9:00 pm
by Sven
hgm wrote:If just before the horizon black in this position plays h6, Qxg7# would get him mated, but standing pat in the face of check would keep him unaware of that. But if he would be aware, he would play g6 just before the horizon, instead of h6. Then Qg7# would mate him just as much as before, but would not be searched in QS, and thus would look like a defense. So forcing black to search on after the capture check doesn't bring a thing if you don't allow searching the same non-capture check. He will just start to 'defend' by preventing the mating move is a capture. (Would be better eval-wise as well.)
The combination of searching quiet checks during the first N plies of QS (usually N=1) and always searching check evasions in QS would address that kind of problem. In your example both h6 and g6 played at horizon would be followed by searching Qxg7 resp. Qg7 and finding that black is checkmated.
Re: Check-extension in QS
Posted: Fri Apr 03, 2015 10:02 pm
by zd3nik
As long as you search at least 1 move when you're in check, to make sure 1) you have at least 1 legal move 2) that legal move doesn't lead to checkmate or major loss of material, then I think it may be reasonable to allow pruning of other moves.
After reading you post I went ahead an tried it in Clubfoot. After some very shallow testing it didn't appear to cause the engine to miscalculate positions with forcing lines that involved checks. And it did add about 1 extra ply of search depth on average, in the small test set I used. But it did, oddly enough, cause it to fail a couple positional tests that it would normally pass without this change. So this initial round of testing is certainly not enough to go on, but doesn't seem to prove the idea to be outright unsound (as long as you search at least one move as stated above).
I then expanded on the idea a little and if the first move searched in a QS node results in getting checkmated and alpha is above the -Mate value, examine ALL moves at that node. I expected this to cause search explosion but it didn't. And it enabled Clubfoot to pass 3 more tests than usual in my smallish initial testing set! So I'll be tinkering with that for a bit.
Thanks for sharing your idea! It always nice to get the ball rolling on something new to try.
Re: Check-extension in QS
Posted: Fri Apr 03, 2015 10:34 pm
by hgm
Sven Schüle wrote:The combination of searching quiet checks during the first N plies of QS (usually N=1) and always searching check evasions in QS would address that kind of problem. In your example both h6 and g6 played at horizon would be followed by searching Qxg7 resp. Qg7 and finding that black is checkmated.
Indeed, the example was for the simplified case where N=0. But I think that whatever N is, the same general problem remains. (You will just need other positions to exemplify it.) Beyond some depth you will only search damaging checks when they are captures, and when you make the engine recognize those it will just alter its moves in the full-width search to make that same and equally damaging check a non-capture, by moving away the target. And that will mask the beneficial effect that recognizing the true effect of the capture-checks could have. I guess the main problem arises when the target is a Pawn, because (accidentally, in orthodox Chess) any other piece you move away would then acquire a move covering its square of origin, so that it would actually defend against the damaging check.
The reason I am interested in quanitative data on this is that I designed a method of selective capture generation on mailbox boards for a low-memory-footprint engine, from a data structure that hold a 'nearest-neighbor map'. This map is very easy to update incrementally on captures, as long as the sub-tree searched from these do not contain non-captures, but would require storing relatively large amounts of undo-info for non-captures (or would make all undo quite slow). So if it conly costs 5 Elo to get rid of all the non-captures (and check evasions would be the only such moves), I am pretty sure I can easily earn that 5 Elo (and more) back by a general speed increase.
cdani wrote:In Andscacs I prune captures that don't recover material balance even if they provoke check. It's bad for finding mate quicker but is good for elo at least for it.
Well, pruning such 'futile' checking-captures is equivalent to allowing stand-pat when in-check. So if it is good for Elo, that's really good news for me.
Re: Check-extension in QS
Posted: Fri Apr 03, 2015 11:30 pm
by cdani
hgm wrote:cdani wrote:In Andscacs I prune captures that don't recover material balance even if they provoke check. It's bad for finding mate quicker but is good for elo at least for it.
Well, pruning such 'futile' checking-captures is equivalent to allowing stand-pat when in-check. So if it is good for Elo, that's really good news for me.
I reviewed the code and I had forgotten than there where a safety margin, 140 cp. It's equivalent to:
https://chessprogramming.wikispaces.com/delta+pruning
Anyway it is pruned if SEE is bad.
Re: Check-extension in QS
Posted: Sat Apr 04, 2015 1:52 am
by lucasart
hgm wrote:What is the consensus on check extensions during QS? In most of my engines, when I accidentally get checked by any of the captures, I usually search all evasions, also the non-capture evasions, i.e. extend to a d=1 search.
Is that really worth it, or could you just as well stand pat when in check, assuming that one of the non-capture evasions will keep you at the current eval?
SF prunes non capturing evasions with a negative SEE:
Code: Select all
// Detect non-capture evasions that are candidates to be pruned
evasionPrunable = InCheck
&& bestValue > VALUE_MATED_IN_MAX_PLY
&& !pos.capture(move)
&& !pos.can_castle(pos.side_to_move());
// Don't search moves with negative SEE values
if ( (!InCheck || evasionPrunable)
&& type_of(move) != PROMOTION
&& pos.see_sign(move) < VALUE_ZERO)
continue;
There are a few extra conditions:
- type_of(move) != PROMOTION, is because SF's SEE doesn't handle promotions correctly
- bestValue > VALUE_MATED_IN_MAX_PLY, is to make sure we don't return unproven mate scores by pruning all the moves, so we need to have searched at least one that resulted in a non mate score
- pos.see_sign(move) < VALUE_ZERO), I'm pretty sure is useless. but, as always with useless stuff, testing resolution is not small enough to allow us to remove them safely...
This is definitely not a big elo gain, but it is mesurable (I don't remember, maybe 5 elo at best).
Re: Check-extension in QS
Posted: Sat Apr 04, 2015 2:11 am
by lucasart
lucasart wrote:
[*] pos.see_sign(move) < VALUE_ZERO), I'm pretty sure is useless. but, as always with useless stuff, testing resolution is not small enough to allow us to remove them safely...
Sorry, I mean that about the castling condition. It's probably a remnant of the time when the SEE was wrong for castling (because castling is KxR, so...).
Re: Check-extension in QS
Posted: Sat Apr 04, 2015 3:58 am
by Ferdy
hgm wrote:What is the consensus on check extensions during QS? In most of my engines, when I accidentally get checked by any of the captures, I usually search all evasions, also the non-capture evasions, i.e. extend to a d=1 search.
Is that really worth it, or could you just as well stand pat when in check, assuming that one of the non-capture evasions will keep you at the current eval? You will miss tactics where he can fork King + hanging piece through a capture (or that the check actually is a mate). But there could be lots of that through non-capture checks, which you would miss anyway. The chances that he could have such a fork by capturing anything should be slim. (I am talking now about the QS phase where you would not search non-capture checks in the parent node. Searching those would obviously not make sense if the opponent would be allowed to stand pat in the face of these.)
E.g. positions like the following:
[d]5rk1/5ppp/8/8/3Q4/2B5/8/8 b
If just before the horizon black in this position plays h6, Qxg7# would get him mated, but standing pat in the face of check would keep him unaware of that. But if he would be aware, he would play g6 just before the horizon, instead of h6. Then Qg7# would mate him just as much as before, but would not be searched in QS, and thus would look like a defense. So forcing black to search on after the capture check doesn't bring a thing if you don't allow searching the same non-capture check. He will just start to 'defend' by preventing the mating move is a capture. (Would be better eval-wise as well.)
At depth 0, the side to move must not be in check, and most of my engines search promote and capture moves, and at depth -1 when side is in check I searched all check evasions - no pruning. It is only at depth -1 that I searched check evasions. At depth 0 when alpha is not improved that is, after searching all available moves, I try to search non-capture check moves that has a good SEE. From your diagram with or without pawn in g7, there is a possiblity that my qsearch will be able to find the Qxg7# or Qg7# move. This works for me so far, in the past I don't search evasion moves in qsearch.