Skip to main content
3 of 4
added 535 characters in body
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

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.

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k