33 ms·
I wonder if existing computer chess engines can be modified to do retrograde analysis, and then find some heuristic for positions that are "obviously" possible
by schoen 10y ago
I wonder if existing computer chess engines can be modified to do retrograde analysis, and then find some heuristic for positions that are "obviously" possible via legal moves, and then see if the retrograde analysis can reach one of those.
I have a feeling this is often tractable, because we could probably construct a cooperative scenario involving sacrifice of arbitrary pieces at the beginning of the game (maybe via a series of knight captures?), and then the main question is confirming how particular pawns moved past each other, and finding a way of ensuring that no stalemates occurred while positioning the kings.
- vinchuco 10y agoSounds computationally intensive. It reminds me of an experiment I read about some time ago, tangentially: http://theinvisiblegorilla.com/blog/2012/02/15/how-experts-recall-chess-positions/ http://theinvisiblegorilla.com/blog/2012/02/15/how-experts-r...
- schoen 10y agoThanks for the link! That in turn reminds me of how Fischer advocated randomizing starting positions in order to eliminate the role of opening theory. https://en.wikipedia.org/wiki/Chess960 https://en.wikipedia.org/wiki/Chess960 (because apart from the structure part that the link you gave mentions, experts seem to know a huge amount of explicit opening theory, in terms of memorized opening lines and particular chess masters' view of their tactical consequences) I'm getting more curious about the reachability question. There are some discussions at https://chess.stackexchange.com/questions/4830/how-many-legal-but-unreachable-positions-exist https://chess.stackexchange.com/questions/4830/how-many-lega... https://mathoverflow.net/questions/138133/what-proportion-of-chess-positions-that-one-can-set-up-on-the-board-using-a-leg https://mathoverflow.net/questions/138133/what-proportion-of... https://www.chess.com/forum/view/general/how-many-different-chess-positions-are-there?page=1 https://www.chess.com/forum/view/general/how-many-different-... https://en.wikipedia.org/wiki/Chess#Combinatorics_of_chess_and_chess_puzzles https://en.wikipedia.org/wiki/Chess#Combinatorics_of_chess_a... Also related: https://en.wikipedia.org/wiki/Proof_game https://en.wikipedia.org/wiki/Proof_game That includes a retrograde solver for openings, but that's not exactly what I was envisioning -- I was thinking of a retrograde solver for endgames, which then needs something kind of akin to an inverse tablebase ("yes, this family of positions is known to be legal!" instead of "this position is a win for black").