close
Skip to main content
MathOverflow

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Cancel
20
  • 4
    $\begingroup$ Have you tried to see if the Fraenkel-Liechtenstein construction is of any use? They show how to simulate a certain Boolean satisfiability game of Stockmeyer and Chandra using chess pieces. I think the Stockmeyer-Chandra game is based on a Turing-machine simulation, so on an infinite board with unboundedly many pieces, you might be able to simulate the halting problem. $\endgroup$ Commented Jun 13, 2010 at 2:46
  • 4
    $\begingroup$ Computability questions very often depend on the format of the input. There are two things that need to be clarified: (1) What are the restrictions on the collection of pieces? Must both players have a king? Are they limited to the usual chess set? (2) How is the position fed as an input to the algorithm? The best option at the moment seems to be as a finite list of (piece, position) pairs that is encoded into a single number and passed to the algorithm all at once. $\endgroup$ Commented Jul 20, 2010 at 11:15
  • 1
    $\begingroup$ Also, I guess we abandon the common tournament rule by which 50 moves without a capture or a pawn move causes stalemate? $\endgroup$ Commented Jul 20, 2010 at 11:33
  • 1
    $\begingroup$ (continued) It goes without saying that this makes no "proof" but it's just my personal conviction out of actual game practice. On the other hand would be very interesting to come up with positions that would be drawn in the regular 8x8 chessboard, but can be won in an infinite (or very large) board thanks to the possibility of manouvering in a wider space. $\endgroup$ Commented Aug 24, 2010 at 13:18
  • 1
    $\begingroup$ I found an argument for why the chess on the infinite board without the 50-move rule is probably undecidable: redhotpawn.com/board/… But I do not know whether that argument uses only finitely many pieces. $\endgroup$ Commented Aug 24, 2010 at 13:41