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 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.