I know that Sam Loydfound the 9.5 move stalemate, but how can we prove that his way of reaching stalemate is the fastest?
-
You can do a brute force search. You can trim it down if you can show that a particular move cannot contribute to a stalemate, so delete it and get a stalemate a ply shorter. What else do you expect or hope for?– Ross MillikanNov 18 at 6:37
-
Prove to whom? A proof is an exercise in cooperation: a person who wants to prove something, and another person who is willing, and able to take the time to read, analyze and understand the proof. As several proof methods appear to be possible, a method based on graph theory is unlikely to be useful for a normal chess player, for example. If all methods require special knowledge, none will be useful for beginning chess players. You really need to say something about who is supposed to decide if the proof is correct.– user30536Nov 18 at 7:04
-
Just for fun, I tried a slow problem solving program on a slow computer. 2 moves 2s, 3 moves 2 min, extrapolate by yourself :-)– Hauke ReddmannNov 18 at 12:45
-
Perft 15 is known. So at the very least up to ply 15 we can check whether any stalemates are possible. Going to ply 19 would be out of reach with a naive brute force method, however. So for that indeed Ross' approach of guiding the search tree should be the way to go.– koedemNov 19 at 10:10
-
I'm pretty sure I read on Talkchess (but can't find the source for some reason) that there are some people working on Perft(16) right now, which means we're almost just two ply away from proving that there is no stalemate faster than the ply 19 one we already know. This would probably take around 1225 (35^2) times the effort of the current Perft(16) search or 42875 (35^3) times the effort of the current Perft(15). If we take Moore's law, we get log_2(1225) = 10.285... which means we can probably prove it with cutting edge hardware in around ten years. That is of course using pure brute-force.– Hank's back rankNov 21 at 4:36
|
Show 1 more comment