Of Games Greater than Ours: A Generalization of Part of a Mathematical Expression about Counting Chess Positions

Imagine if chess had been a different game than the one we are used to, if the number of pieces per side had not been limited to the typical layout of a queen, two rooks, two knights, and two bishops. How much different and more complex would the game be? Well, in this paper, I discuss this topic in a roundabout way by providing an expression that counts all of the unique combinations of an arbitrary number of varying, arbitrarily sized multisets that are only comprised of duplicated elements. In other words, it is on the topic of systematically and efficiently counting all of the various unique piece combinations if there were an arbitrary number of piece types and each piece type had an arbitrary number of duplications. This is the expression that determines that total:

Here, the a_j terms represent the number of j-sized multisets, and the i_k terms represent the momentary number of k-sized multisets that are being counted in each iteration.

The inspiration for this idea came from an undergraduate math project that I completed in 2011 while attending Florida Gulf Coast University. The title of that project was, “Creating an Upper Bound for the Total Number of Possible Chess Positions.” I accomplished this objective by composing an expression that deconstructed the consequences of the piece configurations and rules of chess, though the result was relatively unimpressive when compared to its computer-assisted counterparts (Tromp, 2010). This was the resulting expression:

Here, I use the multiplication-dot to separate the components that perform different roles. Describing this expression from left to right, the value of t in the first sigma represents the total number of pawns; the part containing the absolute value determines the unique number of combinations for a certain amount of pawns that have not yet been captured; and the combination term that follows calculates the number of ways that the 48 squares, which the rules of chess make occupiable by pawns, can be chosen for a given number of pawns. The x in both the next sigma and combination term is used to calculate the number of unique ways that pawns can promote, given that a pawn has been captured. The variables y and z in the two adjacent sigmas are used to incorporate the different piece choices, excluding the two kings. The next combination term counts the number of ways that squares can be chosen for all of the remaining pieces, including promotions and kings, after the squares for the pawns have been picked. Then, all of the pieces, including the kings, pawns, and promotions, are placed on their squares by the term that ends with the factorial. Finally, the last two combination terms, which are the subject of this paper, determine the number of unique ways that the original 14 pieces (not including kings and pawns) can be chosen.

The result of this chess expression is many orders of magnitude larger than the best computer-based estimate of approximately 2¹⁵⁵ (Tromp, 2010). This shortcoming of my project and the fact that the topic of calculating the total number of chess positions is fairly esoteric and inconsequential, means that my result was more of an exercise in displaying some of the limitations of pen-and-paper mathematics than anything. That said, some good, outside of my passing the math class, came of that endeavor. By this I mean, often it is not the goal, which we seek, that is ultimately impressive, but more the way that this goal is attained. Moreover, nearly six years after this project and with some further attempts to refine the overall result, the thought to generalize the implications of the project’s individual components stuck around and ultimately inspired the topic of this paper. This project was also a good example of the free-floating nature of both creativity and the deductive process.

For clarification, the topic of this paper is a generalization of the piece-counting portion of the aforementioned project, shown here:

Here, ‘14’ is the number of starting pieces without kings and pawns included, and ‘6’ represents the number of multisets with two identical pieces -- each side has two rooks, two bishops, and two queens. The ‘8’ then represents the total number of multisets of any size, which would be the six from before and the two queens.

When I had developed this portion of the project’s expression while manually counting the number of chess piece choices, I was somewhat surprised by the form that it ended up taking. That is, initially my mind had a very different idea of how it might look, and, much like when calculating while playing chess, some of the ideas that I humored were little short of outrageous. Recognizing what approach to take in order to generalize this term was not overly complicated, likely because of both the previous experience and the jumping-off point that the original chess project provided, as I only found it necessary to manually count a few more relatively simple examples in order to extrapolate the overall pattern. Instead, the most difficult aspect of this endeavor was realizing that the starting form, in which the original project’s piece-counting term was written, is not optimal for generalizing and then proving. For example, if the generalized piece-counting expression had been written in the form of that in the chess project, it would look something like this:

Here, N is the total number of elements in all of the multisets. This expression is more convoluted and, thus, more difficult to interpret and prove. Instead of requiring both the combined number of elements in all of the multisets, N, along with the number of multisets of each initial size, as this expression would, the main figure showcased in this paper simply needs the latter half of that information. This may seem like a trivial distinction, but it plays a significant role in making the overarching pattern more apparent, in proving the result, and with increasing its aesthetic value. Nevertheless, the form of the term used in the undergraduate chess project turned out to better suit its own purpose, as the ‘14,’ which represents the total number of pieces, N, was necessary elsewhere in that project’s complete figure.

To prove the main result, as before, let N be the total number of elements in all of the multisets, and let a_j represent the number of j-sized multisets. By definition then,

N = 1·a₁ + 2·a₂ +... + x·a_x + ... + n·a_n ≥ 0, with each a_j ≥ 0 and each j > 0.

Using proof by induction, for the base case, N = 0, the expression is correctly zero, as each a_j must equal zero, and so each combination term equals zero, resulting in the whole expression equaling zero.

Next, let the original expression be true for some N_m.

It should be clear that N_m+1 = N_m+1, in that the next value of N is found by simply adding a single, identical element to an arbitrary multiset. This also holds if the new element is not identical, or what I will call a singleton, creating a new multiset altogether. Let this additional element for N_m+1 be placed in a_x. Then, it is easily verifiable that N_m+1 contains one more a_x+1 multiset and one fewer a_x multiset than N_m.

To illustrate this case and the general nature of the proof,

In this same sense, the following proof is completed:

Here, is used to represent the terms in a_j that differ from N_m to N_m+1. Then, using the previous facts that α_x+1 = a_x+1 + 1 and α_x = a_x - 1, we can substitute, leaving:

Simplifying this result gives:

Q.E.D.

A good way to imagine how this main expression works is to think of a multiset of size j as also being a multiset of size j-1, j-2,..., 1, after the possible combinations for the larger sizes of that multiset have been counted. This is why the number of multisets of size j needs to be included in all of the combination terms involving multisets of smaller size. This is also true if, less than the largest value of j, there are no multisets of some size k, or what could be called a gap in the multisets, as all of the multisets larger than size k will ultimately be narrowed down and counted as multisets of size k.

In regards to this paper, it was not the proof of the result, but finding the actual expression and weeding through all of my erroneous attempts, that made this whole process challenging. This was especially due to my taking the wrong approach at first by following the figure from the chess project too closely. I believe that this result and the pattern found within it are elegant, and part of this elegance is due to the expression’s simplicity when compared to the many wayward notions that I had throughout my efforts. It is examples like this -- much like the grace and form found in sports when something is well executed -- that bring us all back in search of more. Most of all, however, it is nice to have a portion of the fog that obscures my mathematical understanding replaced by something slightly less opaque.