Null move, razoring and mate threats

[jdart]

My program recently lost a game as part of a long test match:

[Event "?"]
[Site "?"]
[Date "2013.10.25"]
[Round "?"]
[White "EXchess-7.18"]
[Black "Arasan 16.2"]
[Result "1-0"]
[ECO "C95"]
[TimeControl "240"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3
d6 8. c3 O-O 9. h3 Nb8 10. d4 Nbd7 11. Nbd2 Bb7 12. Bc2 Re8 13. Nf1
Bf8 14. Ng3 g6 15. b3 c6 16. Bg5 Bg7 17. Qd2 Qc7 18. a4 a5 19. Bh6
Bxh6 20. Qxh6 Qb6 21. Ng5 b4 22. Re3 bxc3 23. Nf5 gxf5 24. Rg3 f4
1-0 {Black resigns}

The interesting thing here is, Arasan was quite slow to realize that it was getting mated. For example, consider the position after 23. Nf5:

[D] r3r1k1/1b1n1p1p/1qpp1npQ/p3pNN1/P2PP3/1Pp1R2P/2B2PP1/R5K1 b - - 0 23

Here White has a forced mate. After gxf5 Rg3 f4:

[D] r3r1k1/1b1n1p1p/1qpp1n1Q/p3p1N1/P2PPp2/1Pp3RP/2B2PP1/R5K1 w - - 0 25

White will play Ne6+ and Black can take the Rook or the Knight but in either case, it is checkmate next move. A very nice finish!

But what I see looking at the search is that even at search depth 8, the search is failing to see that all roads lead to mate. For example, after gxf5 Rg3 f4, I see:

trying 3. g5-e6 [-166,-165] d:15
in_check=1
trying 4. f4xg3(pv) [165,166] d:6
window [-166,-165]
stand pat score = -925
razored node, score=-166
4. f4xg3 166 (pv)
beta cutoff

So it sees that the check can be escaped with a winning capture and the position after that is so bad for White, material-wise, that the razoring code cuts it off and it stops there, and does not see that there is a mate next move. In general the search is very ruthless about pruning losing checks because a lot of them are just throwing away pieces. But in this case it is wrong.

I found that Arasan did a lot better in this position if I disabled razoring and null move when the previous move was extended for any reason, such as moves that are forced escapes from check (I also extend a little if there are only 2 escape moves). But this mod performed a lot worse when tested over a large population of games.

--Jon

[gladius]

A fun position to analyze! SF spots it in 5 ply - I suspect because the bonus assigned to king safety, because of a safe queen contact check (in this case a mate . SF effectively doubles the king safety bonus when doing futility pruning, so it seems enough to overcome the material loss in this case.

We tested out a version which brought back the queen contact check mate in evaluation, and it does very well on this position, finding the mate at depth 3, but sadly, it wasn't enough ELO to make it in.

[lucasart]

I found that Arasan did a lot better in this position if I disabled razoring and null move when the previous move was extended for any reason, such as moves that are forced escapes from check (I also extend a little if there are only 2 escape moves). But this mod performed a lot worse when tested over a large population of games.

Obviously it performed much worse in terms of ELO. Forbidding null move when the previous move was extended is way too costly.

Instead of doing two modifications at the same time, you should perhaps try them one at a time:
* no null move when previous move was extended
* no razoring when previous move was extended

My guess is that both will fail anyway, and a fortiori the union will fail even worse.

I have tried to fix tactics in DiscoCheck by similar ideas, and they all failed. Just to give one example:

• I tried to disable razoring when the previous move was a null move (razor fail low, hence null fail high in parent node, which is a good source of missed tactics).
• It failed the test, and scored the same as with razoring disabled completely! The reason is obvious: simply inserting a counter shows that over 95% of the time the parent node of the razor node did a null move...

I know it's hard to accept, and we always want to find ways to solve this or that position faster, but whenever I've tried to do that, it was at best useless, and most often regressive. But it's so tempting...

Another possible reason why these tricks don't work is that they are path-dependant: path-dependant + hash table = nonsense (at least theoretically).

[Henk]

Of course I do not understand razoring. Why doesn't razoring reduce or prune a move that opens a diagonal or line for a winning combination.

If the move is researched then it's not a problem but researches take extra time and then there will be no gain.

[Ferdy]

So it sees that the check can be escaped with a winning capture and the position after that is so bad for White, material-wise, that the razoring code cuts it off and it stops there, and does not see that there is a mate next move. In general the search is very ruthless about pruning losing checks because a lot of them are just throwing away pieces. But in this case it is wrong.

I found that Arasan did a lot better in this position if I disabled razoring and null move when the previous move was extended for any reason, such as moves that are forced escapes from check (I also extend a little if there are only 2 escape moves). But this mod performed a lot worse when tested over a large population of games.

--Jon

[D] r3r1k1/1b1n1p1p/1qpp1n1Q/p3p1N1/P2PPp2/1Pp3RP/2B2PP1/R5K1 w - - 0 25
I generate quiet checks in qsearch if capture and promote moves does not improve alpha.
These moves are prunned if SEE is bad except when it is a hash move. The position is
special because the Ne6 move checks the black king but it is the rook in g3 that does the attack.
Discovered check is indeed dangerous and should not prunned easily, a quick evasion is to capture the rook in g3,
but after that the Ne6 move had already created a deadly combination without regards on the material.

I increase razor margin when there is queen because this piece is dangerous especially when
other pieces are also participating in the attack. Even here the queen position is not ordinary.
A special evaluation feedback before doing razoring probably will help.

Other than that I want to see now my king safety eval there might be codes that are not kicking as intended.

[jdart]

A while ago I tried different extensions for discovered check but it was not a successful idea.

I increase razor margin when there is queen

.

That might possibly help, it is a cheap fix anyway.

--Jon

[Lyudmil Tsvetkov]

I also get the impression that sometimes even top engines reduce too much where they are not supposed to. I do not know if this is due to futility pruning, small margins, etc., but I am sure there are positions where it would be wise not to reduce anything.

My stupid question would be if it is not possible to use eval in a wise way when deciding how much to reduce. For example, it seems that reducing any lines, even if one of the sides gets 5-6 pawns material advantage, would be a suspicious decision, if:
- the king shelter is weakened, just one pawn, or 2 isolated ones, like f7 and h7 in the Jon position
- there is a massive king attack

I think that 5-6 pawns material advantage can not safeguard you from a potential tactical loss, but 9-10 pawns could in similar positions.

I got that impression from my games against engines, where they sometimes, happy with some material gain, as if stop calculating these lines further. It is pretty much obvious, because they allow really very shallow tactics in such situations. But also the fact that almost all top engines perform relatively worse in openings with a sharp material advantage for one of the sides, but positional compensation for the other, like the King's Gambit, might suggest that, being most sophisticated, also in their search, they reduce more than other engines, but such a decision would be wrong with badly sheltered kings or massive attacks.

[jdart]

Indeed there are programs that use information from the static eval (not just the value but details like hanging pieces) to guide search decisions.

This is not so easy to do for me since I use lazy eval and try to avoid a full evaluation whenever possible.

--Jon

[emadsen]

[D]r3r1k1/1b1n1p1p/1qpp1n1Q/p3p1N1/P2PPp2/1Pp3RP/2B2PP1/R5K1 w - - 0 25

White will play Ne6+ and Black can take the Rook or the Knight but in either case, it is checkmate next move. A very nice finish!

But what I see looking at the search is that even at search depth 8, the search is failing to see that all roads lead to mate.

My modest-strength chess engine sees mate at depth 3. My rules for null move, reductions, and pruning:

Don't Attempt Null Move
At root
ToHorizon <= 2
When king is in check
ToHorizon > 4 and material score < beta
ToHorizon <=4 and static score < beta
Side to move has one minor or major piece or less.

Don't Reduce (LMR)
Captures in main search
Pawn promotions
Moves that give check
When king is in check

Don't Prune (Futility)
Captures in main search
Pawn promotions
Moves that give check
When king is in check
Root moves
First legal move
ToHorizon > 4
Abs(Alpha) or Abs(Beta) >= Checkmate score

My null move reduction is 2.
My late move reductions of depth 1, 2, 3 are at quiet moves 3, 7, 15.
My futility margins at QS, 1, 2, 3, 4 are 100, 150, 250, 400, 600.
My qsearch examines all moves when king is in check (and cannot stand pat), only captures otherwise.

Code: Select all

go infinite
info depth 1 seldepth 14 score cp -262 time 247 nodes 1828 nps 7415 pv g3c3
info hashfull 0 currmove g1h2 currmovenumber 34 cpuload 0
info depth 2 seldepth 9 score cp -262 time 262 nodes 2236 nps 8546 pv g3c3 e5d4
info hashfull 0 currmove g1h2 currmovenumber 34 cpuload 0
info depth 3 seldepth 13 score cp -162 lowerbound time 279 nodes 4437 nps 15912
info hashfull 0 currmove g5e6 currmovenumber 7 cpuload 0
info depth 3 seldepth 13 score cp 238 lowerbound time 280 nodes 4532 nps 16191
info hashfull 0 currmove g5e6 currmovenumber 1 cpuload 0
info depth 3 seldepth 13 score mate 2 time 285 nodes 5220 nps 18292 pv g5e6 f4g3 h6g7
info hashfull 0 currmove g1h2 currmovenumber 34 cpuload 0
info depth 4 seldepth 7 score mate 2 time 300 nodes 7754 nps 25815 pv g5e6 f4g3 h6g7
info hashfull 0 currmove g1h2 currmovenumber 34 cpuload 0
info depth 5 seldepth 11 score mate 2 time 359 nodes 15465 nps 43120 pv g5e6 f4g3 h6g7
info hashfull 0 currmove g1h2 currmovenumber 34 cpuload 295

[gladius]

My modest-strength chess engine sees mate at depth 3. My rules for null move, reductions, and pruning:

I think the depth 8 was referring to the earlier position (r3r1k1/1b1n1p1p/1qpp1npQ/p3pNN1/P2PP3/1Pp1R2P/2B2PP1/R5K1 b - - 0 23)

SF finds the mate at depth 1 in the second position. After Ne6+, black captures the rook, then white searches see >0 checks+captures, finding the mate. Even adding checks to just the first ply of q-search should be a huge help, allowing you to reduce more aggressively in null moves.