null move threat extension

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.
Post Reply
AndrewShort

null move threat extension

Post by AndrewShort » Thu Oct 23, 2008 6:32 pm

I want to make sure I understand the null move threat extension.

My understanding is that if the null move search does not return a beta cutoff score, then see if the score is mate against side to move, and if so, increment depth. Basically it's saying - if the side to move passes, and a shallow search shows your opponent can mate you, then extend.

I fail to see how that could help. If there was no beta cutoff, you are going to continue with a normal search, which would find that same mate anyway, since it's a deeper search than the null move search.

Here's the null move block of code (in VB):

Code: Select all

If NullMoveOK Then
       MakeNullMove()
       iVal = -iAlphaBeta(iDepth - 1 - iR, -iBeta, -iBeta + 1, tLocalPV)
       UndoNullMove()
       If (iVal >= iBeta) Then
           Return iBeta
       End If
End If
and here is how I revised it with the null move threat extension:

Code: Select all

If NullMoveOK Then
       MakeNullMove()
       iVal = -iAlphaBeta(iDepth - 1 - iR, -iBeta, -iBeta + 1, tLocalPV)
       UndoNullMove()
       If (iVal >= iBeta) Then
           Return iBeta
       End If
       If iVal < -iMINMATESCORE Then
           iDepth = iDepth + 1
       End If
End If

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

Re: null move threat extension

Post by hgm » Thu Oct 23, 2008 6:49 pm

I guess the idea is that you might have more than one delaying check, if you get the lead move, while you would not have any opportunity to try any of them if the opponent has the lead move, because he is checking you all the time, on the way to the checkmate.

I am not sure it is really helpful. Usually there are indeed delaying checks, but they are mostly suicidal. So playing them should be enough to make the node fail low even without the actua made beng within the horizon. But it might help in situations where you have a few safe spite checks, chasing the King over the board until it finally finds permanent shelter.

Michael Sherwin
Posts: 3041
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: null move threat extension

Post by Michael Sherwin » Thu Oct 23, 2008 10:36 pm

Simple. If you have a move that prevents the mate within the horizon that you are searching a sacrificial line (move) by the opponent that mates you anyway may first be shortened by LMR, pruned by null move which is shortened by various forms of futility/razoring. So, the line that will mate you can be shorter than the original null_move search. In RomiChess I extend 2 ply, but afer writing this I may try a larger extension! :)
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

AndrewShort

Re: null move threat extension

Post by AndrewShort » Thu Oct 23, 2008 11:54 pm

hgm wrote:I guess the idea is that you might have more than one delaying check, if you get the lead move, while you would not have any opportunity to try any of them if the opponent has the lead move, because he is checking you all the time, on the way to the checkmate.

I am not sure it is really helpful. Usually there are indeed delaying checks, but they are mostly suicidal. So playing them should be enough to make the node fail low even without the actua made beng within the horizon. But it might help in situations where you have a few safe spite checks, chasing the King over the board until it finally finds permanent shelter.
the other thing I realized is this only works if you fail soft. Presently I fail hard (yet another item on my long todo list...)

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

Re: null move threat extension

Post by bob » Fri Oct 24, 2008 12:16 am

AndrewShort wrote:I want to make sure I understand the null move threat extension.

My understanding is that if the null move search does not return a beta cutoff score, then see if the score is mate against side to move, and if so, increment depth. Basically it's saying - if the side to move passes, and a shallow search shows your opponent can mate you, then extend.

I fail to see how that could help. If there was no beta cutoff, you are going to continue with a normal search, which would find that same mate anyway, since it's a deeper search than the null move search.
Not quite. The difference is that _you_ don't make a move, so if you "pass" and your opponent can mate you in one move, it is possible that a normal search where you do make a move, avoids the mate. By playing a horizon move. So you extend to see if you lose even if you do play a real move...


Here's the null move block of code (in VB):

Code: Select all

If NullMoveOK Then
       MakeNullMove&#40;)
       iVal = -iAlphaBeta&#40;iDepth - 1 - iR, -iBeta, -iBeta + 1, tLocalPV&#41;
       UndoNullMove&#40;)
       If &#40;iVal >= iBeta&#41; Then
           Return iBeta
       End If
End If
and here is how I revised it with the null move threat extension:

Code: Select all

If NullMoveOK Then
       MakeNullMove&#40;)
       iVal = -iAlphaBeta&#40;iDepth - 1 - iR, -iBeta, -iBeta + 1, tLocalPV&#41;
       UndoNullMove&#40;)
       If &#40;iVal >= iBeta&#41; Then
           Return iBeta
       End If
       If iVal < -iMINMATESCORE Then
           iDepth = iDepth + 1
       End If
End If

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

Re: null move threat extension

Post by bob » Fri Oct 24, 2008 12:17 am

hgm wrote:I guess the idea is that you might have more than one delaying check, if you get the lead move, while you would not have any opportunity to try any of them if the opponent has the lead move, because he is checking you all the time, on the way to the checkmate.

I am not sure it is really helpful. Usually there are indeed delaying checks, but they are mostly suicidal. So playing them should be enough to make the node fail low even without the actua made beng within the horizon. But it might help in situations where you have a few safe spite checks, chasing the King over the board until it finally finds permanent shelter.
The best test position for this is WAC 141. The "mate threat extension" will reduce the depth needed to find the solution by a ply or two...

jesper_nielsen

Re: null move threat extension

Post by jesper_nielsen » Fri Oct 24, 2008 12:03 pm

The way i think about it is that if the side to move will be mated if it does nothing (null move), then a preventing move might be a forced move.

So in order to find the forcing sequence of moves, the search is extended. Kind of like recapture extending.

So the extension is in order to follow the forcing sequence of moves.

For me, extending all null move searches that return a mate score caused search tree explosion. So currently I only extend if the search returns a "mate in one" score.

It certainly helps in tactical test positions! But i do not know how valuable it is in games.

Kind regards,
Jesper

AndrewShort

Re: null move threat extension

Post by AndrewShort » Fri Oct 24, 2008 5:31 pm

jesper_nielsen wrote:The way i think about it is that if the side to move will be mated if it does nothing (null move), then a preventing move might be a forced move.

So in order to find the forcing sequence of moves, the search is extended. Kind of like recapture extending.

So the extension is in order to follow the forcing sequence of moves.

For me, extending all null move searches that return a mate score caused search tree explosion. So currently I only extend if the search returns a "mate in one" score.

It certainly helps in tactical test positions! But i do not know how valuable it is in games.

Kind regards,
Jesper
ok, I get it now. But until I update my code to fail soft, I can't use it. Fail hard won't work here, since you would never get a score < alpha, so you wouldn't be able to test for a mating score against you.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: null move threat extension

Post by Zach Wegner » Fri Oct 24, 2008 5:37 pm

You don't have to do a full fail soft. All you have to do is return the actual values instead of beta on cutoffs. It works like this:

White null moves
Black tries mating move
White cannot move, returns "mated in one"
Black gets beta cutoff, but returns "mate in one" rather than beta
White sees null move returns "mated in two", extends
White proceeds to find refutation move
Tactical position is solved faster
Engine is stronger
Life is better

AndrewShort

Re: null move threat extension

Post by AndrewShort » Fri Oct 24, 2008 5:41 pm

Zach Wegner wrote:You don't have to do a full fail soft. All you have to do is return the actual values instead of beta on cutoffs. It works like this:

White null moves
Black tries mating move
White cannot move, returns "mated in one"
Black gets beta cutoff, but returns "mate in one" rather than beta
White sees null move returns "mated in two", extends
White proceeds to find refutation move
Tactical position is solved faster
Engine is stronger
Life is better
very funny!

Post Reply