Null move alterative in endgames

[bob]

So in both cases it is much safer than null move. The only question in my mind is whether it will save enough time to be worthwhile. I don't expect a big gain from this, maybe just one elo or so.

There are positions where null-move makes impossible to find the right solution regardless of spent time. LMR and "legal null move" does not suffer from it, so they are better at least in analysis mode.

You are comparing your algorithm to traditional null move. But most programs don't use null move in pawn endings. The proper comparison for pawn endings is between your algorithm and no null move. I think your idea should bring a noticeable speedup in pawn endings, at almost no cost. It might be worth 50 elo in pawn endings. Unfortunately that translates to only one or two elo in actual play. Similarly in analysis of pawn endings it may bring a noticeable benefit, but it is rare to encounter a pawn ending which a computer in analysis mode can't solve correctly.

I still believe that because of the repetition problem it is going to hurt, not help...

Well, no need to speculate. Don plans to implement it tonite so I may have some results tomorrow.

Do you know his plan? Either normal null-move or when one would normally disable null-move do this instead, still with reduced depth??? I could try to test as well if I can work my way out of a pile of things to do this afternoon...

[bob]

So in both cases it is much safer than null move. The only question in my mind is whether it will save enough time to be worthwhile. I don't expect a big gain from this, maybe just one elo or so.

There are positions where null-move makes impossible to find the right solution regardless of spent time. LMR and "legal null move" does not suffer from it, so they are better at least in analysis mode.

Two questions. If you "unmake" are you still going to do a reduced-depth (R=3 or whatever) search? If so, are you sure that unmaking a move is such a bad thing that a shallow search can prove that if the "unmaking a move" is still ok for me, I am winning?

What about the rather obvious repetition problem?

At ply=N I make a move. At N+1 you make a move. And N+2 I unmake my move. You can now instantly limit the score at N+3 to be no less than a draw score, because if you unmake your move, we have a repetition. Seems to be a problem to me.

Is there any reason you can't explicitly tell the program to ignore such repetitions? Since I don't write the code myself, I don't know how difficult that will be, but I already mentioned the need for this to Don and he didn't indicate that it would be a problem for him.

There are issues. Do you disable ALL repetitions below such an "unmake"? Would seem to hurt quite a bit if so...

But let me give it a try later this afternoon. I'll post my results later as well...

[bob]

There are other issues. I make a move, you make a move, I "unmake" my last move. I just guaranteed that the score for your move will not be less than the draw score, because you can ALWAYS unmake your move too, and that is a repetition.

Only in half of the cases and only if you MAKE it a repetition. You can always flag the unmove as irreversible, this was already addressed above.
The existence of issues doesn't make an idea invalid.

I find allowing repetitions after a null-move to be a performance gain. So disabling them would seem to lose something for certain. I consider THAT to be an issue (losing anything is an issue).

That is just one problem. Much more sensible, in my opinion, is to just turn null move off when the probability of zugzwang positions climbs above some threshold...

The rule that applies here is that one good measurement means more than a thousand expert opinions. With new ideas it is best to look with an open mind at what is potentially in it instead of focussing on bears on the road. If intuition were our guide there would not be 3000+ elo engines today.

Some programs flag the null move as irreversible, as intuition dictates. Some other don't bother and don't seem to suffer...

And some test it both ways and find an elo GAIN to not flag it as irreversible.

This discussion was done earlier this year or else last year. I currently only ignore reps for the first 4 moves after a null. Then rep detection is back on looking for reps all the way back to the last real non-reversible move in the game.

Some programs switch off null move in the end games, as intuition dictates. Some others don't bother and don't seem to suffer...
Some programs probe EGTs in the endgame, as intuition dictates. Some others don't bother and don't seem to suffer...
Some programs have singular extensions as intuition dictates. Some others don't bother and don't seem to suffer...
Some programs have lazy evaluation, as intuition dictates. Some others don't bother and don't seem to suffer...

[lkaufman]

[quote="marcelkThe rule that applies here is that one good measurement means more than a thousand expert opinions. With new ideas it is best to look with an open mind at what is potentially in it instead of focussing on bears on the road. If intuition were our guide there would not be 3000+ elo engines today.

Some programs flag the null move as irreversible, as intuition dictates. Some other don't bother and don't seem to suffer...
Some programs switch off null move in the end games, as intuition dictates. Some others don't bother and don't seem to suffer...
Some programs probe EGTs in the endgame, as intuition dictates. Some others don't bother and don't seem to suffer...
Some programs have singular extensions as intuition dictates. Some others don't bother and don't seem to suffer...
Some programs have lazy evaluation, as intuition dictates. Some others don't bother and don't seem to suffer...[/quote]

I agree with most of what you say above, except for two items. As far as I know, none of the top programs (Houdini and other Ippolits, Komodo, Critter, Rybka, Stockfish) do null move in pawn endings, and all of them do singular extension. So there is very good evidence that programs that don't do these two things do suffer, since all other programs are miles behind the top five.

Regarding lazy eval, you are quite right. We can't make it work for Komodo, and yet other top programs use it. I think Bob reported huge benefits for it in Crafty, as have some others. I still don't understand why it doesn't help Komodo. For us the speedup is tiny and clearly not worth it.

[lkaufman]

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.

Null move in endgames is not a bad thing for game play. Null move in pawn endings is a bad thing, almost everyone agrees. Are you in doubt about this?

[Gerd Isenberg]

Only in half of the cases and only if you MAKE it a repetition. You can always flag the unmove as irreversible, this was already addressed above.
The existence of issues doesn't make an idea invalid.

If one applies avoid repetition pruning, that is to prune the undo of A if alpha(A) > DRAW_SCORE and B is able to undo itself for a repetition, there are still the cases left to reduce by Aleks' proposal where B may not undo its move because it was irreversible or interacts with the move of A so that undo(B) is not possible, or alpha(A) <= DRAW_SCORE. I think to flag the reversible undo(A) as irreversible is not necessary.

[lkaufman]

So in both cases it is much safer than null move. The only question in my mind is whether it will save enough time to be worthwhile. I don't expect a big gain from this, maybe just one elo or so.

There are positions where null-move makes impossible to find the right solution regardless of spent time. LMR and "legal null move" does not suffer from it, so they are better at least in analysis mode.

You are comparing your algorithm to traditional null move. But most programs don't use null move in pawn endings. The proper comparison for pawn endings is between your algorithm and no null move. I think your idea should bring a noticeable speedup in pawn endings, at almost no cost. It might be worth 50 elo in pawn endings. Unfortunately that translates to only one or two elo in actual play. Similarly in analysis of pawn endings it may bring a noticeable benefit, but it is rare to encounter a pawn ending which a computer in analysis mode can't solve correctly.

I still believe that because of the repetition problem it is going to hurt, not help...

Well, no need to speculate. Don plans to implement it tonite so I may have some results tomorrow.

Do you know his plan? Either normal null-move or when one would normally disable null-move do this instead, still with reduced depth??? I could try to test as well if I can work my way out of a pile of things to do this afternoon...

That's right, when one would normally disable null-move (due to type of endgame, for example pawn-endgames), do this instead, with the same depth reduction. Flag the reversed move as non-reversible for repetitions.

[bob]

So in both cases it is much safer than null move. The only question in my mind is whether it will save enough time to be worthwhile. I don't expect a big gain from this, maybe just one elo or so.

There are positions where null-move makes impossible to find the right solution regardless of spent time. LMR and "legal null move" does not suffer from it, so they are better at least in analysis mode.

You are comparing your algorithm to traditional null move. But most programs don't use null move in pawn endings. The proper comparison for pawn endings is between your algorithm and no null move. I think your idea should bring a noticeable speedup in pawn endings, at almost no cost. It might be worth 50 elo in pawn endings. Unfortunately that translates to only one or two elo in actual play. Similarly in analysis of pawn endings it may bring a noticeable benefit, but it is rare to encounter a pawn ending which a computer in analysis mode can't solve correctly.

I still believe that because of the repetition problem it is going to hurt, not help...

Well, no need to speculate. Don plans to implement it tonite so I may have some results tomorrow.

Do you know his plan? Either normal null-move or when one would normally disable null-move do this instead, still with reduced depth??? I could try to test as well if I can work my way out of a pile of things to do this afternoon...

That's right, when one would normally disable null-move (due to type of endgame, for example pawn-endgames), do this instead, with the same depth reduction. Flag the reversed move as non-reversible for repetitions.

OK, there is MUCH more to this than there appears to be at first glance.

(1) what if the move two plies earlier was a pawn more or a capture? You can't "unmake" that. Now what?

(2) what if the piece moved two plies earlier was captured by the opponent? You can't "unmake" that. Now what? In fact, the piece moved 2 plies earlier might have been your last piece, and when it was captured, it triggered this new "unmake-move" rather than "a normal null-move" search? The piece is gone and the move can't be unmade.

(3) I try nulls unless there are no pieces left. So moves are either pawn moves which can't be unmade, or else king moves which can not always be "unmade". I move my king, you move a pawn or your king, attacking the square my king was on, I now can't unmake that either. In short, one has to exclude this for any move 2 plies back that moves ANYTHING other than the king, as that is the only thing that can be "reversed" in a K+P position. And not all of those can be unmade as I said.

About all I can think of is to simply "give up" if any of the above are true and do nothing at all? It is a big percentage of the time in just king and pawn endings... Which means most of the time it can't even be done.

Working on trying this right now, but after seeing the exceptions above, I don't expect any gain at all, and now really expect it to lose something because the null-move observation is being totally factored out..

Would seem to me that if this is going to work, it should be done somewhere else. How about reducing a move that "unmakes" the move two plies back, when in a king and pawn endgame. Same effect... done in a more rational and logical way...

The bottom line is that the pseudo-code has to look something like this:

if (pieces_are_left()) { do normal null-move search }
else if (piece_moved_2plies_back == king, and from_2plies_back is not attacked by opponent)
{ Invert from/to on move 2 plies back and make that and do a reduced search exactly as done for null-move}

Working to clean it up and then test while I give a test in my x86 asm class.

[marcelk]

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.

Null move in endgames is not a bad thing for game play. Null move in pawn endings is a bad thing, almost everyone agrees. Are you in doubt about this?

No, I meant endings in general.. I'm conservative currently and disable it when there is at most one slider left. At the time I didn't have a good test method yet and I will revisit it early next year as it can sure be improved. But like others I also have a hard time to believe that nulls could work in pawn-only endings.

[lkaufman]

[OK, there is MUCH more to this than there appears to be at first glance.

(1) what if the move two plies earlier was a pawn more or a capture? You can't "unmake" that. Now what?

(2) what if the piece moved two plies earlier was captured by the opponent? You can't "unmake" that. Now what? In fact, the piece moved 2 plies earlier might have been your last piece, and when it was captured, it triggered this new "unmake-move" rather than "a normal null-move" search? The piece is gone and the move can't be unmade.

(3) I try nulls unless there are no pieces left. So moves are either pawn moves which can't be unmade, or else king moves which can not always be "unmade". I move my king, you move a pawn or your king, attacking the square my king was on, I now can't unmake that either. In short, one has to exclude this for any move 2 plies back that moves ANYTHING other than the king, as that is the only thing that can be "reversed" in a K+P position. And not all of those can be unmade as I said.

About all I can think of is to simply "give up" if any of the above are true and do nothing at all? It is a big percentage of the time in just king and pawn endings... Which means most of the time it can't even be done.

Working on trying this right now, but after seeing the exceptions above, I don't expect any gain at all, and now really expect it to lose something because the null-move observation is being totally factored out..

Would seem to me that if this is going to work, it should be done somewhere else. How about reducing a move that "unmakes" the move two plies back, when in a king and pawn endgame. Same effect... done in a more rational and logical way...

The bottom line is that the pseudo-code has to look something like this:

if (pieces_are_left()) { do normal null-move search }
else if (piece_moved_2plies_back == king, and from_2plies_back is not attacked by opponent)
{ Invert from/to on move 2 plies back and make that and do a reduced search exactly as done for null-move}

Working to clean it up and then test while I give a test in my x86 asm class.

Yes, I told Don just to "give up" when the move can't be unmade, such as a pawn move or a king move that would now be illegal. I think that there are generally more king moves than pawn moves in pawn endgames, though I'm not certain. Perhaps close to half the moves will not be eligible for this algorithm. But when no move is eligible, nothing is lost either!
As for reducing unmake moves, this could be done throuout the search, not just in pawn endings. It sounds good, but the problem is that most "unmake" moves (after good ones at least) will have very poor history and will already be near the end of the list and already get heavily reduced, assuming you now use history. If you don't, this might work for you but not for us. But I think it is more logical to do it as suggested in the null move context, because a move and its unmake are the equivalent of two null moves.