Check-extension in QS

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Post Reply
User avatar
hgm
Posts: 22195
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Check-extension in QS

Post by hgm » Fri Apr 03, 2015 5:37 pm

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.)

User avatar
cdani
Posts: 2040
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Check-extension in QS

Post by cdani » Fri Apr 03, 2015 6:10 pm

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.

User avatar
Bloodbane
Posts: 154
Joined: Thu Oct 03, 2013 2:17 pm

Re: Check-extension in QS

Post by Bloodbane » Fri Apr 03, 2015 6:36 pm

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).
Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
https://github.com/mAarnos

Sven
Posts: 3573
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: Check-extension in QS

Post by Sven » Fri Apr 03, 2015 7:00 pm

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.

zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Check-extension in QS

Post by zd3nik » Fri Apr 03, 2015 8:02 pm

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.

User avatar
hgm
Posts: 22195
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: Check-extension in QS

Post by hgm » Fri Apr 03, 2015 8:34 pm

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.

User avatar
cdani
Posts: 2040
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Check-extension in QS

Post by cdani » Fri Apr 03, 2015 9:30 pm

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.

User avatar
lucasart
Posts: 2957
Joined: Mon May 31, 2010 11:29 am
Contact:

Re: Check-extension in QS

Post by lucasart » Fri Apr 03, 2015 11:52 pm

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&#40;move&#41;
    && !pos.can_castle&#40;pos.side_to_move&#40;));

// Don't search moves with negative SEE values
if ( (!InCheck || evasionPrunable&#41;
    && type_of&#40;move&#41; != PROMOTION
    && pos.see_sign&#40;move&#41; < VALUE_ZERO&#41;
    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).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
lucasart
Posts: 2957
Joined: Mon May 31, 2010 11:29 am
Contact:

Re: Check-extension in QS

Post by lucasart » Sat Apr 04, 2015 12:11 am

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...).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Ferdy
Posts: 3595
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: Check-extension in QS

Post by Ferdy » Sat Apr 04, 2015 1:58 am

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.

Post Reply