Number of distinct NxN Reversi games

Now that I have explained how to count the number of possible games, here are the answers for a few low N:

Board size N	Number of possible games
1	0
2	0
3	8
4	15,015
5	189,174,688,641
6	a lot :)
7	a lot more :)

How about the classic N=8?

Nobody knows the exact number. Here is my attempt at an estimate and upper limit.

After that first move that breaks the symmetries on the board there are 59 empty fields. (The board has 8*8=64 fields and five fields now contain disks.) Ignoring that a game may end early when neither player has any valid moves left, each game will have 59 moves (half-turns).

With each half-turn the number of empty fields -- and thus the upper limit on the valid number of moves -- will be reduced by one. So a (way too large) strict upper limit on the number of valid games (also known as the game tree size) on an 8x8 board would be 59*58*57*....*3*2*1. That is 59! or 1.38683119 × 10⁸⁰. That is a large number. In general this simple upper limit for a board of size N is (N²-5)!.
The game tree size can be estimated more realistically by exponentiating the average number of possible moves by the number of half-turns (59 on the 8x8 board, or 58 because the last turn has only 1 choice). Estimating the average number of possible moves at each half-turn as 10 results in a game tree complexity of 10⁵⁸. That is still a large number. A third estimate uses the guess that there are ~10 moves in the game with 14 choices, 30 moves with 9 choices or less, and that all other moves have 4 choices or less. We get an upper limit on the number of legal games of 10¹⁴*30⁹*19⁴ or less than 10³³. This last estimate may be below the actual game tree size, but I think it is the closest to the true value. It is still a big number, but nowhere near as big as the first and second estimates given above.

The state space complexity of Reversi is lower. Each of N² fields can contain a white or black disk or be empty. Thus there are only 3^N*N different boards. This is just an upper limit. We know that the four center fields always contain disks. Also all the disks on the board must be connected. Even then it is not guaranteed that the state (a particular arrangement of disks on the board) can actually be reached from the starting position using only valid moves.

The count of all possible 8x8 boards is (a lot less than, because there are illegal configurations) 3⁵⁹ * 2⁵ bits of information. That is 452172354935639504152473954144 possibilities (4.5*10²⁹). This corresponds to 99 bits or 13 bytes. So, if we index all these possibilities, any game-position (after the first or the tenth turn) can be encoded in 13 bytes and if we have a table or database with 452172 yotta rows of information, we could look up the best next move or who will win the game under perfect play. It clearly exceeds present computer capabilities to have the complete table.

Note that more practically a single state, one position on the 8x8 board, can be encoded in 59*2+5*1=123 bits or 16 bytes. (We could use 8 bytes each for bit patterns of white and black disks, respectively.)
A single game can be encoded by noting for each turn the board position that is played. A simple encoding uses board position numbered from 1 to 64 by row and column. We don't need numbers for the fields already occupied at the start. So, after forcing the first move to break symmetry (no need to encode that), the second move (the first move where there is any real choice) is encoded by a number between 1 and 59. We can then re-number the empty fields left on the board from top left to bottom right and encode the second move in a number between 1 and 58. Continuing in this way, after each turn re-numbering only the empty fields, we can encode a complete game in 291 bits, using 6 bits for the first 59-32=27 moves, 5 bits for the 16 moves 28 to 43, 4 bits for moves 44 to 51, 3 bits for moves 52 to 55, 2 bits for moves 56 and 57, and 1 bit for move 58. If a game ends with fewer than 59 moves, the remaining bits are meaningless. The program can easily determine this situation.
The encoding can be refined to fit a single game in 36 bytes or less.