current community

  • chat blog
    MathOverflow
  • MathOverflow Meta

your communities

Sign up or log in to customize your list.

more stack exchange communities

Stack Exchange
sign up log in tour help
  • Tour Start here for a quick overview of the site
  • Help Center Detailed answers to any questions you might have
  • Meta Discuss the workings and policies of this site
Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Checkmate in $\omega$ moves?

up vote 73 down vote favorite
24

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?

combinatorial-game-theory lo.logic chess
share|improve this question
edited Apr 29 '11 at 18:34
spacer
Qiaochu Yuan
49.7k15189448
asked Apr 29 '11 at 15:13
spacer
Johan Wästlund
3,60211827
36  
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

active oldest votes
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.

spacer spacer

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
answered Apr 30 '11 at 11:33
spacer
Junkie
2,1641011
    
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
5  
The images are no longer available at the free hosting that they were uploaded to. –  Boris Bukh Aug 30 '14 at 0:29
up vote 41 down vote

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

Related searches:
bishop infinite checkmate square quarter
gipoco.com is neither affiliated with the authors of this page nor responsible for its contents. This is a safe-cache copy of the original web site.