The Open File - Is Chess Infinite?

Submitted by NM Zug on Mon, 01/26/2009 at 4:53pm.

The Open File

by Life Master Mike Petersen (Zug)

Is Chess Infinite?

Chess games have to end.  I've never heard of a chess game that ended because of any other reason than by checkmate, stalemate, draw, or resignation.  Draws are the most important, here.  They can happen when the position is repeated three times, there is a perpetual check, or by the 50-move rule.

So, that means that there is a finite number of moves in any chess game.  The question is, how long is the longest possible chess game?  The answer involves some math.  It turns out that, after Black's 5948th move, White is able to claim a draw.  Huh?

The calculation goes like this.  (Pawn_Moves + Captures - Duplicates + Drawing_Interval_Grace_Period) * (Drawing_Interval), or 16*6 +30 -8 +1) * 50 = 5950.  You can subtract two moves from this total because sequences of Captures/Pawn_Moves must have at least 4 alternations between the two players.  Thus the number 5948.

Okay, now let's make some assumptions.  As an extremely loose upper bound on the number of positions possible, allowing all illegal positions, and not differentiating between the various pieces, and noting that chessboards have 64 squares, both White and Black have 16 pieces, etc., we can now make a calculation.  There are 64!/32! ways to place the pieces on the board.  The (!) means "factorial", which is a shorthand mathematical way to indicate 64*63*62...3*2*1.  For example, 5! = 5*4*3*2*1 = 120.  So, 64!/32! = 4.8222 x 10^53.  Read this as 4.8222 times 10 to the 53rd power.  Keep in mind that this allows all positions, including illegal ones and positions which would clearly be impossible.

So, the absolute maximum number of games of chess = (4.8222 x 10^53) ^ 5948. Which equals...(are you ready?)

1.0516 x 10^270993

Uh, this is a very big number, folks.  It is 10516 followed by 270989 zeros (I moved the decimal).  Just how big is this number? 

Well, there is a mathematical term for a pretty big number.  It's called a googol, and it's equal to 10^100 (a one followed by 100 zeros).  There is a bigger number.  It's called a googolplex, and it is equal to a one followed by a googol of zeros.

Uh, okay, how big are these numbers?  According to most astrophysicists, the total number of atoms in the observable Universe is somewhere between 10^72 and 10^82.  While this is a mammoth number, it is far less than even a googol, never mind the mind-boggling googolplex.

Still having trouble wrapping your head around these numbers?  Okay, consider this.  A billion is a puny 10^9.  If you counted to one billion at the rate of one number per second, how long do you think it would take you to count to a billion?  The answer is 32 years.  Starting to get the picture?

So, while the number of possible chess games is larger than a googol, which makes it far larger than the number of atoms calculated to be in the visible Universe, it is not larger than a googolplex.

So, chess is not infinite.  But, it sure seems that way.

==========================

Click here for links to Mike's other work on Chess.com

» posted in Other
 

Comments:

by djbl - 6 months ago
preston United Kingdom
Member Since: Jan 2009
Member Points: 5

the music analogy is a bad one, for a start, the basic (only) element of music is sound, and there is an infinite range of sounds between high and low range. the notes e, c, d etc are conventions, and only approximatiions. between c and d on a scale is a limitless range of sound. like our sense of sight, it is seemless. but a chess piece is either on d4 or it isnt on d4, it cant be almost on d4, or more on d4, it is or isnt.

by jk00750 - 7 months ago
United States
Member Since: Dec 2008
Member Points: 188

That many possibilities?  I knew there were a lot, but not that many.  Is that more than enough dollar bills, stacked one on another, to stretch over the width of the Milky Way 10000000000000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000 times over?  Amazing....

by Eiwob - 9 months ago
Norway
Member Since: Aug 2008
Member Points: 451

I'm afraid I have to make the number larger this time. I think a game can last to white's 6699th move, without being draw by the 50-move rule, insufficient material or anything else before that. Because:

There are 30 possible captures, 7 possible moves per pawn (pawns reaching the end of the board count, don't they?) and 8 duplicates (pawns capturing a piece). (30+7*16-8)*50=6700. But black and white have to switch 3 times who's capturing and making pawn moves, so the game has to end on white's 6699th move. You might think that after all the captures and pawn moves, the game can go on for 50 more moves, but then all the pieces except the kings will be gone, and it is a draw.

Then, my conclusion (apart from the mistakes I probably have done) is that the number of different chess games has to be less than 325^13397.

by NM Zug - 9 months ago
Central Florida United States
Member Since: Feb 2008
Member Points: 747

Fun responses.  You folks are narrowing the number down a bit, which is good, because the entire intent of my column was to show that chess was not infinite, but bounded on the upper end.

Have fun calculating!

- Zug

by Eiwob - 9 months ago
Norway
Member Since: Aug 2008
Member Points: 451

 I will try to limit that HUGE number a bit. The number will still be HUGE, but anyway. If the maximum number of moves in a game is 5948 (I'm not sure that it is, maybe I will check it out later), there will be made 11896 moves. Each move, the players can choose between not more than 323 different moves, in addition to draw, win for white and win for black. (If all the pawns have become queens, which will make the number as large as possible, the largest possible number of king moves will be 8, queen: 27x9=243, rook: 2x14=28, bishop: 2x13=26, knight:2x8=16, and castling: 2. 243+28+26+16+2=323.) Then the largest number of games will be less than 325^11896, or at least 325^((the largest possible number of moves in a game)x2).

by RetGuvvie98 - 9 months ago
Manassas, VA United States
Member Since: Sep 2007
Member Points: 3563

Grakovsky, please help me out here.  What is the true purpose of chess?

I've been grappling with the true purpose of life for a long time, not coming up with more than a seemingly solid confusion on it. so I decided to simplify my search for "true Meaning" and decided to define the "true Meaning" of chess.   But again, due partly to the googolplexitys of it, have ended up confused. 

I'm not sure I can understand the true purpose of it, unless we define the true purpose.

 

so tell me:  What is "the true purpose of it"  as you see it???

anyone less confused than I, feel free to chime in here and help me reduce my googolplexed confusion.

by Lance4635946 - 9 months ago
Smyrna United States
Member Since: Dec 2008
Member Points: 308

Way to put math into Chess.  Interesting facts :)

by Jpatrick - 9 months ago
Pennsylvania United States
Member Since: Jul 2008
Member Points: 192

Chess is not infinite, but it is, so far, intractable.

by Yonatanof - 9 months ago
Ramat Hasharon Israel
Member Since: Sep 2008
Member Points: 77

This is interesting. really big number.

 

Anyway somebody said that the number of 5-minute compositions possible is finite, and I'd just like to point regarding that statement, that in order for it to be true, time, frequency, volume, timbre and all other elements of sound and rhythem have to be incosistant.

I'm not sure, but I think they are, according to quantom theory.

by razoman - 9 months ago
Batangas Philippines
Member Since: Nov 2008
Member Points: 48

Thank God chessclocks were invented and time control established.Wink

by ceecilt - 9 months ago
Chronton Canada
Member Since: Oct 2008
Member Points: 35

I think davidetal is probably right - music Must be limited by a finite number. But the number of every single possible combination of frequencies that can be heard by the human ear in, say, a five minute period, would be Astronomically larger than the number of possible chess games. So no, music isnt infinite. But the number of possible compositions, when you consider how many different sounds could be heard in a single nanosecond, is inconceivably large.

Mr. Zug, this article was most inspiring. No human ever has cause to quit playing chess when you consider the numbers.

by nzjk123 - 9 months ago
Wellington New Zealand
Member Since: Aug 2008
Member Points: 342

I dont know what you just wrote but i know for a fact that the number of possible chess games is around 10^123, which is a HUGE, ENORMOUS NUMBER!

by ayala84 - 9 months ago
United States
Member Since: Dec 2008
Member Points: 5

i get it. list every opening, and just eliminate every possible chain reaction as you go. then start with a new opening not counted yet, eliminate every possible chain reaction as you go. wash, rinse, repeat until you've gone through all possible openings. then add up all the chains counted in each opening, and you get your grand total. I avoid using numbers because i also avoid the headache, but get the gist of it

by NM Zug - 9 months ago
Central Florida United States
Member Since: Feb 2008
Member Points: 747

To davidetal:

No, the analogy doesn't fit.  Chess has a finite playing surface and a finite number of pieces.  Music, on the other hand, has no such limitations.  I have read articles by musicians who are also mathematicians (although I can't give you a reference - sorry) who state that the number of possible compositions may well be infinite.

Thanks for reading...

Zug

by davidetal - 9 months ago
Tarragindi Australia
Member Since: Jan 2008
Member Points: 1755

I was entertained, as well as intrigued:) Though the maths involved far exceed my abilities, which is limited to working out how much the Global Financial Crisis has cost me, so far:(

The question posed - is chess infinite? - is certainly answered, to a certainty. The question - what is the number of legal positions or games? - is a different question.

By analogy, am I right in assuming the number of musical compositions is also limited?

Thanks heaps, zug:)

by NM Zug - 9 months ago
Central Florida United States
Member Since: Feb 2008
Member Points: 747

To devaj:

You said, "finding a number bigger than the real number doesn't really answer the question". 

But of course it does.  The question was, "Is chess infinite?", not "Exactly how many chess games are possible?"  Finding a number larger than the actual shows that chess is indeed not infinite.

You also said, "the resulting number of chess games is way above the real number. does it represent something useful? if you can't figure this out, ask someone who can, but don't pretend to have addressed the problem."

Sigh...this column is intended for entertainment.  As a matter of fact, a part of your question was entertaining:  "does it represent something useful?"  Of course not!  I did it for fun, which is the spirit in which it should be read.

Regards, Mike Petersen

by kaos2008 - 9 months ago
leicester United Kingdom
Member Since: Mar 2008
Member Points: 184

lost me on the first line....

wanna explain again?

Undecided

by devaj - 9 months ago
San Francisco United States
Member Since: Jun 2008
Member Points: 1

as the first post points out, finding a number bigger than the real number doesn't really answer the question. the 5948 number was not explained very well. then, taking the number of arrangements (which is itself way above the possibilities) to the 5948 power is just ridiculous, so much so as to be insulting to the reader - it suggests we could move from any arbitrary arrangement to any other one for the maximum number of moves. the resulting number of chess games is way above the real number. does it represent something useful? if you can't figure this out, ask someone who can, but don't pretend to have addressed the problem.

by SilentThunderStorm - 9 months ago
Saint Louis United States
Member Since: Jan 2009
Member Points: 27

Sure, but keep in mind that the calculations are based on every position on the board... Now, I do understnd the reason that those assumptions were made was to simply the math; but it does beg the question.

I am not up to the challenge, but I am curious as to how many POSSIBLE, LEGAL positions there are on a chess board.  I would be willing to bet that the vast majority of the positions are neither possible nor legal.

by nqi - 9 months ago
Southland New Zealand
Member Since: Jul 2008
Member Points: 445

That's a f%*+@$g big number!

 

Add your comment:

Join Chess.com for free to add your comment! Already a member? Then login now to comment.