Return to Answer

If the initial position has only short-range pieces, then at each stage each player has only finitely many possible moves, and so the game tree is finitely branching. Thus, for any given initial configuration, one may compute the entire (finite) game tree to depth $n$, which lists the complete space of all legal moves for the next $n$ steps. By evaluating whether the resulting level-n positions have achieved checkmate or not, one can determine via back-propagation whether the initial position can force a checkmate in $n$ moves or not. Thus, we may compute the answer to the mate-in-n problem for such a position and furthermore compute the moves of a winning strategy.

The subtle difficulty of the mate-in-n problem arises only when there are long-range pieces, since in this case, the tree becomes infinitely branching, and so one cannot search the tree to depth $n$ in finite time. Nevertheless, as we explain in the article, the mate-in-n problem is still decidable by other means than searching through the tree.

A similar issue arises with the stalemate-in-$n$ problem and the stalemate-or-win-in-$n$, as we explain in our paper, since one can check the level $n$ positions of the tree (or earlier terminal nodes) to see if stalemate or checkmate has occurred, and use back-propagation to see if white can force this situation.

But when it comes to the draw-in-$n$ problem, a complication arises: what does it mean to force a draw in $n$ moves? If one can force a draw, in the sense that there is a finite space of positions, such that in $n$ moves white can force into that space, and white can force the position to stay in that space once in that space. Then, the draw-in-$n$ problem to such a space (or to space of size $k$) is decidable.

Update. But I see in the comments below that you are interested not in the mate-in-$n$ problem for short-range positions, but in the won-position problem for such positions. In this case, the problem is totally open to my knowledge.

But let me point out that the issue of infinite game values can not arise with short-range piece positions.

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$. Thus, the won-position problem for short-range-piece positions is computably enumerable.

Proof: since the game position is finitely branching, the recursive game values will always be taking the supremum of a finite set, and so all game values are finite. Thus, if the initial position has a value, it must be finite, and so if white can win, white will be able to force a win in finitely many moves. This makes the won-position problem for such positions c.e., since one can search for an $n$ such that it is mate-in-$n$, and those questions are decidable. QED

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

If the initial position has only short-range pieces, then at each stage each player has only finitely many possible moves, and so the game tree is finitely branching. Thus, for any given initial configuration, one may compute the entire (finite) game tree to depth $n$, which lists the complete space of all legal moves for the next $n$ steps. By evaluating whether the resulting level-n positions have achieved checkmate or not, one can determine via back-propagation whether the initial position can force a checkmate in $n$ moves or not. Thus, we may compute the answer to the mate-in-n problem for such a position and furthermore compute the moves of a winning strategy.

The subtle difficulty of the mate-in-n problem arises only when there are long-range pieces, since in this case, the tree becomes infinitely branching, and so one cannot search the tree to depth $n$ in finite time. Nevertheless, as we explain in the article, the mate-in-n problem is still decidable by other means than searching through the tree.

A similar issue arises with the stalemate-in-$n$ problem and the stalemate-or-win-in-$n$, as we explain in our paper, since one can check the level $n$ positions of the tree (or earlier terminal nodes) to see if stalemate or checkmate has occurred, and use back-propagation to see if white can force this situation.

But when it comes to the draw-in-$n$ problem, a complication arises: what does it mean to force a draw in $n$ moves? If one can force a draw, in the sense that there is a finite space of positions, such that in $n$ moves white can force into that space, and white can force the position to stay in that space once in that space. Then, the draw-in-$n$ problem to such a space (or to space of size $k$) is decidable.

Update. But I see in the comments below that you are interested not in the mate-in-$n$ problem for short-range positions, but in the won-position problem for such positions. In this case, the problem is totally open to my knowledge.

But let me point out that the issue of infinite game values can not arise with short-range piece positions.

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$. Thus, the won-position problem for short-range-piece positions is computably enumerable.

Proof: since the game position is finitely branching, the recursive game values will always be taking the supremum of a finite set, and so all game values are finite. Thus, if the initial position has a value, it must be finite, and so if white can win, white will be able to force a win in finitely many moves. This makes the won-position problem for such positions c.e., since one can search for an $n$ such that it is mate-in-$n$, and those questions are decidable. QED

If the initial position has only short-range pieces, then at each stage each player has only finitely many possible moves, and so the game tree is finitely branching. Thus, for any given initial configuration, one may compute the entire (finite) game tree to depth $n$, which lists the complete space of all legal moves for the next $n$ steps. By evaluating whether the resulting level-n positions have achieved checkmate or not, one can determine via back-propagation whether the initial position can force a checkmate in $n$ moves or not. Thus, we may compute the answer to the mate-in-n problem for such a position and furthermore compute the moves of a winning strategy.

The subtle difficulty of the mate-in-n problem arises only when there are long-range pieces, since in this case, the tree becomes infinitely branching, and so one cannot search the tree to depth $n$ in finite time. Nevertheless, as we explain in the article, the mate-in-n problem is still decidable by other means than searching through the tree.

A similar issue arises with the stalemate-in-$n$ problem and the stalemate-or-win-in-$n$, as we explain in our paper, since one can check the level $n$ positions of the tree (or earlier terminal nodes) to see if stalemate or checkmate has occurred, and use back-propagation to see if white can force this situation.

But when it comes to the draw-in-$n$ problem, a complication arises: what does it mean to force a draw in $n$ moves? If one can force a draw, in the sense that there is a finite space of positions, such that in $n$ moves white can force into that space, and white can force the position to stay in that space once in that space. Then, the draw-in-$n$ problem to such a space (or to space of size $k$) is decidable.

Update. But I see in the comments below that you are interested not in the mate-in-$n$ problem for short-range positions, but in the won-position problem for such positions. In this case, the problem is totally open to my knowledge.

But let me point out that the issue of infinite game values can not arise with short-range piece positions.

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$. Thus, the won-position problem for short-range-piece positions is computably enumerable.

Proof: since the game position is finitely branching, the recursive game values will always be taking the supremum of a finite set, and so all game values are finite. Thus, if the initial position has a value, it must be finite, and so if white can win, white will be able to force a win in finitely many moves. This makes the won-position problem for such positions c.e., since one can search for an $n$ such that it is mate-in-$n$, and those questions are decidable. 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.

If the initial position has only short-range pieces, then at each stage each player has only finitely many possible moves, and so the game tree is finitely branching. Thus, given an initial configuration, one may simply compute the entire game tree to depth $n$ (which will be a finite tree) and use back-propagation to determine the winning strategy and whether there is one for that position. Thus, we may compute the answer to the mate-in-n problem for such a position and furthermore compute the moves of a winning strategy.

The subtle difficulty of the mate-in-n problem arises only when there are long-range pieces, since in this case, the tree becomes infinitely branching, and so one cannot search the tree to depth $n$ in finite time. Nevertheless, as we explain in the article, the mate-in-n problem is still decidable by other means than searching through the tree.

If the initial position has only short-range pieces, then at each stage each player has only finitely many possible moves, and so the game tree is finitely branching. Thus, for any given initial configuration, one may compute the entire (finite) game tree to depth $n$, which lists the complete space of all legal moves for the next $n$ steps. By evaluating whether the resulting level-n positions have achieved checkmate or not, one can determine via back-propagation whether the initial position can force a checkmate in $n$ moves or not. Thus, we may compute the answer to the mate-in-n problem for such a position and furthermore compute the moves of a winning strategy.

The subtle difficulty of the mate-in-n problem arises only when there are long-range pieces, since in this case, the tree becomes infinitely branching, and so one cannot search the tree to depth $n$ in finite time. Nevertheless, as we explain in the article, the mate-in-n problem is still decidable by other means than searching through the tree.

A similar issue arises with the stalemate-in-$n$ problem and the stalemate-or-win-in-$n$, as we explain in our paper, since one can check the level $n$ positions of the tree (or earlier terminal nodes) to see if stalemate or checkmate has occurred, and use back-propagation to see if white can force this situation.

But when it comes to the draw-in-$n$ problem, a complication arises: what does it mean to force a draw in $n$ moves? If one can force a draw, in the sense that there is a finite space of positions, such that in $n$ moves white can force into that space, and white can force the position to stay in that space once in that space. Then, the draw-in-$n$ problem to such a space (or to space of size $k$) is decidable.

Update. But I see in the comments below that you are interested not in the mate-in-$n$ problem for short-range positions, but in the won-position problem for such positions. In this case, the problem is totally open to my knowledge.

But let me point out that the issue of infinite game values can not arise with short-range piece positions.

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$. Thus, the won-position problem for short-range-piece positions is computably enumerable.

Proof: since the game position is finitely branching, the recursive game values will always be taking the supremum of a finite set, and so all game values are finite. Thus, if the initial position has a value, it must be finite, and so if white can win, white will be able to force a win in finitely many moves. This makes the won-position problem for such positions c.e., since one can search for an $n$ such that it is mate-in-$n$, and those questions are decidable. QED