Revisiting Check Extensions

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.
mjlef
Posts: 1327
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Revisiting Check Extensions

Post by mjlef » Thu Jun 07, 2007 9:25 am

Most programs I have seen seem to extend checks exactly one full ply. Some also extend one reply to checks another full ply (or sometimes less). A very few use an extession of 3/4 a ply. In my continuing experiments in my program, I have tried to come up with different criteria, and in testing they seem to help.

First I divide moves into capture and promotions, or non captures.

For promotions/captures, I use the results of an SEE to determine if the piece moving is being lost. Losing captures get a reduced extension (1/4 a ply to 1/2 a ply seems OK). Winning and equal captures get a full ply extension. I have also experimented with losing up to a pawn or material; getting the full ply extenion. Also, i have epxerimented with varying the extnsion depending on if it is a PV node (non-PV nodes get a lesser extension, but if they become PV nodes, get extended a full ply).

For non-captures, I do something similar (of course, the move is either equal or losing). Losing captures get a smaller extension.

My best tests so far suggest moves losing more than 1.5 pawns of material get no extension. Moves losing less material get 1/4 to 1/2 a ply, and winning or equal moves get a full ply. Ptrobably winning capture checks deserve more than a ply but I have not done enough testing to know for sure.

The goals of all of this is to shape the search tree, so moves with a higher probability of being best have more search under them, and moves likely to be bad, samller trees.

Has anyone revisited this issue, and is there something better than "always a full ply"?

Mark

Uri Blass
Posts: 8036
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Revisiting Check Extensions

Post by Uri Blass » Thu Jun 07, 2007 10:19 am

of course there is something better than always extending full ply
but I do something different.

I do not extend checks when the side that gives the check had a big material advantage before giving the check.

Uri

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Revisiting Check Extensions

Post by Tord Romstad » Thu Jun 07, 2007 10:33 am

Uri Blass wrote:I do not extend checks when the side that gives the check had a big material advantage before giving the check.
Hello Uri,

Are you sure this really works? It looks very dangerous to me: I would expect serious horizon effect problems. One of the main reasons why check extensions work is that in positions where you are faced with some threat against which there is no defence, a check can often postpone the inevitable by one ply. You can easily find many examples of this, for instance positions with a deadly fork or pin, or endgames with a rook against a pair of advanced passed pawns, where the rook cannot stop the pawns, but can give several checks before the pawns can promote.

Mark's scheme looks more promising to me.

Tord

Uri Blass
Posts: 8036
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Revisiting Check Extensions

Post by Uri Blass » Thu Jun 07, 2007 10:59 am

Tord Romstad wrote:
Uri Blass wrote:I do not extend checks when the side that gives the check had a big material advantage before giving the check.
Hello Uri,

Are you sure this really works? It looks very dangerous to me: I would expect serious horizon effect problems. One of the main reasons why check extensions work is that in positions where you are faced with some threat against which there is no defence, a check can often postpone the inevitable by one ply. You can easily find many examples of this, for instance positions with a deadly fork or pin, or endgames with a rook against a pair of advanced passed pawns, where the rook cannot stop the pawns, but can give several checks before the pawns can promote.

Mark's scheme looks more promising to me.

Tord
Note that big material advantage for me is defined as at least 8 pawns

Practically to be more correct it is big evaluation advantage of at least 8 pawns(I evaluate every node)

positions when the side that gives check postpone the inevitable by one ply with that advantage are rare and I believe that it helps.


Note that I did not test it seriously to be sure that it helps

The idea is that you do not want to extend checks when you feel sure about the expected result.

limit_check 800 is the default personality.

It is possible to change the constant of 8 pawns to a bigger constant or smaller constant by changing personality of movei but I did not do it.
If people are interested in testing it then you should only add
limit_check 400 in a personality file to see if not extending when the advantage is 4 pawns is better.

Uri
Last edited by Uri Blass on Thu Jun 07, 2007 11:01 am, edited 1 time in total.

Jose Carlos
Posts: 150
Joined: Wed Mar 08, 2006 9:09 pm
Location: Murcia (Spain)

Re: Revisiting Check Extensions

Post by Jose Carlos » Thu Jun 07, 2007 11:01 am

Tord Romstad wrote:
Uri Blass wrote:I do not extend checks when the side that gives the check had a big material advantage before giving the check.
Hello Uri,

Are you sure this really works? It looks very dangerous to me: I would expect serious horizon effect problems. One of the main reasons why check extensions work is that in positions where you are faced with some threat against which there is no defence, a check can often postpone the inevitable by one ply. You can easily find many examples of this, for instance positions with a deadly fork or pin, or endgames with a rook against a pair of advanced passed pawns, where the rook cannot stop the pawns, but can give several checks before the pawns can promote.

Mark's scheme looks more promising to me.

Tord
I think, but I haven't tested it, that the logic of extensions is to find that a special move changes the score of the line from fail low to fail high. Checks have the chance to convert a fail low (for example down in material) to a fail high (f.e. draw by repetition). Then if you're up in material and expect a fail high, search to normal depth and find a fh, you have no need to extend. However, if you fail low when you expected to fail high, then it makes sense to extend just in case the check might raise the score.
__________________________
José Carlos Martínez Galán

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

Re: Revisiting Check Extensions

Post by hgm » Thu Jun 07, 2007 11:59 am

I still have misgivings about check extensions: there must be much cheaper ways to get the information you describe.

For one, to really keep the threat within the horizon, you really would need an extenison of 2 ply (check + evasion). Otherwise it only partly helps. In most parts of the tree null-move pruning is supposed to solve this problem: you recognize the fork or pin by the null move failing low, and then you are going to do a real search two ply deeper than the null move search. So even accounting for the check + evasion, the threat would still be within the horizon.

Now the only place where this doesn't work is if you are so close to the horizon that the null move cannot get the full reduction. If at d=1 your null move fails low, and giving a check (or capturing something, or attacking a Queen...) seems to help, you are in a spot: you don't really know if it helps, as you know that moves in this class would always seem to help, no matter if they would actually help or not.

I sometimes wonder if it would not make sense to invert the 'burdon of proof' in this case: let the null-move score prevail over that of the real moves. But this would require you to statically distinguish likely solutions of the threat from likely horizon effects. So if the threat was a normally unsolvable one (a fork or pin) you would prefer the null-move score without further search (i.e. really give a reduction), while for a single threat you would only like to search moves that truly aimed at combatting the threat (withdrawal, defending, capturing attacker, interposing), and use the null-move score for others.

Problem is that static recognition is not very reliable. An alternative that solves the problem dynamically might be to have a specialized search (akin to QS) that you would call in cases like this i.e. at d=1 with a null move failing low due to a material threat): It would search 2 ply, but rather than being limited to QS in the end leaves (and thus being alllowed to stand pat) it would be forced to use the null-move score rather than eval for standing pat. So you would in fact get an extension to try fanciful solutions, but if they don't obviously work (as evidenced by the threat being gone), you would invert the burden of proof, and assume they are merely delaying tactics.

mjlef
Posts: 1327
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: Revisiting Check Extensions

Post by mjlef » Thu Jun 07, 2007 1:05 pm

I tried something like that a long time ago (not extending checks if way ahead in material). I did not such a high margins (8 pawns) though, so that might matter a lot. I did steal Tord's idea of not including chekcs in the qsearch if way ahead in material...I have not idea if it helps, but it makes a lot of sense.

I also think maybe extending even losing checks might make sense if the score is under 0. Capturing say a P with a N, and losing the knight might just expose the king to perpetual checks or something. I should experiment with this.

The conditiions I sent in the original message give me 40-50 ELO score improvement in otherwise identical programs that always extends all checks, but I only played a couple of hundred games, so this might not be useful. Tests against a bunch of programs also showed a small improvement, but again I would need 10000 games or somehting to have confidence.

Another idea is to force a full ply extension for any check that has a single response. It would be less costly than a two ply extension (check and single response), yet still catch things like one side distracting a king by sacrificing something to put it out of the range of protecting something more important.

If only I had Bob's cluster to try out 1900 ideas at once! :-)

Mark

Uri Blass
Posts: 8036
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Revisiting Check Extensions

Post by Uri Blass » Fri Jun 08, 2007 8:37 am

I decided to test reducing 8 pawns to 4 pawns at 100,000 nodes per move

result after 30 games was 15-15 when part of the games were completely identical(not all of them but in every 2 games from fixed position the result was 1-1).

Note that the 8 pawns helped me in the past to solve a problem when movei had problems to finish some iteration in pawn endgame because too many extensions of checks.

I found at that time that not extending checks when the check giver has
significant advantage of more than 8 pawns solve the problem.

I can also certainly think about situation when movei fails low and does not have time to solve the fail low in order to find a better move because of too many check extensions and this is the reason that I believe that some limit based on evaluation is good even if it gives only 5 elo rating improvement or something like that.

Uri

ed

Re: Revisiting Check Extensions

Post by ed » Fri Jun 08, 2007 9:40 am

Uri Blass wrote:I decided to test reducing 8 pawns to 4 pawns at 100,000 nodes per Note that the 8 pawns helped me in the past to solve a problem when movei had problems to finish some iteration in pawn endgame because too many extensions of checks.
Uri
There are other solutions as well, when a promotion occurs in a pawn ending I don't extend the first 4 checks that come after that since the vast majority of these checks are rubbish.

Ed

Uri Blass
Posts: 8036
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Revisiting Check Extensions

Post by Uri Blass » Fri Jun 08, 2007 10:06 am

Note that I simply reduce depth after promotion(and reduce more if the promotions happened in pawn endgame) but I have no rule not to extend checks after promotion.

I added this rule later after the rule of not extending checks that gives big advantage.

Inspite of it I think that not extending when there is a big advantage is a good idea not only for promotions because you can get a big advantage by winning a lot of material in some line in the search without promotion and I think that when the better side has a big advantage it is stupid to extend checks of the better side and it is better to spend time on other lines.

Post Reply