Watcha, 10^50 wasn't a number used to estimate anything in chess, it was thrown out there as an estimate for the number of seconds since the big bang... it came up in post #164.
Gr33nsl33v3s said: "But to give a little perspective on the question there are more possible moves in a game of Chess then there have been seconds since the Big Bang... Or if you happen to not believe in the Big Bang, that's 13.8 billion years ago. So... that would be 10 to the 50th power..."
Now that you mention it though... the 10^50 doesn't make sense in that context. assuming 13.8 billion years, I got 4.35x10^17 seconds... WAYYYY less than 10^50... so I guess I don't know where that number came from?
I would like to see the proof of that upper bound of 10^46 for legal positions. I'm curious to see how they counted.
How many distinct chess games are possible, and which is the longest?
oh wait, I just realized my calculation didn't factor in leap years... maybe that's where the extra 2.3x10^32 seconds come from?(lol)
Ed, can you tell us how you got your numbers(or cite something?) they both seem incredably low compared to many of the other estimates. in fact, the number of legal positions seems to be higher than your lower bound for the number of games, which definitely should not be the case since there must be at least one game for every position.
I was looking at the queens problem on a toroidal board, and I managed to get six:
I couldn't find a way to fit seven though. I tried to prove that 8 cannot happen, but any counting methods I tried using became very complicated after the second queen(after you put the second queen on the board, I believe that covers 46 squares[28 squares covered from each queen, with 10 overlaps from the second queen, fortunately regardless of the positioning, it appears that its always 10 overlaps for the second queen] but positioning is important for counting overlaps in the third queen, so I couldn't find a good systematic way to do it...)
Well referring to the point about the possible length of a game I think the limit would stop at somewhere around 1600 due to the fact that there is 32 pieces on a board and the 50 move rule is prevented by captures so 32*50=1600 so my guess would be if at all it could surpass that 1600 it wouldn't be by a lot
Ed, that can happen when you toss around enough astronomically(or in this case ultra-astronomically since even the numbers used in astronomy aren't usually this big) large numbers, a little bit of confusion as to where they all come from comes up.
I've heard 35^80 or ~10^123 as a common estimate, but that's based off an average arbitrary game length of 80 half-moves, which seems(at least to me) rather low for an arbitrary game.
Tom, it seems that the maximum number of moves in one game is 5948. to help your counting, remember only 30 pieces can be captured(the kings cannot), and pawn moves also reset the 50-move clock.(figuring out why its 5948 and not 5950 though is a nice challenge and very interesting in my opinion)
I was looking at the queens problem on a toroidal board, and I managed to get six:
I couldn't find a way to fit seven though. I tried to prove that 8 cannot happen, but any counting methods I tried using became very complicated after the second queen(after you put the second queen on the board, I believe that covers 46 squares[28 squares covered from each queen, with 10 overlaps from the second queen, fortunately regardless of the positioning, it appears that its always 10 overlaps for the second queen] but positioning is important for counting overlaps in the third queen, so I couldn't find a good systematic way to do it...)
I have a position for 7Q:
Position for 7:
EDIT: Derp FAIL.
Yes, remellion, well done, that definitly works.
While your proof does appear to be completely sound, the part about diagonal sets is kind of confusing. I think you could make the proof a little more clear just by observing that the toroidal board(and cylendrical board, since their diagonals are identical as long as distance is not considered) has 8 /-diagonals and 8 \-diagonals(no colors involved), and so each /-diagonal has a queen and each \-diagonal has a queen(by the pigeonhole principle) so each square is controlled 4 times.
wait... why did your proof fail?
if its because you think queens would control 28 squares(7x4) not 27, you're forgetting that on a toroidal board, each pair of diagonals has two points in common, not one.
wait... why did your proof fail?
Qb4 & Qg4.
ahh yeah I completely missed that on the diagram(I just looked at the diagonals, which are the hard parts for the toroidal board), but Remellion also had a proof that 8 couldn't happen, and it looked like it was valid.
Fail'd due to queen controlling 28 squares not 27 -> no contradictions. [EDIT: I am not thinking clearly; this statement double-counts the other diagonal intersection.]
So. The problem is clearly impossible, but the proof... Polya proved the result impossible for all n divisible by 2 and 3. So what magic did he use?
Hm. Right now I'm considering another approach with some bijection/numbering. Give another set of coordinates for the "diagonals" (separately for each dark and light, label / and \ with 1 to 4.) Find some bijection/transform from these coords to regular a1-h8. Then the solution must have the dark&light coords being permutations of (1-4 , 1-4), and hopefully with the bijection it can be shown that there must be some rank/file intersections.
But I wouldn't hold my breath. Other ideas?
ohh! the problem comes from the fact that the squares controlled by the same queen on two different diagonals are only controlled three times!
ohh! the problem comes from the fact that the squares controlled by the same queen on two different diagonals are only controlled three times!
OH WAIT MY PROOF IS SOUND. =.= and I deleted it.
Let's put it back up, with your improvement.
Counting: each queen controls 27 unique squares. 27*8=216, 56 empty squares. Pigeonhole + [a square cannot be controlled more than 4 times] -> 48 squares controlled 4 times, 8 squares controlled 3 times.
Diagonals: - 8 diagonals going / and 8 going \. There must be exactly 1 queen on each - ergo every square is controlled along both its diagonals. Ditto for light squares. Therefore every square is controlled exactly 4 times.
Contradiction -> 8 independent Q on toroidal 8x8 is impossible.
Also yep my 7Q failed and I can't find a fix.
Remellion, your proof isn't sound...
each queen does control 27 squares, so 216 squares are controlled, but going the other way... the 8 "diagonal anti-podes"(go 4 squares along any diagonal from a queen to get to the diagonal anti-pode) of the 8 queens are only controlled 3 times since its the same queen on the / and the \ diagonals, which matches the 216...
More possible moves than molecules in the universe....And that goes for dating moves too.
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.
I don't think you can just decide to apply 1 rule of chess and not another rule.
ahh! I've got a proof that 8 cannot happen. Another proof by contradiction: assume 8 queens can be put on an 8x8 toroidal board such that no two are attacking eachother. Then since there are 8 / diagonals and 8 \ diagonals, each diagonal has exactly one queen on it. Thus there are four queens on black squares and four queens on white squares. Now, observe that on a toroidal board, all the squares are the same, so let us assume that the first queen is on a1. Here is a picture I will be referencing:
now, in this picture, the black pawn represents the queens "anti-podal" point, and the white pieces represent the remaining black squares that queens can be put. Now, I claim that up to translation and reflection, all of the squares that white pawns are on are the same, and all the squares the white bishops are on are the same, so there are only two possible choices(up to translation and reflection) of where to put the next queen
Choice 1: replace a pawn:
Choice 2: Replace a bishop:
Here are the two posibilities after the 2nd choice of square for queens on black squares, with the remaining posilbilties highlighted with white's pieces. now, in both cases, a quick analysis shows that a 3rd choice forces the 4th choice, and after all four choices, you ALWAYS get the same shape(up to reflection and translation): so, in order to cover all the black squares, this shape is forced. The same argument will show this shape is forced to cover the white squares, but these two shapes can't be build simultaneously since this one relies on two pairs of files with black queens seperated by a single file with a white queen, and the other one could not have an isolated white queen(since it also has two pairs of files with white queens.)
11797 is so ridiculously high exponent, that the average number of legal moves per position should be 1.00981 instead of 35, to arrive at 10^50.
This shows that the 10^50 estimate is broken.
10^50 is a very rough estimate on the upper bound of legal positions rather than the number of games ( the proven upper bound on legal positions as of now is 10^46 ).