4 ms·

Not sure the universe is incapable of doing this. The number of states a chess field can have is 13. It's either empty or has one of the 6 different pieces in

Not sure the universe is incapable of doing this. The number of states a chess field can have is 13. It's either empty or has one of the 6 different pieces in black or white on it. So 13^64 is an upper limit for the number of positions. We could solve chess if we could put these 13^64 positions into a tree, right? 13^64 = 10^71. The number of atoms in the observable universe is estimated to be 10^80. So even the observable universe might be big enough to form this tree. Even if we use big clunky objects like atoms. We do not have any idea of the size of the unobservable universe. And I don't know how many states an atom can have. Who knows, maybe a single atom can solve chess if it's programmed correctly? According to quantum theory, pretty small objects like electrons can store and process an amazing (infinite?) amount of information in certain ways.

sjcsjc 12y ago
Hi no_gravity - you've used the word "estaminated" a couple of times. Just in case it's not a simple typo, the word you're after is "estimated".
- no_gravity 12y ago
  Thank you! Fixed it.
heeen 12y ago
I think you overestimated the possible chess positions by a couple orders of magnitude. You can't have a chess configuration with an arbitrary number of pieces.
- endeavour 12y ago
  Also there are restrictions on which pieces can be on which squares (for example: pawns can't move backwards)
- no_gravity 12y ago
  That's why I gave an upper bound, not an estimation.
Someone 12y ago
"So 13^64 is an upper limit for the number of positions." Your conclusion is correct by a huge margin but the argument is flawed. There is state that is not in the board position: - white or black to move? - is an en passant capture possible? - is castling still possible? - how many moves since the last lawn move or capture?
- lukev 12y ago
  All the non-board-state info of a chess game could be easily captured in, like, two bytes.
- no_gravity 12y ago
  You are right. If I count correctly, that's another 17 bit of information. If we make no effort to encode it efficiently. Let's say 10^6 additional states. That brings us to an upper limit of 10^77 states the board can be in. Still enough atoms in the observable universe to assign one to each state.
  - Someone 12y ago
    As I said "your conclusion is correct". I think you need fewer than 17 bits: 1 for "who is to move", 4 for castling, 6.6 for the 50 moves (100 ply) rule would leave less than 6 for en passant. There potentially are 7 possible en passant moves (white pawns at a5, c5, e5, g5 and black ones at b5, d5, f5, and h5 or vice versa), but all you need to store is "the n-th pawn just moved" with n in 0..8. That is just over 3 bits. There is a way more significant flaw in your logic, though: the "three times the same board position with the same player to move is a draw" rule. That explodes your estimate, as there could be (if we do not call in additional chess rules) up to 10^71 positions hat have been visited earlier. With that in mind, I am not sure your limit is correct. There are at most 96 pawn moves in a game (16 pawns walk in 6 moves to the other side of the board) and 30 captures (7 pieces each plus 8 promoted pawns each). With the 50-move rule, that gives at most 126 x 50 = 6300 moves in a game. Each move can be encoded in 12 bits (starting and ending square for white's and black's move), so we need 75600 bits. Taking 2^10 = 1000, that gives me 10^22680 possible games as an upper limit. That is different from what http://www.chess.com/article/view/the-open-file---is-chess-infinite http://www.chess.com/article/view/the-open-file---is-chess-i... or http://members.iinet.net.au/~ray/Chessgames.htm http://members.iinet.net.au/~ray/Chessgames.htm (several estimates) claim, but (if we assume that zero is a misprint) close to Hardy's upper limit, so at least I am in good company.

sjcsjc 12y ago

Hi no_gravity - you've used the word "estaminated" a couple of times. Just in case it's not a simple typo, the word you're after is "estimated".

no_gravity 12y ago
Thank you! Fixed it.

heeen 12y ago

I think you overestimated the possible chess positions by a couple orders of magnitude. You can't have a chess configuration with an arbitrary number of pieces.

endeavour 12y ago
Also there are restrictions on which pieces can be on which squares (for example: pawns can't move backwards)
no_gravity 12y ago
That's why I gave an upper bound, not an estimation.

Someone 12y ago

"So 13^64 is an upper limit for the number of positions." Your conclusion is correct by a huge margin but the argument is flawed. There is state that is not in the board position: - white or black to move? - is an en passant capture possible? - is castling still possible? - how many moves since the last lawn move or capture?

lukev 12y ago
All the non-board-state info of a chess game could be easily captured in, like, two bytes.
no_gravity 12y ago
You are right. If I count correctly, that's another 17 bit of information. If we make no effort to encode it efficiently. Let's say 10^6 additional states. That brings us to an upper limit of 10^77 states the board can be in. Still enough atoms in the observable universe to assign one to each state.
- Someone 12y ago
  As I said "your conclusion is correct". I think you need fewer than 17 bits: 1 for "who is to move", 4 for castling, 6.6 for the 50 moves (100 ply) rule would leave less than 6 for en passant. There potentially are 7 possible en passant moves (white pawns at a5, c5, e5, g5 and black ones at b5, d5, f5, and h5 or vice versa), but all you need to store is "the n-th pawn just moved" with n in 0..8. That is just over 3 bits. There is a way more significant flaw in your logic, though: the "three times the same board position with the same player to move is a draw" rule. That explodes your estimate, as there could be (if we do not call in additional chess rules) up to 10^71 positions hat have been visited earlier. With that in mind, I am not sure your limit is correct. There are at most 96 pawn moves in a game (16 pawns walk in 6 moves to the other side of the board) and 30 captures (7 pieces each plus 8 promoted pawns each). With the 50-move rule, that gives at most 126 x 50 = 6300 moves in a game. Each move can be encoded in 12 bits (starting and ending square for white's and black's move), so we need 75600 bits. Taking 2^10 = 1000, that gives me 10^22680 possible games as an upper limit. That is different from what http://www.chess.com/article/view/the-open-file---is-chess-infinite http://www.chess.com/article/view/the-open-file---is-chess-i... or http://members.iinet.net.au/~ray/Chessgames.htm http://members.iinet.net.au/~ray/Chessgames.htm (several estimates) claim, but (if we assume that zero is a misprint) close to Hardy's upper limit, so at least I am in good company.