a test position

[Uri Blass]

[diag]8/p6p/7p/p6p/b2Q3p/K6p/p1r5/rk3n1n w - - 0 1[/diag]

mate in 130

This position was posted in the israeli chess forum

Here is an example for a possible solution
The idea is basically the same idea after promotion moves and after nonpromotion moves.

Can a program solve it?
Can a program prove that there is no shorter solution?

[Event "?"]
[Site "?"]
[Date "????.??.??"]
[Round "?"]
[White "New game"]
[Black "Rybka 2.1c 32-bit"]
[Result "1-0"]
[SetUp "1"]
[FEN "8/p6p/7p/p6p/b2Q3p/K6p/p1r5/rk3n1n w - - 0 0"]
[PlyCount "259"]

{512MB, Junior9.ctg, URI-AMD} 1. Qd1+ Rc1 2. Qd3+ Rc2 3. Qxf1+ Rc1 4. Qd3+ Rc2
5. Qd1+ Rc1 6. Qd2 Rc2 7. Qe1+ Rc1 8. Qe4+ Rc2 9. Qxh1+ Rc1 10. Qe4+ Rc2 11.
Qe1+ Rc1 12. Qd2 Rc2 13. Qd1+ Rc1 14. Qd3+ Rc2 15. Qe4 h2 16. Qe1+ Rc1 17. Qd2
Rc2 18. Qd1+ Rc1 19. Qd3+ Rc2 20. Qe4 h3 21. Qe1+ Rc1 22. Qd2 Rc2 23. Qd1+ Rc1
24. Qd3+ Rc2 25. Qe4 h4 26. Qe1+ Rc1 27. Qd2 Rc2 28. Qd1+ Rc1 29. Qd3+ Rc2 30.
Qe4 h5 31. Qe1+ Rc1 32. Qd2 Rc2 33. Qd1+ Rc1 34. Qd3+ Rc2 35. Qe4 h6 36. Qe1+
Rc1 37. Qd2 Rc2 38. Qd1+ Rc1 39. Qd3+ Rc2 40. Qe4 a6 41. Qe1+ Rc1 42. Qd2 Rc2
43. Qd1+ Rc1 44. Qd3+ Rc2 45. Qe4 h1=Q 46. Qxh1+ Rc1 47. Qe4+ Rc2 48. Qe1+ Rc1
49. Qd2 Rc2 50. Qd1+ Rc1 51. Qd3+ Rc2 52. Qe4 h2 53. Qe1+ Rc1 54. Qd2 Rc2 55.
Qd1+ Rc1 56. Qd3+ Rc2 57. Qe4 h3 58. Qe1+ Rc1 59. Qd2 Rc2 60. Qd1+ Rc1 61. Qd3+
Rc2 62. Qe4 h4 63. Qe1+ Rc1 64. Qd2 Rc2 65. Qd1+ Rc1 66. Qd3+ Rc2 67. Qe4 h5
68. Qe1+ Rc1 69. Qd2 Rc2 70. Qd1+ Rc1 71. Qd3+ Rc2 72. Qe4 h1=Q 73. Qxh1+ Rc1
74. Qe4+ Rc2 75. Qe1+ Rc1 76. Qd2 Rc2 77. Qd1+ Rc1 78. Qd3+ Rc2 79. Qe4 h2 80.
Qe1+ Rc1 81. Qd2 Rc2 82. Qd1+ Rc1 83. Qd3+ Rc2 84. Qe4 h3 85. Qe1+ Rc1 86. Qd2
Rc2 87. Qd1+ Rc1 88. Qd3+ Rc2 89. Qe4 h4 90. Qe1+ Rc1 91. Qd2 Rc2 92. Qd1+ Rc1
93. Qd3+ Rc2 94. Qe4 h1=Q 95. Qxh1+ Rc1 96. Qe4+ Rc2 97. Qe1+ Rc1 98. Qd2 Rc2
99. Qd1+ Rc1 100. Qd3+ Rc2 101. Qe4 h2 102. Qe1+ Rc1 103. Qd2 Rc2 104. Qd1+ Rc1
105. Qd3+ Rc2 106. Qe4 h3 107. Qe1+ Rc1 108. Qd2 Rc2 109. Qd1+ Rc1 110. Qd3+
Rc2 111. Qe4 h1=Q 112. Qxh1+ Rc1 113. Qe4+ Rc2 114. Qe1+ Rc1 115. Qd2 Rc2 116.
Qd1+ Rc1 117. Qd3+ Rc2 118. Qe4 h2 119. Qe1+ Rc1 120. Qd2 Rc2 121. Qd1+ Rc1
122. Qd3+ Rc2 123. Qe4 h1=Q 124. Qxh1+ Rc1 125. Qh7+ Rc2 126. Qe4 Bc6 127. Qe1+
Rc1 128. Qd2 Rc2 129. Qd1+ Rc1 130. Qb3# 1-0

[Uri Blass]

If this problem is too hard for your program here is significantly easier problem when mate in 41 was proved by retrogrede analysis

[diag]8/8/p7/p7/b3Q2p/K6p/p1r4p/rk6 w - - 0 90[/diag]


New game - Rybka 2.1c 32-bit
8/8/p7/p7/b3Q2p/K6p/p1r4p/rk6 w - - 0 1

Analysis by Yace 0.99.87:

90.Qxh4 h1Q 91.Kxa4
-+ (-14.46) Depth: 1 00:00:00
90.Kxa4
-+ (-6.29) Depth: 1 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 1 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 1 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 1 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 2 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 2 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 3 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 3 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 4 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 4 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 5 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 5 00:00:00
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 6/21 00:00:00 22kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 6/21 00:00:00 60kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 7/21 00:00:00 60kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 7/23 00:00:01 160kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 8/23 00:00:01 160kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 8/27 00:00:01 399kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 9/27 00:00:01 399kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 9/30 00:00:01 995kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 10/30 00:00:01 995kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 10/33 00:00:02 2267kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 11/33 00:00:02 2267kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 11/33 00:00:03 5048kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 12/33 00:00:03 5048kN
90.Qe1+ Rc1 91.Qd2 Rc2 92.Qd1+ Rc1 93.Qd3+ Rc2 94.Qe4 h1Q 95.Qxh1+ Rc1 96.Qe4+ Rc2 97.Qe1+ Rc1 98.Qd2 Rc2 99.Qd1+ Rc1 100.Qd3+ Rc2 101.Qe4 h2 102.Qe1+ Rc1 103.Qd2 Rc2 104.Qd1+ Rc1 105.Qxa4 Rg1
+- (#41) Depth: 12/39 00:00:08 13668kN

[MartinB]

[diag]8/p6p/7p/p6p/b2Q3p/K6p/p1r5/rk3n1n w - - 0 1[/diag]

mate in 130

Can a program solve it?
Can a program prove that there is no shorter solution?

Hi Uri,

The mate solver Gustav can solve this problem by Halumbirek in around 15 minutes on a P4 running at 2.8GHz.

In order to reduce the search tree you however have to limit the black king's number of flight squares to one and this way a shorter solution can not be ruled out... I don't think that there is any program which is going to prove that there's no shorter solution - at least not in a feasible amount of time.

Cheers,

Martin