Timeline for Decidability of chess on an infinite board
Current License: CC BY-SA 2.5
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 4 at 14:10 | history | edited | Joel David Hamkins |
edited tags
|
|
| May 6, 2018 at 0:04 | history | edited | Joel David Hamkins |
edited tags
|
|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jan 26, 2012 at 20:23 | answer | added | Joel David Hamkins | timeline score: 39 | |
| Oct 22, 2011 at 2:05 | comment | added | hakuna | @timothy Do you have any (free,online) reference for the "Fraenkel-Liechtenstein construction"? | |
| May 2, 2011 at 7:05 | answer | added | domotorp | timeline score: 4 | |
| Sep 4, 2010 at 23:46 | answer | added | Dan Brumleve | timeline score: 8 | |
| Aug 24, 2010 at 13:41 | comment | added | Tsuyoshi Ito | 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. | |
| Aug 24, 2010 at 13:28 | comment | added | Tsuyoshi Ito | @Andrea: I agree that intuitively “most” initial positions (in no rigorous sense) will lead to a draw on the infinite board. However, if the initial position is given as input (as is usual with complexity results about chess-like games), we have to deal with all the initial positions and anything can happen. | |
| Aug 24, 2010 at 13:18 | comment | added | Andrea Mori | (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. | |
| Aug 24, 2010 at 13:13 | comment | added | Andrea Mori | @Tsuyoshi: I was assuming (wrongly?) that the initial position would be the same as in the usual FIDE game with rows and columns extended indefinitely. I'm also assuming that the game is played by "knowledgeable" players (Grand Master level). GM level practice shows that it is always possible to play to reach a slightly inferior endgame. Slightly inferior endgames may be lost on a 8x8 chessboard, but are surely drawn if pawn promotions are not allowed. Just consider that even a Queen or Rook advantage with only pawns left is not enough to win. (continued) | |
| Aug 24, 2010 at 11:57 | comment | added | Tsuyoshi Ito | @Andrea Mori: If that were true, that would be the answer. However, the chess on an infinite board is not necessarily a drawn game. It depends on the initial position. This is why the algorithm is given the initial position as input. | |
| Aug 24, 2010 at 11:26 | comment | added | Andrea Mori | I know that this doesn't answer the question, but without pawn promotions and without the possibility of "cornering" Kings, chess on an infinite board is certainly a drawn game (and also quite dull, I may add) | |
| Aug 23, 2010 at 15:54 | comment | added | Tsuyoshi Ito | @András Salamon: If you have to spend one move to avoid the 50-move rule, it can affect who wins. Therefore, it matters (a priori) whether the 50-move rule is in effect or not. | |
| Aug 23, 2010 at 15:48 | comment | added | Tsuyoshi Ito | I agree to Carl Mummert in that it won’t hurt if the question is more specific about the input format. | |
| Aug 23, 2010 at 15:25 | comment | added | András Salamon | With a board that has infinitely many rows, a single pawn moving on a column set aside for the purpose can obviously be used to get past the 50-move rule. | |
| Aug 23, 2010 at 14:26 | comment | added | Carl Mummert | It's a reasonable assumption, but certainly not the only reasonable one. From the viewpoint of computability theory, the most natural way to define an "infinite chessboard" is as a function that takes a location and returns the contents of that location. That way also generalizes to the case of infinitely many pieces, while the canonical index method does not. But the deeper issue, as usual, is that the format of the input can make a difference. I will also comment below. | |
| Aug 23, 2010 at 13:38 | comment | added | Tsuyoshi Ito | @Carl Mummert: Given that there are only finitely many pieces on the board, I think that it is a common assumption that the input is given as a finitely many pairs of the form (location, piece). | |
| Aug 23, 2010 at 2:12 | answer | added | Dan Brumleve | timeline score: 6 | |
| Jul 20, 2010 at 11:33 | comment | added | Joel David Hamkins | Also, I guess we abandon the common tournament rule by which 50 moves without a capture or a pawn move causes stalemate? | |
| Jul 20, 2010 at 11:15 | comment | added | Carl Mummert | 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. | |
| Jul 20, 2010 at 3:07 | comment | added | Joel David Hamkins | Could you clarify the form of the input? Carl's interesting answer assumed a particular kind of input, but others also seem reasonable. | |
| Jul 20, 2010 at 0:33 | answer | added | Carl Mummert | timeline score: 7 | |
| Jul 20, 2010 at 0:08 | history | edited | Charles Stewart |
edited tags
|
|
| Jun 13, 2010 at 2:46 | comment | added | Timothy Chow | 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. | |
| Jun 13, 2010 at 0:01 | comment | added | Richard Stanley | Yes, I was thinking of any initial configuration as input, with no bound on the number of men. But it seems to me one can also ask the question for a fixed set of men, e.g., the usual set of men at the beginning of the game. | |
| Jun 12, 2010 at 21:45 | comment | added | supercooldave | Sorry. Didn't read the question properly. | |
| Jun 12, 2010 at 20:41 | comment | added | TonyK | @supercooldave, the initial configuration is the input to the algorithm, if I understand the question. | |
| Jun 12, 2010 at 20:08 | comment | added | supercooldave | What is the initial configuration? | |
| Jun 12, 2010 at 19:51 | history | asked | Richard Stanley | CC BY-SA 2.5 |