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;
}