A while ago I was in the waiting room of the doctor’s office, staring at the ceiling, and looking for something to keep myself amused before the appointment. (The visit was nothing serious, just wanting to update my vaccinations.)<\/p>\n
![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/05\/IMG_4551s-300x225.jpg\")
<\/a>Ceiling at doctor’s office<\/p><\/div>\n
The ceiling was covered with those white acoustic panels, forming a very large colorless and seemingly infinite chess board. I stared at the tiles, trying to think up some kind of puzzle to keep me amused while waiting. I came up with this:<\/p>\n
The Chess Density Problem<\/h3>\n
Suppose you have an infinite chessboard, and an infinite number of one of the six kinds of chess pieces (King, Queen, Rook, Bishop, Knight, and Pawn). What is the densest packing of \u201cfriendly\u201d pieces you can have on that board?<\/strong><\/em><\/p>\n Just asking the question raises more questions:<\/p>\n So far I\u2019ve spend a fair amount of time and scratch paper on this \u2014 quite a bit while sitting around with Gigi\u2019s family for Christmas \u2014 and have some things to report. The first version of this post was very math-heavy. Now it is a bit lighter. You\u2019re welcome.<\/p>\n Friends who have suffered through games with me will tell you that I am terrible<\/i><\/b> at playing chess, and spend far too long to come up with a bad move that in standard chess notation would probably be denoted \u201cNf3 Nc6??\u201d. Not just Chess, but Go, Twixt, Bridge or other strategic games. In defense, I can only say that I am spending all of that time trying to solve the problem, based on the game-theoretic fact that a \u201cbest\u201d move exists. The decision tree is so deep, however, that no computer yet exists that can explore it completely more than a few moves ahead.<\/p>\n Good chess players acquire skill through experience and study, making decisions with imperfect knowledge. They stand at the edge of the Grand Canyon of moves and can walk down trails blazed by others. I can only stand at the edge, frozen by the awesome infinitude of the depths. Then I fall in.<\/p>\n Anyway, this isn\u2019t the organic chemistry of Chess, but the simpler math of atoms and fundamental particles, Boards and pieces. Moving on…<\/p>\n Here is a simple (finite) example of four Queens on a $4 \\times 4$ board, where no Queen is attacking any other, either on rank, file, or either diagonal:<\/p>\n <\/p>\n Four friendly Queens<\/p><\/div>\n So for the $4 \\times 4$ board, with its 16 squares, you can only \u201cpack\u201d at most four queens, meaning the \u201cdensity\u201d (which I denote $\\delta$) of Queens on this board is<\/p>\n $$\\delta = 4\/16 = 1\/4$$<\/p>\n Is this the “best” we can do in this case? The answer is yes, for the simple reason that at most one Queen can be on each row (or they would not be friendly), and there are four rows.<\/p>\n This “packing” puzzle is what’s known as a Mathematical Chess Problem<\/a><\/span>, and falls in the category of “recreational mathematics”. That is, mathematics done for amusement rather than “professional” work on “serious” problems. It should be noted, however, that often these problems lead to questions which are actually “deep” and lead to more important work.<\/p>\n In any case, from the literature, the task of arranging “friendly” chess pieces is called an Independence Problem<\/em> (or an “Unguard” problem), and a chess position in which all of the pieces are friendly is called “Unguarded”. If an unguarded position is the “best” we can do (ie, there is no unguarded position with more pieces), we will call it maximally unguarded<\/strong>.<\/p>\n So, for example, on the standard $8 \\times 8$ chessboard, here are examples of how to arrange \u201cfriendly\u201d Pawns, Knights and Kings:<\/p>\n 32 Friendly Pawns<\/p><\/div>\n 32 Friendly Knights<\/p><\/div>\n 16 Friendly Kings<\/p><\/div>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n We will show (later) that these are “maximally unguarded” positions, and so the density of these pieces on the standard 8-board are 1\/2, 1\/2, and 1\/4, respectively.<\/p>\n And here is how to arrange the remaining three “friendly” pieces, the Rooks, Bishops and Queens:<\/p>\n 8 Friendly Rooks<\/p><\/div>\n 14 Friendly Bishops<\/p><\/div>\n 8 Friendly Queens<\/p><\/div>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n These last three are maximally unguarded positions, and so the density for these three pieces on the standard board are 1\/8, 7\/32, and 1\/8, respectively.<\/p>\n To see this in the case of the Rooks and the Queens, we can use the same argument as we did above with the Queens on the 4-board, by noting that there are exactly 8 rows and only one Rook or Queen can be on any row.<\/p>\n For the 14 Bishops, you can make a similar argument, by noting two things:<\/p>\n Fifteen Bishop Diagonals<\/p><\/div>\n We have separated out the pieces into these two sets of three, because each set have their own unique characteristics, unlike the other set; and the differences in density become more pronounced as the size of the boards becomes larger and becomes infinite. Not only that, but the kind of “density” has to be defined differently, and even the size of the “infinite” board becomes important; as we’ll see, some chess boards are more infinite than others.<\/p>\n All of the “chess boards” we will be working with will be two-dimensional, and each “square” on which a chess piece can be placed can be indicated by a pair of numbers $(x,y)$, where $x$ and $y$ are coordinates in some set $A$, which we will call the Address space. A chess board that uses coordinates in Address space $A$ will be denoted $B_A$. Mathematically, the board $B_A$ can be identified with the Cartesian product $A \\times A$.<\/p>\n For example, the squares of our standard $8 \\times 8$ chess board can be specified using $A = \\{0,1,2,3,4,5,6,7\\}$. The set of integers from 0 to 7 is sometimes denoted $\\mathbb{Z}_8$, and so the standard chess board is $B_{\\mathbb{Z}_8}$.\u00a0 To make life simple(r), we will also call this board $B_8$, or simply the “8-Board”, and similarly an $n \\times n$ board (where n is an integer) will be called the “n-Board”, or $B_n$.<\/p>\n Here for example is the 5-board $B_5 = B_{\\mathbb{Z}_5}$:<\/span><\/p>\n The 5-Board<\/p><\/div>\n Okay, so far so good (you still with me, here?). Now the point of all this mathematical gobbledegook (a scientific term), is that I wanted to look at the “Unguarded” chess problem on an infinite chess board, meaning that I want to use for a “coordinate space” $A$ an infinite<\/em> set. The first one that comes to mind is the set of whole numbers, ie<\/p>\n $$\\mathbb{W} = \\{0,1,2,. . .\\}$$<\/p>\n And so we can define our first infinite chess board as $B_{\\mathbb{W}}$, consisting of all $(x,y)$ where $x$ and $y$ are non-negative integers.<\/p>\n Intuitively, the board can be visualized like this:<\/p>\n The \u03c9-Board<\/p><\/div>\n This picture looks a lot like the ceiling at my doctor’s office, which is what started this whole thing.<\/p>\n Now the “size” (cardinality) of the whole numbers is “infinite”, but the specific mathematical name for this “infinite” value is $\\aleph_0$ (pronounced aleph-null). Unlike the conventional symbol for infinity ($\\infty$), $\\aleph_0$ has a more precise meaning, and it refers only to “countably” infinite sets, ie, those which you can count with the integers 1,2,3, etc. A related infinite “ordinal” number is called $\\omega$ (small omega), and with some “abuse of notation” we will refer to $B_{\\mathbb{W}}$ as $B_{\\mathbb{\\omega}}$, or simply the $\\omega\\text{-Board}$.<\/p>\n There are many other ways to define infinite boards, but for now the only other board we will look at uses as its coordinate space the closed unit interval on the real line, that is,<\/p>\n $$I = \\{ x \\in \\mathbb{R}: 0 \\le x \\le 1 \\}$$<\/p>\n The board $B_I$ can be visualized as the unit square, including every single point on the boundary and in the interior as a distinct “square” on which you could place a chess piece:<\/p>\n The c<\/em>-Board<\/p><\/div>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n The size of the set of real numbers in $I$ is a transfinite number which is infinitely larger than $\\aleph_0$, and is called simply $c$, the infinity of the continuum. If we embrace “The Continuum Hypothesis<\/a>“, this number c can be identified as $\\aleph_1$, the next largest infinity. We shall therefore also call $B_I$ the c<\/em>-Board, or $B_c$. The number of “squares” on $B_c$, unlike the $\\omega\\text{-Board}$, is uncountably<\/strong><\/em> infinite.<\/p>\n The “density” results for each infinite board and piece will be shown (in later posts) to be as follows. $$\\omega\\text{-Board}$$<\/p>\n $$c\\text{-Board}$$<\/p>\n (*) Not Defined for this piece on this board.<\/p>\n (?) Unknown whether a Hausdorff-measurable solution exists.<\/p>\n (**) 1d-Measure = (Hausdorff Content<\/a><\/span>)<\/p>\n\n
Disclaimer<\/h3>\n
Density: A Simple Example<\/h3>\n
![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/AFC181A1-F996-4F81-B1CB-09A723F4A21D-300x296.jpeg\")
<\/a>What is Already Known<\/h3>\n
![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/2230C0BC-08DE-4759-94FC-282E77D55CBF.jpeg\")
<\/a>![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/E1B7CA93-E247-44E5-ACA6-C6F24438CADE.jpeg\")
<\/a>![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/friendly_kings.png\")
<\/a>![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/friendly_rooks.png\")
<\/a>![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/friendly_bishops.png\")
<\/a>![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/friendly_queens.png\")
<\/a>\n
![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/friendly_bishops_max.png\")
<\/a>Chess Boards: Finite and Infinite<\/h3>\n
![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/05\/five-board-150x150.jpg\")
<\/a>![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/omega_board.png\")
<\/a>Chess Boards: Infinity and Beyond<\/h3>\n
![\"\"](\"https:\/\/www.nilesritter.com\/wp\/wp-content\/uploads\/2019\/12\/c-board.png\")
<\/a>Sneak Preview<\/h3>\n
\nThe pieces are in order of their decreasing (2d or fractal) density, and thus their increasing “power”:<\/p>\n\n\n
\n Piece<\/th>\n Board<\/th>\n 2d-Density<\/th>\n Fractal Dimension<\/a><\/span><\/th>\n 1d-Measure (**)<\/th>\n<\/tr>\n \n Pawn<\/td>\n $B_\\omega$<\/td>\n 1\/2<\/td>\n 2<\/td>\n *<\/td>\n<\/tr>\n \n Knight<\/td>\n $B_\\omega$<\/td>\n 1\/2<\/td>\n 2<\/td>\n *<\/td>\n<\/tr>\n \n King<\/td>\n $B_\\omega$<\/td>\n 1\/4<\/td>\n 2<\/td>\n *<\/td>\n<\/tr>\n \n Rook<\/td>\n $B_\\omega$<\/td>\n 0<\/td>\n *<\/td>\n *<\/td>\n<\/tr>\n \n Bishop<\/td>\n $B_\\omega$<\/td>\n 0<\/td>\n *<\/td>\n *<\/td>\n<\/tr>\n \n Queen<\/td>\n $B_\\omega$<\/td>\n 0<\/td>\n *<\/td>\n *<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n \n\n
\n Piece<\/th>\n Board<\/th>\n 2d-Density<\/th>\n Fractal Dimension<\/span><\/a><\/th>\n 1d-Measure (**)<\/th>\n<\/tr>\n \n Pawn<\/td>\n $B_c$<\/td>\n *<\/td>\n *<\/td>\n *<\/td>\n<\/tr>\n \n Knight<\/td>\n $B_c$<\/td>\n *<\/td>\n *<\/td>\n *<\/td>\n<\/tr>\n \n King<\/td>\n $B_c$<\/td>\n *<\/td>\n *<\/td>\n *<\/td>\n<\/tr>\n \n Bishop<\/td>\n $B_c$<\/td>\n $0$<\/td>\n $1$<\/td>\n $2\\sqrt 2$<\/td>\n<\/tr>\n \n Rook<\/td>\n $B_c$<\/td>\n $0$<\/td>\n $1$<\/td>\n $2$<\/td>\n<\/tr>\n \n Queen<\/td>\n $B_c$<\/td>\n $0$<\/td>\n ?<\/td>\n ?<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n