Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Mate in 38.

Author: Heiner Marxen

Date: 20:41:52 01/25/01

Go up one level in this thread


On January 25, 2001 at 22:31:33, Uri Blass wrote:

>On January 25, 2001 at 21:48:06, Heiner Marxen wrote:
>
>>On January 25, 2001 at 20:41:50, Paul wrote:
>>
>>>On January 25, 2001 at 20:31:55, Heiner Marxen wrote:
>>>
>>>>On January 25, 2001 at 19:40:58, Paul wrote:
>>>>
>>>>>On January 24, 2001 at 19:39:52, Dan Andersson wrote:
>>>>>
>>>>>>[D]1R6/6pK/5p2/4p3/1B1p3n/8/p1p1pp2/1k3b2 w - - 0 1
>>>>>>Krabbé (1985)
>>>>>
>>>>>I just tried this position with my program Pretz, after having unsuccesfully
>>>>>grappled with the mate in 16/20 positions by José Antônio Fabiano Mendes
>>>>>(I ran out of patience :) and indeed get a mate in 38! It's amazing!
>>>>>
>>>>>02:17 WM38 09 1. Ba3+ Ka1 2. Bb2+ Kb1 3. Bxd4+ Kc1 4. Be3+ Kd1 5. Rd8+ Ke1 6.
>>>>>Bd2+ Kd1 7. Bb4+ Kc1 8. Ba3+ Kb1 9. Rb8+ Ka1 10. Bb2+ Kb1 11. Bxe5+ Kc1 12. Bf4+
>>>>>Kd1 13. Rd8+ Ke1 14. Bd2+ Kd1 15. Bb4+ Kc1 16. Ba3+ Kb1 17. Rb8+ Ka1 18. Bb2+
>>>>>Kb1 19. Bxf6+ Kc1 20. Bg5+ Kd1 21. Rd8+ Ke1 22. Bd2+ Kd1 23. Bb4+ Kc1 24. Ba3+
>>>>>Kb1 25. Rb8+ Ka1 26. Bb2+ Kb1 27. Bxg7+ Kc1 28. Bh6+ Kd1 29. Rd8+ Ke1 30. Bd2+
>>>>>Kd1 31. Bb4+ Kc1 32. Ba3+ Kb1 33. Rb8+ Ka1 34. Be7 c1=Q 35. Bf6+ Qb2 36. Rxb2
>>>>>e1=Q 37. Rb8+ Qe5 38. Bxe5x
>>>>>
>>>>>I used 96MB hash and full ply extensions on check and one-rep, and some
>>>>>other tricks :) Does this look ok? Has anyone else tried this position?
>>>>>
>>>>>Groetjes,
>>>>>Paul
>>>>
>>>>That looks ok to me.
>>>>From a 1993 posting of Dennis Breuker:
>>>>
>>>>An implementation of proof-number search (a kind of conspiracy-number
>>>>search) finds the intended solution in 225752 nodes (86 seconds)
>>>>on a SPARC-2.
>>>>
>>>>He gives the exact same solution as you do.
>>>>
>>>>Heiner
>>>
>>>Thanks for checking that for me. I couldn't believe it at first!!
>>>
>>>I really hope some other programmer will also try this, coz I don't use
>>>proofnumber search, just 'plain' alpha-beta. Didn't know it was possible.
>>
>>Since the solution line is nearly completely forced, that does not
>>look so impossible to me.  I would expect that some programs do find this one,
>>depending on the nature of extensions they do.
>>
>>>Heiner, is it out of reach for Chest? What do you think?
>>>
>>>Paul
>>
>>Yes, that is absolutely out of reach for Chest.  The problem is not to find
>>the solution, but to prove all the non-solutions up to a depth of 38.
>>For depth 9 Chest needs 111 seconds, and increasing the depth by one,
>>multiplies the search time by 4.  Do the math and be shocked.  ;-)
>
>The assumption of branching factor of 4 is not always correct.

Sure, I guessed the 4 from the following Chest output:
#  1      0.00  0.87          1-         0
#  2      0.00  1.00          1-         0
#  3      0.00  0.99         23-         0
#  4      0.05  1.24        373-         0
#  5      0.31  1.75       2986-         0
#  6      1.44  2.45      14224-         0
#  7      6.42  3.16      65054-         0
#  8     27.35  3.91     298488-         0
#  9    111.02  5.02    1277416-         4
# 10    455.52  6.15    5152726-     38100
# 11   2004.38  6.86   22534927-  13787298
(dep   seconds speed   nodes in  nodes out)
The last two lines are new, but 2004.38/455.52 = 4.4002, so I expect the
effective branching factor of chest to stay around or even above 4.

>In order to prove that the mate in 38 is the shortest mate you need only to
>prove that white has no alternatives.
>
>I do not know if it is possible to do it in this case but it may be possible

Sure, you are right.
Unfortunately, Chest cannot (yet) do that.

>In order to do it it is enough to prove that after every alternative of white
>except 1.Ba3 black can force a mate or a repetition(proving a mate or repetition
>can be easier than proving only mate).

Well, I have done some thinking/planning about proving that one side
cannot loose due to repetition, but that is just a start, and not yet
implemented.  I have no idea, how much that would yield, but the
potential in some chess problems is enormeous.

The basic mechanism is similar to endgame table bases: working back from
the end.  Those positions without a value from that backup are remis,
i.e. the defending side can stay away from the decisive positions,
thus forcing a repetition.

>It is possible that you need an hour to prove for every move of white in the
>first 29 moves that it is singular and in this case you need only 30 hours to
>prove the mate(I guess that you can prove the last mate in 9 in an hour).
>
>Uri

Now _that_ would be a result!
I would be very proud of it!

Well, there is still a lot of room for innovations and improvements.
Do you know of any program that does such "proving" methods
(i.e. not just search) ?  Any articles or pointers?

Heiner



This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.