How many distinct chess games are possible, and which is the longest?

Sort:
SeanEnglish

So, assume that a game is automatically drawn if the 50-move rule is violated. Since there are only so many possible pawn moves and only so many possible captures, there would be a finite number of chess games possible. Furthermore, since theres only finitely many distinct chess games, there is some "longest" chess game(not necessarily unique) in terms of the number of moves. 

So my question is this, how many distinct chess games are there, and how many moves is the longest possible chess games?

For the sake of this question, assume that a chess game cannot be drawn by insufficent material, so a KvK or KvK+B or KvK+N endgame could go on for 50 moves.

Also, two chess games are "distinct" if they differ at even one move, so games that transpose into one another are still distinct.


Here are some upper and lower bounds I figured out for the question

# of moves: The longest game under these conditions is somewhere in between 5100 and  6300 moves if I calculated correctly, but cannot be either one of these.

a(very unsharp) upper bound for the number of distinct games is the astronomically large number 74^6300.

Anyone have better bounds? 

SeanEnglish

I'm sorry, 74^6300 may not be an upper bound, but the even bigger 270^6300 is.

and for the longest game, I think I figured out a way to have a game be 5900 moves, so its at least that. 

toiyabe

More possible games than # of atoms in known universe was always a good enough number for me.. Tongue Out

SeanEnglish

Fixing, Even if there was another universe of the same size as ours for each atom in our universe, there would still be more possible chess games then atoms in the multiverse.

toiyabe

I think there are other universes, but that is a very different topic hehe. That number is impossible to comprehend...  

SeanEnglish

Yeah, its a very large number. It's crazy to think about how easy it is to know that there is a specific number of things, but how hard it can be to actually calculate that number. Like, its obvious that there are only so many possible chess games(as long as a draw is forced at 50 moves), but to actually find how many is a daunting task.

Another question that just came to me, that answering could actually have a lot of practical use in the world of chess: I believe I read that there are certain K+B+N vs K endgames that are theoretically winnable but take more than 50 moves to checkmate. Thus, the 50 move rule can actually cause positions that should be winning to be drawn. While something akin to the 50 move rule is necessary to draw in cases of fortresses and perpetual checks, 50 moves isn't enough. We could just drop the 50-move rule and use only 3-fold repition draw rule(which would cause draws in cases of fortresses and perpetual checks), but the 3-fold rule is hard to utilize since it can be hard to tell which positions have been repeated, whereas counting the number of moves since last capture or pawn move is much easier.

So, since 50 moves isnt enough, what is the minimum necessary # of moves without pawn moves or captures such that no position that is winnable with best play can be called a draw?

Murgen

There are some checkmates that require more than 50 moves to force (that's why I despise the 50 Move Rule).

What I've read is that KBN vs K should require no more than  33 moves from any position in which it is possible (the defending King can't immediately capture one of the attackers pieces or stalemate) - and can be done in less from most positions. (I can't do it myself but I'd like to be able to - it might not be likely to come up in a real game... but it's cool! Wink)

K2B (OCB's) vs K takes a maximum of 20 or 22 (I can't remember which) again with the provisos that the defender can't immediately capture one of the bishops and stalemate)

K3N vs K takes a maximum of 20 or 20 (whichever number Two Bishops takes it's the other one) with the same provisos.

SeanEnglish

Oh yeah, you're right about the K+B+NvsK not needing more than 50, I think it was actually K+2NvsK that needs more than 50 at times.

shell_knight
mashanator wrote:
Murgen wrote:

There are some checkmates that require more than 50 moves to force (that's why I despise the 50 Move Rule).

No there aren't. Not with perfect play or pawns, in any case.

White to move.  Mate in 72.



SeanEnglish

ahh yeah, it was K+2NvsK+P that can take more than 50, according to my research, those positions can take up to 82 moves with perfect play, and there are other positions that can take longer still.

So at least 82 moves would be required. 

shell_knight

White to move.  Mate in 545 (lol)



SeanEnglish

Lol Shell_knight, did you just make up the 545 or is that legit?

The complexity of chess scares me at times. 

shell_knight

I don't have 7 man TB to verify, but I googled it.

This vid shows one with 550 (with some previous records)

https://www.youtube.com/watch?v=mwYQRteeHbE

archana777

All I can say is that the number is very very large!

SeanEnglish

Mashanator, how do you know that its a max of 250? whats your reasoning?

TBentley

https://en.wikipedia.org/wiki/Shannon_number

"Allis also estimated the game-tree complexity to be at least 10^123, 'based on an average branching factor of 35 and an average game length of 80'."

SeanEnglish

TBentley, that number seems extremely small... I could be completely missing something, but considering all possible games, I would guess the average game length would be greater than 80 since there would be a large number of games making foolish back and forth moves.

I guess that the average length of 80 is based off of actual games played, rather than potential games, which would ignore all the games that have a bunch of stupid repitions and wasted moves. 

shell_knight

Average game would be around 40 moves probably.  Definitely less than 80 in any case.

SeanEnglish

shell_knight, thats average moves per games played intelligently, not average moves per all possible games.

rbjones999

SeanEnglish, are you assuming 3-fold repetion is a forced draw? Or completely ignored?