Timeline for What proportion of chess positions that one can set up on the board, using a legal collection of pieces, can actually arise in a legal chess game?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 25, 2021 at 16:23 | comment | added | Andrew Buchanan | Natch is a really good program: one of the fastest around at its chosen task. The chess problem database PDB contains 1350+ proofgames validated by Natch. These include some with over 60 single moves. Hence I myself wouldn't have selected the word "purport" to describe its capabilities. | |
| Jul 31, 2013 at 19:13 | comment | added | The Masked Avenger | It seems it was Thompson, 5 pieces, and if they did straightforward isomorphic reductions, one might extract the number of legal positions for 5 pieces from that work, and use that as a better basis for extrapolation. | |
| Jul 31, 2013 at 11:18 | comment | added | domotorp | @Masked: About end game positions, see en.wikipedia.org/wiki/Endgame_tablebase but I doubt this would be of much use. | |
| Jul 30, 2013 at 22:16 | comment | added | The Masked Avenger | I think Kernighan or Brent in the early days of UNIX developed a database of end game positions for up to 6 pieces. For small collections, one could try none's suggested approach and see how the ratio falls as the number of pieces grows. Just looking at 3 pieces, one gets bad arrangements only for bishops and pawns that aren't excluded already by adjacent kings. | |
| Jul 30, 2013 at 13:11 | comment | added | Joel David Hamkins | Isn't finding even a single proof game difficult, let alone the shortest one? Reachability is difficult in general, and the shortest game path may have exponential length (see mathoverflow.net/questions/27944/…). | |
| Jul 30, 2013 at 9:19 | comment | added | Gerry Myerson | If one of the guesses in the comments ($2^{-32}$) is anywhere near correct, you'll be waiting a long tie for Natch to accept one of your randomly generated positions. | |
| Jul 30, 2013 at 9:10 | review | First posts | |||
| Jul 30, 2013 at 9:11 | |||||
| Jul 30, 2013 at 8:54 | history | answered | none | CC BY-SA 3.0 |