[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.