Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 his 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 $2\omega + 3$ means that after Black's fourth move, White will be able to specify how many more moves it will take until he 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?

share|improve this question
35  
If $\gamma$ could be large, this would lead to the possibility of positions where proving that White could force a mate had high consistency strength. I'd love to see that problem in the newspaper chess column: "Show that White can mate, using the existence of a measurable cardinal..." –  Henry Towsner Apr 29 '11 at 17:54
    
It seems to me that the current state of knowing sits: $N\omega$ is possible on ${1\over 4},{1\over 2}$-$\infty$ boards (Elkies), and $\omega$ is possible on the original all-infinite board ($Z^2$). But the $N\omega$ constructions start using $N$ pieces, and one suspicion is that $\omega^2$ is already not possible with finitely many pieces? –  Junkie May 3 '11 at 14:53
    
I can now get $N\omega$ on ${\bf Z}^2$ using only $O(1)$ pieces. Details coming below. So $\omega^2$ might be possible. –  Noam D. Elkies May 3 '11 at 18:39
2  
It is interesting that you write $2\omega+3$ and not $\omega 2 + 3$. –  Gerald Edgar May 4 '11 at 12:57
1  
$2x$ in ordinary algebra is read aloud as ‘$2$ times $x$’, or equivalently twice $x$, meaning literally $x + x$. The reasons for writing ordinal multiplication the other way are good reasons, but it is still backwards from the usual convention, so it's quite natural to (accidentally or on purpose) write $2\omega$ for $\omega + \omega$. –  Toby Bartels Feb 19 '13 at 7:52

11 Answers 11

up vote 54 down vote accepted

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 alt text

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.

share|improve this answer
    
Now I see there is no specific need to lock all Black pieces. It is enough that they demand some sloth in influencing play. Having them less dormant also makes it less likely White wins faster by chasing the Black king back to the pawns somehow, as White would be forced to check every move, or else be succumbed by the superior Black forces. Black can be given any number of pieces that are not able to check White in one move, and cannot reach to interpose f4/g3 on Board B in one move, and don't guard the checking mechanism. For instance, Black queen a7 on Board B, and another two west of that. –  Junkie Apr 30 '11 at 12:43
    
this could work Im convinced that the left board will help with a solution. But what if white tries to cover the g7 square in the right board? Maybe we should secure the above and below part so white cannot cover the g6 square or do d2 and and move around the board with the southeast B. If white is able to go Be9 without being taken it covers the g7 square and that would be a problem. But I think you can secure e9 and other squares here so this wont happen –  Jose Capco Apr 30 '11 at 15:30
    
I think this can be easily modified to give a perfect solution. –  domotorp Apr 30 '11 at 16:34
1  
I love the left board its just beautiful :) –  Jose Capco Apr 30 '11 at 17:12
1  
The images are no longer available at the free hosting that they were uploaded to. –  Boris Bukh Aug 30 at 0:29

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

share|improve this answer
21  
Welcome to MO, Dr. Elkies! –  Qiaochu Yuan May 1 '11 at 22:04
    
Does something like B3p3/1rp1P3/prk1P3/prp1P3/B1RpP3/3P4 work for the pinned rook(s), with the White c-pawn starting N squares below the picture? Then the White King cannot ferry across the b-file, so by starting it to the east and putting half-shells around the right side, this could work. EDIT: I guess not, for the free Black rook goes to the b-file, rather than checking, and can attack the c-pawn from it. –  Junkie May 1 '11 at 22:29
    
[Comment relocated to the right thread] \\ @Q.Yuan: Thanks for the Welcome message :-) \\ @Junkie: It's close. Having two pinned Rooks on the column helps. I think I see how to make it work now, and with a bounded number of pieces independent of the multiple of $\omega$. How did you post the chess diagrams here? I could give a link like janko.at/Retros/d.php?ff=B3p3/1rp1P3/... [Use the entire FEN; Mathoverflow won't show the full URL :-(], but that's probably poor form. –  Noam D. Elkies May 3 '11 at 14:44
    
I did screencapture from an "xboard" usage, and then clicked on the Image button (6th from left) on the toolbar under Your Answer when posting here. You need to upload the images to freeimagehosting.net or some similar portal. Having bigger than 8x8 would be useful too. –  Junkie May 3 '11 at 14:58
    
Maybe pp2R3/pp1K4/pp2q3/pp1kb3/pppppppp/prprprpr/PpPpPpPp/1P1P1P1P for the $Z^2$ board, with the border patterns extended by some finite amount? White plays Rxe6, and attacks the Black bishop or checkmates, every move thereafter. Black cannot give up the bishop and still survive, if the finite extensions are elongated sufficiently. –  Junkie May 3 '11 at 16:14

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:

alt text

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.

share|improve this answer
    
Impressive! I'm unable to find a flaw in the analysis. A couple of trivial remarks, I guess you mean that we reach $N\omega$ by moving the outlying Knight about $2N$ squares to the left? And a bit later the other white knight that mustn't move is on e8, not e7. I guess the roving knight could also try to reach ... let's see ... j12, but that would be even slower. –  Johan Wästlund May 4 '11 at 8:02
1  
Thanks! And thanks for the corrections: yes, it's $N/2$ squares, not $2N$, and the Knight is on e8, not e7 (I'm not used to navigating such large boards). Is the usual protocol here to make the edit in my original answer even though it leaves your comment hanging? Yes, there's also a potential mating square at j12, though the roving Rook could stop that and still harass the White King from a distance. Better to aim for l13, from which White threatens mates at both j12 and k11; Black can stop both with Rk12, but has no waiting moves and eventually runs out of checks. [cont'd below...] –  Noam D. Elkies May 4 '11 at 18:38
    
[...due to character-count limit] But Black can stop White from playing Nl13. Still I think this back-door route is useful because it seems now that White cannot force the Nxe10xg9 mate with just one Knight if Black uses the roving Rook to control the access path. He can, however, either do that or capture the top Black pawns at f14 and g13; then the threat of Ni14 and Nh12/j12# ties Black to stopping Ni14, and then White can get back to e10 via e14 and f12 after hiding the White King on say j2. –  Noam D. Elkies May 4 '11 at 18:44

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.

alt text

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.

alt text

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.

alt text

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.

alt text

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$.

alt text

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).

alt text

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.

share|improve this answer
    
The new $\omega$ construction is neat. [For those unfamiliar with the symbol, the black triangle means Black to move.] I'm not entirely convinced it works with only three Rooks (e.g. 2 Qf5+ Kd6 3 Qxg6+ looks promising), but with a few more distant Black Rooks (or Queens!) it should be unimpeachable. $$ $$ Once you allow infinitely many men on the board, it's natural that you can go well beyond $\omega$, but it's still very nice that you can push it to the edge of computability. –  Noam D. Elkies Feb 19 '13 at 7:01
    
Thanks Noam, I'm glad you like it. We explored the line you suggested, and it doesn't seem to work. But this is indeed why we also present the positions in the paper with the extra rooks, where it is clear that white should not depart from the main line. –  Joel David Hamkins Feb 19 '13 at 11:15
    
Black can aim, you see, to sacrifice his two remaining rooks for the pawns, since Q+R versus K is a draw, as there is no checkmate position. Incidentally, another line for white might be to skewer the center black rook after it moves up, but this has similar problems. –  Joel David Hamkins Feb 19 '13 at 11:20
1  
Joel, do you have a conjecture/result for how large an ordinal can be which is a value of an infinite chess game with finitely many pieces? –  Joël Feb 19 '13 at 17:23
1  
Joël, in the paper, we conjecture that $\omega_1^{\mathfrak{Ch}}$ is the Church-Kleene ordinal $\omega_1^{CK}$, the supremum of the computable ordinals. This is far larger than $\omega^3$ and $\omega^{\omega^\omega}$ and the other specific ordinals mentioned here, and is the upper bound identified by Andreas Blass in his answer to this question. So there is an enormous gap between the known lower bounds and our conjecture. We do prove the analogue of the conjecture for infinite positions in infinite three-dimensional chess, where every countable ordinal is realized as a value. –  Joel David Hamkins Feb 19 '13 at 18:25

alt text

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.

share|improve this answer
    
Perhaps you should mention that on the Kings journey east to defeat the rook, he should stay on only the white squares, since otherwise it is conceivable that the black bishop could give check later on. –  Eric Naslund Dec 21 '11 at 9:06
    
Nice! This solution actually seems more easy to understand than the others. –  Zsbán Ambrus Apr 4 '13 at 20:01

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:

alt text

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.

share|improve this answer
    
While black does have two chances to make the game arbitrarily long, it's still a mate in $\omega$, because the sum of two arbitrarily large integers is still just an integer. –  Hurkyl Aug 19 '11 at 17:57
    
$\omega$ means something much more precise and specific than "an arbitrarily large integer". –  Noam D. Elkies Jan 5 '12 at 21:59
1  
Noam, in this and your other answers, you should write $\omega3$ and $\omega4$, rather than $3\omega$ and $4\omega$, since in the usual notation, which goes back to Cantor, we have $\omega\cdot 3=\omega+\omega+\omega$, but $3\omega=3+3+\cdots=\omega$, which is not what you mean. –  Joel David Hamkins Jan 23 '12 at 0:16

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}$.

share|improve this answer
    
Andreas, could you explain? I agree that the game tree of all possible plays from a given position is computable. But since this tree includes the bad moves as well as the good moves, it is in general not well-founded. The game value assignment would seem to require one to identify the well-founded nodes (or well-founded after having selected good moves from that position for the designated player), which would seem to have complexity $\Pi^1_1$. –  Joel David Hamkins Jan 22 '12 at 20:40
    
Joel, I think you're right. For any particular position p from which White has a forced win, there will be a recursive ordinal as I claimed, but as p varies, those ordinals could be cofinal in $\omega_1^{CK}$. As long as we're looking at the tree of moves from a particular p, there's an arithmetical monotone induction that marks the nodes where White wins, starting from the leaves and working toward the root. If White wins starting from p, that induction will eventually mark the root, and this happens at a recursive ordinal stage. –  Andreas Blass Jan 22 '12 at 22:31
    
Andreas, I'm glad to hear that you agree with my objection. But I'm not sure that your new claim completely repairs the issue. If the strategy from a won position $p$ was computable, then I would agree that the ordinal rank of the resulting game tree (where white plays according to that computable strategy) would be a computable ordinal. But perhaps the winning strategy is not computable. In general, the best upper bound I know for this problem is at the level of $\Delta^1_2$, or slightly better: it is computable by infinite time Turing machines. –  Joel David Hamkins Jan 22 '12 at 22:41
    
Joel, I don't claim that the strategy from a won position $p$ is computable, but I do claim (until I see why I shouldn't) that it is hyperarithmetic. In the tree $T$ of plays starting from $p$, inductively define sets $W_\alpha$ of nodes as follows. $W_0$ consists of those terminal nodes where White has won. For $\alpha>0$, $W_\alpha$ consists of those nodes where either it is White's move and some child is in $\bigcup_{\beta<\alpha}W_\beta$ or it is Black's move and every child is in $\bigcup_{\beta<\alpha}W_\beta$. Continue until the process stabilizes, and go to the next comment. –  Andreas Blass Jan 22 '12 at 23:03
    
After stabilization, $p$ will be in the union of the $W_\alpha$'s, because otherwise Black could win or draw or play forever by never moving into this union. The $W_\alpha$'s are the stages of an arithmetical, monotone, inductive definition (or they would be if I had remembered to put the elements of $W_0$ into all the later $W_\alpha$'s). Such an induction stabilizes in at most $\omega_1^{CK}$ steps, and any particular element that enters the $W_\alpha$'s does so at a stage $\alpha<\omega_1^{CK}$. In particular the root $p$ enters before stage `$\omega_1^{CK}$. Go to next comment. –  Andreas Blass Jan 22 '12 at 23:09

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."

P.S. Sorry, I switched the colors.

share|improve this answer
    
Great! The white king's strategy should be to go North-East. I can't see immediately how to get the perpetual, but it seems to work. This looks like the simplest example so far on an edgeless board. –  Johan Wästlund Jan 5 '12 at 20:42
    
Yes, this is nice, though indeed the perpetual would have to be verified (already in Q+P vs. Q on an 8x8 board there are positions that are won after a long near-perpetual). A full perpetual is not needed, only that for each $N$ the Queen can move where it can check for at least $N$ moves if the Rooks stop checking. Under the same assumption, we can remove the pawn (which serves only to stop Westwards Queen moves) by moving the Queen one square NE and her husband one square South. This gives the Queen a check, but a Rook can safely block while giving check and then the Queen is soon lost. –  Noam D. Elkies Jan 6 '12 at 0:45
    
Good observation; removing the pawn surely goes a long way in proving the existence of a perpetual. A queen sufficiently far away always has at least 5 possible check squares. They can't all be blocked, since there are only 4 rooks. –  Philip Engel Jan 6 '12 at 1:28
    
That's very nice! White should also make sure his king doesn't get in the way of any of those five checks, but consistently going N-E already takes care of this. I guess this means that Noam's modification brings the solution down to seven pieces with the losing side to move. –  Johan Wästlund Jan 6 '12 at 7:24
    
If the pawn is removed, could you explain why white cannot move the queen west, rather than east, and go for the perpetual from the left side. It seems this would ruin black's forking/skewer plan. –  Joel David Hamkins Feb 19 '13 at 23:39

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

share|improve this answer
1  
True, but that's a rather different notion of the "value" of the position (more properly, of a chunk of a position) that's not directly related with the "how many moves to mate?" question at issue here. –  Noam D. Elkies May 2 '11 at 18:27

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.

share|improve this answer

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

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.

share|improve this answer
2  
I think you've misunderstood the question Jose. What is asked for is one position, where the mate will occur but where (in your notation for the colours) white gets to choose how long it will take. What you have shown us is a position where the size of the position itself tells us how long it might take (or at least gives us an upper bound). What is being asked for is one fixed position where black (in your notation) can name a number $N$ and then, however large $N$ was, white can then make a move (depending on $N$), and then black can checkmate but must take at least $N$ moves to do it. –  Kevin Buzzard Apr 30 '11 at 7:33
2  
PS despite your personal preferences for colours, I think things would be a bit easier if you had stuck to the conventions of the question regardless of what you thought of them. –  Kevin Buzzard Apr 30 '11 at 7:34
    
oh so the OP wants a position that black (in my notation) can mate in 1,2,3,.... moves depending on whites choice of move right? I think this can be done with the same position a bit modified (infinite board with no boundaries). I'll try to check it out after breakfast :) –  Jose Capco Apr 30 '11 at 7:35
    
Right! And note also that one part of the proof must be to prove that black (in your notation) cannot mate in less than this number of moves. For example, in the analogue of your position above but on a 10000x10000 board, we can all see the mate in 10000-or-so, but one also has to prove that there is no mate in 27 where black just stops the king from moving more than 5 squares north, with his rook, and then pushes a pawn forward to queen and mates with the queen and rook in a total of 27 moves regardless of how big the position is. –  Kevin Buzzard Apr 30 '11 at 7:39
2  
Well initially I thought that the question was: given a number n, find position in an infinite board with finite pieces where I have mate in n (but not less). But as kevin pointed out I understood the question wrongly. I didnt deleted the example from the answer because I thought it has some point of interest here. –  Jose Capco May 3 '11 at 18:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.