Chess and Infinity

In a previous post I asked the question: How many different games of chess are possible? I then went on to supply a woefully inadequate answer. While it was, in my defense, as good or better than any other answer I've seen to the question, it was still off by either billions of orders of magnitude, or by an amount that is actually infinite, depending on how you look at it and how much you enjoy criticizing me. I calculated an estimation of 10^17,000 (1), using the same basic methodology used by Claude Shannon to arrive at his far more respected and well-known figure of 10¹²⁰.

Photograph courtesy Tekniska Museet of Sweden Licence

10¹²⁰ is an estimate on the total number of chess games of no more than 40 moves, not the total number of actual games possible, which is why it's so much lower. 10¹²⁰ is known as Shannon's number, though I very much doubt 10^17,000 will ever be immortalized as Breslin's number, which is disappointing. I want my own number, and it seems only fair that I should get one. Heck, we should all get our own numbers. We have enough of them to give each of us our own infinite sets of numbers. In fact, even if we had an infinite number of people, we could give every one of them his or her own unique infinite set of numbers. The fact that this is entirely counter-intuitive is gleefully, almost giddily, conceded, and the paradoxical, but intoxicatingly fascinating nature of infinite things is the subject of this essay.

10^17,000, or, as it is known in some small but very intelligent, not to mention good-looking, circles, Breslin's number, is big. Very very big. Huge. Enormous. Gargantuan. Behemoth-esque. But it's still finite, and one commentator on the previous post pointed out that as far as an estimate on the total number of possible different chess games, it is off not merely by a large amount, but it is in fact off by an infinite amount. The total number of possible games is infinite.

The rules of chess allow either player to claim a draw under certain conditions. Out here in reality, there is every reason to expect at least one of the players will have enough sense to do so, which places a natural limit on the longest possible game. There is no consensus on what that limit actually is, but it's in the neighborhood of 5,000 moves or so.

If both players are happy to just keep moving their pieces in a pointless and repetitive little ballet, any game could go on for 10,000, 100,000, 1,000,000 moves. There is no longest possible game. There are, therefore, an infinite number of possible different games. Now the question is: how infinite?

That might seem like a bizarre question. Infinite is infinite, right? No, actually, infinite is not infinite. Some infinities are much bigger than other infinities. Infinitely bigger, in fact.

The man who we have to thank/blame for this is Georg Cantor, a German mathematician, founder of set theory, and father of infinity (2), or so he would be known, if he had had a decent publicist. Cantor didn't invent the idea of infinity. That concept has been around for thousands of years. One of the most celebrated proofs of all time, and deservedly so, is Euclid's proof that there are an infinite number of prime numbers. That dates back about 2,300 years and is still, to this day, a shining example of the power of mathematical reasoning. But Euclid and his contemporaries, and pretty much every mathematician that followed for over 2,000 years, up until Cantor came along at the end of the 19th Century, never suspected that there was more than one type of infinity, let alone, as Cantor showed, an infinite number of infinities.

Take the natural numbers. They start off: 1, 2, 3, and keep going . . . forever. Your collection of every single natural number is a set containing an infinite number of elements. And even though it's infinite, you can start listing them, one by one, as we started to do just now. This is a countable infinity.

But then lets say you add to this infinite set one additional number, zero. So now you have the timeless schoolyard expression of infinity plus one which is, I'm sorry to disappoint the clever disputant who thought this the perfect retort, exactly the same size as your original infinity. And now add all the negatives of all those natural numbers, -1, -2, -3 and so on, forever. So now we've multiplied our original infinity by two and added one, and it's still the same infinity.

Our set is now full of all the integers. We can add to it every fraction (known more formally in math-speak as the rational numbers) that can possibly be constructed using those integers. So between 0 and 1, you add 1/2 and 1/3 and 1/4 and so on. You'll have an infinite number of elements between 0 and 1 alone, and you'll have an infinite number of elements between 1 and 2. In fact, you'll have an infinite number of these rationals between any two arbitrarily chosen ones, no matter how close they are.

So, there are obviously many more rational numbers than there are natural numbers, right? I'm afraid not, but don't feel bad if that was your intuitive notion. The fact that there are the same number of fractions as there are natural numbers just violates every logical instinct you could reasonably be expected to have. Perhaps even less intuitive is the fact that if you add to this growing infinite set all the algebraic irrationals, numbers like the square root of 2, as well as every square root, cube root, ninth root, and any other root of any other natural number, you will still have the same size set.

Let's return to our original infinite set of natural numbers. 1, 2, 3, et infinite cetera. We can take this infinite set and using our patented magical math scalpel, cleave it neatly into two subsets, namely odd numbers and even numbers. So the first set starts off 1, 3, 5 . . . and the second one starts 2, 4, 6 . . . Either one of them goes on forever and neither contains any elements in common with the other. The two together form the set of all natural numbers but each of the subsets is, paradoxically, the same size as the original complete set of all natural numbers. Abracadabra.

Here is why: let's take that set of even numbers, 2, 4, 6 . . . Notice that each of the elements in this set has a clearly defined relationship with the elements in the natural numbers, which is that each is exactly twice as big. The 2 is 2 x 1. The 4 is 2 x 2. The 6 is 2 x 3. So you can put each of the elements in your set of all even numbers on a one-to-one correspondence with the set of all natural numbers. Multiply each element in the set of natural numbers by 2, and you will have the set of all even numbers.

So even though the set of all even numbers seems to be half the size of the set of all natural numbers, it actually isn't.

In a similar fashion, you can put the set of all the rationals on a one-to-one correspondence with the natural numbers. Even less intuitively, you can add to this set all the algebraic irrationals, numbers like the square root of 2, as well as the square roots and cube roots and ninth roots and googleplexian roots of any other of the natural numbers, and there is still a way to put them on a one-to-one correspondence with the infinitely numerous (but countable) natural numbers. So now this set—which itself contains the set of all natural numbers, as well as infinitely many more additional numbers that are not part of the set of natural numbers (like 1/2 and the square root of 2)—turns out to be the same size as the set of natural numbers alone. Ta da! Nothing up my sleeve.

Placing the rationals and algebraic irrationals on a one-to-one correspondence with the natural numbers is a little bit more complex than placing the even numbers or odd numbers on the same correspondence, but trust me: it can be done. Or don't trust me. That's up to you.

(The proof of the countability of the rationals is actually quite fun and easy to understand. The proof of the countability of the algebraic irrationals is less so. It is, again, up to you whether you want to trust me on this. To be honest, I'm probably the last person you should trust, ever. Including advice as far as who you should trust. And don't trust people from Crete either. They are all liars.) (4)

This raises the question: if all the algebraic irrationals and all the rational numbers are the same size of infinity as the countable set of all the natural numbers, then what could be larger?

The short answer is: the real numbers. Well, that's one short answer anyway. The real numbers are a set of numbers that contain all the integers, and all the rationals, and all the algebraic irrationals. (5) This set we've described thus far is a countable infinity, no larger than the set of natural numbers alone. But the real numbers contain another kind of number we haven't discussed yet. These are the transcendental numbers. Numbers like π and e and . . . well those are the only two transcendental numbers you are likely to have heard of.

Even though there have only been a small handful of transcendental numbers specifically identified, and π and e are the only ones that get much airtime, the surprising fact is that most numbers are transcendental. And by “most” we mean “pretty much all of them.” And by “pretty much all of them” we mean that if you were to take the set of all real numbers and pick one of those at random, the probability that it would not be a transcendental number is infinitesimal. And by infinitesimal, we do not just mean “very small,” we mean it in a mathematical sense, which means, essentially, closer to zero than you can ever get with a number without actually being zero.

The transcendental numbers are not merely infinite, they are uncountably infinite. And not just uncountable in a practical sense, because who has an infinite amount of time to waste counting numbers? Even if you had an infinite amount of time, and didn't need to get laundry done, you would still not be able to count them. There is no way to order them so that they are on a one-to-one correspondence with the natural numbers.

Now seems like a perfect opportunity to inject a Hebrew letter into the conversation. It's Aleph, and the little subscript under it, though it looks just like a zero, is pronounced “null.” (Actually, you can call it Aleph zero if you want to, but none of the mathematicians will think that you are cool if you do.)

ℵ₀ describes the “cardinality” of the countable infinities, so the natural numbers, the integers, the rationals, the odd numbers, the even numbers, the algebraic numbers, all have cardinality ℵ₀. Even though some of these sets are subsets of some of the other ones, they are all the same size. ℵ₁ is the designation for the smallest infinite set that is larger than ℵ₀.

The set of all real numbers (with cardinality = 𝔠, which stands for “continuum”) is bigger than ℵ₀. It stands to reason that it's equal to ℵ₁, but it turns out that it's not as simple as that. Maybe ℵ₁ = 𝔠. Or maybe ℵ₁ < 𝔠, which is to say there exists an infinite set that is larger than our beloved little countable infinities, but smaller than that big 'ole continuum with its legions of omnipresent but mostly incognito transcendentals. It turns out that it is “undecidable,” meaning it can't be proved or disproved, and depends on which axioms you use for your set theory, in a manner similar to whether you accept Euclid's fifth postulate, giving you either Euclidean or non-Euclidean geometry, each of which is internally consistent, and neither of which is “correct.”

That, of course is another fascinating topic we'll save for another day, especially since it has almost nothing to do with chess, no matter how much we try to force the issue. The current topic can be made to relate to chess if we squeeze it right, which we'll do momentarily. But first, just a little more Cantorian set theory:

ℵ₀, our designation for those countable infinities, has the interesting property that if you multiply, divide, add or subtract to it any finite number, it's still ℵ₀. You can even raise it to any finite exponent, and it is still ℵ₀. If, on the other hand, you raise some finite number equal to 2 or greater to the power of ℵ₀, you get something bigger than ℵ₀. You get 𝔠.

Returning, at long last, to chess, we've shown that because the rules do not actually require a game of chess to be drawn due to either repetition or astounding boredom, there is no longest possible game. It can last a million moves. A billion moves. A trillion. It can go on for an infinite number of moves, but clearly this is a countable infinity. It's ℵ₀.

Let's make a little chart to help us track the total number of possible games corresponding to each game length. (Each move on each side of a chess game is called a “ply” for reasons I've never bothered to look up and do not care.) Note also that the asterisk indicates that every number in the right column from that point on is not an exact number, but an estimate, which gets rougher as it gets bigger. (6)

The player with the white pieces can make any of 20 possible 1st moves. Black can then make any of 20 replies. By the third ply it's already difficult to calculate, because in some of those 400 different positions after the first two plies, White still has 20 different choices, but in some positions it may be more or less than 20. But it's roughly 20 and black has roughly 20 different replies to this. At each different ply, we need to multiply the existing possible sequences by the number of different choices available at that ply, which Shannon showed to be 30, on average, in his analysis.

The biggest flaw in my own earlier analysis was assuming (7) that this average of 30 possible moves would remain in effect for games lasting into the thousands of moves. There's no reason to expect that it should and lots of reasons to expect it shouldn't but it's so much easier to pretend we don't realize this.

In any event, we're not as worried about it for this essay. In the earlier one we were trying to determine a reasonable estimate for the total number of possible games, given rules that would ensure a large but finite longest possible game. Our simplifying assumptions resulted in huge uncertainties in our final calculated number. In this one it won't matter at all. We're only interested in the cardinality of a number we know is going to be infinite. Whether there are 10, 20, 30, 40 or some other number of possible moves at any given point in any game is irrelevant.

So, that last number in that last column is a product of an infinite number (a countably infinite number) of finite factors. It's 20 x 20 x 20ish x 20ish, etcetera. The specific numbers don't matter. What does is that it's the product of an infinite number of finite factors of 2 or greater.

Since it doesn't matter, let's just say it's 2 all the way. In reality there are more than 2 legal moves in the vast majority of positions, but let's just pretend that at every position there are only 2 possible moves the player can make. 2 multiplied by itself an infinite number of times is 2^ℵ₀, and that, of course, is equal to 𝔠, our old friend the continuum (and possibly ℵ₁, depending on how you take your set theory).

What this means is that not only are there an infinite number of possible chess games (assuming no forced drawing) the number is not even countably infinite. It's infinitely larger than the set of natural numbers or integers.

That's a lot of chess games. Infinitely bigger than Breslin's number, which I thought was pretty impressive at the time.

← Return to essays