ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel

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

Updated on September 28, 2019

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 aj terms represent the number of j-sized multisets, and the ik 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 2155 (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 aj represent the number of j-sized multisets. By definition then,

N = 1·a1 + 2·a2 +... + x·ax + ... + n·an ≥ 0, with each aj ≥ 0 and each j > 0.

Using proof by induction, for the base case, N = 0, the expression is correctly zero, as each aj 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 Nm.

It should be clear that Nm+1 = Nm+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 Nm+1 be placed in ax. Then, it is easily verifiable that Nm+1 contains one more ax+1 multiset and one fewer ax multiset than Nm.

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 aj that differ from Nm to Nm+1. Then, using the previous facts that αx+1 = ax+1 + 1 and αx = ax - 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.

Comments

    0 of 8192 characters used
    Post Comment

    No comments yet.

    working

    This website uses cookies

    As a user in the EEA, your approval is needed on a few things. To provide a better website experience, hubpages.com uses cookies (and other similar technologies) and may collect, process, and share personal data. Please choose which areas of our service you consent to our doing so.

    For more information on managing or withdrawing consents and how we handle data, visit our Privacy Policy at: https://maven.io/company/pages/privacy

    Show Details
    Necessary
    HubPages Device IDThis is used to identify particular browsers or devices when the access the service, and is used for security reasons.
    LoginThis is necessary to sign in to the HubPages Service.
    Google RecaptchaThis is used to prevent bots and spam. (Privacy Policy)
    AkismetThis is used to detect comment spam. (Privacy Policy)
    HubPages Google AnalyticsThis is used to provide data on traffic to our website, all personally identifyable data is anonymized. (Privacy Policy)
    HubPages Traffic PixelThis is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.
    Amazon Web ServicesThis is a cloud services platform that we used to host our service. (Privacy Policy)
    CloudflareThis is a cloud CDN service that we use to efficiently deliver files required for our service to operate such as javascript, cascading style sheets, images, and videos. (Privacy Policy)
    Google Hosted LibrariesJavascript software libraries such as jQuery are loaded at endpoints on the googleapis.com or gstatic.com domains, for performance and efficiency reasons. (Privacy Policy)
    Features
    Google Custom SearchThis is feature allows you to search the site. (Privacy Policy)
    Google MapsSome articles have Google Maps embedded in them. (Privacy Policy)
    Google ChartsThis is used to display charts and graphs on articles and the author center. (Privacy Policy)
    Google AdSense Host APIThis service allows you to sign up for or associate a Google AdSense account with HubPages, so that you can earn money from ads on your articles. No data is shared unless you engage with this feature. (Privacy Policy)
    Google YouTubeSome articles have YouTube videos embedded in them. (Privacy Policy)
    VimeoSome articles have Vimeo videos embedded in them. (Privacy Policy)
    PaypalThis is used for a registered author who enrolls in the HubPages Earnings program and requests to be paid via PayPal. No data is shared with Paypal unless you engage with this feature. (Privacy Policy)
    Facebook LoginYou can use this to streamline signing up for, or signing in to your Hubpages account. No data is shared with Facebook unless you engage with this feature. (Privacy Policy)
    MavenThis supports the Maven widget and search functionality. (Privacy Policy)
    Marketing
    Google AdSenseThis is an ad network. (Privacy Policy)
    Google DoubleClickGoogle provides ad serving technology and runs an ad network. (Privacy Policy)
    Index ExchangeThis is an ad network. (Privacy Policy)
    SovrnThis is an ad network. (Privacy Policy)
    Facebook AdsThis is an ad network. (Privacy Policy)
    Amazon Unified Ad MarketplaceThis is an ad network. (Privacy Policy)
    AppNexusThis is an ad network. (Privacy Policy)
    OpenxThis is an ad network. (Privacy Policy)
    Rubicon ProjectThis is an ad network. (Privacy Policy)
    TripleLiftThis is an ad network. (Privacy Policy)
    Say MediaWe partner with Say Media to deliver ad campaigns on our sites. (Privacy Policy)
    Remarketing PixelsWe may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.
    Conversion Tracking PixelsWe may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.
    Statistics
    Author Google AnalyticsThis is used to provide traffic data and reports to the authors of articles on the HubPages Service. (Privacy Policy)
    ComscoreComScore is a media measurement and analytics company providing marketing data and analytics to enterprises, media and advertising agencies, and publishers. Non-consent will result in ComScore only processing obfuscated personal data. (Privacy Policy)
    Amazon Tracking PixelSome articles display amazon products as part of the Amazon Affiliate program, this pixel provides traffic statistics for those products (Privacy Policy)
    ClickscoThis is a data management platform studying reader behavior (Privacy Policy)