Xyo wrote:
I don't know how many "perfect" positions there are, but there are more possible ways a chess game can go than there are atoms in the universe. Good luck.
Yeah, as a matter of fact, the universe is thought to contain roughly 10 ^ 75 atoms versus roughly 10 ^ 120 chess positions. That means there are 10 ^ 45 times more chess positions than there are atoms in the entire cosmos!
If you google "chess position statistics," you should find the website of François Labelle at UC Berkeley who is working on computer modeling and mathematics and has an interest in chess. You'll see that he is carrying Claude Shannon's research much further.
_emily wrote:
I think this would be interesting to try to calculate. People talk about the number of possible chess games, or the number of legal positions after a given number of moves, but you are asking about the number of legal positions, period. There are actually 13 possible conditions for a given square at a given time: the six types of pieces in each color plus no piece. There are 13^64 positions, including legal, illegal, and impossible. That number includes such positions as a totally empty board and a board filled with 64 black kings. The number of legal positions would be much smaller, and of course harder to calculate.
Not that much harder. Forget symmetry for a moment. Fix the orientation of the board so the first square is a1. Settle for completed, legal postions. Straightaway you can see that no pawn can go on the first square. So there are only 11 possibilities for that square (and the other 15 similar squares).
Whenever I start to ponder questions like this I tell myself that 'Somewhere there is a beer that is not being drunk'!
This is 'back-of-a-beermat' arithmetic. Examine the two pieces instance. Take a quarter of the chessboard. There's one corner square: king on that blocks 4 squares (leaving 60 available). There's 6 edge squares: king on one of those blocks 6 squares (leaving 58 available). There are 9 centre squares: king on one of those blocks 9 squares (leaving 55 available). That gives us 1x60 + 6x58 + 9x55 = 903. Quadruple it to allow for the four quarters of the chess board. Double it to allow for colour symmetry. That comes to 7224 legal positions involving two pieces. The number of positions for 3 .. 32 pieces is left as an exercise for the reader.
After you've figured out the number of positions, figure out how many years it will take [Rybka] to solve chess!
You still need to account for restrictions like no pawns on the 1st or 8th ranks, no more and no less than one king of each colour allowed, no more than eight pawns of each colour, no more than 16 pieces of each colour, eliminate any positions where both kings are in check and then once you've got the count of legal positions you need to double it as it could be either white or black's move...
...unless of course one of the kings is in check -- don't double count those, as it can only be the colour who is in check to move...
...oh, and also add in duplicate positions where castling is alternatively allowed or disallowed, likewise for en-passant.
You can see where the complexity in the calculation adds up quickly.
bowanza wrote:
Fourpointo wrote:
This is a hard one, but I thought about it and it could be a new way to look at chess and/or chess computers. Assuming there is a perfect single move for every position, how many would have to be known to create a theoritical perfect chess computer/player? What is the point of the fine print? If you want people to take you seriously, don't force them to get out a microscope to read your question.
To start, there are 7 different possiblilites that can be on a square at one time. A King, Queen, Knight, Bishop, Rook, Pawn, or an empty space. So that means the max possible number of positions would be 7^64 (number of squares) which is somewhere around 1.2 e 54, or 2.4 e54 if you count whose move it is. But then when you start taking out impossible combinations, such as more than 2 king on the board at once, pawns on the back row, more than 10 of a knight, rook, bishop, 9 of a queen, or 8 of a pawn on either side, it gets smaller. And of course there are other board impossibilites, like 8 pawns on the same side lined up vertically, a double knight check, etc.
So has anyone ever heard of someone who has calculated this number? I tried searching for it but it doesn't seem many people have thought as chess this way.
Because I pressed the wrong button and it wouldn't go back on my old computer.
I didn't know about Shannon's number... It's interesting. However my chess handbook says after the first 10 moves there are 169518829100544000000000000 different positions, that is 1.7 e 28. This is enough to say that I won't ever play twicw the same match!!
paul211 wrote:
Fourpointo wrote:
This is a hard one, but I thought about it and it could be a new way to look at chess and/or chess computers. Assuming there is a perfect single move for every position, how many would have to be known to create a theoritical perfect chess computer/player? I may be able to help you as I have studied advanced maths. That said can you expand a little or clarify more your thoughts? When you say : "there are 7 different possiblilites that can be on a square at one time" I am sure that you mean 7 pieces, my dilemna here is that there are 8 pieces in the first row and more than one pawn can occupy any given square after the game is started and depending on the position. The two Bishops, I grant you cannot occupy the same square as they are on different colors squares and cannot cross over, with the knights this is quite different as one can have both knights covering or attacking the same square, and I am positive that you have been in that position yourself. Now there are not 7^64 positions as when you start a game one half of the square are already occupied by pieces of artillery and pawns. The number of combinations is actually a function of the moves. When you start a new game there are only 10 possible moves you can make with your first move, and any square available to make the move can only be occupied by one single piece of chess. As the game progresses and exchanges happen the number of combinations change at every single move. So can you expand on your question? Are you asking how many combinations are there after the first, second, third etc... move or is your question how many combinations exist when playing a game of chess or last how many combinations are left after any move? Awaiting your reply.
To start, there are 7 different possiblilites that can be on a square at one time. A King, Queen, Knight, Bishop, Rook, Pawn, or an empty space. So that means the max possible number of positions would be 7^64 (number of squares) which is somewhere around 1.2 e 54, or 2.4 e54 if you count whose move it is. But then when you start taking out impossible combinations, such as more than 2 king on the board at once, pawns on the back row, more than 10 of a knight, rook, bishop, 9 of a queen, or 8 of a pawn on either side, it gets smaller. And of course there are other board impossibilites, like 8 pawns on the same side lined up vertically, a double knight check, etc.
So has anyone ever heard of someone who has calculated this number? I tried searching for it but it doesn't seem many people have thought as chess this way.
There are 6 possible pieces (pawn, knight, bishop, rook, king, queen) or the space could be empty. So on any given square at any one time there are 7 different possibilities. It shouldn't count doubles, if that's what was confusing.
And two bishops can be on the same color, if a pawn were promoted that way.
Also, what move it is, the prior move, or next move would not matter because you're only looking at the position. Otherwise the number could be infinity, because you could just move pieces back and forth without taking. (Although you could wait 49 moves before each pawn movement or piece capture, but it would still be really long)
All I'm asking is how many different legal board position are there in chess.
fasapo wrote:
According to Shannons number it is 10120 unique games of chess.
In case someone can't visualize it, it's
1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
DIFFERENT games of chess!
_emily wrote:
I think this would be interesting to try to calculate. People talk about the number of possible chess games, or the number of legal positions after a given number of moves, but you are asking about the number of legal positions, period. There are actually 13 possible conditions for a given square at a given time: the six types of pieces in each color plus no piece. There are 13^64 positions, including legal, illegal, and impossible. That number includes such positions as a totally empty board and a board filled with 64 black kings. The number of legal positions would be much smaller, and of course harder to calculate.
Good point, I totally forgot about which color it could be.
There is just One Position. The Current Position
I don't care what any mathematician says, the maximum number of looks that a chess board can have during legal play is limited only by the imagination of the players.
Granted, after white's inital move, there are only 20 possible board positions. After black's 1st move, the board can look a total of 400 different ways. By White's second move you've started overlapping positions in different lines. For example: (1. e4 e5 2. Nf3) results in the same position and look as (1. Nf3 e5 2. e4). If you continue to multiply possible moves by possible moves, you will get the number of possible lines a game can take, but not the number of positions/looks a board can have.
However, both numbers (possible lines and possible positions) are limitless. However theoretical certain games may be, as long as they operate under the existing laws of chess, I saw someone post a game on this site where both white and black had 9 queens!! Try promoting every pawn on the board without putting someone in checkmate. I've seen games played out to a position where the pieces were all in the center forming a giant yin/yang symbol.
If the mind can conceive it...
TheGrobe wrote:
You still need to account for restrictions like no pawns on the 1st or 8th ranks, no more and no less than one king of each colour allowed, no more than eight pawns of each colour, no more than 16 pieces of each colour, eliminate any positions where both kings are in check and then once you've got the count of legal positions you need to double it as it could be either white or black's move... ...unless of course one of the kings is in check -- don't double count those, as it can only be the colour who is in check to move... ...oh, and also add in duplicate positions where castling is alternatively allowed or disallowed, likewise for en-passant. You can see where the complexity in the calculation adds up quickly.
I forgot about positions that don't break any of the rules but are impossible to reach -- like this one, for example:
We would have to think about the fact that, for example, when the King is in check, he has to move or have a piece protect it, which also affects greatly the numbers...
though on the other side, if all legal moves were taken into account, the answer is easy: infinity. Example: 1. Nc3 Nc6 2. Nb1 Nb8 3. Nc3 Nc6 etc...
What could be calculated is the number of games where "all moves are made within the X% of the best possible moves", where X is a number that is considered reasonable. We'd have to run a tool such as Crafty or Fritz for each move, and then for each second move, etc. while skipping identical boards.
This could probably calulated, though the "perfect chess program" concept could be easily broken by not playing the best move... though it's certainly interesting.
EDIT: Oh, "Positions"... reading too fast is bad! "Now I understand! 254-6011!" (I don't think a lot of people will get this one)
To Billium 248:
"However, both numbers (possible lines and possible positions) are limitless."
Both numbers are very very high, but have limits. After 50 moves without a pawn movement or piece taken, the game can end in a tie. Both the number of times you can take a piece (15 for each side) and number of times you can move a pawn (56 for each side) is limited so you can't just keep moving back and forth, otherwise it's a stalemate. And like I said before, there are only so many different pieces you can put on the board at one time, 13 per any one square (Wking, Wqueen, Wknight, Wbishop, Wrook, Wpawn, BKing, Bqueen, Bknight, Bbishop, Brook, Bpawn, or an empty space.) If there were only one square on the board, it would be 13 possible positions. If there were only two, it would be 169 (13 x 13). If there were 3, it would be 2197 (13 x 13 x13), and so on to 64 squares at 1.96 x 10^71 (13^64), or 3.92 x 10^71 if you count whose move it is.
To Grobe:
Your example does break a rule, two queens can't double check someone, because if you move one from a check to reveal another that means it was checking it before you moved it, which is impossible.
Rather interesting about the number of games. But as for the number of positions, I think the sum total of information presented in these posts would give you a fairly accurate estimation.
As for computability in solving chess (not just making an AI that can beat everybody on earth), chess is part of a set of problems generally refered to as "NP Complete" many real world problems in business, marketing and other areas are also in this set. What makes NP complete problems really nifty in mathematics is that there is one particularly esoteric NP complete problem that has the following unusual property: any problem that can be proven to be NP complete posesses a unique mathematical transform into the one problem, and a unique transform that can be aplied to the solution of the one problem for every problem in the set of all NP complete. So basically, if you find a way to solve just one of these guys, all the rest fall like dominos. So much attention is given to chess because it is by far the oldest NP complete problem that has been continuously worked on, it gets worked on by a lot of people, and its fun, too :) !!
Fourpointo wrote:
Both numbers are very very high, but have limits. After 50 moves without a pawn movement or piece taken, the game can end in a tie.
It CAN, but it doesn't have to. Go to the list of current games on this site and sort by number of moves. The #1 game at the time of this post was on move #347!! The 50-move-rule is NOT automatic!! It is designed to allow one player to declare a draw even when the other player refuses. If neither side claims the draw, and both sides agree to play on, then there is no limit to the number of moves that can be made.
I usually sit up in a chair or something, my legs slightly apart, or sometimes crossed, depending on my mood.
My left hand is usually on my knee or holding a beverage of some kind, while my right hand deftly manouvers the mouse.
I suppose there are other chess positions, but this is the one that works for me.