Check extension vs LMR

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 22327
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Check extension vs LMR

Post by hgm » Tue Apr 04, 2017 3:06 pm

I always adhered to the common wisdom that one should not apply LMR reductions to moves that you would extend, without giving it much thought. So when I am doing check extension, it cancels LMR.

But now I realize there is a catch, because I really used to extend the check evasions, rather than the checks. That is, when a node finds the stm in check, it increases the requested depth by 1. In the end the result is the same, the branches reach 1 ply deeper, and it does not matter where along them the extesion was awarded.

But nowadays I typically apply LMR of moves 'after the fact', that is, I first make the move, informing the daughter node it is a late move, and then leave it up to the daughter to decide about the reduction. The daughter would figure out if the stm is in check anyway, so it saves me the trouble of throwing an extra test on every move in the parent, to see if it delivers check.

But this is equivalent to exempting checking moves from LMR, and not the evasions. So some of the check evasions (in particular the King withdrawals and the interpositions) will be qualified as 'late', and will be reduced. This somehow feels wrong; I don't see any reason why these 'silent' evasions would on average have less chance to be good, or would need less depth to pove their worth as capturing the checker. Often it is the opposite: when the check was unsafe, and can be refuted by gobbling up the checker, it is usually obvious at very low depth. And if the check was safe, you are completely dependent on late moves for evasions. Normal killers or history moves are not likely to work in an in-check position.

How do other engines do this? Do they exempt checking moves from LMR, or all check evasions? Or perhaps both?

jdart
Posts: 3507
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Check extension vs LMR

Post by jdart » Tue Apr 04, 2017 4:07 pm

Funny you should post this now - I have just tested a change that applies LMR to some evasions and it had a positive ELO gain. One reason may be that the first evasion is pretty often either a hash hit (so it was best in some previous visit) or a good capture (which get sorted first), so the late moves in both these cases are likely to be less good. But there will certainly be positions where that is not true.

--Jon

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

Re: Check extension vs LMR

Post by cdani » Tue Apr 04, 2017 5:59 pm

hgm wrote: How do other engines do this? Do they exempt checking moves from LMR, or all check evasions? Or perhaps both?
I do LMR, which I reduce by one if there is check extension. There is check extension if the SEE of the checking move is not negative.

Also I don't prune the move if is check.
jdart wrote:I have just tested a change that applies LMR to some evasions and it had a positive ELO gain.
Yes, this works.

bob
Posts: 20347
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Check extension vs LMR

Post by bob » Thu Apr 06, 2017 6:40 pm

Probably a deeper topic than most of us will imagine. My thinking has always been "KISS". In Cray Blitz, I extended on the evasion. But in Crafty, I extend on the checking move itself. I never considered the idea of extending a checking move then reducing the evasions as particularly reasonable. I experimented with the inverse, not extending the check, then extending (or even reducing) the evasions. But it was more complicated and didn't seem to affect results when testing.

There's probably dozens of different approaches. Perhaps all the way to eliminating extensions completely (I have already removed all but check extensions as it stands today). Probably could all be collapsed into the LMR code which is something I might try.

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

Re: Check extension vs LMR

Post by lucasart » Fri Apr 07, 2017 11:35 am

hgm wrote:I always adhered to the common wisdom that one should not apply LMR reductions to moves that you would extend, without giving it much thought. So when I am doing check extension, it cancels LMR.

But now I realize there is a catch, because I really used to extend the check evasions, rather than the checks. That is, when a node finds the stm in check, it increases the requested depth by 1. In the end the result is the same, the branches reach 1 ply deeper, and it does not matter where along them the extesion was awarded.

But nowadays I typically apply LMR of moves 'after the fact', that is, I first make the move, informing the daughter node it is a late move, and then leave it up to the daughter to decide about the reduction. The daughter would figure out if the stm is in check anyway, so it saves me the trouble of throwing an extra test on every move in the parent, to see if it delivers check.

But this is equivalent to exempting checking moves from LMR, and not the evasions. So some of the check evasions (in particular the King withdrawals and the interpositions) will be qualified as 'late', and will be reduced. This somehow feels wrong; I don't see any reason why these 'silent' evasions would on average have less chance to be good, or would need less depth to pove their worth as capturing the checker. Often it is the opposite: when the check was unsafe, and can be refuted by gobbling up the checker, it is usually obvious at very low depth. And if the check was safe, you are completely dependent on late moves for evasions. Normal killers or history moves are not likely to work in an in-check position.

How do other engines do this? Do they exempt checking moves from LMR, or all check evasions? Or perhaps both?
What I can say from experience (ie. proper testing, not theoretical arguments) is this:
- extending all checks hurts elo.
- extending SEE >= 0 checks is good.
- that's why you should do it in the parent node, not in the child node, unless you want a messy code-base, with parent node lookup in a search stack.
- not reducing checks hurts elo. yes, you should combine reductions and extensions, rather than use extension to prevent reduction, or you get a double whammy cost.

In broad terms, I (or rather my test results) agree with Daniel Jose. But the devil is in the details. Testing is the only answer. The rest is hand-waving at best.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
hgm
Posts: 22327
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Check extension vs LMR

Post by hgm » Fri Apr 07, 2017 5:09 pm

It is not clear to me what you are saying. The parent node (from where the checking move is made) would not know that the move delivers check. This will become only apparent in the daughter node. This is why the decision to extend or not is taken in the node that generates the evasions. The question is really whether I should distinguish evasions into early and late evasions, or whether I should search any evasion to the same depth.

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

Re: Check extension vs LMR

Post by cdani » Fri Apr 07, 2017 5:12 pm

hgm wrote:It is not clear to me what you are saying. The parent node (from where the checking move is made) would not know that the move delivers check. This will become only apparent in the daughter node. This is why the decision to extend or not is taken in the node that generates the evasions. The question is really whether I should distinguish evasions into early and late evasions, or whether I should search any evasion to the same depth.
Not really. In Andscacs I know that the move is a checking one in the parent node. And is the same for Stockfish and sure others.

nionita
Posts: 153
Joined: Fri Oct 22, 2010 7:47 pm
Location: Austria

Re: Check extension vs LMR

Post by nionita » Fri Jun 02, 2017 7:44 am

lucasart wrote:
hgm wrote:I always adhered to the common wisdom that one should not apply LMR reductions to moves that you would extend, without giving it much thought. So when I am doing check extension, it cancels LMR.

But now I realize there is a catch, because I really used to extend the check evasions, rather than the checks. That is, when a node finds the stm in check, it increases the requested depth by 1. In the end the result is the same, the branches reach 1 ply deeper, and it does not matter where along them the extesion was awarded.

But nowadays I typically apply LMR of moves 'after the fact', that is, I first make the move, informing the daughter node it is a late move, and then leave it up to the daughter to decide about the reduction. The daughter would figure out if the stm is in check anyway, so it saves me the trouble of throwing an extra test on every move in the parent, to see if it delivers check.

But this is equivalent to exempting checking moves from LMR, and not the evasions. So some of the check evasions (in particular the King withdrawals and the interpositions) will be qualified as 'late', and will be reduced. This somehow feels wrong; I don't see any reason why these 'silent' evasions would on average have less chance to be good, or would need less depth to pove their worth as capturing the checker. Often it is the opposite: when the check was unsafe, and can be refuted by gobbling up the checker, it is usually obvious at very low depth. And if the check was safe, you are completely dependent on late moves for evasions. Normal killers or history moves are not likely to work in an in-check position.

How do other engines do this? Do they exempt checking moves from LMR, or all check evasions? Or perhaps both?
What I can say from experience (ie. proper testing, not theoretical arguments) is this:
- extending all checks hurts elo.
- extending SEE >= 0 checks is good.
- that's why you should do it in the parent node, not in the child node, unless you want a messy code-base, with parent node lookup in a search stack.
- not reducing checks hurts elo. yes, you should combine reductions and extensions, rather than use extension to prevent reduction, or you get a double whammy cost.

In broad terms, I (or rather my test results) agree with Daniel Jose. But the devil is in the details. Testing is the only answer. The rest is hand-waving at best.
After this discussion I implemented 2 branches in Barbarossa (in which I until then extended all checks and did not reduce late extended moves):
- version one: LMR also for extended moves (aka checks)
- version two: extend only checks with SEE >= 0

Both were winner: one won 18 Elo (+- 6), two won 8 Elo (+- 6).

But when I combined them, there was no win at all (but a regression is very very probable, final Elo is not clear yet).

Every engine is different, but at least in my case, it looks like the SEE effort for checks does not pay out.

User avatar
MikeB
Posts: 2526
Joined: Thu Mar 09, 2006 5:34 am
Location: Pen Argyl, Pennsylvania

Re: Check extension vs LMR

Post by MikeB » Fri Jun 02, 2017 2:35 pm

nionita wrote: ...

After this discussion I implemented 2 branches in Barbarossa (in which I until then extended all checks and did not reduce late extended moves):
- version one: LMR also for extended moves (aka checks)
- version two: extend only checks with SEE >= 0

Both were winner: one won 18 Elo (+- 6), two won 8 Elo (+- 6).

But when I combined them, there was no win at all (but a regression is very very probable, final Elo is not clear yet).

Every engine is different, but at least in my case, it looks like the SEE effort for checks does not pay out.
For SEE not to work out is very unusual , I have tried removing the SEE test from many engines and it is always better with SEE. Every engine is different, but would suggest double checking your implementation. Without SEE, the search blows up eventually. A built in bench command will see a fairly dramatic pickup (20-25%) in the nodes per depth without SEE and that is what causes the ELO reduction.

Edit: Rethinking this - it may not be 20-25%, but even if it 10%, I believe it will hurt ELO. Not sure of the % now but you can test.

jorose
Posts: 122
Joined: Thu Jan 22, 2015 2:21 pm
Location: Zurich, Switzerland

Re: Check extension vs LMR

Post by jorose » Fri Jun 02, 2017 3:03 pm

I have been very hesitant with implementing SEE, especially as how I understand it it probably has to be tuned somehow to work with the evaluation function? The value of piece extremely variable, ie SEE has to deal with active bishops and passive bishops, knights on a8 and knights on d4, is this typically dealt with in SEE implementations?

When reading about SEE it just seems so arbitrary to me. Do SEE implementations vary greatly between the top engines?

Post Reply