The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an infinite board decidable? In other words, given a position on an infinite board (say $\mathbb{Z}\times \mathbb{Z}$, though now pawn promotion is not possible) with finitely many men, say with White to move, is there an algorithm to determine whether White can checkmate Black (or prevent Black from checkmating White) against any Black defense?

4$\begingroup$ Have you tried to see if the FraenkelLiechtenstein 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 StockmeyerChandra game is based on a Turingmachine simulation, so on an infinite board with unboundedly many pieces, you might be able to simulate the halting problem. $\endgroup$– Timothy ChowCommented 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$– Carl MummertCommented 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$– Joel David HamkinsCommented 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$– Andrea MoriCommented Aug 24, 2010 at 13:18

1$\begingroup$ I found an argument for why the chess on the infinite board without the 50move rule is probably undecidable: redhotpawn.com/board/… But I do not know whether that argument uses only finitely many pieces. $\endgroup$– Tsuyoshi ItoCommented Aug 24, 2010 at 13:41
5 Answers
There is a positive solution for the decidability of the matein$n$ version of the problem.
Many of us are familiar with the White to mate in 3 variety of chess problems, and we may consider the natural analogue in infinite chess. Thus, we refine the winningposition problem, which asks whether a designated player has a winning strategy from a given position, to the matein$n$ problem, which asks whether a designated player can force a win in at most $n$ moves from a given finite position. (And note that as discussed in Johan Wästlunds's question checkmate in $\omega$ moves?, there are finite winning positions in infinite chess which are not matein$n$ for any finite $n$.) Even so, the matein$n$ problem appears still to be very complicated, naturally formulated by assertions with $2n$ many alternating quantifiers: there is a move for white, such that for every black reply, there is a countermove by white, and so on. Assertions with such quantifier complexity are not generally decidable, and one cannot expect to search an infinitely branching game tree, even to finite depth. So one might naturally expect the matein$n$ problem to be undecidable.
Despite this, the mateinn problem of infinite chess is computably decidable, and uniformly so. Dan Brumleve, myself and Philipp Schlicht have just submitted an article establishing this to the CiE 2012, and I hope to speak on it there in June.
D. Brumleve, J. D. Hamkins and P. Schlicht, "The mateinn problem of infinite chess is decidable," 10 pages, arxiv preprint, submitted to CiE 2012.
Abstract. Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The matein$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most n moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiersthere is a move for white, such that for every black reply, there is a countermove for white, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth. Nevertheless, the main theorem of this article, confirming a conjecture of the first author and C. D. A. Evans, establishes that the matein$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such matein$n$ positions. The proof proceeds by showing that the matein$n$ problem is expressible in what we call the firstorder structure of chess $\frak{Ch}$, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Unfortunately, this resolution of the matein$n$ problem does not appear to settle the decidability of the more general winningposition problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\rm chess}$ is not known.
The solution can also be cast in terms of Presburger arithmetic, in a manner close to Dan Brumleve's answer to this question. Namely, once we restrict to a given collecton of pieces $A$, then we may represent all positions using only pieces in $A$ as a fixedlength tuple of natural numbers, and the elementary movement, attack and incheck relations are expressible for this representation in the language of Presburger arithmetic, essentially because the distance piecesrooks, bishops and queensall move on straight lines whose equations are expressible in Presburger arithmetic. (There is no need to handle sequence coding in general, since the number of pieces does not increase during play.) Since the matein$n$ problem is therefore expressible in Presburger arithmetic, it follows that it is decidable.

5

7$\begingroup$ Yes, of course! We cite this very question, mentioning Richard Stanley specifically, in our opening paragraph as the origin of our interest in the problem. $\endgroup$ Commented Jan 26, 2012 at 21:37

2$\begingroup$ Very nice! As the authors point out, it doesn't answer my question (for which $n$ is not part of the input), but it is still an interesting contribution. $\endgroup$ Commented Jan 27, 2012 at 17:21

5$\begingroup$ Dan Brumleve has now joined as coauthor of the paper. Philipp and I invited him to join us after realizing that his idea of using Presburger arithmetic amounted to essentially the same method of proof as the automatic structure approach. $\endgroup$ Commented Jan 28, 2012 at 0:29

2
Yes, because any chess position can be translated into Presburger arithmetic. For a fixed initial combination of piece types, let's define a position to consist of an (x, y) location for each piece as well as a bit (c) to indicate whether or not it has been captured. Multiplication of these parameters is not required to describe the legality and the effects of any one move, so in Presburger arithmetic we can recursively define the proposition "White cannot capture Black's King in fewer than t moves starting from initial position X.", then apply the axiom schema of induction to get an expression meaning "White cannot ever checkmate starting from initial position X." Since Presburger arithmetic is complete we will always be able to prove either this statement or its negation.
EDIT: Summary of how this is supposed to work:
 P(A) = It is White's move and White has not yet won in position A.
 R(A, B) = Position B legally follows in one move from position A.
 Q(A, 0) = P(A)
 Q(A, t) = for all B: (R(A, B) > there exists C: R(B, C) > Q(C, t  1))
 S(A) = Q(A, 0) and (for all t: Q(A, t) > Q(A, t + 1))
This works fine at least up to line four where Q(A, t) is defined recursively. If Q(A, t) could be defined as a predicate in Presburger arithmetic then I think line five would also work. But this is a serious problem and maybe breaks the whole approach.

1$\begingroup$ Could you explain why Presburger arithmetic (which has only addition) is able to carry out this kind of encoding? The usual Goedel coding of such combinatorial operations, such as for Turing machines, would use something more like Peano Arithmetic or weakened forms. Presburger arithmetic, in contrast, cannot carry out that arithmetization, for example in the case of Turing machines, precisely because it is a decidable theory. $\endgroup$ Commented Sep 5, 2010 at 0:04

1$\begingroup$ Yes, there is induction, but only for assertions involving only addition. There is no Goedel encoding of finite sequences in Presburger arithmetic, for if there were, then its theory could not be decidable, since we could express the halting problem. $\endgroup$ Commented Sep 5, 2010 at 0:59

3$\begingroup$ Although Presburger arithmetic can prove all instances of the proofbyinduction principle that can be expressed in its (very limited) language, it cannot express definitions by recursion, such as those proposed in this answer. If definition by recursion were available, then we could use it to define multiplication and therefore have an undecidable theory. $\endgroup$ Commented Sep 5, 2010 at 2:49

2$\begingroup$ Although the inductive part of this answer is problematic, it does contain a correct account of the mateinn problem via Presburger arithmetic. For a fixed collection of pieces, one needn't do the Goedel coding of sequences inside the Presburger theory, because the number of pieces does not increase during play. Thus, one may represent a position with $r$ many pieces as a $3r+1$ tuple of natural numbers, in the manner Philipp Schlicht and I describe in our paper, and the movement and incheck relations are expressible in Presburger arithmetic, ...(cont'd) $\endgroup$ Commented Jan 27, 2012 at 14:31

2$\begingroup$ ...essentially because the distance pieces move on straight lines whose equations are expressible in Presburger arithmetic. Thus, the mateinn problem for a fixed collection of pieces is expressible in Presburger arithmetic, and hence decidable. Similarly, one can get computable strategies from such positions in this way. I voted up this answer when it was first posted, but I feel it deserves more votes. $\endgroup$ Commented Jan 27, 2012 at 14:33
There's no such algorithm under at least one rigorous specification of the question.
Consider a position in which there is a black king at (0,0) and no other black pieces; white rooks at $(1,5)$ and $(1,5)$, and possibly a white queen at a position of the form (0,$n$) for some large $n$. Picture a king backed into a long tunnel. Then white can checkmate black (and does, from the start) if and only if the queen actually exists somewhere along the tunnel. If there are only two rooks, I believe that the king can stave off checkmate by moving off towards infinity indefinitely (see my explanation in the comments below).
Using positions like that, given any r.e. set $K$ and any number $m$, I can make a chess position such that white can checkmate black if and only if $m \in K$: I put the queen at $(0,n+5)$ if and only if $m$ is enumerated in $K$ after exactly $n$ steps. So I can decide membership in $K$, relative to an oracle for your problem. Actually I only need an oracle that works for indices of computable positions. This shows that any solution to your problem is of degree at least $0'$.
Note: I have taken a "position" to be a function from locations on the board to pieces. You could try to work around this solution by specifying something else as a "position". For example, you could make a position a function from a list of pieces to locations on the board, and that might lead to a different solution. However you need to require the list to explicitly say how many pieces there are from the beginning, or a variation of this solution will still apply.

6$\begingroup$ 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. $\endgroup$ Commented Jul 20, 2010 at 3:06

9$\begingroup$ 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. $\endgroup$ Commented Jul 20, 2010 at 3:15

2$\begingroup$ 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 dfile. 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. $\endgroup$– JunkieCommented Jul 20, 2010 at 7:25

9$\begingroup$ 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. $\endgroup$ Commented Aug 23, 2010 at 13:45

3$\begingroup$ 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. $\endgroup$ Commented Aug 23, 2010 at 15:44
Yes. There is a finite board size that has essentially the same solution structure as all larger boards and an infinite board, and we can find it by solving the game completely for increasing board sizes until that ultimate size can be recognized. (The infinite board is different from a very large board only in that it has no edges or corners, so its solution structure is smaller.) Eventually this is possible, because there are only a finite number of pieces, and therefore only a finite number of equivalence classes of solution structures. When the number of such equivalence classes stops growing, we are done. Basically, all positions with pieces not close to the edge of the board but far from the center (say those with pieces inside an annulus) can be identified with more bounded positions (those surrounded by that annulus), because the pieces with an infinite number of options (Queen, Rook, Bishop) can go anywhere (up to parity) with no more than 2 moves, and the other pieces are forced to walk long distances for which all that matters are their relative path lengths to a certain precision. When one set of pieces moves far enough away from another set of pieces that the two sets are now in general position, these subproblems interact in an equivalent way, so the description of the complete solution will eventually stop increasing with board size.
More generally this strategy works for any chesslike game in which the pieces can be classified into "ultramobile" and "paramobile" types with constant and linear freedom respectively. For example it is also true for checkers because all pieces are paramobile.
I am still unable to specify the equivalence between positions precisely enough to set an explicit bound on the necessary size of the finite board in terms of the number of pieces n, but I guess that it is O(f(n!)) for some polynomial function f whose order is O(n), or in other words O((n!)^(k*n)) for some k, using the construction technique that I have suggested. The superexponential term is contributed by the paramobile pieces and the polynomial by the ultramobiles. In any case I have intended only to demonstrate that the necessary board size has a computable bound.

3$\begingroup$ This is an intriguing idea for a solution, but it's not precise enough to be a proof yet. For example, the input convention matters (see my answer) but the sketch doesn't refer to it. Do you have a formal definition of the equivalence relation in mind? $\endgroup$ Commented Aug 23, 2010 at 11:06

1$\begingroup$ Or think about it this way: whenever it is to one player's advantage to continue increasing the variance of the position forever, the other player is willing to accept a draw. $\endgroup$ Commented Aug 23, 2010 at 21:06

2$\begingroup$ I had once voted this answer up because I thought that it was “obviously correct,” but I canceled my upvote because I realized that I cannot be sure about its correctness. It is plausible that your idea works, but I cannot tell whether it really works or not from this sketch. $\endgroup$ Commented Aug 24, 2010 at 1:30

2$\begingroup$ This looks to me like a very fuzzy suggestion on how one might be able to do something, but more likely not. There are too many unclarified concepts (structure, what structure? What equivalence classes precisely?), and my feeling is they can never be clarified. $\endgroup$ Commented Aug 24, 2010 at 11:41

3$\begingroup$ As for the downvote, I do not think it is healthy to worry about it too much. People can upvote or downvote for various, sometimes pretty arbitrary, reasons. I can imagine that many users vote a post up just because a poster is famous or just because the poster sounds confident. Similarly, I can imagine that some (hopefully not many) users vote a post down just because someone says it is wrong or simply because the voter lacks the knowledge required to understand it. $\endgroup$ Commented Aug 25, 2010 at 12:39
I would like to convince everyone that this problem is undecidable. I cannot prove it for chess, as I lack the ability to design certain configurations but I think they must exist. And even if they don't, for some chesslike game they certainly do which shows that the attempts to prove decidability should be incorrect.
Hm, after reading the comments to the original question carefully, I realised that there is already a pointer to an argument very similar to mine by Tsuyoshi Ito: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006 I still leave my proof here, as in fact two counters are enough and maybe mine is more detailed.
The reduction relies on the notion of counter machine*. It is undecidable whether a counter machine with only two counters halts or not. So our goal would be to simulate any such machine with a chess position. I can see two ways for this.
i, Build two separate configurations, such that both have a starting part and a moving part that can change (to store the state). Also, the moving parts would be connected, eg. by rooks, which could checkmate, if released, so this is why if one states moves 1, the other has to move k, and so on.
ii, Build a single configuration, that depending on its state, moves l horizontally and k vertically. Also, place a rook at (0,0) that would never move but could guarantee that the configuration can "sense" when it gets back to an empty counter.
So all left to do is to design such configurations, which I guess should be possible with some effort and knowledge of chess. Also, note that in both cases the construction uses a piece whose range is not bounded, I wonder if this is really necessary.
*I realized that the definition on wikipedia is different from what I want. In fact, my machine should be probably called a 2stack machine that can push only one letter to the stack. So I want a finite state machine with two counters that are empty at the beginning and it can increase or decrease any counter by one or check whether a counter is zero or not. The problem of whether such a machine halts or not, is undecidable.