Test positions for draw detection

[mar]

Ok, I have finally found an engine that gives a winning score for Black in the above position in a reasonable time. Cheng 4 gives a score of -3.32 at depth 28 after 33 seconds. Congratulations, Martin!

jm

Thanks I guess people will now switch to Cheng for analysis

[hgm]

Here is the full winning line
[pgn][Event "?"]
[Site "?"]
[Date "????.??.??"]
[Round "?"]
[White "New game"]
[Black "?"]
[Result "*"]
[SetUp "1"]
[FEN "1B1k4/3p4/1Kp5/PpP2p2/1PqP1P2/8/1P6/8 w - - 0 0"]
[PlyCount "51"]

1. a6 Kc8 2. a7 Qa2 3. Bd6 Qa4 4. Be7 Qa2 5. Bh4 Qa4 6. b3 Qa3 7. Bg3 Qa2 8.
Bf2 Qa1 9. Be1 Qa2 10. Bd2 Qa1 11. Bc1 d5 12. Be3 Qa3 13. Bf2 Qa2 14. Bh4 Qa3
15. Bf6 Qa1 16. Be5 Qa3 17. Bb8 Qa2 18. Be5 Qa3 19. Bf6 Qa1 20. Bh4 Qa3 21. Bg3
Qa2 22. Bf2 Qa1 23. Be1 Qa2 24. Bd2 Qa3 25. Bc3 Qa2 26. Bb2 *[/pgn]

This is not the correct line; it contains a repetition, (B on h4, Q on a3), and all moves in between first and second occurence are a waste of time. After black could weasel its way out of the first zugzwang by moving a Pawn, it is enough for white to retract its Bishop to h4. The black can only go to a1, a2, a3, so having the move white can pot his Bishop immediately on the same rank, without the need to back out any further.

As to the possibility for engines to see this, I am not so pessimistic at all.
This is a case where there is a very small set of 'undecided' positions, while all others lose quickly. It should always pay to push the search further along such lines, without wasting much more time on the losing side branches. The undecided branches merge into each other all the time by transpositions.

In fact this is a position where each side has only a single piece. Such positions should always make you expect zugzwangs, especially if almost all Pawns are blocked. And especially if the Queen is bound to a file for stopping a promotion. Recognizing this might be relatively expensive, but if you only do it in nodes with remaining depth >= 10 it is basically free.

Reducing like an idiot when your opponent is basically paralyzed is not advisable, and I cannot imagine it would cost much Elo (if any) when you refrain from doing it, as it is very rare that your opponent is nearly paralyzed. And when it is the case it would almost always pay off very handsomely to exploit it.

[Nordlandia]

Blathy composed one very similar one, just different initial Queen position.

I'm clearly convinced this is forced win for white.

[pgn][Event "?"]
[Site "Otto Blathy"]
[Date "1908.??.??"]
[Round "?"]
[White "New game"]
[Black "?"]
[Result "*"]
[SetUp "1"]
[FEN "1B1k4/3p1q2/1Kp5/PpP2p2/1P1P1P2/8/1P6/8 w - - 0 1"]
[PlyCount "47"]

1. a6 Kc8 2. a7 Qa2 3. Bd6 Qa4 4. b3 Qa3 5. Be7 Qa1 6. Bh4 Qa2 7. Bf2 Qa3 8.
Be3 Qa1 9. Bc1 d5 10. Be3 Qa3 11. Bf2 Qa2 12. Bh4 Qa3 13. Bf6 Qa1 14. Be5 Qa3
15. Bb8 Qa1 16. Be5 Qa3 17. Bf6 Qa1 18. Bh4 Qa3 19. Bg3 Qa2 20. Bf2 Qa3 21. Be3
Qa2 22. Bd2 Qa3 23. Bc3 Qa2 24. Bb2 *[/pgn]

Also i find it quite strange that even today, 17 years from the actual game. No engines finds 47...Bh3

[d]8/8/4kpp1/3p1b2/p6P/2B5/6P1/6K1 b - - 0 47

[Vinvin]

...
Also i find it quite strange that even today, 17 years from the actual game. No engines finds 47...Bh3

[d]8/8/4kpp1/3p1b2/p6P/2B5/6P1/6K1 b - - 0 47

11 months ago :
http://www.talkchess.com/forum/viewtopic.php?t=54289

[Nordlandia]

[d]8/8/4kpp1/3p1b2/p6P/2B5/6P1/6K1 b - - 0 47

I find it somewhat bothersome that i first have to manually make the 47...Bh3 move then revert it back, then the engine automatically detects it. Unless i show the 47...Bh3 move to the engine it rather go for Be4...

Code: Select all

New game
8/8/4kpp1/3p1b2/p6P/2B5/6P1/6K1 b - - 0 1

Analysis by StockfishTS 240915 64 POPCNT:

-+  (-1.83)   Depth: 85/98   00:44:09  81797MN, tb=597910681
47...Be4 48.Kf2 Kf5 49.g3 a3 50.Ke3 a2 51.Kd2 Kg4 52.Bxf6 Kxg3 53.Ke3 Kg4 54.Kd2 Kf4 55.Bd4 Bb1 56.Bc3 Ke4 57.Bb2 d4 58.Ba1 Bd3 59.Bb2 Bc4 60.Ba1 Bb5 61.Bb2 Bd3 62.Ba1 Bc4 63.Bb2 Bb3 64.Ba1 Be6 65.Bb2 Bg4 66.Ba1 Bd7 67.Bb2 Be6 68.Ke2 Kd5 69.Kd2 Kc4 70.Kc2 Bf5+ 71.Kd2 Be4 72.Ba1 Bf3 73.Bb2 Bg2 74.Kc2 Be4+ 75.Kd2 Bf5 76.Ba1 Kd5 77.Bb2 Ke4 78.Ke2 Bg4+ 79.Kd2 Bf3 80.Ba1 Bg2 81.Bb2 Bh3 82.Ba1 Kd5 83.Kc2 Kc4 84.Bb2 Bd7 85.Kd2 Kc5 86.Kc2 Bf5+ 87.Kd2 Kd5 88.Ba1 Ke4 89.Bb2 Bc8 90.Ba1 Kd5 91.Bb2 Bh3 92.Ba1 Kc4 93.Bb2 Bd7 94.Kc2 Bc6 95.Kd2 Bd5 96.Ba1 Be6 
  -+  (-1.83)   Depth: 86/99   00:47:01  86424MN, tb=647008399

[zullil]

[d]8/8/4kpp1/3p1b2/p6P/2B5/6P1/6K1 b - - 0 47

I find it somewhat bothersome that i first have to manually make the 47...Bh3 move then revert it back, then the engine automatically detects it. Unless i show the 47...Bh3 move to the engine it rather go for Be4...

Code: Select all

New game
8/8/4kpp1/3p1b2/p6P/2B5/6P1/6K1 b - - 0 1

Analysis by StockfishTS 240915 64 POPCNT:

-+  (-1.83)   Depth: 85/98   00:44:09  81797MN, tb=597910681
47...Be4 48.Kf2 Kf5 49.g3 a3 50.Ke3 a2 51.Kd2 Kg4 52.Bxf6 Kxg3 53.Ke3 Kg4 54.Kd2 Kf4 55.Bd4 Bb1 56.Bc3 Ke4 57.Bb2 d4 58.Ba1 Bd3 59.Bb2 Bc4 60.Ba1 Bb5 61.Bb2 Bd3 62.Ba1 Bc4 63.Bb2 Bb3 64.Ba1 Be6 65.Bb2 Bg4 66.Ba1 Bd7 67.Bb2 Be6 68.Ke2 Kd5 69.Kd2 Kc4 70.Kc2 Bf5+ 71.Kd2 Be4 72.Ba1 Bf3 73.Bb2 Bg2 74.Kc2 Be4+ 75.Kd2 Bf5 76.Ba1 Kd5 77.Bb2 Ke4 78.Ke2 Bg4+ 79.Kd2 Bf3 80.Ba1 Bg2 81.Bb2 Bh3 82.Ba1 Kd5 83.Kc2 Kc4 84.Bb2 Bd7 85.Kd2 Kc5 86.Kc2 Bf5+ 87.Kd2 Kd5 88.Ba1 Ke4 89.Bb2 Bc8 90.Ba1 Kd5 91.Bb2 Bh3 92.Ba1 Kc4 93.Bb2 Bd7 94.Kc2 Bc6 95.Kd2 Bd5 96.Ba1 Be6 
  -+  (-1.83)   Depth: 86/99   00:47:01  86424MN, tb=647008399

Latest Stockfish without endgame tables gets it:

Code: Select all

info depth 40 seldepth 55 multipv 1 score cp 283 lowerbound nodes 8680022301 nps 41900088 hashfull 189 tbhits 0 time 207160 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 289 lowerbound nodes 9360642454 nps 42198320 hashfull 200 tbhits 0 time 221825 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 299 lowerbound nodes 10233147836 nps 42547879 hashfull 210 tbhits 0 time 240509 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 313 lowerbound nodes 11186967461 nps 42986456 hashfull 214 tbhits 0 time 260244 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 334 lowerbound nodes 12337924156 nps 43449055 hashfull 218 tbhits 0 time 283963 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 365 lowerbound nodes 13659094301 nps 43958363 hashfull 227 tbhits 0 time 310728 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 412 lowerbound nodes 15380727582 nps 44439740 hashfull 240 tbhits 0 time 346103 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 482 lowerbound nodes 17273452360 nps 45092509 hashfull 259 tbhits 0 time 383067 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 587 lowerbound nodes 21099000260 nps 46309852 hashfull 296 tbhits 0 time 455605 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 744 lowerbound nodes 27035845667 nps 47427064 hashfull 355 tbhits 0 time 570051 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 seldepth 55 multipv 1 score cp 981 lowerbound nodes 33385029348 nps 47455890 hashfull 448 tbhits 0 time 703496 pv f5h3
info depth 40 currmove f5h3 currmovenumber 1
info depth 40 currmove d5d4 currmovenumber 4
info depth 40 seldepth 64 multipv 1 score cp 981 nodes 42014204277 nps 47192866 hashfull 577 tbhits 0 time 890266 pv f5h3 g1f2 e6f5 f2e3 h3g2 c3b2 g2h1 e3d2 h1e4 d2e2 g6g5 h4h5 g5g4 h5h6 f5g6 h6h7 g6h7 e2e3 h7g6 e3f4 f6f5 b2d4 a4a3 d4c5 a3a2 c5d4 g6h5 d4f6 e4b1 f6e5 h5h4 e5f6 h4h3 f6d4 g4g3 f4e5 g3g2 e5d5 a2a1q d4a1 b1e4 d5c5 g2g1q a1d4 g1c1 c5b5 f5f4 d4c5

[F. Bluemers]

Hi,

Code: Select all

[Event "Computer chess game 0 300 +3 0 0"]
[Site "ICC"]
[Date "2001.10.28"]
[Round "5"]
[White "Yace 0.99.57"]
[Black "Tinker"]
[Result "1/2-1/2"]
[ECO "B78"]
[WhiteElo "2972"]
[BlackElo "2519"]
[SetUp "1"]
[FEN "7k/2R3b1/6R1/1r5P/6K1/8/8/8 w - - 0 55"]
[PlyCount "21"]
[EventDate "2001.??.??"]

55. Rcxg7 $4 Rg5+ 56. Kf3 Rf5+ 57. Ke2 Re5+ 58. Kd1 Rd5+ 59. Ke1 Re5+ 60. Kd1
Rd5+ 61. Kc2 Rc5+ 62. Kd2 Rd5+ 63. Ke3 Re5+ 64. Kd4 Rd5+ 65. Kxd5 1/2-1/2

Dirty finds the Rg5 trick but then thinks that 55. h6 instead of 55. Rg7
is winning

Code: Select all

26	+9.41!	275.6M	8:43.65	h6! 
 25	+8.16 	275.6M	3:52.10	h6 Bb2 Re6 Rb8 Kh5 Rf8 h7 Be5 Rd7 Bb2 Kg6 Bg7 Rc7 Rf2 Rxg7 Rg2+ Kf5 Rxg7 Rg6 
 25	+8.16 	256.6M	3:35.93	h6 Bb2 Re6 Rb8 Kh5 Rf8 h7 Be5 Rd7 Bb2 Kg6 Bg7 Rc7 
 24	+8.16 	256.6M	3:35.93	h6 Bb2 Re6 Rb8 Kh5 Rf8 h7 Be5 Rd7 Bb2 Kg6 Bg7 Rc7 
 24	+8.16 	240.8M	3:22.19	h6 Bb2 Re6 Rb8 Kh5 Rf8 h7 Be5 Rd7 Bb2 Kg6 Bg7 Rc7 Rf2 Rc8+ Rf8 Rxf8+ Bxf8 Rc6 Bh6 
 23	+7.73 	171.7M	2:25.05	h6 Bb2 Re6 Rb8 Kh5 Rf8 h7 Be5 Rce7 Bf6 Rd7 Ba1 Kg6 Bg7 
 23	+7.73 	164.0M	2:18.61	h6 Bb2 Re6 Rb8 Kh5 Rf8 h7 Be5 Rce7 Bf6 Rd7 Ba1 Kg6 Bg7 
 22	+7.73 	158.2M	2:13.87	h6 Bb2 Re6 Rb8 Kh5 Rf8 h7 Be5 Rce7 Bf6 Rd7 Ba1 Kg6 Bg7 
 22	+7.73 	146.2M	2:03.58	h6 Bb2 Re6 Rb8 Kh5 Rf8 h7 Be5 Rce7 Bf6 Rd7 Ba1 Kg6 Bg7 
 21	+6.74 	133.7M	1:53.08	h6 Bb2 Re6 Rb4+ Kh5 Rb8 Rce7 Rf8 Re8 Rg8 R6e7 Ba1 Rxg8+ Kxg8 Re8+ Kf7 Ra8 Bb2 h7 Bg7 Kg4 Ke6 h8=Q Bb2 
 21	+6.74 	129.1M	1:48.43	h6 Bb2 Re6 Rb4+ Kh5 Rb8 Rce7 Rf8 Re8 Rg8 R6e7 Ba1 Rxg8+ Kxg8 Re8+ Kf7 Ra8 Bb2 h7 Bg7 Kg4 Ke6 h8=Q Bb2 
 20	+6.74 	127.8M	1:46.98	h6 Bb2 Re6 Rb4+ Kh5 Rb8 Rce7 Rf8 Re8 Rg8 R6e7 Ba1 Rxg8+ Kxg8 Re8+ Kf7 Ra8 Bb2 h7 Bg7 Kg4 Ke6 h8=Q Bb2 
 20	+6.74 	116.1M	1:36.83	h6 Bb2 Re6 Rb4+ Kh5 Rb8 Rce7 Rf8 Re8 Rg8 R6e7 Ba1 Rxg8+ Kxg8 Re8+ Kf7 Ra8 Bb2 h7 Bg7 Kg4 Ke6 h8=Q Bb2 
 20	+1.25!	16.2M  	0:13.81	h6 Rb4+ Kf5 Bb2 Rc8+ Kh7 Ra6 Rb5+ Kf4 Rb4+ Kg3 Rb8 Rxb8 Be5+ Kg4 Bxb8 Ra8 Kxh6 Rxb8 Kh7 Re8 Kh6! 
 20	  0.00 	16.2M  	0:12.89	Rcxg7 Rg5+ Kf4 Rf5+ Ke3 Re5+ Kd3 Rd5+ Kc2 Rc5+ Kb2 Rb5+ Ka2 Rb2+ Ka3 Rb3+ Ka4 Rb4+ Ka5 Rb5+ Ka6 Ra5+ Kb7 Ra7+ Kc6 Rxg7 Rxg7 Kxg7 Kd7 Kg8 h6 Kh7 Ke6 Kxh6 
 20	+7.12?	15.4M  	0:12.72	Rcxg7? 
 19	+8.37 	15.4M  	0:12.29	Rcxg7 Rg5+ Kf4 Rf5+ Ke3 Re5+ Kd3 Rd5+ Kc2 Rc5+ Kd1 Rxh5 Rg8+ Kh7 R6g7+ Kh6 Rg4 Kh7 R8g7+ Kh8 Rd7 Rb5 Ke2 Rb2+ Ke3 Rb3+ Kf4 Rb4+ Kf5 Rxg4 

[hgm]

[d]2k5/P7/1Kp5/1pPp1p2/1P1P1P2/1P6/8/q1B5 w - d6 0 12

The cheap trigger for recognizing that positions like the above need special treatment is that you get a null score for the PV move, while the current evaluation (or the QS score) is far below zero. Of course it is not unusual the score to rise above the current eval value (e.g. when you can play a move that forks some valuable pieces). But the fact that it rises to a draw score suggests you can force a repetition. (And because it is a PV move, it also returns a PV, so you can verify that.)

Now that white can force a repetition suggest that black only has a very small number of positions available in which he can survive. This conveys more information than the fact that he has few viable moves in the current position (which could be established through a 'singularity search' with a down-shifted window, and counting the number of moves that fail high against it); the latter case could just be temporary, and even a single viable move could liberate some pieces, and make the branching factor explode again. (E.g. it could be a check evasion moving the King to a safe place.) But that you can force a repetition suggests that the trapping is perpetual.

Now when you can force a repetition, it is often possible to force something even better. This is especially true if the trapping is static, rather than dynamic, i.e. if it doesn't require any action from the forcing side to keep the number of viable opponent moves low. In a perpetual check you have to renew the check every move, so this is dynamic, and this severely limits your opportunity to manoeuver. In the case at hand the trapping of black is static, and doesn't put any restriction on the Bishop.

A straightforward way to investigate if the trapping is static or dynamic would be to repeat the search (possibly reduced) with altered repetition logic: normally you would ignore null-move-spanning repetitions, but now you would recognize only repetitions that have nothing but null moves for one side in the repeat loop. (And you would not reduce null move!). If this would still force a repetition at a similar depth as where the normal search would force one, you have proven that the confinement of black is perpetual. In the current case this would quickly materialize, as black exhausts its viable positions in only 3 moves (Qa1, Qa2 or Qa3), and has to start repeating after that, or do a losing move. (You would need enough search depth to recognize these moves as losing, of course. Although the positions after them would likely be still in the TT from the original search.)

Now the next question would be if you have 'free pieces', i.e. pieces not involved in keeping up the confinement. To investigate this you could delete the pieces one by one; in this case there is only a Bishop. So remove the Bishop from the board, and repeat the search with null-moves-only repetition rules. This will show that the confinement was not lifted by removing the Bishop, i.e. the Bishop is a free piece, which you can move at will while the opponent stays trapped in his a1-a2-a3 dance, which quickly starts repeating.

Then things start to look good, because you can try to formulate a long-range plan to wreck havoc on the opponent with the aid of that Bishop. In fact you could apply the same procedure as in fortress detection, because we are actually dealing with a black fortress here, consisting of 3 positions. So you would want to know if there is any placement of your Bishop against any of the three fortress candidates that would crack open the fortress. It turns out that Qa2, Bb2 is such a position (out of the 3x26 possible ones) where black is forced to leave the fortress (and any way to do it quickly loses). Note that we already know black to have quite restricted move choice, so zugzwang is a likely possibility, and we should not allow black any null moves in any of the fortress-candidate positions.

This proves a winning position exists; the next question is whether this position can be reached. This might take a long Bishop tour. So we definitely would not want to reduce any moves with this Bishop. So we redo the search again, but now under no-black-null-move, no-white-Bishop-LMR rules. In fact we could even consider extending the Bishop moves in the fortress-candidate positions (i.e. as long as the Queen is on a1,a2,a3, and the Pawns and Kings stay where they are). This would quickly (i.e. without spending too much effort on deepening the losing side branches, which will still be heavily reduced according to the normal scheme; only the fortress candidates are treated differently) force the search to surge ahead along the PV that brings the Bishop back to the position that forces black to leave the fortress. (I.e. to h4 in order to flip the zugzwang, and then back to b2.)


Note that I still have some doubts on the original position; in the move that led to the position I show here (d7-d5) black seems to unnecessarily lock himself in. He could have played d7-d6 instead (as he would be exposed to e.p. capture anyway), to leave him the option to make some more captures with that Pawn to dodge later zugzwangs.

[Nordlandia]

[d]1N1Brkbn/5p2/6pr/4P1Pp/4P3/7K/8/7N w - - 0 0

White is winning but the engine is not able to detect the winning sequence unless retrograde analysis. Any explanation?

[hgm]

Same theme: black is trapped in a fortress consisting of Ra8, c8 and e8. white has Nh1 as 'free piece', and it needs to make a long tour in order to cover the two fortress squares where the Rook is not, so that zugzwang forces the latter to expose itself to capture.

It takes many moves to achieve this, many more than you can handle in a full-width search. The latter would allocate almost all effort to stupid moves that allow black to escape the confinement, and make the branching factor explode. So the first part of the cure is that you should not control the search depth by the number of plies, but by a node budget. Then at any time a reasonable fraction of the nodes can get allocated to search the actual solution.

The rest of the solution is the same: recognize the position as a black fortress, do not reduce the moves of the 'free piece' in fortress-candidate positions, but extend them, and do not allow a null-move reply to them. That should be enough to find the solution. Otherwise, no chance. The 'stronger' the engine (Elo wise), the lower the chances it would ever find it.