lkaufman wrote: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...
Ok, here is what I did, which is probably already clear from my last post of a few minutes ago.
I didn't change any pruning rules or reductions, it's exactly the same as normal null move pruning except instead of doing null move I play the reverse of the most last played for the side to move. And then only if it's legal. If it's not legal I don't use it and go full width. I flag the move as irreversible which also restarts the 50 move counter. A null move of course is not reversed.
bob wrote:[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.
In my implementation I undo captures too which can only apply to king captures in king and pawn endings. I don't restore the piece captured however, I just move the king back to the original square.
There are some similarities with multi-cut - which basically involves trying N moves at reduce depth (and replaces null move pruning) and requiring some subset of them to return a score >= beta. This is almost a special case of that except that N is 1 and the move is pre-destined.
hgm wrote: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.
I agree with you on this. Null move pruning does not work so well in games where long term threats are prolific. And in king and pawn endings a simple king move can be a very long term threat.
A few years ago when programs rarely exceeded 5 or 6 ply, even null move pruning was defeated by players able to set up long term slow building king side attacks. Every time you do a null move you give away 2 or 3 ply of threat resolution.
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.
lkaufman wrote: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...
Ok, here is what I did, which is probably already clear from my last post of a few minutes ago.
I didn't change any pruning rules or reductions, it's exactly the same as normal null move pruning except instead of doing null move I play the reverse of the most last played for the side to move. And then only if it's legal. If it's not legal I don't use it and go full width. I flag the move as irreversible which also restarts the 50 move counter. A null move of course is not reversed.
One subtle note in case you missed it. I discovered last year with a lot of testing that allowing repetition detection after a null-move helps Elo. With a restriction. The restriction is that I disable repetitions for the first 4 plies (including the ply that plays the null) only, and then turn it back on, but I allow repetitions to be detected across the null-move. That is, a position 5 plies below a null move can match with one 10 plies before the null and I call that a draw. I am not completely sure why that "4" works best, but I played hundreds of thousands of games to find that "point"...
lkaufman wrote: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...
Hi Bob,
I'm jumping into this discussion late and have not read anything that comes after, but I have already tried it in Komodo based on Larry's suggestion. I don't really unmake the move, I reverse it and only if it's legal. So I cannot reverse pawn moves since it is not legal to move them backwards. I just don't prune these moves - admittedly in king and pawn endings that may nullify some of the benefit.
The repetition is no problem, I can't understand why you see that as a hurdle with your programming skill. In my case I just call the reversed move an irreversible move so that I do not check it for repetition or any moves prior to it. That is pretty simple, right?
Since you are reversing a move, it's like you never made it, so it's generally going to be similar to a null move in power. There may be bizarre exceptions but in general this should not normally be a useful move.
Having said all of that, the idea did not pan out in Komodo.
I think that "non-reversible" trick hurts more than it helps, based on my testing last year with repetitions across a null-move. For my testing this time around, I used the same idea I use for nulls, that is that repetitions are disabled for 4 consecutive plies, counting the ply where the null-move is played. After that, repetitions can happen across the null-move, or in the current case, across the "retracted move"...
BTW it didn't do a thing for me either, so I tossed it out as I have so many other ideas the past 6 months, ideas that sometimes sound good, but which don't help, or actually hurt...
hgm wrote: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.
If that is true, it should be possible to play a null move in pawn endings and just not reduce. The null move could still fail high and give you a cutoff, or at the very least it gives you an indiaction about the opponent's threats.
Of course that doesn't mean that it would actually be beneficial to try the unreduced null move in pawn endings, but it would at least be testable.
