27 Jul 05
if by the time both players have moved 3 times, there are supposedly something like 9 million variations... and of course, that number jumps exponentially very quickly to the point where it seems as if there are infinitely permutatable chess positions- or if not positions, then methods of arriving at those positions- but if all the numbers here are finite numbers, and we're limited to 64 squares and 32 peices... then would the number of permutations also be finite, just very very large? if so, has anyone figured out The Answer to : how many chess games are there?
27 Jul 05
Originally posted by Darth SpongeIt would be finite. It would be very, very large. It would tend to inifinity. But its rather like asking what the largest prime number is. You feel sure there is an answer, but the capacity to arrive at a defintive answer is way beyond our reach.
then would the number of permutations also be finite, just very very large?
27 Jul 05
1 edit
Originally posted by Darth SpongeThere are certainly an infinite number of "games", if we consider move sequence. Some of these games would be meaningless difference based on simply repeating patterms of moves.
if by the time both players have moved 3 times, there are supposedly something like 9 million variations... and of course, that number jumps exponentially very quickly to the point where it seems as if there are infinitely permutatabl ...[text shortened]... anyone figured out The Answer to : how many chess games are there?
However, it is easy to put an upper bound on the number of board positions (obviously some board positions can be arrived at multiple ways).
A very, very gross estimate for number of board positions would be 33^64 or 1.53E97. This is arrived by realizing each square can either by empty, or occupied by one of 32 pieces (33 choices for each of 64 squares). This estimate of upper bound can be carved down by huge orders of magnitude - maybe I'll come up with a tougher calculation later - but we certainly see it is not "infinite".
27 Jul 05
To quote "the guide"
"Space is big. Really big. You just won't believe how vastly hugely mindbogglingly big it is. I mean you may think it's a long way down the road to the chemist, but that's just peanuts to space. Listen..." "the simple truth is that interstellar distances will not fit into the human imagination"
So there you have it. Since it has been shown that there are more possible possitions in chess than atoms in the galaxy and space is big. No human could ever understand just how many games are possible. Of course most of the games I play result in a loss for which ever colour I'm playing as and don't last much longer than 45 moves each so I can only play a fraction of these games
1. e4, 20 possible replies
27 Jul 05
Originally posted by RookRAKUsing a spreadsheet and just 5 minutes of copy/paste/fill, I can lower the upper bound on board positions from 1.53E97 to 1.52E64
There are certainly an infinite number of "games", if we consider move sequence. Some of these games would be meaningless difference based on simply repeating patterms of moves.
However, it is easy to put an upper bound on the number of board positions (obviously some board positions can be arrived at multiple ways).
A very, very gross estimate for n ...[text shortened]... be I'll come up with a tougher calculation later - but we certainly see it is not "infinite".
It again is certainly much lower, but method to reduce the upper bound (more accurately) involves tougher math.
27 Jul 05
Originally posted by GatecrasherI am sure there isn't a largest prime number.
It would be finite. It would be very, very large. It would tend to inifinity. But its rather like asking what the largest prime number is. You feel sure there is an answer, but the capacity to arrive at a defintive answer is way beyond our reach.
27 Jul 05
1 edit
1st move: 20 variations
2nd move: 400 variations
3rd move: 8,902 variations
4th move: 197,281 variations
5th move: 4,865,609 variations
6th move: 119,060,324 variations
If there was no such thing as the 50 move rule or a draw after 3 equal positions in a game, then it certainly would be infinite. With these rules though, there would be an end no matter what line you take, but it would be a very huge number.
I have searched around and found a site which has approximated the number of variations after 50 moves (which is about 10^134):
http://www.geocities.com/explorer127pl/szachy.html
28 Jul 05
1 edit
Originally posted by BowmannIf the estimate of the number of atoms is credible (10^82), then the number of potential games of chess lasting up to 40 moves (10^120) exceeds it by a significant number.
Has it?
I don't understand these things, but François Labelle does. See
http://www.cs.berkeley.edu/~flab/chess/statistics-positions.html
28 Jul 05
Originally posted by RookRAKActually this is more complex. And not really that simple. Many positions arrived at in this way will be illegal as you said.(Only one king. Pawns standing on promotion rank. Both kings in check aso.)
There are certainly an infinite number of "games", if we consider move sequence. Some of these games would be meaningless difference based on simply repeating patterms of moves.
However, it is easy to put an upper bound on the number of board positions (obviously some board positions can be arrived at multiple ways).
A very, very gross estimate for n ...[text shortened]... be I'll come up with a tougher calculation later - but we certainly see it is not "infinite".
I Still think there would be planty more though. Considering all possible promotion situations and all the following positions. (Plenty of them. 10 knights. 5 knights and three white squared bishops aso)
This Is a VERY difficult math problem.
28 Jul 05
Originally posted by Darth Spongeyou allude to a variety of questions ...
if by the time both players have moved 3 times, there are supposedly something like 9 million variations... and of course, that number jumps exponentially very quickly to the point where it seems as if there are infinitely permutatable chess positions- or if not positions, then methods of arriving at those positions- but if all the numbers here are fin ...[text shortened]... very very large? if so, has anyone figured out The Answer to : how many chess games are there?
- the number of possible games,
- the number of possible positions.
essentially they are similar.
either way the problem is unlikely to be solved exactly, the method instead is to find a number greater than the number, and a number smaller, then we know the answer is somewhere in the middle.
simple upper and lower bounds exist:
a lower bound:
there is at least 10 first moves which have 10 different second moves etc for at least 10 moves, so it is greater than 10000000000,
an upper bound:
there are never more than 100 possibilities per move,
and there must be less than 50 moves before a pawn moves or a piece is captured, and there are at most 7*16 pawn moves and 2*15 captures
so there is an upper bound of 100^(50*(7*16+2*15)) which is a stupidly large number .... roughly 1 followed by 2*50*7*16 = 10000 zeros.
the game is next to refine the number by increasing the lower bound and decreasing the upper bound. we know the truth is somewhere in the middle.
i understand a lower bound has been found which is greater than the number of atoms in our planet!!!!
28 Jul 05
1 edit
Originally posted by RookRAKWell for a start, there are only 12 different pieces! So 13^64 = 1.96E71 is the crudest estimate.
A very, very gross estimate for number of board positions would be 33^64 or 1.53E97. This is arrived by realizing each square can either by empty, or occupied by one of 32 pieces (33 choices for each of 64 squares). This estimate of upper b ...[text shortened]... r calculation later - but we certainly see it is not "infinite".
Edit: Ooh 666 moves 🙂
29 Jul 05
Originally posted by RookRAKThis should be the other way round. Take a piece - there are 64 possible squares. Take the next, there are 64 possible squares (this covers reduced material) so there's 64 choices for the first piece times 64 for the next and so on = 64 ^ 32 possible positions as the largest upper bound. This comes out at 6.28 * 10^57. This actually assumes that all the pieces are different, and allows all sorts of illegal positions, so it massively overestimates the number of possible positions.
There are certainly an infinite number of "games", if we consider move sequence. Some of these games would be meaningless difference based on simply repeating patterms of moves.
However, it is easy to put an upper bound on the number of board positions (obviously some board positions can be arrived at multiple ways).
A very, very gross estimate for n ...[text shortened]... be I'll come up with a tougher calculation later - but we certainly see it is not "infinite".
29 Jul 05
1 edit
Originally posted by DeepThought[Edit: sorry disregard this post. didn't think about the 'all pieces are different' part]
This should be the other way round. Take a piece - there are 64 possible squares. Take the next, there are 64 possible squares (this covers reduced material) so there's 64 choices for the first piece times 64 for the next and so on = ...[text shortened]... s, so it massively overestimates the number of possible positions.
It still does not adress promotions... You won't find any positions on there with three white knights... So this is not a way to find an upper bound on positions.
This is not the answer but some rules:
Two kings must be placed. At least one square apart. (I cant even see the simple math in that)
Each set of pawns can be placed on 6x8 squares.
Each bishop can be placed on 31 squares, takes into account that 2 squares are occupied by kings.
Knights,rooks and queen can all be placed on any of 62 squares, (kings again)
A pawn can be promoted to 4 different pieces (or 5 if you separate the two bishops).
These promotions give birth to MANY more positions. So it's not so easy to find the upper bound on chess positions.