A Chess Puzzle, Part III: The Pawns, Knights and Kings

Part III of A Mathematical Chess Puzzle:
- Part I: The Infinite Chess Board
- Part II: Ruminations
- Part III: The Pawns, Knights and Kings
- Part IV: A Group of Rooks
- Part V: Rooks and Topology
- Part VI: The Bishop
- Part VII Episode 1: The Fractal Queen
- Part VII Episode 2: The Rational Super Queen
- Part VIII Conclusion: The Transfinite Super Queen and Beyond
This is part III of my series of posts on the “Chess Density Problem”. In Part I, I introduced the problem and laid out some definitions to clarify what I meant by some of the terms such as “Board” and “Density”. In Part II I gave everyone a breather. Hope you’ve rested up. In this one the math is going to be a bit thick, but the purpose of it all will be to prove this first theorem:
The Chess Density Theorem – Pawn, Knight and King
DENSITY THEOREM 1: For Pawns, Knights, and Kings, their asymptotic density
1.1)
1.2)
1.3)
In other words, on an infinite chess board, you can pack at most half of the squares with “friendly” Pawns or friendly Knights, and only a quarter of the board with friendly Kings. As a reminder, by “friendly” I mean that none of the pieces are threatening each other by standard chess rules.
Plan of Attack
As a starting point, we can note that the solutions found on the standard 8-board can be seen as built up from simple “tile” patterns made of identical small boards:
These tiles each have the densities that are claimed by the Density Theorem above. If we can prove that no such tiles can have a greater density, we can show that this must hold for larger boards. The way which we will do this is to define a precise way to “measure” the density of any arbitrary block of squares, and prove some useful properties of that measure-function.
Definitions
It always helps to define things precisely. There are a lot of fancy symbols, but the general ideas should be clear.
The Pieces
The six standard Chess pieces are King, Queen, Bishop, Knight, Rook, and Pawn, which we will denote with the initials {K,Q,B,N,R,P}, respectively. To this set we will also add the “Empty” piece, denoted
The set of all pieces including the empty piece will be denoted
We include that “empty” piece to allow us to explicitly specify that a square is empty.
Control Zones
DEFINITION: The control zone of a piece X at position
The Control Zones of the Pawn, Knight and King are shown in blue below:
One thing to note about these three pieces is that their control zones can be defined by a specific finite set of integer offsets from the location of the piece itself. The same cannot be said for the other three pieces (Rook, Bishop, Queen), as their Control Zones are not defined by a fixed set of offsets, but a set of directions on the board, by which they can attack (again, assuming that there are no other pieces blocking the way).
The Control Zone directions for the Rook, Bishop and Queen are shown below.
As we begin to work with the infinite boards we will see that this difference between the two sets of pieces profoundly affects how “dense” they can be.
In particular, on infinite boards the control zones of the Rook, Bishop and Queen are also infinite.
Chess Positions
A lot of the definitions below are just stuff I made up. If they correspond to standard chess terms I will mark them with (standard). If I feel that the definition may not be clear, I will give an example as well.
DEFINITION: For a given board
For all of the chess positions we are considering for this puzzle, we only have one kind of piece on the board at the time. And so we will call them “Pawn-positions”, “Queen-positions” etc. Thus if
DEFINITION (standard): A Position is called Unguarded if no piece in the position is in the control zone of another piece. In other words, unguarded positions are positions where the pieces are all “mutually friendly”.
DEFINITION: If
Measurement of Positions
DEFINITION: For any position
EXAMPLE: In the little 4-board below, there are four queens, and the rest are empty.
So, following the defintion above, the board
DEFINITION: The for any position
DEFINITION: The for any integer n>0, the n-Density (denoted
EXAMPLE: So, in the previous example for the unguarded queens on the 4-board, it can be seen that:
With all of these preliminaries out of the way, we can now define what we really mean by the density of a piece on an infinite board:
DEFINITION: The Asymptotic Density (denoted
The Linear Density Measure
For each of the pieces mentioned in the theorem above, their claimed density is of the form
So, suppose
and so if indeed
and therefore
Using this fact, for any sub-position
Intuitively, what this measure value tells you is how much over or under the expected density a position is from
LEMMA 1: If
that is, the m-linear density of the union of two disjoint positions is the sum of the m-linear densities of each.
PROOF: Follows immediately from the fact that the size of the union of disjoint sets is the sum of the sizes, and regrouping of terms:
and so, regrouping like terms:
QED (Quod Erat Demonstrandum = which was to be proved).
LEMMA 2: There exists a positive constant
PROOF: We will start with the formula for the Pawn; the other proofs will be similar. We first note that for the
So now what about the 2-linear density for the
Now note that since this n-board (for
since all of the terms are known to be
We have just shown that for all even n, and unguarded positions
So now we can play the same game here, and compute the largest possible values of
Now there are
And so, what all this means is that for the Pawns, given any unguarded position
Similarly, for the King, we can play the same game, but now using the 4-density
And so for the King we can use the constant
Finally, for the Knight, we have to work a bit harder. The Control Area around the knight extends beyond just a single square, and so we need to use a 4×4 tile to build up a solution. In the 4×4 tile we showed above, we were able to fill exactly half (8) with friendly knights, giving the 4×4 tile a 2-density of
We see that there are eight pairs of mutually-attacking squares by knight moves, meaning we can choose at most one from each pair on which to put a knight. This means there can be at most eight friendly knights on any 4×4 tile. And so, just as with pawns we have
By the same arguments we gave before, if
PROOF OF THEOREM 1
The theorem is in three parts, for the Pawn, Knight, and King. We will only show the proof for the Pawn, the other proofs are identical in structure. From Lemma 2, formula (2.1), there is a positive constant C such that for all positive integers
which by definition of
Dividing both sides by
But since on the n-Board
in other words (adding one and dividing by 2):
And so, since
Unguarded Positions on the Infinite Board
So far, we have been talking about the density of unguarded positions on large but finite boards
If we use the finite solutions as a guide, we can quickly propose positions
The solutions are:
It is relatively straightforward to see that when restricted to a finite n-Board these positions are the same as the ones using the “tiles” we defined above, and so they are still unguarded positions. But in what sense are they “maximal”? The weight of these positions are infinite, so how can one infinite position have a greater weight than another? The answer is, they are maximal in that expanding the position to include additional pieces in locations where the original position does not, must also have a hostile piece in the set.
The proof that these positions are indeed maximal, is left as an exercise to the reader.
What the infinite solutions look like
Here are the Knight and King Positions for the infinite boards, as viewed from a great distance (the white squares are the empty ones):
This is not actually an infinite board, of course, but a 300 x 300 one. As you can see, as the number of squares on a side increases to infinity, the individual pieces blur out to form a shade of grey, about 50% black for the Knight, and 25% black for the King. Another way to define the density, is that if you were to throw a dart at one of the boards (say, the King), the odds would be 1/4 that your dart would hit a King.
In the next post, we will look at the Bishops, Rooks, and Queens, and see just how strange and different the situation becomes, especially as we venture into larger transfinite boards.