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.