Endgame recognition

[niel5946]

Hi,

I am implementing null move pruning into my engine, and I am wondering what the best way of recognizing endgames is. In another engine i wrote, I just said that it was an endgame if the queens were removed, or the only non-pawn material left were queens (no knights, bishops or rooks), but I think it can be done better.

How do you determine if you're in an endgame when doing null move pruning?

[No4b]

In the chess engine i just check if there are any non-pawn pieces for the side i want to try NPM for (white have BKP, so i can do NMP; black have KPPPP, so i cant)

In my chess variant engine i just have some non-pawn-material threshold, if the side to move have more material than it, i do NMP

[hgm]

That you are in an end-game doesn't automatically mean you cannot use null-move pruning. This depends on whether there is a risk of zugzwang. It is usually assumed that this risk is minimal when you still have a slider. So a player with only Pawns and Knights had better switch it off.

This will mean you will occasionally lose with a Bishop, when it has to keep protecting two Pawns in different directions.

An alternative to switching off NMP is to do verified null-move pruning. Then you still do a strongly reduced search of the real moves even when the null-move fails high, and when that doesn't fail high, you continue that search to full depth. This way you will eventually see all zugzwangs, albeit only at a somewhat higher depth. But many zugzwangs lose material almost immediately, and you would not need much depth to see that. With pure NMP you would not see a zugzwang that loses you something in the reply because you have to stop protecting it, no matter how deep you search.

[niel5946]

That you are in an end-game doesn't automatically mean you cannot use null-move pruning. This depends on whether there is a risk of zugzwang. It is usually assumed that this risk is minimal when you still have a slider. So a player with only Pawns and Knights had better switch it off.

This will mean you will occasionally lose with a Bishop, when it has to keep protecting two Pawns in different directions.

An alternative to switching off NMP is to do verified null-move pruning. Then you still do a strongly reduced search of the real moves even when the null-move fails high, and when that doesn't fail high, you continue that search to full depth. This way you will eventually see all zugzwangs, albeit only at a somewhat higher depth. But many zugzwangs lose material almost immediately, and you would not need much depth to see that. With pure NMP you would not see a zugzwang that loses you something in the reply because you have to stop protecting it, no matter how deep you search.

Isn't this just null-move reductions? If I understand what you're saying correctly, this means that if I have a slider left, I can use LMP, but if I dont, I can use NMR. I could reduce depth by R - 1 in the real search and still gain speed while avoiding the risk of zugzwang.

Is this correct?

[hgm]

No, any sort of null move would make you fail to see zugzwangs. Because zugzwangs by definition are positions where passing your turn would be good, but doing any legal move is fatal. So the null move (turn pass) will return a score that is not representative for the position, but a gross overestimate. This doesn't depend on how deep you search; the turn pass can still be good with infinitely deep search. It is not a horizon effect, but it is the artefact caused by allowing an action that in reality is illegal. For example:

[d]8/8/8/3Kp3/4Pk2/8/8/8 w

White to move loses here, as the obligation to move forces him to abandon his Pawn. The opponent will capture it to convert to a won KPK. If, however, white null moves (and then black cannot, because you don't allow two null moves in a row), it is black who will have to abandon his Pawn, and white will win. You can search that as deep as you like, but that won't alter the fact that white will win. In the end your search will reach the checkmate. While the true result would have been opposit.

The way to avoid this is either switch of null move in positions like this (because you have no sliders here), or verify the null move with another reduced search of the real moves. Perhaps even more reduced than the null-move search itself. You often don't need much depth to see the zugzwang. Here you would already see at d=1 (+QS) that moving will lose you a Pawn.

[niel5946]

No, any sort of null move would make you fail to see zugzwangs. Because zugzwangs by definition are positions where passing your turn would be good, but doing any legal move is fatal. So the null move (turn pass) will return a score that is not representative for the position, but a gross overestimate. This doesn't depend on how deep you search; the turn pass can still be good with infinitely deep search. It is not a horizon effect, but it is the artefact caused by allowing an action that in reality is illegal. For example:

[d]8/8/8/3Kp3/4Pk2/8/8/8 w

White to move loses here, as the obligation to move forces him to abandon his Pawn. The opponent will capture it to convert to a won KPK. If, however, white null moves (and then black cannot, because you don't allow two null moves in a row), it is black who will have to abandon his Pawn, and white will win. You can search that as deep as you like, but that won't alter the fact that white will win. In the end your search will reach the checkmate. While the true result would have been opposit.

The way to avoid this is either switch of null move in positions like this (because you have no sliders here), or verify the null move with another reduced search of the real moves. Perhaps even more reduced than the null-move search itself. You often don't need much depth to see the zugzwang. Here you would already see at d=1 (+QS) that moving will lose you a Pawn.

Alright. I think my formulation was a bit misleading. What I was trying to say was exactly that: That if there are no sliders left one can switch to reductions instead of pruning, such that if the null move search still beats beta we don't prune, but instead reduce the depth to which we search the real moves. This reduced depth would still give a speedup (comparable to that of NMP?) while also letting the engine find the zugzwang (if one was there).
So in your example, the null move search would fail high, but since there isn't a slider on the board, the depth would just be reduced. Thus, when searching the real moves, we would still find the zugzwang. Correct?

[hgm]

Correct. This is what 'verified null-move pruning' does. Of course when you reduce much, you would not be able to see very deep zugzwangs. But most zugzwangs encountered in games (such as the example above, or what you need to force checkmate in KRK) are already visible in rather shallow searches. (KPK would still be a problem, though, as the difference only becomes visble when you actually promote, so it is usually better to switch off NMP completely in Pawn endings. Unless, of course, your evaluation is so smart that it already knows the outcom of a position without further search.)