Body: <p>I know that Sam Loydfound the 9.5 move stalemate, but how can we <em>prove</em> that his way of reaching stalemate is the fastest?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-11-18T06:37:54.683Z
Comments.Text: 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?
Comments.UserDisplayName: Ross Millikan
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-11-18T12:45:27.127Z
Comments.Text: Just for fun, I tried a slow problem solving program on a slow computer. 2 moves 2s, 3 moves 2 min, extrapolate by yourself :-)
Comments.UserDisplayName: Hauke Reddmann
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-11-19T10:10:38.913Z
Comments.Text: 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.
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-11-21T04:36:03.973Z
Comments.Text: 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.
Comments.UserDisplayName: Hank's back rank
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-11-26T03:52:42.020Z
Comments.Text: Correction: most Perft programs use bulk counting so they don't actually examine leaf nodes, so go ahead and increase all those numbers by a factor of 35.
Comments.UserDisplayName: Hank's back rank
Tags: <stalemate>
Title: Proving the fastest way for stalemate
ThreadText: # Proving the fastest way for stalemate
  
  (Asked by: username_0 on 2023-11-17)
  
  I know that Sam Loydfound the 9.5 move stalemate, but how can we *prove* that his way of reaching stalemate is the fastest?
  
  **Tags:** stalemate
  
  > **Comments:**
  > **username_1**: 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?  
  > **username_2**: Just for fun, I tried a slow problem solving program on a slow computer. 2 moves 2s, 3 moves 2 min, extrapolate by yourself :-)  
  > **username_3**: 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 username_1' approach of guiding the search tree should be the way to go.  
  > **username_4**: 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.  
  > **username_4**: Correction: most Perft programs use bulk counting so they don't actually examine leaf nodes, so go ahead and increase all those numbers by a factor of 35.  
  
  ---
  
  ## 0 answers
  
  