14

The post Checkmate in ω moves? has inspired a lot of discussion and mathematical research into positions on an infinite chessboard where white can mate in a transfinite amount of moves. The current record for a game value of a position with finitely many pieces is ω⋅n with an arbitrary natural number n.

Is it possible to achieve ω²?

I believe that I have found such a position, which I will share in the answer of this post - Q&A style.

5
  • 1
    I am impatiently waiting for the next questions, about mates in ω^3 moves, and then in ω^ω moves...
    – Evargalo
    Aug 10, 2023 at 13:53
  • @Evargalo Me too! :) It's exciting that there is still so much to do in infinite chess. Aug 10, 2023 at 23:44
  • Looks like we will never reach the end of that infinite stuff...
    – Evargalo
    Aug 11, 2023 at 14:30
  • You may enjoy the fact that you may have partially inspired Naviary's infinitechess.org Aug 11, 2023 at 17:23
  • 1
    @BenjaminWang It's actually the other way round! His first video two months ago informed me of the existence of infinite chess. :D Aug 11, 2023 at 19:12

1 Answer 1

19

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 as an answer to the original post "Checkmate in ω moves?".

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.

4
  • 2
    Minor nitpick in the remarks: if Black disregards Component D, and goes through Component E twice in a row, then the White Queen will be on the same side of E as the rook. Then White can 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, saving ω² moves. Jul 3, 2023 at 22:13
  • @MichaelGottlieb Oh, you are right, this does not work for Black! So there don't seem to be any alternative stratgies for Black apart from the main line. Jul 3, 2023 at 22:21
  • 5
    I am very impressed by the 10 upvotes. Are there really 10 people on Earth capable of understanding this construction ?
    – Evargalo
    Jul 6, 2023 at 15:28
  • 1
    Sorry for the numerous edits, I have tried to simplify the position as much as possible in order to make the variations more easily analyzable. Jul 25, 2023 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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