[no_gravity]

A little nitpicking: Everytime the author writes "infinite", a more accurate word would be "enough". For example:

    if you had infinite computing capacity,
    you could actually solve chess.

The statement is correct. But you do not necessarily need infinite capacity to solve chess. Just enough capacity.

Would be interesting to estimate how much capacity.

[_fizz_buzz_]

I think "infinite" was used in the engineering-sense of the word and not in the stricter mathematical-sense. For me, as an electrical engineer, infinity is often somewhere beyond 1 ms.

[howeman]

People write that chess has ~ 10^42 board positions. If you read the paper about solving checkers (which you should because it's excellent), they evaluated about sqrt(N) positions, and the final solution took cuberoot(N) board positions. IF that extrapolates to chess, it means that the weak solution would take 10^21 evaluations and 10^14 storage. That's big, but in the realm of feasibility.

[maaku]

More than you would have if the entire universe were transformed into computonium.

So effectively infinite.

[no_gravity]

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]

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]

Thank you! Fixed it.

[Someone]

"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?

[no_gravity]

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]

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-i... or 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.

[no_gravity]

Thinking about it again, maybe we don't need to encode off-the-board information in the tree at all.

The tree would start from the starting position and then branch out to all legal moves in each step. So each node in the tree would have the previous moves encoded in it's position in the tree.

So my initial upper limit of 10^71 nodes might hold true. No need to encode information about castling, black or white to move, en passant etc.

Repeat positions are another issue though. Do we have to encode them? My 10^71 tree would not contain them. At first I thought we can leave them out. Now I'm not so sure anymore.

A move that leads to a repeat position is certainly not necessary to win a game. You could play the winning moves right away.

But it can be necessary to force a draw. Hmm...

You might be right. Maybe the "repeat position" issue kills the upper limit of 10^71 nodes in the tree of chess moves. So we have to resort to your upper limit of 10^22680.

[lukev]

All the non-board-state info of a chess game could be easily captured in, like, two bytes.

[heeen]

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]

Also there are restrictions on which pieces can be on which squares (for example: pawns can't move backwards)

[no_gravity]

That's why I gave an upper bound, not an estimation.