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.)
Check-extension in QS
Moderators: hgm, Rebel, chrisw
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
- Posts: 2204
- Joined: Sat Jan 18, 2014 10:24 am
- Location: Andorra
Re: Check-extension in QS
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.
Also when in check I prune evasions that captures something (i.e. checker) but SEE is bad.
Daniel José - http://www.andscacs.com
-
- Posts: 154
- Joined: Thu Oct 03, 2013 4:17 pm
Re: Check-extension in QS
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.
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).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.
Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
https://github.com/mAarnos
https://github.com/mAarnos
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Check-extension in QS
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.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.)
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
Re: Check-extension in QS
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.
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.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Check-extension in QS
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.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.
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.
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.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.
-
- Posts: 2204
- Joined: Sat Jan 18, 2014 10:24 am
- Location: Andorra
Re: Check-extension in QS
I reviewed the code and I had forgotten than there where a safety margin, 140 cp. It's equivalent to:hgm wrote: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.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.
https://chessprogramming.wikispaces.com/delta+pruning
Anyway it is pruned if SEE is bad.
Daniel José - http://www.andscacs.com
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Check-extension in QS
SF prunes non capturing evasions with a negative SEE: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?
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;
- 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...
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Check-extension in QS
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...).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...
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 4833
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Check-extension in QS
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.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.)