|
|
|
Topic: How many different positions can occur in the game of chess?
| |
|
|
Author
| Message |
|---|
|
|
I also think of that. He will take the King with him.  
Ray Duque III
New York City
|
|
|
There are so many different positions can occur in chess game but I can not name one of them.
Ray Duque III
New York City
|
|
|
GileCar is correct. There is a finite number of possible positions. Another way to pose the question is, What is the entropy of a chess game?" Entropy is defined as the natural logarithym of all the possibilities. For example the entropy of a deck of cards is ln52! (! means factorial of 52 ie 52*51*50...
For whites first move there are 20 possibilities. Black has 20 possible replys for each. Hence 400 possible positions can confront white on his second move. In many of these cases white will have far more than 20 possible replies. Lets guess that most games would go beyound 50 moves (100 half moves) if resigning was illegal. Lets also assume the only a tiny fraction of the positions are duplicates. Our answer must be greater than 20^100 = 10^100 * 2^100 = 10^100 * 1024^10 > 10^100 * 10^30 = 10^130
A queen centered on an open board has 27 squares to move to a Rook = 14, B=14, N = 8 K=8 p = 1,2 or 3. Lets choose 2 for the number of pawn moves. Pieces not centered have fewer. I get an upper bound by erroneously cosidering the case in which all 16 pieces are centered. K + Q + 2R + 2B + 2N + 8p = 8 + 27 + 2*14 + 2*14 + 2*8 + 8*2=35 + 4*14 + 4*8= 35 + 56 + 32 = 127
Certainly the average number of choices per player per move is less than 125. The vast majority of gfames would require less than 100 moves. Each move is 2 half moves. The answer must be less than 125^200= (1000/4)^200 = 10^600/2^400 = 10^600/(1024^40) < 10^600/10^120 = 10^480
I assert that
1. the number of unique positions is greater than 10^130 but less than 10^480
2. Somebody sould over me a job. Man cannot live on entropy alone
|
|
|
| phystutordotcom wrote: For whites first move there are 20 possibilities. |
You appear to be confusing the number of possible games of chess and the number of possible positions that can occur in these games. Arguments based on the number of moves available at each point in the game calculate the number of games, not the number of positions. The same position may be reached by many different routes.
| Lets also assume the only a tiny fraction of the positions are duplicates. |
That's not the case if you really are counting positions, rather than games. Consider any sequence of at most fifty knight moves that returns to the initial position. Let's say (very conservatively) that there are a hundred such sequences (there are surely millions or more). That means that, for every position reachable from the initial position without spurious knight moves, there are at least a hundred other ways to reach that position. In other words, at most 1% of positions generated in this way can be unique. In fact, the fraction will be much smaller than that: even moving just those two pawns, there are at least twelve ways of getting white pawns to e4 and d4, even without moving any other pieces.
| Certainly the average number of choices per player per move is less than 125. The vast majority of gfames would require less than 100 moves. Each move is 2 half moves. The answer must be less than 125^200= (1000/4)^200 = 10^600/2^400 = 10^600/(1024^40) < 10^600/10^120 = 10^480 |
Eep.
1) You assume that a product of k numbers is equal to the kth power of their arithmetic mean: this is not true. Suppose we play a game where there are four possible first moves and ten possible second moves and all combinations lead to distinct positions. Thus, there are forty possible positions. However, your argument is that there are, on average six possibilities at each stage and there are two moves, so there are 6^2 = 36 possible positions. So, not only is the kth power of the mean not equal to the product; it is not even an upper bound on the product.
2) You have truncated a diverging sequence. You counted only the number of games up to length 200 ply. But there are 125 times as many games of 201 ply as there are of 200. And 125x125 times more of length 202 ply. And so on. Every time you add an extra ply, the number of possibilities gets exponentially bigger. You cannot truncate the sequence at any point and claim that the sum of your truncated sequence is the correct answer.
3) You have underestimated a quantity in two different ways and then claimed that the calculation gives an upper bound.
| I assert that the number of unique positions is greater than 10^130 but less than 10^480 |
No, it's much smaller than 10^130. There are 64 squares on a chessboard. Each one of those is either empty, or has one of twelve types of piece on it (white king, black king, white queen, black queen, ...). Thus, there are 13^64 ways of arranging a large supply of chess pieces on a chess board. It can be either white or black to move, giving a factor of two increase. Each player either can or cannot castle in each direction, giving a factor of 16. There are nine possibilities for the en passant square (a-file, b-file, ..., or none). We should perhaps also factor in the number of times the position has occurred before (zero, one, or at least two) and the number of half-moves since the last pawn move or capture (1, 2, ..., 98, at least 99), since these affect whether a player can claim a draw.
This gives an absolute upper bound of 13^64 x 2 x 16 x 9 x 3 x 99, which is about 1.7x10^76. Note that this includes all kinds of junk such as the `position' where every square has a white king on it and black can castle queenside and capture en passant to e3.
| Somebody sould over me a job. |
I don't think your post is a very good advert if you're looking for a job using maths or physics. Sorry.
|
|
|
Richerby: I think your calculations prove, in fact, that the maximum number of positions in chess is less than 1.7X10^76.
However, I dont agree with you in the following factors you included:
1) the factor of 3 to include the number of times the position has occured before: if a a position has occured before it should count only once.
2) the factor of 99 related with the number of half-moves since the last pawn move or capture: like you very well said, we are counting positions and not moves.
If we exclude this two factors we can calculate 13^64 x 2 x 16 x 9, and say that the number of positions is less than 5,6x10^73.
This still includes a very big lot of impossible positions, perhaps most of them.
Challenge: can someone narrow down this number and get it as near has possible to the exact number?
Phystutordotcom: If you achieve to calculate the exact number of positions ill recomend you for a job in NASA (even tough I dont know anybody there)
|
| Previous 1 2 3 4 5 6 7 8 Next |
|
|
|
