Shortest Reversi game on boards 7x7 and larger

After only 9 half-turns the shortest game ends 13:0. On an 8x8 or larger board neither player reaches the edge of the board. There are actually many different games that end 13:0. There are even more that end 0:14 for player 2. But there are none that are shorter.

Here is one 13:0 game that I played in KReversi.

Player 1 wins Reversi-5x5

If player 1 plays a perfect game (s)he will always win, regardless of how well player 2 plays. 5x5 is the smallest board size that player 1 can win under perfect play. Player 2 will win on 4x4 or 3x3 boards, as mentioned in this blog before.

Perfect Play

To determine the outcome of perfect play on both sides I keep track at each iteration if
-- any of the possible moves lead to the player winning whose turn it is or
-- all of the possible moves lead to the other player winning.
Otherwise it will be a tie.

The modified program to do this is here. It also writes to a log file periodically, so I know what is going on and can maybe estimate how long it will take to complete.

With this program I verified that on 3x3 and 4x4 boards player 2 wins under perfect play. I will get the result for 5x5 in roughly 8 days.

#include <iostream>
#include <fstream>

using std::min; using std::max;

static std::ofstream* of;
static long uninum;

class versibrd
{
public:

  versibrd();
  versibrd(versibrd const& bd);

  static const int size=5; // <-- CHANGE BOARD SIZE HERE
  static int fieldfromrowcol(int const r, int const c) {return r*size+c;}

  bool put(const int f) {return possible(f/size, f%size, true);}
  int getvalid(int* flist);
  int score(int& p1, int& p2);
  long long recurse(int const m, int& bw);

private:
  void skip() {++t;}; // skip move. Only legal if no valid moves are available
  bool possible(int r, int c, bool doturn); // execute move if doturn is true

  unsigned int t; // half-turn of the game.
  char b[size][size];
  long unum;
};

class scorekeeper
{
public:
  scorekeeper() {memset(s,0,(versibrd::size*versibrd::size+1)*
                        (versibrd::size*versibrd::size+1)*sizeof(long long));}
  void keep(int a,int b) {++s[a][b];}
  void print();

private:
  long long s[versibrd::size*versibrd::size+1][versibrd::size*
                                               versibrd::size+1];
};

static scorekeeper* scor;

void scorekeeper::print()
{
  long long total = 0;
  long long ma = 0;
  std::cout << "Dump of score matrix:" << std::endl;
  for (int i=0;i!=versibrd::size*versibrd::size+1;++i) {
    std::cout << "Row " << i << std::endl;
    for (int j=0;j!=versibrd::size*versibrd::size+1;++j) {
      std::cout << s[i][j] << "\n";
      total += s[i][j];
      if (s[i][j] > ma) ma = s[i][j];
    }   
  }
  std::cout << "Maximum entries per bin : " << ma << "\n"
            << "Total entries : " << total << "\n"
            << "End of score dump." << std::endl;
}

versibrd::versibrd(): t(0)
{
  unum = ++uninum;
  memset(b,0,size*size*sizeof(char));

  if (size%2 == 0) {//even size
    b[size/2-1][size/2-1]=2;
    b[size/2-1][size/2]=1;
    b[size/2][size/2-1]=1;
    b[size/2][size/2]=2;
  } else {// odd size
    b[size/2][size/2]=2;
    b[size/2][size/2+1]=1;
    b[size/2+1][size/2]=1;
    b[size/2+1][size/2+1]=2;
  }
}

versibrd::versibrd(versibrd const& bd) : t(bd.t) {
  memcpy(b,bd.b,size*size*sizeof(char));
  unum = ++uninum;
}

bool versibrd::possible(int r, int c, bool doturn)
{
  bool poss = false;
  int me = t%2+1;
  int s = size;
  for (int i = max(0,r-1); i!=min(r+2,s); ++i)
    for (int j = max(0,c-1); j!=min(c+2,s); ++j) {
      if (me + b[i][j] != 3) continue; // adjacent field has same color
      // Ok, now see if there is one of me somewhere behind that one.
      int dr = i-r;
      int dc = j-c;
      int nf = 1;
      int rr = r+dr;
      int cc = c+dc;
      while ( rr >= 0 && rr < size &&
              cc >= 0 && cc < size &&
              b[rr][cc] + me == 3 ) {
        rr += dr;
        cc += dc;
        ++nf;
      }
      if (b[rr][cc] == 0 || //empty field behind
          rr < 0 || rr >= size || cc < 0 || cc >= size
          //opponent color to edge of board
      ) continue;

      // Ok, flip these.
      if (doturn) {
        for (int n = 0; n != nf; ++n) {
          b[r+n*dr][c+n*dc]=me;
        }
      poss = true;
      }
      else return true; // Don't need to check other directions
    }
  if (poss && doturn) ++t;
  return poss;
}

int versibrd::getvalid(int* flist)
//Must be called with array of size (size*size)
{
  memset(flist,0,size*size*sizeof(int));
  int n = 0;
  for (int r=0; r!=size; ++r)
    for (int c=0; c!=size; ++c) {
      if ( b[r][c] != 0) continue;
      if (possible(r, c, false)) *(flist+(n++)) = (r*size+c);
    }
  return n;
}

long long versibrd::recurse(int const m, int& bw)
//return number of completions of game tree
{
  put(m); //play move given from previous iteration
  long long ret = 0;

  int vm[size*size]; // list of valid moves
  int imax = getvalid(vm);
  if (! imax) {
    skip();
    imax = getvalid(vm);
    if (! imax ) {
      int a,b;
      bw = score(a,b);
      scor->keep(a,b);
      return 1;
    }
  }

  if (t<10) *of << "At " << this->t << " to " << imax << "." <<unum<< std::endl;
  else if (unum%1000 == 0) *of << "At " << t << " unum " << unum << std::endl;

  int perf = -1;
  bw = -1;
  int me = t%2+1;
  bool opponentwins = true;
  for (int i = 0; i!=imax; ++i) {
    // need to check which player is on?
    ret += versibrd(*this).recurse(vm[i], perf);
    if (me == perf) bw = perf; //This move guarantees this player to win
    if (me+perf!=3) opponentwins = false;
  }

  if (bw == -1) bw = (opponentwins ? bw = 3-me : 0);
  
  return ret;
}

int versibrd::score(int& p1, int& p2)
{
  p1=0;
  p2=0;
  for (int r=0; r!=size; ++r) {
    for (int c=0; c!=size; ++c) {
      if ( b[r][c] == 1) ++p1;
      if ( b[r][c] == 2) ++p2;
    }
  }
  return (p1-p2==0 ? 0 : (p1>p2 ? 1 : 2));
}


int main()
{
  versibrd vb;

  of = new std::ofstream("perfplaylog.txt");
  uninum = 0;
  scor = new scorekeeper();

  int perfplay;
  int m[versibrd::size*versibrd::size]; // list of moves

  std::cout << "On a " << versibrd::size << "x" << versibrd::size
        <<" board there are ..." << std::endl;
  vb.getvalid(m);
  std::cout << "..." << vb.recurse(m[0],perfplay) << " possible games." << std::endl;

  scor->print();

  std::cout << "Perfect play: " << perfplay << ", i.e.: Under perfect play ";
  if (perfplay == 0 ) std::cout << "it is a tie." << std::endl;
  else std::cout << "Player " << perfplay << " wins." << std::endl;

  of->close();

  return 0;
}

short games on a 6x6 board

This plot shows the scores for Reversi 6x6 games that end after 14 or fewer half-turns. The shortest games end 13:0, i.e. after 9 half-turns.

The full table of all Reversi-6x6 results will have more numbers to the top and right, but it will contain the same data as this table in the lower left, where (Player1 score + Player2 score) < 19.

Reversi-5x5 results plot

Here is the plot of all Reversi-5x5 game scores:

Click on the image to get a larger, readable version.

Reversi-5x5 games

There are 189,174,688,641 distinct games on a 5x5 sized board. Half of these games end with one of the 8 scores from 11:14 to 18:7, all of these scores resulting for 10.3 to 14.75 billion games. There are a lot more games that player 1 wins than games that player 2 wins.

My histograms have a maximum bin content of 2 billion events (32 bit integer), so I can't plot this without making some changes first.

The shortest games end after nine disks are played with scores of 13:0 (8 times), 12:1 (once), followed by games ending in 14:0 (once) and 6:8 (4 times).

Reversi-4x4 games

On a 4x4 board things get a little more intersting than on the 3x3 board.
Most of all the possible games end in a tie (8:8, the red field in the center) or with one player winning by a narrow margin (9:7, 7:9, or 6:10, the red and orange fields).
But there is also one possible game that ends with much of the board still empty, player 1 winning 9:1. I guess player 2 will not play that bad in any real game, but it is a possible outcome that does not violate any rules of the game. Here is that game in detail:

Reversi-3x3 games

The ROOT software is great to make histograms and plots of data.

Here is a plot showing the scores of all possible games on a 3x3 board. There are 8 entries in the histogram, one for each of the possible different games. For all entries player 2 wins. In four of the possible games the board is completely filled with 9 disks of player 2 in the end (represented by the red square in the histogram). For three of the possible games player 2 has eight disks on the board in the end and one field is left empty (yellow square in the histogram). And there is only one game that ends with the board containing eight disks of player 2 and one disk of player one. None of the other combinations are possible.



And here is the ROOT macro that generated the plot:

void p(char* fname) {
  gStyle->SetPalette(1);
  gStyle->SetOptStat(0);
  gStyle->SetCanvasColor(0);
  gStyle->SetCanvasBorderMode(0);
  gStyle->SetCanvasBorderSize(0);
  gStyle->SetTitleFillColor(0);
  gStyle->SetTitleBorderSize(1);
  ifstream in;
  in.open(fname);

  string s;
  int r,c;
  long n;
  TH2F *h2 = new TH2F("h2","Scores for Reversi games;Player 1; Player 2",
                      37,-0.5,36.5,
                      37,-0.5,36.5);
 
  while (s!="Row") {
    in >> s;
    //cout << s << endl;
    if (!in.good()) break;
  }
  s = "";
  while (s!="Maximum") {
    c = 0;
    in >> r;
    cout << "Reading row " << r << endl;
    in >> s;
    while (!(s=="Row" || s=="Maximum")) {
      n = atoi(s.c_str());
      h2->Fill(r,c,n);
      //cout << r << c << n << endl;
      ++c;
      in >> s;
    }
  }
  in.close();
  TCanvas* cnv = new TCanvas("c","cnv",400,400);
  h2->GetXaxis()->SetRange(0,c);
  h2->GetYaxis()->SetRange(0,c);
  stringstream t;
  int size = (int)sqrt(c);
  t << "Scores for Reversi-" << size << "x" << size;
  h2->SetTitle(t.str().c_str());
  h2->Draw("colz");
}

Source code to determine number of possible games

Here is the program I used to generate the numbers quoted in the previous post. I actually had a little bug, so this post is corrected.
(Under Linux just save this as prog.cc and build with g++ prog.cc, then run with ./a.out. It will probably run with different OS and/or compiler, too.)

#include <iostream>

using std::min; using std::max;

class versibrd
{
public:

  versibrd() {clear();}

  static const int size=3; // <-- CHANGE BOARD SIZE HERE
  static int fieldfromrowcol(int const r, int const c) {return r*size+c;}

  bool put(const int f) {return possible(f/size, f%size, true);}
  int getvalid(int* flist);
  void score(int& p1, int& p2);
  long long recurse(int m);

private:
  void clear(); //initiallize & clear board
  void skip() {++t;}; // skip move. Only legal if no valid moves are available
  bool possible(int r, int c, bool doturn); // execute move if doturn is true

  unsigned int t; // half-turn of the game. This is redundant with board.
  char b[size][size];
};

class scorekeeper
{
public:
  scorekeeper() {memset(s,0,(versibrd::size*versibrd::size+1)*
                        (versibrd::size*versibrd::size+1)*sizeof(long long));}
  void keep(int a,int b) {++s[a][b];}
  void print();

private:
  long long s[versibrd::size*versibrd::size+1][versibrd::size*
                                               versibrd::size+1];
};

static scorekeeper* scor;

void scorekeeper::print()
{
  long long total = 0;
  long long ma = 0;
  std::cout << "Dump of score matrix:" << std::endl;
  for (int i=0;i!=versibrd::size*versibrd::size+1;++i) {
    std::cout << "Row " << i << std::endl;
    for (int j=0;j!=versibrd::size*versibrd::size+1;++j) {
      std::cout << s[i][j] << "\n";
      total += s[i][j];
      if (s[i][j] > ma) ma = s[i][j];
    }   
  }
  std::cout << "Maximum entries per bin : " << ma << "\n"
            << "Total entries : " << total << "\n"
            << "End of score dump." << std::endl;
}

void versibrd::clear()
{
  t = 0;
  memset(b,0,size*size*sizeof(char));

  if (size%2 == 0) {//even size
    b[size/2-1][size/2-1]=2;
    b[size/2-1][size/2]=1;
    b[size/2][size/2-1]=1;
    b[size/2][size/2]=2;
  } else {// odd size
    b[size/2][size/2]=2;
    b[size/2][size/2+1]=1;
    b[size/2+1][size/2]=1;
    b[size/2+1][size/2+1]=2;
  }
}

bool versibrd::possible(int r, int c, bool doturn)
{
  bool poss = false;
  int me = t%2+1;
  int s = size;
  for (int i = max(0,r-1); i!=min(r+2,s); ++i)
    for (int j = max(0,c-1); j!=min(c+2,s); ++j) {
      if (me + b[i][j] != 3) continue; // adjacent field has same color
      // Ok, now see if there is one of me somewhere behind that one.
      int dr = i-r;
      int dc = j-c;
      int nf = 1;
      int rr = r+dr;
      int cc = c+dc;
      while ( rr >= 0 && rr < size &&
              cc >= 0 && cc < size &&
              b[rr][cc] + me == 3 ) {
        rr += dr;
        cc += dc;
        ++nf;
      }
      if (b[rr][cc] == 0 || //empty field behind
          rr < 0 || rr >= size || cc < 0 || cc >= size
          //opponent color to edge of board
      ) continue;

      // Ok, flip these.
      if (doturn) {
        for (int n = 0; n != nf; ++n) {
          b[r+n*dr][c+n*dc]=me;
        }
      poss = true;
      }
      else return true; // Don't need to check other directions
    }
  if (poss && doturn) ++t;
  return poss;
}

int versibrd::getvalid(int* flist)
//Must be called with array of size (size*size)
{
  memset(flist,0,size*size*sizeof(int));
  int n = 0;
  for (int r=0; r!=size; ++r)
    for (int c=0; c!=size; ++c) {
      if ( b[r][c] != 0) continue;
      if (possible(r, c, false)) *(flist+(n++)) = (r*size+c);
    }
  return n;
}

long long versibrd::recurse(int m) //return number of completions of game tree
{
  put(m); //play move given from previous iteration
  long long ret = 0;

  int vm[size*size]; // list of valid moves
  int imax = getvalid(vm);
  if (! imax) {
    skip();
    imax = getvalid(vm);
    if (! imax ) {
      int a,b;
      score(a,b);
      scor->keep(a,b);
      return 1;
    }
  }

  for (int i = 0; i!=imax; ++i) {
    ret += versibrd(*this).recurse(vm[i]);
  }
  return ret;
}

void versibrd::score(int& p1, int& p2)
{
  p1=0;
  p2=0;
  for (int r=0; r!=size; ++r) {
    for (int c=0; c!=size; ++c) {
      if ( b[r][c] == 1) ++p1;
      if ( b[r][c] == 2) ++p2;
    }
  }
}


int main()
{
  versibrd vb;

  scor = new scorekeeper();

  int m[versibrd::size*versibrd::size]; // list of moves

  std::cout << "On a " << versibrd::size << "x" << versibrd::size
        <<" board there are ..." << std::endl;
  vb.getvalid(m);
  std::cout << "..." << vb.recurse(m[0]) << " possible games." << std::endl;

  scor->print();

  return 0;
}

As given above, it prints out the number of possible games and then a matrix of how the games are scored.
The matix can be visualized with external software. I did not want to bloat this program with any dependencies.

This program does not give any information on who wins under perfect play. Maybe I will look at that later.

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.