Checkmate in $\omega$ moves?

Question

Is there a chess position with a finite number of pieces on the infinite chess board $\mathbb{Z}^2$ such that White to move has a forced win, but Black can stave off mate for at least $n$ moves for every $n$?

This question is motivated by a question posed here a few months ago by Richard Stanley. He asked whether chess with finitely many pieces on $\mathbb{Z}^2$ is decidable.

A compactness observation is that if Black has only short-range pieces (no bishops, rooks or queens), then the statement "White can force mate" is equivalent to "There is some $n$ such that White can force mate in at most $n$ moves".

This probably won't lead to an answer to Stanley's question, because even if there are only short-range pieces, there is no general reason the game should be decidable. It is well-known that a finite automaton with a finite number of "counters" can emulate a Turing machine, and there seems to be no obvious reason why such an automaton could not be emulated by a chess problem, even if we allow only knights and the two kings.

But it might still be of interest to have an explicit counterexample to the idea that being able to force a win means being able to do so in some specified number of moves. Such an example must involve a long-range piece for the losing side, and one idea is that Black has to move a rook (or bishop) out of the way to make room for their king, after which White forces Black's king towards the rook with a series of checks, finally mating thanks to the rook blocking a square for the king.

If there are such examples, we can go on and define "mate in $\alpha$" for an arbitrary ordinal $\alpha$. To say that White has a forced mate in $\alpha$ means that White has a move such that after any response by Black, White has a forced mate in $\beta$ for some $\beta<\alpha$.

For instance, mate in $\omega$ means that after Black's first move, White is able to force mate in $n$ for some finite $n$, while mate in $\omega\cdot 2 + 3$ means that after Black's fourth move, White will be able to specify how many more moves it will take until they can specify how long it will take to mate.

With this definition, we can ask exactly how long-winded the solution to a chess problem can be:

What is the smallest ordinal $\gamma$ such that having a forced mate implies having a forced mate in $\alpha$ for some $\alpha<\gamma$?

Obviously $\gamma$ is infinite, and since there are only countably many positions, $\gamma$ must be countable. Can anyone give better bounds?

Answer 1

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.

Answer 2

Update. (Oct 28, 2015) See below, for a position with game value $\omega^4$.

---

This is a great question, which I have been pondering for some time.

I have just completed a joint article Transfinite game values in infinite chess with C. D. A. Evans, which describes several new positions exhibiting high transfinite game values in infinite chess. (Follow the link through to the arxiv for a pdf preprint.)

Because we found interesting positions with infinitely many pieces, we took the liberty of abandoning the finiteness requirement of the original question, considering the finite positions merely as a special case.

C. D. A. Evans and Joel David Hamkins, Transfinite game values in infinite chess, under review.

Abstract. We investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these values---the omega one of chess---denoted by $\omega_1^{\mathfrak{Ch}}$ in the context of finite positions and by $\omega_1^{\mathfrak{Ch}_{\hskip-1.5ex{\ \atop\sim}}}$ in the context of all positions, including those with infinitely many pieces. For lower bounds, we present specific positions with transfinite game values of $\omega$, $\omega^2$, $\omega^2\cdot k$ and $\omega^3$. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true $\omega_1$.

The paper has 38 pages and 18 figures, detailing several positions. We also included an elementary discussion of the game-theoretic meaning of the smallish ordinal games values, such as $\omega^2$ and $\omega^3$.

Let's display here a few of the positions.

First, a simple position with value $\omega$. The main line of play here calls for black to move his center rook up to arbitrary height, and then white slowly rolls the king into the rook for checkmate. For example, 1...Re10 2.Rf5+ Ke6 3.Qd5+ Ke7 4.Rf7+ Ke8 5.Qd7+ Ke9 6.Rf9#. By playing the rook higher on the first move, black can force this main line of play have any desired finite length. We have further variations with more black rooks and a white king.

Next, consider an infinite position with value $\omega^2$. One should imagine here that the wall of pawns continues infinitely upward and downward. The central black rook, currently attacked by a pawn, may be moved up by black arbitrarily high, where it will be captured by a white pawn, which opens a hole in the pawn column. White may systematically advance pawns below this hole in order eventually to free up the pieces at the bottom that release the mating material. But with each white pawn advance, black embarks on an arbitrarily long round of harassing checks on the white king.

Here is a similar position with value $\omega^2$, which we call, "releasing the hordes", since white aims ultimately to open the portcullis and release the queens into the mating chamber at right. The black rook ascends to arbitrary height, and white aims to advance pawns, but black embarks on arbitrarily long harassing check campaigns to delay each white pawn advance.

Next, by iterating this idea, we produce a position with value $\omega^2\cdot 4$. We have in effect a series of four such rook towers, where each one must be completed before the next is activated, using the "lock and key" concept explained in the paper.

We can arrange the towers so that black may in effect choose how many rook towers come into play, and thus he can play to a position with value $\omega^2\cdot k$ for any desired $k$, making the position overall have value $\omega^3$.

Please see the article for further explanation of these positions and others.

Another interesting thing we noticed is that there is a computable position in infinite chess, such that in the category of computable play, it is a win for white---white has a computable strategy defeating any computable strategy of black---but in the category of arbitrary play, both players have a drawing strategy. Thus, our judgment of whether a position is a win or a draw depends on whether we insist that players play according to a deterministic computable procedure or not.

The basic idea for this is to have a computable tree with no computable infinite branch. When black plays computably, he will inevitably be trapped in a dead-end.

In the paper, we conjecture that the omega one of chess is as large as it can possibly be, namely, the Church-Kleene ordinal $\omega_1^{CK}$ in the context of finite positions, and true $\omega_1$ in the context of all positions.

We had an idea for proving this conjecture, but unfortunately, it does not quite fit into two-dimensional chess geometry. But we were able to make the idea work in infinite three-dimensional chess. In the last section of the article, we prove:

Theorem. Every countable ordinal arises as the game value of an infinite position of infinite three-dimensional chess. Thus, the omega one of infinite three dimensional chess is as large as it could possibly be, true $\omega_1$.

Here is one component of the three-dimension position, used to allow white to force the black king from one layer to a higher layer. Imagine the layers stacked atop each other, with $\alpha$ at the bottom and further layers below and above. The black king had entered at $\alpha$e4, was checked from below and has just moved to $\beta$e5. Pushing a pawn with check, white continues with 1.$\alpha$e4+ K$\gamma$e6 2.$\beta$e5+ K$\delta$e7 3.$\gamma$e6+ K$\epsilon$e8 4.$\delta$e7+, forcing black to climb the stairs (the pawn advance 1.$\alpha$e4+ was protected by a corresponding pawn below, since black had just been checked at $\alpha$e4).

The argument works in higher dimensional chess, as well as three-dimensional chess that has only finite extent in the third dimension $\mathbb{Z}\times\mathbb{Z}\times k$, for $k$ above 25 or so.

My co-author Cory Evans holds the chess title of U.S. National Master.

---

Update. In new joint work, we've found a position with game value $\omega^4$.

• C. D. A. Evans, J. D. Hamkins, and N. L. Perlmutter, A position in infinite chess with game value $\omega^4$.

In this position, the kings sit facing each other in the throne room, an uneasy détente, while white makes steady progress in the rook towers. Meanwhile, at every step black, doomed, mounts increasingly desperate bouts of long forced play using the bishop cannon battery, with bishops flying with force out of the cannons, and then each making a long series of forced-reply moves in the terminal gateways. Ultimately, white wins with value $\omega^4$.

The position is fully explained in the article (click through to the arxiv for the pdf).

Answer 3

Thanks to Richard Stanley and Kevin Buzzard for independently drawing my attention to this thread.

Such constructions are often easier on a half- or quarter-infinite board: the board edges are useful and also let us adapt more patterns known from the orthodox $8 \times 8$ game. I'll show that a known theoretical position with only two men on each side becomes a "checkmate in $\omega$" on a quarter-infinite board. I'll also show for each natural number $N$ two routes to "checkmate in $N\omega$" on a half-infinite board. I think one of them should adapt with some more work to chess on the edgeless square lattice.

On an infinite board even K+Q vs. K is not sufficient mating material against a lone King, while on a quarter-infinite board it is well known that K+R still suffice, with a mate of bounded length given the positions of the Kings (I think this is even in Winning Ways). Since mate in $\omega$ also requires Black to have a long-range piece, the minimum conceivable material is K+R vs. K+B. I claim that this is sufficient!

In the orthodox game K+R vs. K+B is usually an easy draw, but there are some known nontrivial wins. One standard example is Kb3,Rc2 / Kb1,Bc1. I claim that if we set this up on a quarter-infinite board with Black to move then White forces checkmate in $\omega$ moves.

White's winning plan is to play something like Rh2, Rh1, and then a waiting move like Rf1 to force Black to play Ka1 when Rxc1 is mate. (That's why this wouldn't work shifted one square left.) On the $8 \times 8$ board Black can postpone this for only a few moves. For example, if Bf4 then Rf2 and if Black saves the Bishop then Rf1 etc. (best is Kc1 but we know that after Rxf4 White wins in $O(1)$ moves). Black does better with Bg5, so after Rg2 Black can play Be3 to prevent Rg1; but White continues with Re2 and next move either takes the Bishop or initiates the mating pattern with Re1. Note that if White went to a "random" spot on the second row Black would escape with Kc1; that's why it's important to move to the file the Bishop is on.

I observed some years ago that on an $n \times n$ board the same position is checkmate in $\log_2(n) + O(1)$ moves, which seems to be the maximum for K+R against K+B. For example, with at least 11 columns and 9 rows, Black could hold on to his Bishop for an extra move by starting Bk9, so that Rk2 can be answered with Bg5 holding k1. But then Rg2 reduces to a previously solved problem. On our larger board Black can answer with either Be3 or Bi3, but Re2/Bi2 etc. wins as before. To survive one more move than that, Black would have to start by moving the Bishop 16 squares out, etc.; in general if Black moves to row $k+1$ then White checkmates in $v_2(k)+O(1)$ moves (where $v_2$ is the 2-adic valuation). So on a quarter-infinite board we get checkmate in $\omega$ as claimed. With some more effort (and a lot of added passive pieces) I think one can make this work on the edgeless board by contriving an artificial corner around a1.

EDIT See my subsequent answer for a variant of this position with K+R vs. K+B+P on a quarter-infinite board thats mate in $2\omega$, and might be extended to $3\omega$, $4\omega$, etc. with more pawns. TIDE

(I think the theoretical position Kc3,Qd1/Ka2,Rb2 is likewise a White win in $\log_2(n) + O(1)$ on an $n \times n$ board, and thus in $\omega$ on a quarter-infinite board, but the analysis is harder and it might be harder to adapt to an edgeless board.)

To get checkmate in $N\omega$ for arbitrarily large $N$ on a half-infinite board, set up something like the following, suggested by K.Buzzard's e-mail. I assume the board edge is horizontal, but much the same works with a vertical edge. Give Black Ka3 and Rb2 and White Ka1 plus a few Queens and about 3N pawns: use the pawns to fill a rectangle of 3 columns and about $N$ rows starting somewhere above the third row, and in the middle column replace each of (say) the second, third, and fourth pawns with a Queen. White will win after moving $N + O(1)$ pawns in one of the outer columns, after which the bottled-up Queens escape and finish Black off. After each pawn move, Black gets to move his Rook arbitrarily far along the second row, threatening mate; White will have to move his King one step at a time, pursued by Black's, until reaching the Rook to get a "tempo" for the next pawn move: 1...Rz2 2 Kb1 Kb3 3 Kd1 Kd3 4 Ke1 Ke3 ... Ky1 Ky3 and now another pawn move.

I don't know how to adapt this construction to an edgeless board. So here's another approach. By the vertical edge of the board, set up a position with the Black King and some White and Black pawns, none of which can move except for one White pawn that will give checkmate in $N$ moves. Surround this with a Black shell of pieces surrounded by pawns that the White King cannot penetrate and that cannot unravel within $N$ moves to either escape or stop the mate. Outside that shell put the White King and a Black Rook. $N$ times Black will choose how far out to play the Rook to harass the White King with horizontal checks.

EDIT See below for an explicit construction of mate in $N\omega$ with a fixed number of pieces on a ${\bf Z}^2$ board. TIDE

This doesn't work as it stands on an edgeless board because the White King can hide around the shell in $O(1)$ moves rather than go after the Rook. But I think something similar should succeed, using a protected but pinned Black rook to substitute for the vertical edge.

NDE

Answer 4

Here's an example on the edgeless ${\bf Z}^2$ board that shows "mate in $3\omega$ moves" and, I think, can be extended to arbitrarily large multiples $N\omega$ by moving the outlying Knight about $N/2$ squares to the left. FEN = 14/5p4/5Pp3/4p1B1p1/N3p1Prrp/2p1p1prkp/2p1p1prpp/2PpN1B1np/3P1B3p/4P4p/9p/9p/9Pr/11K/1:

_{(source: harvard.edu)}

Black to move. White will play Na11-b13-c11/d12, then capture the pawn on e10 (four squares left of the Black King), and checkmate with N(either)xg9+, Nxg9; Nxg9 exploiting the pin on the Rook at h9. Black gets three chances to move the Rook arbitrarily far to the right and harass the White King with horizontal checks until the King reaches the Rook.

Other Black defenses are no better, as long as White takes care not to move the King to one of the few squares where it could be checked with a move of the Black Knight. If that Knight moves without giving check then Nxg9 is mate immediately (which in turn means the White Knight on e7 must not move, else Black can unwind by moving the Knight, pushing the pawn to its square, and escaping with the King). None of the other Black pieces have a legal move except the Rook now on k3 (near the White King). If that Rook captures a pawn, White retakes with a pawn or Bishop and Black must soon move the Knight and get mated. Likewise after ...RxBf7; Pxf7, or ...RxBg8; Bxg8, or ...Rh12 (attacking Bg11); Pxh12. Finally if Black moves the Rook up and around to the d-file to answer Nc11 with Rd10 then White plays a random "waiting" move with his King and Black must move the Rook and allow Nxe10 and mate in two more moves.

Except for the Rook captures of the previous paragraph, White in turn must not move any piece except the King, the roving Knight, and possibly the Bf7 which must still be ready to return to f7 to defend the Bg8 and block the Rook's path to f8-f11. For example, after ...RxBf7 White must not play Bxf7? lest Black escape with ...g8; Bxg8, g9, followed by Rf10 (or g10), Kh10, etc.

To construct larger multiples of $\omega$, move the Knight from a11 far enough to the left. Black still has nothing better than to delay the King with horizontal checks. For instance, if Black could answer Nb13 with Rc12/d11 then White would play a random King move to force the Rook to relinquish its control over either c11 or d12 so the Knight could advance further. I think the Knight has enough freedom to reach its goal with the assistance of such waiting moves no matter what the Rook does. But if I'm wrong then a cavalry of $O(1)$ Knights would certainly suffice.

Answer 5

Dropping the assumption of finitely many pieces as in this answer, we construct for any countable ordinal $\alpha$ a position having mate in $\beta > \alpha$, so $\gamma = \omega_1$ in the context of positions with infinitely many pieces.

Our strategy to prove this is the same as the one used for 3-dimensional chess by Joel David Hamkins and C. D. A. Evans in their paper Transfinite Game Values in Infinite Chess. As in their paper, for a tree $T$ on $\omega$ (Meaning $T \subseteq \omega^{<\omega}$ and any initial segment of an element of $T$ is also in $T$) define the Climbing-through-$T$ game as follows. White's only role is to watch. Black begins on the root node of the tree. At any stage of the game, black is on a node of $T$, and selects an immediate successor to move to. Black loses if and only if they move to a leaf node. It is clear White wins Climbing-through-$T$ if and only if $T$ is well-founded, and that in this case the game value of Climbing-through-$T$ is the same as the ordinal rank of $T$. As such trees of arbitrarily large countable ordinal rank exist, if for all trees $T$ on $\omega$ we can embed a game equivalent to Climbing-through-$T$ into infinite chess, we will have proven $\gamma = \omega_1$.

In the positions we construct, Black's king is imprisoned in the White court

Black is in local zugzwang - currently white cannot give mate, but if black is ever reduced to no moves outside the court, then they will be forced to take on d8 and will be promptly mated after 1... Kxd8 2. Rc8+ Kd9 3. Rd8+ Kxd8 4. Qc8#. This will determine both player's play as black desperately tries to achieve an infinite source of moves, while white's only winning plan is to prevent this.

We now begin the construction of the Climbing-through-$T$ game, beginning with analysis of a local position which will act like a node of our tree. The box from b2-f6 is simply to initialize the position, and will be empty for generic nodes.

In the above position, we assume the court is somewhere far below and that otherwise Black's only legal moves are with the bishop on e5. Thus, if Black moves this bishop to somewhere unprotected, White will simply capture it, leaving black with no option but to checkmate themself within the court. Therefore, Black's only reasonable option shown is the indicated Bn14 (In the final position, there will be more protected squares further along the infinite a1-w23 diagonal). Black now has the potent threat of Bo13, escaping the eyes of the d4 bishop in order to eventually leave along the a5-s23 or a7-q23 diagonals, after which white can never hunt down the bishop on an open board. Thus white is forced to play Bxn14, allowing mxn14.

At this point, black plans to move the n14 pawn down to take o6, then push the o pawns, eventually freeing the p10 bishop to escape via o9 (Other options for black will result in play ending in finite time if white just plays waiting moves). White therefore must play to free their v2 bishop by pushing the u pawns, as the only other local options simply speed up blacks plan and allows the p10 bishop to escape to the wilderness.

We thus arrive at the following position with the last move having been u4 and black in a situation very similar to that which we began in. The local position leaves no pawn moves for black, and Black's only hope to prolong play more than a few moves is to move the o9 bishop to some space along the infinite w1-a23 diagonal. White's v2 bishop will then snatch it, potentially starting this process again.

We now indicate how to build Climbing-through-$T$ . Easiest is to first build a tree $\mathcal T$ where at every node black is faced with countably many choices. Above is the start of our embedding of $\mathcal T$ with two full nodes in view, together with White's court. Note the crucial fact that the court has been placed such that no white piece outside it (All pawns and bishops of a single color) can take the black pawns holding it in place, so White's only plan is indeed the zugzwang idea. Below is a more zoomed out view, in order to give a better idea of the structure. To describe the specific positions of all the nodes, label the green diagonal $R_0$ and the yellow diagonals parallel to it $R_n$, and the yellow diagonals in the other direction $L_n, n \in \mathbb Z^+$. Then we build nodes on the intersections of certain diagonals, so that $R_n$ exits onto $\{L_m | m \equiv 2^n \pmod {2^{n+1}}\}$ and $L_n$ exits onto $\{R_m | m \equiv 2^{n-1} \pmod {2^{n}}\}$. One checks that this indeed is a tree, and is isomorphic to $\mathcal T$ as every node has countably infinite many children.

Play now proceeds as in the Climbing-through-$\mathcal T$ game. In the main line, Black begins by moving their single mobile bishop along the green diagonal to one of the infinitely many protected squares along the diagonal indicated in red, choosing the next diagonal play will occur on. Our earlier analysis then applies (We confirm that Black's bishops can still easily escape outside the tree if white ever deviates), and will result in Black eventually moving a bishop along the yellow diagonal emerging from black's chosen node, selecting a new diagonal from infinitely many choices and beginning the process again.

As every tree $T$ on $\omega$ is isomorphic to a subtree of $\mathcal T$, it is clear that in order to build Climbing-through-$T$ , all we must do is not build those nodes in $\mathcal T$ but not $T$, so any countable ordinal can indeed be achieved.

Answer 6

alt text http://www.freeimagehosting.net/uploads/d2ac857a24.jpg

Here is another one, hopefully it fits on one(!) board with no more modifiers. White (in check) plays Kh3xQg3, and Black threatened by Rxb7#, moves the Rf4 arbitrarily far to the east, uncovering check from the Bd6. White just takes the bishop (any way), and Black has no defense but to keep on checking White horizontally with the eastern rook, with the White king heading east until it (finally!) attacks the rook, when then White will win via Rxb7.

Notes: White has no other way to avoid the annoying rook checks, for the self-guarding Black rooks on the e-file prevent king movement to the west, and no interposes are possible by geometry. White's king can simply move east on ranks 2 and 3, but it doesn't matter too much. Black's moving the rook north on move 1 (when uncovering the bishop check) is not effective, for then White can interpose a rook on future vertical checks. The double check Rg4+ on Black's move 1 is also easily defeated by capturing that rook with the king. The only loose end is then whether by White's 1. Ki2 (not taking the queen) a faster checkmate is possible. The answer is no, for White doesn't even win, for Black can check forever with the queen on the g-file, the White king restricted to rank 3 and below.

Unless there is something missing, this seems to work also.

Answer 7

Since you were nice enough to ask for any bounds on $\gamma$ better than countable: $\gamma$ is a recursive ordinal, because the game tree, starting from any finite position, is recursive.

Correction: As pointed out by Joel David Hamkins in the comments (see also my subsequent comment), the recursiveness of the game tree implies only that, for every position $p$ from which White has a forced win, there is a recursive ordinal $\alpha$ such that White wins in $\alpha$. A uniform bound $\gamma$ that works for all such $p$ simultaneously would thus be the first non-recursive ordinal $\omega_1^{CK}$.

Answer 8

Introducing a position of game value ω² with finitely many pieces

In the following position with finitely many pieces, White has mate-in-ω² (Black to move): (For convenience, I put the position into a public Google spreadsheet so that everyone can browse it at their own leisure or copy the sheet to edit it. Alternatively, click on the pictures in this post if you want to expand them or here for a high-res image of the full position.)

The basic idea of the position is that Black will lure away the White Queen to the left by an arbitrary number of moves in the beginning. The position is constructed in such a way that

• White can never move his Queen back in a straight line because he has to keep answering constant threats by Black in very specific ways. Instead, the Queen has to be moved back very slowly in a zig-zag line, 18 squares at a time, in order to keep answering the threats. White will win only when the Queen has traveled back near the rest of the pieces.

• Inbetween every second Queen move by White, Black can move his Rook arbitrarily far away from the White King and proceed to continuously check him in such a way that White's only resort is chasing down the Black Rook with his King.

In total, these two factors lead to a game value of ω², because Black can choose in the very beginning how often he can play the check-the-White-King-from-afar game.

Overview of the five components of the position

Now let us proceed by introducing the components of the position:

Component A is the fortress of the Black King. White has pinned two Rooks to the Black King and almost every single Black piece is completely blocked. Black can freely move exactly two pieces in the entire position during the game: his one active Rook on Aac27 and his pawn on Aac2, which exists solely to prevent stalemate & zugzwang and has no further significance. (Note: I put the letter A in front of the file letter in order to unambiguously specify that I am describing the coordinates of component A.) The Black Rook cannot threaten the White Bishops in any way or disentangle his position.

There are a few noteworthy observations about this fortress: First, the White King's movement is restricted to the top right quadrant of the board by the pinned Black Rooks. Thus, if Black were to move his free Rook north and start giving checks, then White would be unable to hide his King - he would be forced to move his King north to meet the Black Rook and push it away. Secondly, White can checkmate the Black King by capturing the highlighted Black pawn on At11 with his Queen (which is the only White piece that can freely move around the entire board, as we shall see). The numbers in the position show the path that the Queen has to take through the twisting corridor in order to reach the checkmate square: If the White Queen starts from immediately outside the corridor on the red highlighted square marked with an X (Ae17), or any other outside square on the entrance diagonal, then she will need 7 moves to checkmate Black. Keep this number in mind as the game will critically depend on every single tempo. Finally, note that the entrance diagonal into the corridor is quite obstructed - the pawn wall to the left as well as the Northern and Southern Barriers completely block off any immediate access from the West or from the vertical files Ab through Af into the corridor.

Component B serves two functions: First, it serves the initialization of the free White Queen. We will see later that the optimal first move by Black is to move his queen as many squares as possible to the left - let's say N squares - which will lead to a position of a game value of ω⋅O(N). We will also see later that White is forced to immediately capture the Black Queen after that in order to prevent perpetual check onto his overly exposed King. After the first move, this Component is effectively frozen and will never be revisited under optimal play. The second important function of Component B is that it acts as a barrier that blocks files Ab through Af: no piece can directly move onto the entrance diagonal in Component A by moving vertically down from North.

Component C serves two functions as well: First, it is the Southern Barrier and blocks files Ab through Af from below. Secondly, it can be viewed as a ticking time bomb that Black needs to worry about. The White pawn on Cc2 can slowly move up the Cc file and capture the Black pawn on Cd17, which will allow White to slowly move up the pawn column on file Cd and release his trapped Queen on Ce3. However, this threat is very slow and White needs 30 tempi in total to release the White Queen with no way to speed this procedure up. This mechanism is significantly slower than any other threat in the position and exists solely to punish Black for sacrificing his Rook or trading it for the White Queen. Thus, this Component gives White the alternative win condition of successfully trading his Queen for the Black Rook, since Black would have no further way of preventing the inevitable release of the second White Queen. Under typical play, this Component will remain frozen for the entire game since it is far too slow. (Also note that if White ever sacrifices his Queen without compensation for some reason, Black can permanently defuse Component C after the c2 pawn has advanced 5 squares by parking his Rook on Cd6.)

Component D is a large defensive formation in which almost all pieces are frozen in place. Black has several trapped Queens on the right and White has to utilize this defensive formation in order to stop Black from liberating his Queens. (Recall that the White King is completely exposed on the top right quadrant of the board and that a roaming Black Queen will lead to draw by perpetual checks.) The Black Rook can attempt to make an incursion into the formation in order to free his Queens by moving onto the files Dm and Dq from above or Dl and Dp from below, thus threatening to move onto the red marked entrance squares with the Roman numerals I through IV (and the secondary incursion squares Iβ and IVβ). Supposing, for example, that the Black Rook is somewhere far away on the top right of the infinite chessboard (let's pick Dy45 as an example), then he can free a Black Queen with the moves 1...RDq45, 2...RDq26, 3...RxDw26, 4...RDq26, 5...Dw26, 6...Dw27, 7...QDv27, 8...QDv31 or QDv35 or QDv39, 9...Black Queen checks the White King. Thus, a Black Rook in the North or South of the chessboard always threatens perpetual-in-9-moves, pending a successful incursion onto the squares with the Roman numerals.

Now let's examine how White can answer this threat: The White Knight on Do16 (marked in orange) can defend the incursion squares II and III by jumping between the two orange squares Do16 and Dp18. Other than that function, this Knight has no freedom of movement. The White Queen can defend the incursion squares I and IV (as well as Iβ and IVβ) from afar by moving between the rows D8 and D26. Note that this suffices as a defense despite the incursion squares I and IV being defended by Black pawns, since a trade of the Queen for the Rook is a victory condition for White, as discussed above (Black can only move pawns to no effect while White slowly releases his Queen in Component C). Finally, the four White pawns on Dg7, Dh7, Dh25, Di25 (marked in blue) have the sole function of preventing an incursion by the Black Rook from the West. For instance, if the Black Rook moves to Da8, then White can defend the incursion with Dg8. Other than that function, these White pawns can make no further progress.

Note that Black is theoretically free to move the pawns on Dq9 and Dr27 forward by one square. However, this move is useless since the pawns are blocked after that move and will have achieved nothing but permanently blocking the rows D8 and D26 for Black, thus removing the threat of the incursion squares I (and Iβ) as well as IV (and IVβ).

We are now ready for an important observation: During the game, the White Queen will mostly zig-zag between rows D8 and D26 to answer threats, as we will see later. If the White Queen is very far away on the left of the board on one of these two rows, then it can reach the entrance diagonal of the Black King's Fortress (e.g. square Ae17) in 3 moves. (This is due to Components B and C acting as barriers. Look at the entire board configuration in order to convince yourself of this fact.) Recalling our analysis of the corridor, White thus threatens checkmate-in-10 assuming no Black counterplay. This is a tempo disadvantage for White: he needs 10 moves to checkmate but Black can typically start giving perpetual check in 9 moves if the White Queen abandons its defensive post! However, this situation drastically changes, once the White Queen has approached the position and is within 22 squares to the left of the file Da. Then the White Queen can move diagonally onto the files Ac through Af between the two barriers and reach the entrance diagonal one move faster. Thus, White's approach is rewarded with a tempo, yielding a checkmate-in-9 threat!

Finally, Component E is a defensive formation guarded by a lonely undefended White Bishop, the only moving piece in the position, which guards the marked pawn on Ez8, which controls a trapped Black Queen. In the position pictured above, assume that the Black Rook is on the square En26 threatening the White Bishop on En20. Assuming that White does not answer the threat, Black will free the Queen by playing 1...RxEn20 2...REn1 3...REaf1 4...REaf8 5...RxEab8 6...RxEz8 7...QEy9 8...QEs15 or QEn20 9...Black Queen checks the White King, i.e. Black again threatens perpetual-in-9. Thus, White is best advised to move his Bishop out of the way. The movement of the Bishop is quite restricted, in fact it can only ever visit the three unguarded squares marked in green: Ef12, En20 and Er16 (the latter two squares have a view of the important pawn). In the situation from before with the Black Rook on En26, the White Bishop should move to the right, i.e. BEr16, because moving to the left would simply result in a repetition of moves, i.e. 1.BEf12 REf26 2.BEn20 REn26, since the left green square can only be attacked from the North while the right green square can only be attacked from the South. Thus, conversely, if Black were to threaten the White Bishop from below, then the White Bishop has to move away to the left under cover, since any capture of the Bishop on any of the three green squares results in perpetual-in-9.

If the White Bishop ever sacrifices itself by going on any other square than the three green squares, then it can be immediately captured by a Black pawn or Knight. White to move will now typically have a mate-in-10 threat, as discussed above, while Black threatens (at worst) perpetual-in-9 via 1...REaf1 2...REaf8 3...RxEab8 4...RxEz8 5...Black Rook goes to the far right 6...QEy9 7...QEz8 8...Black Queen goes to the far right 9...Black Queen checks the White King.

Note that other than that, the position in this component is completely frozen. Any movement by the Black Knight on Ei12 is completely pointless - the Knight exists only in order to guard a few squares from the White Bishop. Moving the Knight to Eg13 or Ej14 results in immediate capture by a pawn or Bishop, if available, and the White Bishop gains a safe square on Eh14. Moving the knight to Eh14 can either be answered by capturing it with the Bishop or, in case the White Bishop is on Er16, it can be safely ignored until it is captured by the Bishop in the future, since all further moves of the Black Knight to Ef13, Ef15, Ej13, Eg16 or Ei16 can be answered by pawn captures. Thus, Black strictly improves White's position by moving the Knight.

In short, Component E is simply a switch that enables the Black Rook to move from the North of the position to the South and vice versa without losing any tempi to White.

The opening move

What will happen in the beginning of the game? Let's examine the possible moves by Black and the best answers by White:

• Black moves his free Rook anywhere. At best, Black now threatens perpetual-in-9 by one of the methods described above. White captures the Black Queen with Bfxe5 and threatens mate-in-8 because the White Queen is already in the line of sight of the entrance diagonal. White wins almost immediately.

• The Black Queen captures any pawn. White can capture it back and threatens mate-in-9 because the Queen can reach the entrance diagonal in two moves. Black to move does not threaten perpetual-in-9 yet. White wins almost immediately.

• The Black Queen captures the White Queen. White answers with Bgxf5. White threatens mate-in-9 with its newly liberated Queen. Black to move does not threaten perpetual-in-9 yet. White wins almost immediately.

• The Black Queen moves far West. The Black Queen threatens perpetual-in-1. White has no choice but to capture it and, thus, move his Queen far away. Black then moves his Rook up an arbitrary number of squares and threatens perpetual-in-9 in Component D. (Making a threat in Component E and crossing it does not work just yet, as we will see below, because the White Knight in Component D is in the bottom orange square.) White cannot checkmate in 9 moves by moving the Queen back and, thus, he has to answer the threat by defending it with his Queen and Knight after Black moves to file Do. (We will see below which responses for White work and which do not.)

Let us now see how a typical sequence of moves in the bulk of the game looks like:

A typical game sequence

Assume the position above with the Black Rook on α, the White Queen on Q4, the defending White Knight on the upper orange square and the defending White Bishop on the left green square. White has just defended the Black incursion from the file Do and the Black Rook needs to make a new threat - since he does not threaten perpetual-in-9 (Thus, Black passing the turn would allow White to immediately move his Queen to the right and threaten mate-in-9). Black moves to square β΄ and threatens the White Bishop. The White Bishop has to move to the central green square. Black moves to square β and the White Bishop moves the right green square. The Black Rook cannot threaten the Bishop anymore and moves his Rook to square γ (Any move in another direction would just waste a tempo). Now Black threatens an incursion from the file Dn in two moves and White (needing at least two moves to defend this threat) thus moves his Queen to square Q3. Black proceeds by moving his Rook to the square δ, which White has to answer by moving his knight to the lower orange square - White has defended the threat just in time. Now Black moves his Rook to γ΄, the White Bishop has to run to the central green square, Black responds by moving to γ, White moves his Bishop to the left green square, and then, finally the Black Rook moves up in the direction of square β, to which White responds by moving his Queen to Q2. Here, the transfinite ω has come into play! Namely, the "new" square β can be as arbitrarily far North from the White King as Black wishes! Now Black can start giving checks to the White King from above and the White King is forced to approach the Black Rook - this might take many moves. Before the White King reaches the Black Rook, Black moves his Rook to square α and White has to move his Knight to the upper orange square in defense - he has just made it in time again. This closes the loop and the position is exactly the same as before, except that the White Queen is now on Q2 instead of Q4, i.e. it has moved 36 squares to the right in "ω+8" moves. This loop continues until the White Queen reaches Q1, which is sufficiently near to the Barriers in order to allow the White Queen to dip between the two Barriers, which improves White's imminent threat from mate-in-10 to mate-in-9. As soon as the next position is reached where Black only threatens perpetual-in-9, White can ignore the threat and proceed to checkmate Black.

Strategic summary of the main line

After the first move, White and Black find themselves in a constant battle of tempi. White is threatening mate-in-10 (assuming no black counterplay) for the entire duration of the game. This forces Black to only make threats that are faster than 10 moves. Black can indeed quite successfully keep playing for a very long time in such a way that his every single move both threatens perpetual-in-9 and forces an immediate response by White to prevent this. Neither can Black ever find a strategy that breaks through the defense of White nor can White immediately force a position of mate-in-9 which would be fast enough to beat Black - that is until the White Queen is within ~22 squares of Component D, when the balance turns in favor of White and he does in fact reach a position of mate-in-9, which ends the game. It turns out that this best defense by Black has a game value of exactly ω².

Remarks, deviations from the strategy above and their refutations

• If Black manages to ever successfully release a Black Queen and start checking the White King, then White has no way of winning anymore. Not even a Queen trade and Component C can still salvage the position, since Component C is easily disarmed by a Black Rook, as stated above.

• Black gains no advantage by threatening the secondary incursion squares Iβ and IVβ (Dl8 and Dm26) since this threat is strictly weaker than the threats on the files Dp and Dq.

• If Black ever moves his Rook to the far left or far right, then White can immediately move his Queen right to Component D in a straight line because such a move by Black is no threat. The blue-colored pawns in Component D prevent any incursion from the left in a single move, if needed - thus Black has created no new threat and just wasted a move. If Black moves his Rook onto rows D8 or D26, White defends with a blue pawn, threatens mate-in-9 and will win very shortly. Similarly, Black capturing the Eab8 pawn without having removed the defending Bishop is pointless since it wastes 3 tempi and White needs 1 tempo at most to guard the crucial Ez8 pawn with his Bishop. All in all, Black cannot ever capture any non-significant White pawn or move his Knight in Component E since this wastes too much time.

• Black cannot go through Component E twice in a row without threatening Component D, since then the White Knight would be on the same side of Component E as the Black Rook after the second time. In this case, White could use the tempo, where the Knight would normally have to move, to instead move the Queen as far right as he wants while still defending against the threat in D.

• A long horizontal move by the White Queen to the right at any point in time results in a draw because Black makes a new perpetual-in-9-threat every single move that needs to be answered, either by moving the Bishop or Knight or by changing the row of the Queen. Thus, White has wasted a critical move and cannot answer the next Black threat or incursion attempt like in the main line.

• A long diagonal move by the White Queen to the files Dp or Dq as a defense against the Black Rook having reached squares β or γ is pointless, because the Black Rook can just immediately threaten the secondary incursion squares Iβ and IVβ, and the White Queen has no choice but to revert its last move. (These secondary incursion squares exist solely for this reason.) Note that the White Queen cannot defend the secondary incursion squares from Dp8 or Dq26 since these squares are guarded by Black pawns (which exist solely for that reason). Similarly, a long vertical move by the White Queen can also be dealt with in the same way since White cannot ever prevent Black from threatening both the primary and the secondary incursion squares.

• A long diagonal move by the White Queen to the file En in order to defend the White Bishop is pointless because the Black Rook can just move back to α or δ respectively, threaten an incursion into Component D again, and force the White Queen to undo its last move.

• White cannot ever leave a threat to his Bishop in Component E unanswered because this would lead to a draw, since the White Queen cannot defend the vulnerable White pawn on Ez8. Without the defending Bishop in Component E, a Black Rook on the far right of row E8 threatens (at worst) perpetual-in-7 in Component E and perpetual-in-10 in Component D. The Black Rook is free to move North and South, making threats to Components D and E that cannot all be covered simultaneously.

• Important: The Black Rook needs to be careful to choose its distant squares α, β, γ and δ in such a way that the White Queen cannot ever interfere with the Rook diagonally. This is always possible for Black since he can move his Rook sufficiently farther away vertically than double the horizontal distance to the Queen.

• White could try to move his King in such a way that the White Queen can at some point block a check by the Black Rook from the North by moving directly in front of the King, but this only leads to a repetition of moves since Black can move his Rook back to square α and repeat his last threat. Thus, the White King actually has to hunt down the Black Rook.

• When the White Queen finally attempts to checkmate Black in the end, the White King needs to be careful to not stand on certain diagonals and files, namely those that release the Queens out of Components D and E, else Black will have a threat of perpetual-in-8. This is possible for White since he has enough freedom of movement with his King to stay away from these critical lines.

• White cannot prevent the immediate check from the Black Queen in the 9th move (after leaving a perpetual-in-9 threat unanswered) solely by moving his King to a suitable position on the top right quadrant, because both Components D and E give the respective Black Queens several exits that are spaced sufficiently far apart. (For instance, in component D, the Black Queen can choose between the squares Dv31, Dv35 and Dv39 on the move before initiating perpetual checks.) The Black Queen will always be able to threaten the undefended White King vertically or horizontally.

• The Black and White pawn to the left of Component B exist solely to prevent the White Queen moving horizontally back onto file Dq after the initial capture and Black Rook movement. (In this deviation, the Black Rook will threaten the incursion square Iβ from above and the White Queen is unable to defend it in time because of being blocked by pawns.)

Remark: This same position with the Black Rook shifted k squares to the right has a game value of ω²+k, since Black can start by giving k checks to the White King. As long as the White King is careful not to go above row A29 during this chase, the position is qualitatively the same and Black will not gain any advantage with these checks.

Disclosure: I have also posted this analysis on Chess Stack Exchange to ask for feedback and a review by chess players.

Edit: Further work has led me to revisit this position and slightly rework the Components, however without changing the idea of the position or the main line. My goal was to make the position more convincing and clear up some problematic aspects of the previous position, like unforeseen piece sacrifices and deviations from the main line.

Answer 9

Earlier I showed how to interpret a theoretical position of K+R vs. K+B as a "mate in $\omega$" on a quarter-infinite board. If I'm doing this right, it takes only an additional Black pawn on the quarter-infinite board to get $2\omega$.

Reflect the board about the diagonal, to get White Kc2, Rb3 vs. Black Ka2, Ba3, and add a Black pawn on h4:

_{(source: harvard.edu)}

Black to move. White can't go after the pawn at once, because then the Black King escapes. White's plan is to pin the Bishop on a3 as before, forcing the pawn to advance to h3, so that when the Rook attacks and captures it the Rook will also prevent the Black King's escape: eventually ...Bc5; Rb5, Bq19; Ra5+, Ba3; Ra4, h3; Rh4, B-any; Rxh3. But then Black will have a second chance to make the game arbitrarily long.

[In case you've not seen this before: the Rook doesn't need to be on the b-file for this to work -- e.g. Rxh3, Bc5; Rh5, Bb4; and now not Rh4?, Ka3 = draw, but (say) Rh8 and if Ka3 then Ra8+ still wins because the Bishop blocks its own King's escape!]

I think it should be possible to get $3\omega$, $4\omega$, etc. by adding more Black pawns on the same file or on multiple columns, though some care may be needed to get the counts right because the White Rook could eliminate more than one pawn at each iteration.

Answer 10

The white queen moves anywhere to the east, then the black rooks force the king east, back rank mate-style, until they've either skewered, pinned, or forked the queen and king. Worst case scenario, black loses 2 rooks, and can still mate. If black ever doesn't check, white will have a perpetual. Note that black can't force mate, as white's strategy can always be "go in a northerly direction to escape check."

http://www.freeimagehosting.net/t/56042.jpg

P.S. Sorry, I switched the colors.

Answer 11

I have an idea for how to get up to $\omega_1^{CK}$. Consider this position: black's king is trapped and white has a mate in one. However, white's king is trapped in a perpetual check. The only way out for the white king is to go along a specific trail, emulating a finite-state machine. Along certain points on the trail, black will need to check white by moving a queen somewhere along an infinitely long line or diagonal. There will be two black queens which are far enough from the rest of the pieces that they will be able to move freely along these lines. As the white king goes along various lines the queens will be forced to emulate a two-register Minsky Machine. Note that with two queens and an infinite chess board there will be enough space to ensure that only one queen will be able to attack the king in at any one time. For the decrement operation black must be able to force white along of two paths, one of which will be obstructed for the queen if she is beyond the '0' square, the other of which will be obstructed only for a queen at the '0' square.

So now we have a Minsky machine. Next we need a source of $\omega$-power. For this, the white king will occasionally be forced to block the line white needs to checkmate black. When white is there, black will not have any checks in one move. However, one of the queens will be in square '0', and it would have been able to force a checkmate were it in any farther square. Now black moves their queen as far back as they please and threaten to checkmate white the next move. White cannot checkmate black because the line is blocked by the white king. The only way for white to avoid checkmate is to move the white king one step further and allow black to continue their perpetual checks, with an arbitrary value on one of the registers.

The way this is currently designed has a problem: If one of the registers is 0, the other must contain the state information. Then, when the first register moves to an arbitrary value, the Minsky machine must fully make use of the values in both registers. However, two-register Minsky machines are too inflexible to do this. Luckily, by moving from lines to diagonals or vice versa, a chess queen can also divide and multiply by 2. That should be enough to adequately manipulate both registers. Another possibility is to add more queens and when multiple queens can check the king along a line, make it unstrategic for all but one of the queens to do so. This approach will also be needed to modify this strategy to work in quarter-infinite and half-infinite boards.

To completely work out this strategy it is necessary to describe in full the chess positions that will make up the trail for the king and to also describe in detail how to maneuver the queens to force them to emulate a Minsky machine. I have some idea for how this will go, but not entirely. Still, I believe this idea can work.

Answer 12

See On numbers and endgames: Combinatorial game theory in chess endgames by Elkies for some chess positions with non-integer values.

Answer 13

Yes there is if the finite number of pieces are large enough. But to answer your question I want black to win (because I hate it when problems most often require white to win). Let's consider the case for $N\times N$ boards and extrapolate it and then I will show how this is done for infinite boards. For a usual $8\times 8$ board there is no argument on the fact that we have mates in $1,2,\dots,7$ (and Im sure even more). I claim that for an $N\times N$ board we can have mates in $1,2,\dots,N-1$, and then I show how this is done for an infinite board.

Consider this classical mate in 7 (white to move, black mates in 6 plies, white moves maximum 7 plies) position (actually its mate in 8 if a queenside castling was allowed and we had black rook in a8 and king in e8, its funny position I always show people who never considered castling when solving such problems):

alt text http://i.harepix.com/i/389837748.jpg

Now you can reproduce the same position for an $N\times N$ board and get a mate by $N-1$ for any $N>8$. To make this work for an infinite board just surround an infinite board by black's pawn to "create" a bounded $N\times N$ board. So to make an $8\times 8$ board like the one in the diagram below. Just surround the $10\times 10$ area by Black's pawn. White's king cannot move away from the "boundary" because of the pawns. So in this way we see that we get mate in $7,8,9,\dots$ for an infinite board. For $1,2,\dots,6$ moves to mate, we do the same by only creating an $8\times 8$ board but hopefully in such a way that the "boundary" cannot be taken or moved by white (I don't think its difficult to provide the particular examples here).

My instincts tell me that this particular example can be done for any ordinal as well.