There is a positive solution for the decidability of the mate-in-$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 winning-position problem,
which asks whether a designated player has a winning strategy from
a given position, to the mate-in-$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 mate-in-$n$ for any finite $n$.) Even so, the
mate-in-$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 mate-in-$n$ problem to be undecidable.
Despite this, the mate-in-n 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 mate-in-n problem of infinite
chess is decidable," 10 pages, arxiv pre-print, 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 mate-in-$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 quantifiers---there is
a move for white, such that for every black reply, there is a counter-move
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 mate-in-$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 mate-in-$n$ positions. The proof
proceeds by showing that the mate-in-$n$ problem is expressible in
what we call the first-order 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 mate-in-$n$ problem does not appear to settle the
decidability of the more general winning-position 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 fixed-length tuple of natural numbers, and the elementary movement, attack and in-check relations are expressible for this representation in the language of Presburger arithmetic, essentially because the distance pieces---rooks, bishops and queens---all 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 mate-in-$n$ problem is therefore expressible in Presburger arithmetic, it follows that it is decidable.
Here is my first try at a solution. Your idea was a good one, but
bishops are better than rooks, I surmise.
The two pictures here are placed in some distinct parts of the infinite board.
The first just ensures it is White to move (in check), and that White's king
will never play a role, as capturing a black unit, which are nearly stalemated as is,
will release heavy pieces.
alt text http://www.freeimagehosting.net/uploads/3c8e277e7d.jpg alt text http://www.freeimagehosting.net/uploads/72ef1c9b7e.jpg
So White is left to checkmate with the four bishops and pawns.
White threatens checkmate via a check from below on the northwest diagonal,
and Black can only avoid this by moving the bishop northeast some amount.
Upon Black moving this bishop, White then makes the bishop check anyways,
the Black king moves where the Black bishop was, the pawn moves with check,
the Black king again retreats northeast along the diagonal, and then White
alternately moves the dark-square bishops, giving checks until the Black
bishop is reached when it is mate.
The point of this second picture is that White cannot checkmate Black
unless the Black bishop plays a role. Four bishops are not enough to
checkmate a king on an infinite board, and hopefully I have set it up so
that the White pawns play no part once Black starts the king running northeast.
Pawns are not too valuable when they cannot become queens.
In extended chess notation, White plays 1. Ke5 on board A,
then Black plays 1...Bz26 on board B, followed by
2. Bg3+ Kf6 3. e5+ Kg7 3. Bi5+ Kh8 4. Bf10+ Ki9 5. Bk7+ Kj10 6. Bh12+ ...,
as White successively cuts off NW-SE diagonals until the Black bishop
is reached. By moving the bishop X squares northeast on move 1, Black
can delay the checkmate for X moves, if I set this up proper.
Other plans by White should be beatable by moving the Black king off
the long diagonal or capturing the light White bishop with the pawn.
Once Black's king exits the area with the pawns, the Black bishop
must be a part of the mating pattern. I don't think the Black king
can be forced back to that area.
Well, this is a first try.
Best Answer
This is a really great question!
Previous attempts to make sense of infinite Go have sometimes had problems because it wasn't clear how to define the winner of a game of Go after transfinite play. The problem was that perhaps a black group was surrounded by a white group, which was surrounded by a black group, and so on forever in such a way that the asymptotic density did not converge. In this case it wouldn't necessarily be clear who had more area. (Another separate issue is to define the state of the board at time $\omega$, in situations where stones had been placed and then killed unboundedly often; it seems most natural to keep only stones that had persisted from some time on.)
Your formulation of the problem gets around this difficulty by making the winner of the game depend on the life or death of a single designated stone. This makes the game an open game and therefore subject to the theory of transfinite open game values.
The answer is yes. There is a position with a black stone that is part of a group that white can definitely kill in finitely many moves, but black can make this take as long as desired.
Consider the following position.
There are infinitely many stones, with black to play, and one should imagine that the pattern continues to the right. The designated black stone is part of the main infinite horizontal group of black stones, which continues to the right, with little black knobs poking down on the underside. This group is nearly surrounded and has only three liberties (at top) and no eyes. Because of the knobs, the surrounding white stones form separate groups, although they are nearly connected.
For each knob, black has the opportunity to make a hopeless cut, attempting to capture the two isolated white stones touching the end of the knob. For example, black could play at $A$, cutting the two white stones off on one side. This move is hopeless by itself, of course, because white can simply connect the two isolated stones on the other side at $B$, and then aim to kill the main black group shortly thereafter. So the hopeless initial cut is only valuable for black, if white should ignore it. There are similar such hopeless cutting moves at each knob.
A key point to observe, however, is that white cannot afford to follow the policy of always answering the hopeless cuts, since this would lead to infinite play, which is what black wants. So eventually, white will indeed have to ignore one of the hopeless cuts, in order to make progess on surrounding the main black group.
When white ignores the hopeless cut, then black will immediately play the other cut, with Atari on the two white stones. White cannot allow that black will connect the main black group to the live black group, and so white must extend. This leads to a ladder, which is ultimately broken by the lower isolated white stones.
The main thing to observe is that these ladder-breaking stones are further and further away as you consider successive knobs. Thus, black can choose to act on knob $n$, aiming to have a ladder of size at least $n$. After the ladder is played out, then the white stones in the ladder will gain sufficient liberties for white to kill the main black group shortly thereafter. So ultimately, the ladder is also hopeless for black, since white will eventually kill the main group; but the point is that black can prolong play as long as she likes, by choosing to act on a knob whose ladder is that long, even if she does lose after that.
So the main line play is as follows. Black makes a hopeless cut on the $n^{th}$ knob for some particular $n$, chosen as large as black likes. White cannot afford to always answer these hopeless cuts, because this would lead to infinite play. And so white will eventually choose to ignore the hopeless cut, playing instead so as to reduce the main black group to only two liberties. At this point, black gets to make the other cut, which leads to a ladder of $n$ forcing moves with black playing Atari on the white group at each step in the ladder. Ultimately, however, the ladder was hopeless, because it is broken by the isolated white stones. When this happens, the white stones in the ladder will get three liberties, which is not enough, since at this point white will make Atari on the main black group and then capture it, as black has no response. Note that after the ladder is broken, further hopeless cuts on other knobs are now truly hopeless, since white can answer them by capturing the main group.
In summary, white will eventually kill the main black group in finitely many moves, but black can choose any $n$ and play so as to postpone her loss of that group for at least $n$ steps. So the life-and-death of that group has game value $\omega$.
I believe that one could hope to modify the position to achieve much larger game values in Go. One could also modify the example by making the main black group much larger, so that it has asymptotic density 3/4, say, which would find tranfinite game values in the asymptotic density area calculation formulation of the game.
Update. Let me explain how to modify the position to achieve game value $\omega\cdot n$ for any finite $n$. What we do is give the main black group $n+2$ liberties, instead of only 3, and then also make the ladder-blocking white stone a live group. In addition, we can add a diagonal of white stones parallel to the ladder, just to ensure that black has no advantage to deviating from the main line.
With these revisions, black will be able to make $n$ hopeless cuts in succession, each leading to a ladder of length $n$ before the next begins, giving the game value $\omega\cdot n$ overall. Black may make $n$ announcements in all, with each being the length of play before the next announcement, until he loses his group at the end.
I'll try to post an image later. Next challenge: $\omega^2$.