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.