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.

Counting the number of distinct NxN Reversi games

The Reversi board looks symmetric at the start of a game. It can be rotated by half a turn or reflected at the diagonal and will look the same.

For the first move black can play four positions as shown here for a 6x6 board:

But no matter where black chooses to put the disk, I can rotate the board and/or look at it in a mirror, and it will look as if black put the disk on the field in the third row, second column.
So, without loss of generality, we may as well assume that black always plays that position! This breaks all ambiguities. There are no symmetries after the first move.

In general, on a NxN board I assume that black always plays in the field with the lowest column number first. On a board with even N that is column (N/2)-1, row N/2. For boards with odd N it is column (N-1)/2, row (N+1)/2. (For the odd N boards the game will be different if black plays on one of the sides with fewer fields to the edge of the board. Nonetheless, I will only consider the first move for black as described above.)

After the first move on a 6x6 board, the board will look like this:

Boards of size N by N

The normal Reversi is played on 8x8 boards. In general the board can be larger or smaller, for example 10x 10 or 6x6 fields.

It could be rectangular, NxM fields, for example 6x10. Even stranger shapes could be imagined. On all these boards the rules would be exactly the same as for Reversi on 8x8 boards. The initial four disks on the board should be in the center of the board. For some odd shapes the center may not be easy to define. I will not consider anything other than square boards here. I will consider boards of NxN for odd numbers, e.g. the 5x5 board. In that case the four disks that are on the board at the start of the game are not quite in the center and have one more empty field towards two edges of the board than towards the other two edges.

The board at the start of a game for N=5 looks like this (Made using templates from Wikimedia commons, GNU-FDL):




Note that I label both columns and rows with numbers. I don't use letters for the column as is usual on a 8x8 board. Column 1 is always on the left and Row 1 always on the top.

Reversi

Reversi is a board game for two players also known as Othello. It is played on a board with 8 rows and 8 columns. The rules are quite simple. It can be played online in many places on the web, person against person or person against computer. Of course you can also play it using a chess board and a bunch of coins, head is white and tail is black.

Like many board games Reversi is difficult to win against a computer because - despite the simple rules - there are many possibilities for each move and it is hard to 'look ahead' as far as computers can do. But of course the computer can be set to play easy. Sometimes a game ends with much of the board left empty (when all pieces of one of the players are turned over). So what is the lowest number of game turns before a game can end this way?

Wikipedia has a good article on Reversi.
It includes the following passage: "Mathematically, Othello still remains unsolved. Experts have not yet figured out what the outcome of a game will be where both sides have perfect play. However, analysis of thousands of high-quality games (most of them computer-generated) has led to the conclusion that, on the standard 8-by-8 board, perfect play on both sides results in a draw. When generalizing the game to play on an n-by-n board, the problem of determining if the first player has a winning move in a given position is PSPACE-complete.^[4] On 4-by-4 and 6-by-6 boards under perfect play, the second player wins."

I wasted a few CPU cycles trying to verify that last statement, toy around with other questions, and look at n-by-n boards in general. This blog contains the results.