Null move alterative in endgames

[bob]

[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.

Testing for me is done. This had absolutely ZERO effect on Elo...

Crafty-23.5-2 2674 4 4 30000 63% 2567 22%
Crafty-23.5nmm 2673 3 3 60000 63% 2567 22%
Crafty-23.5-1 2672 4 4 30000 63% 2567 21%

I am not sure why my "nnm" version (which had two separate runs) was combined into one, but it made no difference in anything. I will go back after lunch and correct the names in one of the runs to separate them.]

As I observed, if the only thing you can unmake is a king move, and you can't even unmake all of them, I could not see how this would be anything significant at all. It seems to be so...

23.5-1 and 23.5-1 are just two separate 30K tests of the most recent 23.5 version. 23.5nnm is that exact same source, but with the null-move replacement idea in pawn-only endings...

And again, make/unmaking a move is not quite the same thing as making a null-move. It is an extra reduction because you took two plies to play a "null". And many have other considerations, such as can you now allow a "double double-null" (consecutive make/unmake/make/unmake?) And then there is repetition, where if you disable repetition below a null you hurt performance, if you don't disable here, you have an artificial lower bound because of the "draw in hand" your opponent has, etc...

Seems like a lot of ifs, maybes, and effort. And for no return at all based on a quick 60,000 games...

It might be interesting to insert counters to see how often the new code is executed. One consequence of your testing methodology is that a change that makes a significant difference in relatively rare situations may well not be recognized as clearly better. Another way to estimate the possible size of the change is to test regular null move in pawn endings and see how many elo worse it is (you may have already done this at some time).

I did run it, but do not remember the results. With the cluster idle, it is easier to re-run than look thru a gazillion prior matches for the answer. Should be done later today, will post the results...

[Uri Blass]

[quote="bobDo you guys do the same with null-move as I do? IE only shut 'em off when all pieces are gone? I have not (yet) tested to see what might happen with turning null-move off a bit earlier and then relying on this a little heavier. Certainly with just king and pawns, there is little opportunity to use this trick since it only applies to some of the king moves but not all. And only when you reach pieceless endings, where most games are already resolved, result-wise.

Yes, we also shut off null-move only in pawn endings. Today we tried what you suggest, turning null-move off a bit earlier in favor of this reversed move idea. When I tried it in all endings with one minor piece each or less, the result was negative. When I tried it only in knight endings (and the pawn endings), the results were mixed; overall a tiny elo gain at fixed depth for a tiny node increase. As is often the case, it will probably be too difficult to measure whether this is an improvement or not, but perhaps I'll try.[/quote]

I wonder if somebody tried to replace null move pruning by random move multicat pruning(it can be used not only in endgame).

The idea is simply to make a random move and search after the random move with reduced depth
if the random move cause a cutoff then do the same with another random move and if 2 random moves cause a cutoff you decide to return beta.

The idea is that if 2 random legal moves are good enough to produce a cutoff then probably the position is good and it is a waste of time to search with full depth.

[lkaufman]

[quote="Uri BlassI wonder if somebody tried to replace null move pruning by random move multicat pruning(it can be used not only in endgame).

The idea is simply to make a random move and search after the random move with reduced depth
if the random move cause a cutoff then do the same with another random move and if 2 random moves cause a cutoff you decide to return beta.

The idea is that if 2 random legal moves are good enough to produce a cutoff then probably the position is good and it is a waste of time to search with full depth.[/quote]

I never heard this idea of random multicut (as opposed to normal multicut). Is this your idea or a known idea? Has this been tested in general (not just in the endgame as you suggest)?

[bob]

The old results were actually easier to find than I thought. Result was doing null-move in pawn-only endings was -6 Elo. Not huge. But turning null-move off at that point was the best value, that is, null until there are no pieces left for the side to move. Turning it off earlier hurts more than leaving it on everywhere...

Note I do not do double-nulls (I consider that a waste although it can let null-move work pretty well in pawn-only endings)..

[lkaufman]

Note I do not do double-nulls (I consider that a waste although it can let null-move work pretty well in pawn-only endings)..

Double-null in pawn endings only sounds reasonable to me. Did you ever test that?

[Uri Blass]

[quote="Uri BlassI wonder if somebody tried to replace null move pruning by random move multicat pruning(it can be used not only in endgame).

The idea is simply to make a random move and search after the random move with reduced depth
if the random move cause a cutoff then do the same with another random move and if 2 random moves cause a cutoff you decide to return beta.

The idea is that if 2 random legal moves are good enough to produce a cutoff then probably the position is good and it is a waste of time to search with full depth.

I never heard this idea of random multicut (as opposed to normal multicut). Is this your idea or a known idea? Has this been tested in general (not just in the endgame as you suggest)?[/quote]

I also never heard about the idea that I suggested but of course it does not prove that it is not a known idea(because I do not claim to know every known idea).

[bob]

Note I do not do double-nulls (I consider that a waste although it can let null-move work pretty well in pawn-only endings)..

Double-null in pawn endings only sounds reasonable to me. Did you ever test that?

Yes, It just never produced anything that was stronger. It's an easy thing to test. I will see if I can either find the results or run the test again...

[hgm]

I don't think zugzwang is the major issue that makes null-move fail in pawn endings. So this proposal could very well be a 'solution' to a non-existing problem.

Null-move doesn't perform in pawn edigs, because you cannot afford reductions in such endings. "When he can't hurt me when I pass my turn, he will likely not be able to hurtme when I make my best move" is of course a non-starter for explaining null-move pruning, because it doesn't describe what the latter is doing. More accurate would be: "When he can hurt me when I pass my turn, but I turn a blind eye to it (by reducing depth!), he won't be able to hurt me when I make my best move". And in Pawn endings that is usually not true.

The reason is that in Pawn endings it is usually not possible to find forcing moves that can push the threat over the horizon. (Like attacking his Queen, so that he has to withdra itfirst, or fail low, or to capture something, which he must recapture or fail low despite his threat.) The only way to be reasonably confident that you won't be slaughtered after your best move is to play an unreduced null move. Which kind of spoils most of the gains standard ull-move pruningbrings you.

How important zugzwags are for NMP can easily be tested on pawn endings in a chess variant that only differs from standard chess in that ull-moving is legal. Zugzwag is a non-existent concept in that variant. My prediction is that standard null-move pruning will also be counter-productive there.

Note that Crafty was reported to not have any problems winning KRK with null-move switched on. While we all know zugzwang is completely essential for wining that end-game.

[bob]

I don't think zugzwang is the major issue that makes null-move fail in pawn endings. So this proposal could very well be a 'solution' to a non-existing problem.

Null-move doesn't perform in pawn edigs, because you cannot afford reductions in such endings. "When he can't hurt me when I pass my turn, he will likely not be able to hurtme when I make my best move" is of course a non-starter for explaining null-move pruning, because it doesn't describe what the latter is doing. More accurate would be: "When he can hurt me when I pass my turn, but I turn a blind eye to it (by reducing depth!), he won't be able to hurt me when I make my best move". And in Pawn endings that is usually not true.

The reason is that in Pawn endings it is usually not possible to find forcing moves that can push the threat over the horizon. (Like attacking his Queen, so that he has to withdra itfirst, or fail low, or to capture something, which he must recapture or fail low despite his threat.) The only way to be reasonably confident that you won't be slaughtered after your best move is to play an unreduced null move. Which kind of spoils most of the gains standard ull-move pruningbrings you.

How important zugzwags are for NMP can easily be tested on pawn endings in a chess variant that only differs from standard chess in that ull-moving is legal. Zugzwag is a non-existent concept in that variant. My prediction is that standard null-move pruning will also be counter-productive there.

Note that Crafty was reported to not have any problems winning KRK with null-move switched on. While we all know zugzwang is completely essential for wining that end-game.

You are correct about KRK, which means I will have to think about that. As far as zugzwang in KP endings, you may wall be right there.. but that will take a ton of analysis that I am not sure is worth the effort. All I know, for sure, is that the deeper into the endgame I extend "null-move enabled" the higher the Elo, until I reach just king and pawns, where the Elo drops -6 from turning null-move on all the time, as opposed to turning it off when the last piece disappears.

I still think that the "null-move observation" is a critical component of this, that "if I let my opponent make two moves in a row and I am still >= beta, my position is good enough to stop searching it". Zugzwang is the thing that makes that fail, as doing "nothing" is sometimes better than doing "anything" which is a real problem. Certainly reduced depth is an issue. But I think it is less of an issue so long as zugzwang doesn't bite...

[Ferdy]

I don't think zugzwang is the major issue that makes null-move fail in pawn endings. So this proposal could very well be a 'solution' to a non-existing problem.

Null-move doesn't perform in pawn edigs, because you cannot afford reductions in such endings. "When he can't hurt me when I pass my turn, he will likely not be able to hurtme when I make my best move" is of course a non-starter for explaining null-move pruning, because it doesn't describe what the latter is doing. More accurate would be: "When he can hurt me when I pass my turn, but I turn a blind eye to it (by reducing depth!), he won't be able to hurt me when I make my best move". And in Pawn endings that is usually not true.

The reason is that in Pawn endings it is usually not possible to find forcing moves that can push the threat over the horizon. (Like attacking his Queen, so that he has to withdra itfirst, or fail low, or to capture something, which he must recapture or fail low despite his threat.) The only way to be reasonably confident that you won't be slaughtered after your best move is to play an unreduced null move. Which kind of spoils most of the gains standard ull-move pruningbrings you.

How important zugzwags are for NMP can easily be tested on pawn endings in a chess variant that only differs from standard chess in that ull-moving is legal. Zugzwag is a non-existent concept in that variant. My prediction is that standard null-move pruning will also be counter-productive there.

Note that Crafty was reported to not have any problems winning KRK with null-move switched on. While we all know zugzwang is completely essential for wining that end-game.

You are correct about KRK, which means I will have to think about that. As far as zugzwang in KP endings, you may wall be right there.. but that will take a ton of analysis that I am not sure is worth the effort. All I know, for sure, is that the deeper into the endgame I extend "null-move enabled" the higher the Elo, until I reach just king and pawns, where the Elo drops -6 from turning null-move on all the time, as opposed to turning it off when the last piece disappears.

I still think that the "null-move observation" is a critical component of this, that "if I let my opponent make two moves in a row and I am still >= beta, my position is good enough to stop searching it". Zugzwang is the thing that makes that fail, as doing "nothing" is sometimes better than doing "anything" which is a real problem. Certainly reduced depth is an issue. But I think it is less of an issue so long as zugzwang doesn't bite...

Bob I don't know if you have tried this, instead of doing a null move, try to find a worst move (say a move that gives material) and make it. Now I think this is much worst than passing.