Decidability of the winning-position problem in an infinity chess with a finite number of short-range pieces only

Question

Definitions

Long-range pieces: queens, rooks, bishops.

Short-range pieces: pawns, knights, kings.

We can extend the definition of short-range pieces to include also fairy pieces like: Berolina pawns, wazirs, ferzes, dabbas, alfils, threeleapers, camels, zebras, trippers, etc. (see: http://en.wikipedia.org/wiki/Fairy_chess_piece).

Background

Inspired by Richard Stanley’s question Joel David Hamkins with coauthors wrote the paper where they conjectured “that the general winning-position problem is undecidable and indeed, not even arithmetic”. The main argument preventing us from expanding the “mate-in-n” theorem to the winning position problem is a fact that “a player may have a winning strategy from a position, without there being any finite bound on the number of moves required”. This issue is directly related to the question here. The formulation of the question states that such a position “must involve a long-range piece for the losing side”.

Questions

Is it possible to apply the “mate-in-n” theorem to settle the winning-position problem in positions with only short-range pieces?

If so, how can we calculate the upper bound for $n$ in a given position? How can we be sure that we don’t have to keep solving the “mate-in-n” for larger and larger $n$?

If not, what are the promising ways which could possibly lead to a proof of the problem decidability?

Considerations

With a finite board we know that repetitions of the positions have to occur. Then, we can use the non-repetition argument. If every path in the game tree leads to a repeated position then the initial position is a draw. With an infinite board the number of possible new positions is not a finite number. Heuristically, we can argue that if a white short-range piece is “too far away” from its nearest neighbor (any other piece), then such a position is not better for White than the one when the piece is still far away but not “too far away” from its nearest neighbor. The idea here is that if the piece is “too far away” it does not participate in the game. Thus, if we place it closer but still far away then it doesn’t change anything important – it still doesn’t participate in the checkmating process. Accepting the above argument, it is enough to consider only a finite number of positions to be sure that a position is a draw. I’m not sure if it is possible to make this heuristic argument rigorous.

UPDATE 28th March 2014: I’ve just came across a version of an infinite chess which was considered by Dénes Kőnig in 1927 (source: slide 26 here). It is played:

• on an infinite chessboard,

• with the rules of Chess, and

• with the same moves as on a normal chessboard (i.e., the Queen, Rook, and Bishop move at most seven squares at a time).

Thus, the above version is the one with short-range pieces only. This version (let call it Kőnig version) has the rules for moves which are in perfect agreement with the rules of an ordinary chess. The same is true of the version with Queen, Rook, and Bishop able to move through any number of unoccupied squares (let call it Brumleve-Hamkins-Schlicht, or BHS for short).

It seems to be a plausible conjecture that while the winning position problem is undecidable for the BHS version it is decidable for the Kőnig version.

Answer 1

The decidability of the special case of the won-position problem, restricted to positions having only short-range pieces, remains open to my knowledge. Nevertheless, as you suspected, one can use the methods of the mate-in-$n$ analysis to provide a much lower upper bound on the complexity. Whereas we had conjectured that the general won-position problem might not be arithmetic, in the case of your restricted positions, the problem is at worst computably enumerable.

Theorem. A position with only short-range pieces is a won position for white if and only if it is mate-in-n for white for some $n$.

Proof: Since the game position is finitely branching, the recursive game values on positions with black-to-move will always be taking the supremum of a finite set, and so inductively we can see that all game values will be finite. This is a general fact: in any open game, where black has only finitely many moves at any stage, then all the game values are finite. In particular, if the initial position has a value, which is to say, if white can force a win, then the value must be finite. Thus, if white can force a win at all, then white will be able to force a win in $n$ moves for some specific $n$. QED

In particular, the phenomenon of transfinite game values in infinite chess does not arise with positions having only short-range pieces.

Corollary. The won-position problem for short-range-piece positions is computably enumerable.

Proof: Given any finite position having only short-range pieces, we can search for an $n$ such that it is mate-in-$n$, and those questions are decidable. By the theorem, this is equivalent to the original position begin winning for white. QED

One can similarly enumerate computably the won-positions for black, and also enumerate the positions for which white or black can force a draw by means of forcing the position into a closed finite space of positions. But this is not the same as forcing a draw, since perhaps black can force the play to continue indefinitely, without forcing it into a finite closed space of positions. So this possibility prevents us from having a partition of the positions into finitely many c.e. classes, and so undecidability still seems possible.

Answer 2

I think we can try to build further on Joel’s answer that one can “enumerate the positions for which white or black can force a draw by means of forcing the position into a closed finite space of positions. But this is not the same as forcing a draw, since perhaps black can force the play to continue indefinitely, without forcing it into a finite closed space of positions.”

There are two cases in which black can force a draw: forcing the position into a closed finite space of positions and forcing the play to continue indefinitely without forcing it into a finite closed space of positions. Case 1 is c.e. (see Joel's comments below).

Consider case 2. How would a situation be like if black can force the play to continue indefinitely without forcing it into a finite closed space of positions? First, white can be left with insufficient material to checkmate.

Secondly, the situation where a white mating formation (a few knights) is unable to decrease the distance between itself and the black king. We know that a single knight moves at a speed twice the speed of a king. The formation of two knights move at a speed equal to the speed of a king. Thus, on an empty part of the board black king is able to keep a constant distance between itself and a two-knight formation. Moreover, it is well known that two knights alone cannot force a checkmate (in fact even 2 knights with a king on a finite board cannot). It is a case of insufficient material. Thus, we know that a possible white mating formation has to consist of at least 3 knights and it implies that such a formation is slower than the black king. Black can force a draw if the black king can go to an empty part of the board.

Now, it seems that the only problem which remains is whether case 2 always has to take a form of insufficient white material or the black king being able to go to an empty part of the board.

Answer 3

Let’s start with the simplest case when white has only pawns (no king) and black has only a king.

The position is a draw if the black king can be placed in:

a) a file (column) more to the right (left) than the rightmost (leftmost) pawn,

b) a rank (row) below the lowest pawn.

White has to prevent the black king from escaping to the right or the left or to the bottom. To achieve this white has to block the way through the top. If the black king is not blocked from the top it can move one step diagonally every time and finally it reaches a file (column) mentioned in point a). The above indicates that a necessary condition for a white win is to build a kind of a “cage” – a closed finite region from which the black king cannot escape. White has to build “cage walls” from its pawns.

What is the highest possible vertical length of the cage? For sure, it is finite. Let $n$ be the number of pawns. We can easily see that it has to be less than $n/2$ as in each rank (row) at least one pawn has to block the left direction and one the right one.

Now consider any move of a pawn to square on a file $n/2$ files higher than a file of the black king. Such a pawn cannot be a part of a cage wall. If white is able to stop the black king on its way to the top it is possible to block the king lower with blocking pawns being a part of the cage walls.

However, it does not necessarily mean that moves beyond a file $n/2$ files higher than a file of the black king are not optimal. It can be a case that they are applied to avoid zugzwangs. Nevertheless, we can treat such moves as null-moves. That way, we are able to reduce the problem from an infinite board to its finite fragment. Starting from the initial position, we can limit our analysis to a rectangle with the left/right file (column) one file to the left (right) from the leftmost/rightmost pawn, bottom rank (row) one rank below the lowest pawn’s rank and the top rank $n/2$ files higher than the king’s rank or the top rank is simply the rank of the topmost pawn (depending which is higher).

We reduced the infinite game to a finite one. Every path in the finite game tree has to end with one of the following:

• checkmate,

• stalemate,

• repeated position,

• the black king on the left or right file or on the bottom or top rank.

---

Now, I think that it is quite straightforward to extend the above argument to a case when both sides have pawns and there are 2 king on the board. The leftmost/rightmost pawn can be of any color. Now the bound for the vertical length is $n$ as we have to look to the top from both kings perspective.

I also believe that the above reasoning is applicable to the original problem with knights + pawns + kings and maybe even to a case with any short-range pieces. With knights + pawns + kings, we know that a knight mating formation is not able to move at a speed of a king and that such a formation has to consist of at least 3 knights (see my previous answer to this question). If the black king can be placed more to the left (right, bottom, top) than the third leftmost (rightmost, bottommost, topmost) white knight and it cannot be blocked by pawns it escapes. Again, in order to be able to mate, the winning side has to build a “cage”. With a finite total number of pieces on the board, this cage has to be of finite size. It enables us to consider only a finite part of the board. Moves trying to go beyond the finite part of the board are regarded as null-moves.