How many moves possible in chess
the way i hear it is that there are more possible moves in a chess game then atoms in the universe
can somone tell me how we know how much matter is in the universe or through out some number for me so i can understand a little better, because this seems wrong (though i'm sure its right)
can somone tell me how we know how much matter is in the universe or through out some number for me so i can understand a little better, because this seems wrong (though i'm sure its right)
Comments
It depends on what you define as a separate move in chess. Do you mean the number of possible moves any piece on the board can make from any square? Or does it involve other pieces as well? To explain better, I'll give an example.
In the first case, White moves a knight from the starting position to the third row (I'll refrain from the official grid as I don't know it by heart). That's considered One Possible Move.
In the second case, White moves the knight in the same way. However, assuming you're considering the positions of the other pieces, would it be Two Possible Moves if in the first instance, the white knight moved when Black was in their normal positions, and in the second instance, Black had one of their pawns out, even if the two pieces don't interact?
Perhaps "every possible move" means you take every possible configuration of the chess board, from 1 piece to all 32, and find out every move that every piece can make from there. And that can't include things that can't happen, such as a white bishop being on a black square or vice versa.
I dunno if what I said made any sense. I can barely understand what I'm saying now... if I could show you a picture, it would be so much better. Whatever.
i know people (usually beginners) who do not allow pawns to play en passant (in passing - to take an opposing pawn who chooses its opening double move (to row 4 or 5) to avoid threat which would come if it made the single advance, the attacker can execute an en passant attack and move onto the single-advance square (row 3 or 6) it would have occupied... effectively passing behind the piece on the diagonal)
en passant is a legal move, but i have met players who don't want to include that rule... strange.
additionally, there are legal moves in the strict sense of permutations of board and pieces which are illegal during a game (such as moving into check or revealing to check)
finally, if we're talking about pawn promotion, you could argue that the act of pushing a pawn to the final rank and exchanging it for another piece is a single move, but if you consider all the permutations of what it morphs into, does making it a knight count as one while making it a bishop count as a numerically unique move to be tabulated (and are multiple queens, multiple coloured bishops legal?)
with all of these things factored for the maximum number of moves (hedging each to whichever extreme gives the largest total number of possible legal game moves), the basic question repeats with "how many possible games in chess"
maybe the deep blue site has figures on computational preload as well as it's kasparov-specific settings
found these figures using your question as google exact phrase search <a href="http://216.239.57.100/search?q=cache:95Q7eA9xI1gC:www.indiana.edu/~workshop/ui/Chapter2_D6_EO_REVISED.pdf+many+deep+blue+"possi ble+moves+in+chess%22&hl=en&ie=UTF-8" target="_blank">here</a>
[quote]The full game tree for a highly structured game, such as chess, cannot be fully articulated.
In chess, for example, the first players can open with any of 20 actions and the second player can respond with 20 as well.
Thus, after the first two moves, there are already 400 branches to specify if one wanted to try to represent chess as a formal game.
?It has been estimated that the total number of possible moves in chess is on the order of 10^120, or a ?one? with 120 zeros after it. . . .
A supercomputer a thousand times faster than your PC, making a billion calculations a second, would need approximately 3x10^103 years to check out all of these moves? (Dixit and Skeath, 1999: 66). <hr></blockquote>
[ 03-10-2003: Message edited by: curiousuburb ]</p>
<a href="http://www.duke.edu/philosophy/explorer/aiandgo.html"; target="_blank">from the AIandGo page here</a>
<strong>you should also specify if you're playing full chess </strong><hr></blockquote>
<img src="graemlins/bugeye.gif" border="0" alt="[Skeptical]" />
<a href="http://www.opinionjournal.com/extra/?id=110003081"; target="_blank">Man vs. Machine
A new era in computer chess.
BY GARRY KASPAROV</a>
<strong>You guys are making this too complex. He's just asking about the number of possible legal moves.
<img src="graemlins/bugeye.gif" border="0" alt="[Skeptical]" /> </strong><hr></blockquote>
he's asking the number of particles in the universe and we're making it too complex?
part game theory, part chaos theory, part cosmology, part dark matter expansion theory...
maybe the question is just masquerading as deceptively simple
<img src="graemlins/hmmm.gif" border="0" alt="[Hmmm]" />
<strong>
he's asking the number of particles in the universe and we're making it too complex?
part game theory, part chaos theory, part cosmology, part dark matter expansion theory...
maybe the question is just masquerading as deceptively simple
<img src="graemlins/hmmm.gif" border="0" alt="[Hmmm]" /> </strong><hr></blockquote>eh, sorry, I just meant the part about the chess.
And, uh, chess... what was the question?
The answer is, a whole lot.
so the simple answer from them is
atoms in universe: \t\t\t10^77
possible moves in chess
possible moves in go
however...
the Hubble, Chandra, and other new telescopes keep expanding our measurement of an expanding universe, so it's quite likely that our estimate of the universe's atomic population is incomplete
and as many have mentioned, stellar activity adds and destroys atoms and particles continuously, so the number is never fixed
hope this helps
<strong>the way i hear it is that there are more possible moves in a chess game then atoms in the universe
can somone tell me how we know how much matter is in the universe or through out some number for me so i can understand a little better, because this seems wrong (though i'm sure its right)</strong><hr></blockquote>
It's easy to come up with numbers bigger than the number of atoms in the universe, and by such a comfortable margin that it hardly matters how you came up with the number of atoms in the first place. All you need is something which grows exponentially rather than arithmetically.
When you talk about "possible moves", I'm taking it that you're talking about possible sequences of moves, that is the number of possible different valid games of chess that can be played.
Without some special rules about how you count the number of games of chess, the number of possible games is actually infinite. Both players could shuffle pieces back and forth, making valid moves but accomplishing nothing, forever. Take each game that starts with one such meaningless shuffle before progressing to a "real" game, two such shuffles, three such shuffles, etc., and you now have a infinite number of games.
Counting the number of possible games, while discounting both the obvious and not-so-obvious non-progressive infinite games, is a very complex problem in combinatorics. But some quick, gross oversimplifications can be used to show how big the numbers involved really are.
Let use consider only those games of chess that last exactly 100 moves, and not even count all of the others possible longer or shorter games. Imagine that there are roughly 10 possible moves that can be made for each move. There are far more possible moves than that usually, although occasionally there may only be one valid move. In any case, this is a very conservative estimate.
How many possible 100-move games are there then? 10 x 10 x 10 .... x 10, one hundred times over, 10^100, 1 followed by 100 zeros. A "googol" of games.
As for the number of atoms, most of the estimates I've seen for the number of atoms in the universe come in around 10^78 -- 1 followed by 78 zeros. Even if this estimate is short by a factor of a billion, a trillion, or a quadrillion (an American, not a British quadrillion!), the number of possible chess games is obviously much larger. If you want a more comfortable margin, just add on the 110- or 120-move games.
Abandoning this overly simplified example, a more rigorous analysis of chess by Claude Shannon came up with around 10^120 possible 40-move games -- well, well in excess of the number of atoms in the universe by a gargantuan order of magnitude. (See <a href="http://www.maa.org/mathland/mathland1.html"; target="_blank">http://www.maa.org/mathland/mathland1.html</A>; .)
<strong>most of the estimates google returns on an "atoms in universe" exact phrase search seem to agree on a number of 10^77 atoms, but no clear identification of how wide their definition is
so the simple answer from them is
atoms in universe: \t\t\t10^77
possible moves in chess
possible moves in go
however...
the Hubble, Chandra, and other new telescopes keep expanding our measurement of an expanding universe, so it's quite likely that our estimate of the universe's atomic population is incomplete
and as many have mentioned, stellar activity adds and destroys atoms and particles continuously, so the number is never fixed</strong><hr></blockquote>
The important thing is, however, the enormous gulf between 10^77 (or 10^78 as I found) and 10^120 (which only accounts for games of chess 40 moves long). There could be a whole extra known-universe worth of atoms for every single star in the know universe, and the total number of atoms would still fall well short of 10^120. Fluctuations in the numbers of atoms over time are absolutely trivial compared to staggering discrepancy between the number of atoms and the number of possible games of chess.
[ 03-10-2003: Message edited by: shetline ]</p>
my math teacher was tryign to explain an empty void to me...still not sure how we know...knew it existed since its nothing...u can't even give it a place or description
i always wonder if out modern science sometimes is like the science that told us our earth was flat
<strong>psh...chess is gay...i'm not impressed</strong><hr></blockquote>
First you ask an interesting question, then you toss off a dumb comment like this where you come off sounding crass and ignorant. Go figure.
<strong>When you talk about "possible moves", I'm taking it that you're talking about possible sequences of moves, that is the number of possible different valid games of chess that can be played.
Without some special rules about how you count the number of games of chess, the number of possible games is actually infinite. Both players could shuffle pieces back and forth, making valid moves but accomplishing nothing, forever. Take each game that starts with one such meaningless shuffle before progressing to a "real" game, two such shuffles, three such shuffles, etc., and you now have a infinite number of games.</strong><hr></blockquote>But there is a three-time repeat rule, and a 50 move rule, that would limit that.
You don't need to think in terms of games, just in terms of possible legal moves after each possible previous legal move, like curiousburb's quote does. The result is a problem space, absurdly huge for chess or go, but finite and theoretically containing all the possible legal moves, not just the possible legal moves for one game. Each path through the problem space ends (with either a draw or someone winning), so every possible game is represented.
chinese chess (with the river in the middle of the board) is interesting, too
<strong>But there is a three-time repeat rule, and a 50 move rule, that would limit that.</strong><hr></blockquote>
Just to beat a dead horse (because the approach to the problem you give below is much more elegant than mine), the 50-move rule only starts once one player is down to one piece, his king, so 100-move games are still a valid consideration, and even with the three-time repeat rule, calling for a draw for this is optional, not mandatory, so it's still "possible" to go on forever, and certainly it's possible to permutate through exponentially large numbers of useless positions while not making a single repetition of positions.
[quote]<strong>You don't need to think in terms of games, just in terms of possible legal moves after each possible previous legal move, like curiousburb's quote does. The result is a problem space, absurdly huge for chess or go, but finite and theoretically containing all the possible legal moves, not just the possible legal moves for one game. Each path through the problem space ends (with either a draw or someone winning), so every possible game is represented.</strong><hr></blockquote>
That's an elegant way of pinning down a finite answer. In my (perhaps weak) defense, my simplified example might be better at conveying rough orders of magnitude to someone not accustomed to thinking in terms of solution spaces.
[ 03-10-2003: Message edited by: shetline ]</p>
<strong>Just to beat a dead horse (because the approach to the problem you give below is much more elegant than mine), the 50-move rule only starts once one player is down to one piece, his king, so 100-move games are still a valid consideration, and even with the three-time repeat rule, calling for a draw for this is optional, not mandatory, so it's still "possible" to go on forever, and certainly it's possible to permutate through exponentially large numbers of useless positions while not making a single repetition of positions.
</strong><hr></blockquote>
ummm i was under the impression that the 50 move limit has to do with not taking any pieces for 50 moves... you can have any number of pieces on the board, not just your king and you can start to count