Timeline for Decidability of chess on an infinite board
Current License: CC BY-SA 2.5
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 4, 2016 at 15:50 | comment | added | John Gowers | I don't think you need to worry about the ability of the black king to stave off checkmate by moving in a particular way. It is impossible for two rooks (and no king) to checkmate a king, even with the king's cooperation: two rooks cannot cover a 3x3 grid of squares between them. | |
| Aug 24, 2010 at 15:30 | comment | added | Carl Mummert | Put another way: the question is ambiguous whether we are looking at an infinite board that happens to have finitely many pieces, or finitely many pieces that happen to be on an infinite board. My solution addresses the first of these. If you can have infinitely many pieces, there is a tension between knowing the location of each piece and knowing the contents of each square. If you are only given an enumeration of pieces and locations, how can you possibly tell whether a given square is empty, or whether a move is legal? In that case, it's equally hard to say we're "dealing with chess". | |
| Aug 24, 2010 at 15:21 | comment | added | Carl Mummert | Assuming that what you're proposing actually gives a many-one reduction from an the set K to the set of computable infinite boards for which white has a winning strategy, that's exactly the point I'm making with my solution. If you use this input convention, the problem is unsolvable. The question itself left the definition of "infinite chessboard" and "position" undetermined, and the only way to tell which definitions are unattractive is to actually prove the results that show it. That's what I'm doing here. | |
| Aug 24, 2010 at 11:45 | comment | added | Andrej Bauer | @Carl: if we are allowed to giv input in your way, then why not do the following: given a Turing machine $T$, let the position be a check-mated black king if $T$ halts and only both kings otherwise. If there were an algorithm for deciding who wins, we could obviously solve the Halting Problem. With your kind of input it doesn't matter that we are dealing with chess, we might as well be playing the game "is there a queen here to be seen?". | |
| Aug 23, 2010 at 15:45 | comment | added | Tsuyoshi Ito | However, whether something is obvious or not is subjective and I doubt that my argument is convincing enough. Furthermore, I do not think that I am adding anything useful to the original question, so I will try to keep quiet from now on until I can come up with more useful comments. | |
| Aug 23, 2010 at 15:44 | comment | added | Tsuyoshi Ito | Thank you for the reply, but I am still unconvinced. As Joel David Hamkins commented, many “basic” questions are undecidable with the input format used in your solution. Therefore, I find it difficult to agree that this kind of solution has to be stated in this much detail to establish that this input format is very difficult to handle. | |
| Aug 23, 2010 at 14:25 | comment | added | Carl Mummert | I agree this solution shows that it might be more productive to define the input differently. But a solution of this form is required to establish that. Also, if we had started by getting a positive solution for the problem under a stronger (more informative) input convention, the natural question would arise whether we could also get a positive solution under a weaker (less informative) input convention like the one I considered. So a solution like mine would still be required to close off that line of inquiry. It is somewhat routine, but similar things occur all the time in computability. | |
| Aug 23, 2010 at 13:45 | comment | added | Tsuyoshi Ito | This answer is technically correct but, in my opinion, it only shows why giving the input as a Turing machine which computes a function from locations on the board to pieces is a bad idea. | |
| Jul 20, 2010 at 12:44 | comment | added | Carl Mummert | It seems a version of the solution works with a black king at (0,0), a white rook at (-1,5), a white king at (2,0), and possibly a white queen at (0, n). If the queen is there, checkmate. If not, white has only a king and a rook. Only the rook can put the black king into check, because kings can never be adjacent. So if the black king is in check, he just needs to head vaguely away from the white king. | |
| Jul 20, 2010 at 12:04 | comment | added | Carl Mummert | @Joel: I agree I have only solved one possible version of the original problem. I edited my solution to be more explicit about that up front. The other version of the problem (where the position is specified by a single natural number) seems much more difficult. The interesting thing is that it's not clear that a decision algorithm for infinite boards would work for finite boards, or vice-versa. | |
| Jul 20, 2010 at 11:58 | history | edited | Carl Mummert | CC BY-SA 2.5 |
Copyediting: Clarify that this is only one specification. Fix three-rooks issue.
|
| Jul 20, 2010 at 11:14 | comment | added | Carl Mummert | @Junkie: I don't quite follow your strategy. In my solution, White has no king. I'll have to think about how it changes things to add one... Anyway, here is what I was thinking about how to stave off checkmate in my solution. Assume the black king is in check. If both rooks are attacking on the same line, the King can move sideways. If both are attacking on crossing lines, the King can move diagonally. If only one is attacking, draw a line through it and the King. The other rook is on one side or the other of that line; move in the other direction. Did I miss a something obvious there? | |
| Jul 20, 2010 at 7:25 | comment | added | Junkie | No I can mate you with two rooks on the infinity board. Use a normal chess board, black will never reach the edge. To start, as above I can move around so to get Rooks c1/e1, Black d4 say, King h5. Black moves Kd5, then Kg6 Kd6, then Kf7, and Black can't move to d7 for Red1, and so the king must walk back down the d-file. White follows. Continuing, Kf7 Kd5, Kf6 Kd4, Kf5 Kd3, Kf4 Kd2, Kf3 Kd3, Red1 caput. Another presentation is white Rooks at c1/e8 to start, and the Black at d4 and white at h4. Then Black can run either up or down, and white just has to keep the right parity in either case. | |
| Jul 20, 2010 at 7:08 | comment | added | Junkie | "If there are only two rooks, I believe that the king can stave off checkmate by moving off towards infinity indefinitely." White can stop this by moving the rooks on the 1st and -1st columns far enough down? I think you are in principle correct, but White can force Black around using the rooks and eventually his king. My complaint is that Black cannot simply head off to infinity. | |
| Jul 20, 2010 at 3:15 | comment | added | Joel David Hamkins | For example, from that input data, your argument shows that we can't even decide if a given input position is already in checkmate, or whether a proposed move is a legal move, etc., although if we are given the complete finite position, then these questions would be decidable. | |
| Jul 20, 2010 at 3:06 | comment | added | Joel David Hamkins | Carl, this solution is very interesting (+1), but it is dependent on the input being a computable function from position$\to$pieces. (For example, your solution relies on us not being able to compute the number of pieces from your input data.) But since the problem was to have only finitely many pieces, however, it would seem natural to have the input be the (complete) finite list of pieces and their positions. In this case, your method wouldn't work. | |
| Jul 20, 2010 at 0:39 | history | edited | Carl Mummert | CC BY-SA 2.5 |
sigh
|
| Jul 20, 2010 at 0:33 | history | answered | Carl Mummert | CC BY-SA 2.5 |