Null move alterative in endgames

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Aleks Peshkov
Posts: 870
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Null move alterative in endgames

Post by Aleks Peshkov » Wed Nov 16, 2011 11:01 am

It is known that null move have problems detecting zugzwangs. But in most positions there is a known move that is legal most of time but almost always futile -- unmaking last made move back (in case if it is was a reversible move). It seems that this move is a better alternative to plain "no move" if it is a legal one, at least in typical late endgames.

User avatar
asanjuan
Posts: 211
Joined: Thu Sep 01, 2011 3:38 pm
Location: Seville, Spain

Re: Null move alterative in endgames

Post by asanjuan » Wed Nov 16, 2011 11:44 am

Then your are reaching the same position when analyzing null-move two plys before....¿or not?
¿am i saying something stupid? :?

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

Re: Null move alterative in endgames

Post by bob » Wed Nov 16, 2011 2:20 pm

Aleks Peshkov wrote:It is known that null move have problems detecting zugzwangs. But in most positions there is a known move that is legal most of time but almost always futile -- unmaking last made move back (in case if it is was a reversible move). It seems that this move is a better alternative to plain "no move" if it is a legal one, at least in typical late endgames.
I don't follow. If you play a real move, how can you safely reduce the depth as null-move does? The point of null-move is that giving your opponent the right to make two consecutive moves is such a powerful thing that you can do so, and reduce the depth, and if you are STILL winning, you can safely "fail high" here and move on. If you play a real move, why would you reduce the depth and use that result? If you do do that, why not just try ANY move?

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

Re: Null move alterative in endgames

Post by Uri Blass » Wed Nov 16, 2011 2:28 pm

bob wrote:
Aleks Peshkov wrote:It is known that null move have problems detecting zugzwangs. But in most positions there is a known move that is legal most of time but almost always futile -- unmaking last made move back (in case if it is was a reversible move). It seems that this move is a better alternative to plain "no move" if it is a legal one, at least in typical late endgames.
I don't follow. If you play a real move, how can you safely reduce the depth as null-move does? The point of null-move is that giving your opponent the right to make two consecutive moves is such a powerful thing that you can do so, and reduce the depth, and if you are STILL winning, you can safely "fail high" here and move on. If you play a real move, why would you reduce the depth and use that result? If you do do that, why not just try ANY move?
The idea as I understand is to replace the null move in the search in the endgame by a real move that does not help the opponent and has a similiar effect to null move(except that you have no problem of zugzwangs).

This real move cannot be every move and it should be a move that does not change the evaluation function or almost does not change it.

You are not going to replace null move by some logical move that increase the static evaluation like pushing a passed pawn or centralizing the king.

Edit:I guess that if you cannot find a relevant move the idea is not to use something similiar to null move pruning but if you can find a relevant move then you can try it first with reduced depth and if it fail high you can skip other moves in the same way that you do in null move pruning.

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

Re: Null move alterative in endgames

Post by bob » Wed Nov 16, 2011 4:04 pm

Uri Blass wrote:
bob wrote:
Aleks Peshkov wrote:It is known that null move have problems detecting zugzwangs. But in most positions there is a known move that is legal most of time but almost always futile -- unmaking last made move back (in case if it is was a reversible move). It seems that this move is a better alternative to plain "no move" if it is a legal one, at least in typical late endgames.
I don't follow. If you play a real move, how can you safely reduce the depth as null-move does? The point of null-move is that giving your opponent the right to make two consecutive moves is such a powerful thing that you can do so, and reduce the depth, and if you are STILL winning, you can safely "fail high" here and move on. If you play a real move, why would you reduce the depth and use that result? If you do do that, why not just try ANY move?
The idea as I understand is to replace the null move in the search in the endgame by a real move that does not help the opponent and has a similiar effect to null move(except that you have no problem of zugzwangs).

This real move cannot be every move and it should be a move that does not change the evaluation function or almost does not change it.

You are not going to replace null move by some logical move that increase the static evaluation like pushing a passed pawn or centralizing the king.

Edit:I guess that if you cannot find a relevant move the idea is not to use something similiar to null move pruning but if you can find a relevant move then you can try it first with reduced depth and if it fail high you can skip other moves in the same way that you do in null move pruning.
However, you are still reducing the search by 2 plies. What makes THAT move one that you can say "making this move and giving my opponent 2 plies less to refute it means my position is really good?"

null-move makes sense. A real move does not.

User avatar
marcelk
Posts: 348
Joined: Fri Feb 26, 2010 11:21 pm
Contact:

Re: Null move alterative in endgames

Post by marcelk » Wed Nov 16, 2011 4:50 pm

Aleks Peshkov wrote:It is known that null move have problems detecting zugzwangs. But in most positions there is a known move that is legal most of time but almost always futile -- unmaking last made move back (in case if it is was a reversible move). It seems that this move is a better alternative to plain "no move" if it is a legal one, at least in typical late endgames.
This is a pretty interesting line of thinking and definitely worth exploring.

Even though I have not truly convinced myself yet that the null move in endgames is really a bad thing for game play, it is something that is useful to disable in specific positions. Your trick can be a nice substitute.

User avatar
marcelk
Posts: 348
Joined: Fri Feb 26, 2010 11:21 pm
Contact:

Re: Null move alterative in endgames

Post by marcelk » Wed Nov 16, 2011 4:54 pm

asanjuan wrote:Then your are reaching the same position when analyzing null-move two plys before....¿or not?
¿am i saying something stupid? :?
move A, move B, unmove A, REDUCE

It is effectively giving the opponent a free move, similar to null move.
No repetition because opponent's move B is in between.

Besides, you can always treat 'unmove A' as an irreversible move with respect to repetitions.

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

Re: Null move alterative in endgames

Post by Uri Blass » Wed Nov 16, 2011 10:06 pm

bob wrote:
Uri Blass wrote:
bob wrote:
Aleks Peshkov wrote:It is known that null move have problems detecting zugzwangs. But in most positions there is a known move that is legal most of time but almost always futile -- unmaking last made move back (in case if it is was a reversible move). It seems that this move is a better alternative to plain "no move" if it is a legal one, at least in typical late endgames.
I don't follow. If you play a real move, how can you safely reduce the depth as null-move does? The point of null-move is that giving your opponent the right to make two consecutive moves is such a powerful thing that you can do so, and reduce the depth, and if you are STILL winning, you can safely "fail high" here and move on. If you play a real move, why would you reduce the depth and use that result? If you do do that, why not just try ANY move?
The idea as I understand is to replace the null move in the search in the endgame by a real move that does not help the opponent and has a similiar effect to null move(except that you have no problem of zugzwangs).

This real move cannot be every move and it should be a move that does not change the evaluation function or almost does not change it.

You are not going to replace null move by some logical move that increase the static evaluation like pushing a passed pawn or centralizing the king.

Edit:I guess that if you cannot find a relevant move the idea is not to use something similiar to null move pruning but if you can find a relevant move then you can try it first with reduced depth and if it fail high you can skip other moves in the same way that you do in null move pruning.
However, you are still reducing the search by 2 plies. What makes THAT move one that you can say "making this move and giving my opponent 2 plies less to refute it means my position is really good?"

null-move makes sense. A real move does not.
A real move also make sense if it has the same effect as null move(meaning that the evaluation is the same or almost the same as the evaluation after a null move).

If that real move(that usually is not the move that you consider as best) with reduced search cause a cutoff then you skip searching all moves with full depth because probably there is also a real move that cause a cutoff.

If that real move does not cause a cutoff with reduced depth then you search normally all moves.

I do not know if the idea works practically and maybe there are programmers who tried it and found that it does not work for them but in theory it is not clear to me that the idea cannot work.

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

Re: Null move alterative in endgames

Post by bob » Thu Nov 17, 2011 12:42 am

Uri Blass wrote:
bob wrote:
Uri Blass wrote:
bob wrote:
Aleks Peshkov wrote:It is known that null move have problems detecting zugzwangs. But in most positions there is a known move that is legal most of time but almost always futile -- unmaking last made move back (in case if it is was a reversible move). It seems that this move is a better alternative to plain "no move" if it is a legal one, at least in typical late endgames.
I don't follow. If you play a real move, how can you safely reduce the depth as null-move does? The point of null-move is that giving your opponent the right to make two consecutive moves is such a powerful thing that you can do so, and reduce the depth, and if you are STILL winning, you can safely "fail high" here and move on. If you play a real move, why would you reduce the depth and use that result? If you do do that, why not just try ANY move?
The idea as I understand is to replace the null move in the search in the endgame by a real move that does not help the opponent and has a similiar effect to null move(except that you have no problem of zugzwangs).

This real move cannot be every move and it should be a move that does not change the evaluation function or almost does not change it.

You are not going to replace null move by some logical move that increase the static evaluation like pushing a passed pawn or centralizing the king.

Edit:I guess that if you cannot find a relevant move the idea is not to use something similiar to null move pruning but if you can find a relevant move then you can try it first with reduced depth and if it fail high you can skip other moves in the same way that you do in null move pruning.
However, you are still reducing the search by 2 plies. What makes THAT move one that you can say "making this move and giving my opponent 2 plies less to refute it means my position is really good?"

null-move makes sense. A real move does not.
A real move also make sense if it has the same effect as null move(meaning that the evaluation is the same or almost the same as the evaluation after a null move).

If that real move(that usually is not the move that you consider as best) with reduced search cause a cutoff then you skip searching all moves with full depth because probably there is also a real move that cause a cutoff.

If that real move does not cause a cutoff with reduced depth then you search normally all moves.

I do not know if the idea works practically and maybe there are programmers who tried it and found that it does not work for them but in theory it is not clear to me that the idea cannot work.
This discussion makes no sense. The "null-move observation" (that giving the opponent two moves in a row is such a powerful advantage, if he can't do any damage to me, my position is effectively winning. And that advantage is so powerful, I don't need nearly as deep a search to see that his two moves can't hurt me."

What does that have to do with something other than a null-move? I am mystified...

lkaufman
Posts: 3685
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Null move alterative in endgames

Post by lkaufman » Thu Nov 17, 2011 1:44 am

[quote="bob"

This discussion makes no sense. The "null-move observation" (that giving the opponent two moves in a row is such a powerful advantage, if he can't do any damage to me, my position is effectively winning. And that advantage is so powerful, I don't need nearly as deep a search to see that his two moves can't hurt me."

What does that have to do with something other than a null-move? I am mystified...[/quote]

I'm surprised that you don't see this Bob. The player who makes the reversed move has in effect made TWO null-moves, so it should be much safer to reduce than after just one null-move. I am pretty sure that this algorithm would be in every program now if for some reason null move didn't work. But I think that the concensus is that null move helps except in pawn endings, so the question here is whether this new idea is powerful enough to work even in pawn endings. I think it should be so. We should definitely test it in Komodo.

Post Reply