Test positions for draw detection

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Nordlandia
Posts: 2372
Joined: Fri Sep 25, 2015 7:38 pm
Location: Sortland, Norway

Re: Test positions for draw detection

Post by Nordlandia » Fri Oct 02, 2015 9:23 pm

[pgn][Event "?"]
[Site "?"]
[Date "????.??.??"]
[Round "?"]
[White "New game"]
[Black "?"]
[Result "*"]
[SetUp "1"]
[FEN "1N1Brkbn/5p2/6pr/4P1Pp/4P3/7K/8/7N w - - 0 0"]
[PlyCount "35"]

1. Nd7+ Kg7 2. Bf6+ Kh7 3. Kh4 Rc8 4. Nf2 Re8 5. Nh3 Ra8 6. Ng1 Rc8 7. Nf3 Re8
8. Ne1 Ra8 9. Nd3 Rc8 10. Nc1 Ra8 11. Na2 Re8 12. Nb4 Rc8 13. Nc2 Re8 14. Ne3
Rc8 15. Nc4 Re8 16. Ncb6 Rb8 17. e6 fxe6 18. Nxb8 *[/pgn]

User avatar
hgm
Posts: 23468
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Test positions for draw detection

Post by hgm » Fri Oct 02, 2015 9:35 pm

I was expecting gxh6 instead of e6.

User avatar
hgm
Posts: 23468
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Test positions for draw detection

Post by hgm » Sat Oct 03, 2015 8:45 am

A more simplistic and perhaps sufficient implementation could be the following:

Whenever alpha is at a rep-draw score in a node with negative eval, don't search moves with window {alpha, beta} but with window {alpha-1, beta}. This will tell you whether the moves will be able to force a rep-draw too. (Which you would not know when you searched them with alpha = repDraw, as it might just return the repDraw because the opponent made no effort to avoid it, assuming the rep-draw was as good a refutation as any.)

Any move that scores repDraw will then automatically be researched without reduction in the context of the normal LMR implementation, as it did not fail low. You would pass a 'no-null-move' flag to the daughter in this case, though, to be sure the opponent cannot dodge zugzwang by turn passing, and to prevent he will push his defeat we are looking for over the horizon by bringeng the latter closer through the null-move reduction. And to prevent him from thwarting rep-draw detection by null moving.

You could even consider extending these moves, rather than just undoing their reduction.

There is one catch: it might be difficult to recognize this type of rep-draws (i.e. where the side that wants to avoid it is trapped) in the face of null moving. This depends on whether you recognize null-move-spanning repeats. Normally you would not want to do that, because the null move merely represents any quiet move, and that move would have changed the position. The price for considering null-move-spanning repeats as draws is that a leading cut-side can never play two null moves in a row, as after null - pointless move - null the opponent would simply play the reverse pointless move to collect a draw.

So if you do not happen to find the rep-draw in the first branch you search, (when the window is still {-INF, INF}, and the null move can never fail high), so that you end in a leave with a score around the root eval, you would never be able to find it, as whatever you do, the opponent just keeps null moving, and will be able to prove that way that you can never improve over the favorable static evaluation he has. Your only weapon to eat away that advantage is to blackmail him into doing something desparate with the threat of a repetition, which you cannot do if he just sits, ignoring repeats.

So I guess you would still need some singularity search with shifted window to conclude you are in a position with very few playable moves to conclude that you are trapped, and null-moving is not appropriate. This is needed to detect that you can force rep-draw in the first place, not so much to see you can actually go for a win with a long-term plan.

So in summary:

If you do a verification search after null-move fail high (perhaps induced by worrisome mobility, which makes you anticipate zugzwangs), do it with a down-shifted window first, to weed out the moves that are truly cr*p. If the number of playable moves that remain is low, (say <= 3), consider the verification search a failure, and force a normal (unreduced) search of those playable moves. If the number of playable moves is one, even consider extending it (singular extension). If the number of playable moves is high, you could consider re-searching the playable moves with an unshifted window to get final confirmation of the null-move fail high. This takes care of missing zugzwangs and excessive reduction in trapped positions.

Then on the other side, never allow alpha to be at the rep-draw score when current eval < repDraw, but lower it by one if it is. This forces all moves that can achieve a rep-draw to be re-searched at nominal depth.

With these two modifications, positions like we discussed here should be solvable. The Bishop or Knight tour would not be reduced, or even extended, for as long as black keeps shuttling his Queen or Rook between the fortress positions, and he would be fully subject to zugzwang. Initially this would just discover deeper rep-draws, but at some point the B or N reach the location where the black fortress collapses in the unreduced lines.

Node-based depth control would be helpful in the second position, where there is lots of immobile material that could distract the search when it gets liberated.

Vinvin
Posts: 4332
Joined: Thu Mar 09, 2006 8:40 am
Full name: Vincent Lejeune

Re: Test positions for draw detection

Post by Vinvin » Thu Aug 15, 2019 7:16 pm

Vinvin wrote:
Mon Sep 28, 2015 10:55 am
Some old hard positions based on draw threats :
...
[Event "Test position"]
[Site "-**-"]
[Date "2012.07.11"]
[Round "?"]
[White "White"]
[Black "Black"]
[Result "1/2-1/2"]
[SetUp "1"]
[FEN "4knQ1/7r/3p2p1/2bP1pP1/5P1N/6K1/8/8 b - - 1 1"]

59...Rxh4!! 60. Kxh4 Bd4 {getting the draw} 61. Kg3 Ke7 62. Kf3 Ba1
1/2-1/2 ...
This one still not easy these days for SF :
Sometimes it finds it in 30 sec and sometimes not found in 4 minutes (6*4 GHz).

Code: Select all

Stockfish_19081422_x64_modern:
...
 71/118	03:29	1 816 488 002	8 673 526	+4,28	1. ... Bf2+ 2.Kxf2 Rxh4 3.Kf3 Rh3+ 4.Ke2 Rh4 5.Qg7 Rxf4 6.Qf6 Rg4 7.Kd3 Rg1 8.Kc4 Rc1+ 9.Kb4 Rb1+ 10.Ka4 Rb6 11.Ka5 Rb7 12.Qxd6 Kf7 13.Qc6 Rd7 14.Kb4 Kg8 15.Qc4 Rf7 16.Qf4 Nd7 17.Kc4 Kg7 18.d6 Nf8 19.Kd3 Kg8 20.Ke2 Kg7 21.Kf3 Nd7 22.Qd4+ Kg8 23.Ke3 Kh7 24.Qc4 Kg8 25.Qc8+ Kh7 26.Ke2 Nf8 27.Qe8 Kg7 28.Kf3 Kg8 29.Qd8 Rh7 30.Kf4 Kf7 31.Qe7+ Kg8 32.Qe8 Rf7 33.Qb8 Kg7 34.Kf3 Nh7 35.Qe8 Nf8 36.Qc8 Nd7 37.Qc3+ Kh7 38.Kf2 Kg8 39.Ke2 Rf8 40.Qd4 f4 41.Kf3 Rf5 42.Qc4+ Kg7
 72/124	03:57	2 082 235 031	8 774 694	+4,28	1. ... Bf2+ 2.Kxf2 Rxh4 3.Kf3 Rh3+ 4.Ke2 Rh4 5.Qg7 Rxf4 6.Qf6 Rg4 7.Kd3 Rg1 8.Kc4 Rc1+ 9.Kb4 Rb1+ 10.Ka4 Rb6 11.Ka5 Rb7 12.Qxd6 Kf7 13.Qc6 Rd7 14.Kb4 Kg8 15.Qc4 Rf7 16.Qf4 Nd7 17.Kc4 Kg7 18.d6 Nf8 19.Kd3 Kg8 20.Ke2 Kg7 21.Kf3 Nd7 22.Qd4+ Kg8 23.Ke3 Kh7 24.Qc4 Kg8 25.Qc8+ Kh7 26.Ke2 Nf8 27.Qe8 Kg7 28.Kf3 Kg8 29.Qd8 Rh7 30.Kf4 Kf7 31.Qe7+ Kg8 32.Qe8 Rf7 33.Qb8 Kg7 34.Kf3 Nh7 35.Qe8 Nf8 36.Qc8 Nd7 37.Qc3+ Kh7 38.Ke2 Kg8 39.Qc8+ Nf8 40.Qd8 Rd7 41.Qb8 f4 42.Kf3 Rf7

Post Reply