board.cpp

学习 open inventor 的例子

          n = solutionSpace[i][0];
          solutionSpace[i][++n]=j;
          solutionSpace[i][0]=n;
        }
      }
    }
  }
}

Board::Board()
{
  clear();
}

Board::~Board()
{
}

void
Board::clear()
{
  for (int k=0;k<4;k++)
    for (int j=0;j<4;j++)
      for (int i=0;i<4;i++)
        this->setToken(i,j,k,NONE);
}

// Returns first available slot (height) or -1
int
Board::checkPosition(int x, int y)
{
  if (x<0 || x>3 || y<0 || y>3) return -1;
  
  for (int z=0;z<4;z++) {
    if (this->getToken(x,y,z)==NONE) return z;
  }
  return -1;
}

//
// Check if col har all 4 indices covered
//
bool
Board::check(Token col, int i1, int i2, int i3, int i4)
{
  if (!(this->board[i1]&col)) return false; 
  if (!(this->board[i2]&col)) return false; 
  if (!(this->board[i3]&col)) return false; 
  if (!(this->board[i4]&col)) return false; 
  return true;
}

//
// Returns the indices making up solution sol
//
void 
Board::getSolution(int sol, int& i0, int& i1, int& i2, int& i3)
{
  if (sol>=0) {
    i0 = sboard->solutions[sol][0];
    i1 = sboard->solutions[sol][1];
    i2 = sboard->solutions[sol][2];
    i3 = sboard->solutions[sol][3];
  }
}

//
// Checks if a winning condition occured after placing a token of
// color col at position x,y,z. Returns the solution index in solution.
//
bool
Board::validate(int x, int y, int z, Token col, int& solution)
{
  int idx = index(x,y,z);
  int num = sboard->solutionSpace[idx][0];
  for (int i=1;i<=num;i++) {
    int sol = sboard->solutionSpace[idx][i];
    if (check(col,
              sboard->solutions[sol][0],
              sboard->solutions[sol][1],
              sboard->solutions[sol][2],
              sboard->solutions[sol][3])) {
      solution=sol;
      return true;
    }
  }
  return false;
}

//
// Calculates heurestic for current board seen from col when col 
// have just placed his token at x,y,z.
//
int
Board::heurestic(Token col, int x, int y, int z)
{
  /* Scores (first is best)
     O 4-in-a-row
     O Blocked other player's 3-in-a-row
     o FIXME: 2 times 3-in-a-row w/last places available next round (winning move)
     o 3-in-a-row w/last place available next round (forces opponent)
     o 3-in-a-row w/last place !available next round (positioning)
     o Maximize 2-in-a-row's
       - Crossing 2-in-a-row where cross is available is good
     o Crossing 1-in-a-row where cross is available is good
     o Corner z=0/3 (check avail.)
     o Inner z=1/2 (check availability)
   */


  // Calculate total score of board
  int hsums[76]; // One sum for each solution
  int score=0;
  for (int i=0;i<76;i++) {
    hsums[i]=0;
    int colidx=-1;
    int availableNow=0;
    int availableLater=0;
    for (int j=0;j<4;j++) {
      int solidx = sboard->solutions[i][j];
      int val = this->board[solidx]&(RED|BLUE);
      hsums[i] += val;
      if (hsums[i]==col) colidx=j;
      if (val==NONE) {
        int solx = GET_X(solidx);
        int soly = GET_Y(solidx);
        int solz = GET_Z(solidx);
        if (checkPosition(solx,soly)==solz) availableNow++;
        else availableLater++;
      }
    }
    if (hsums[i]==col*3 &&
             (availableNow+availableLater)>=1) score+=0x00100000;
    else if (hsums[i]==col*2 &&
             (availableNow+availableLater)>=2) score+=0x0000100;
    else if (hsums[i]==col &&
             (availableNow+availableLater)>=3) {
      
      int idx = sboard->solutions[i][colidx];
      int cx = GET_X(idx);
      int cy = GET_Y(idx);
      int cz = GET_Z(idx);
      if (isCorner(cx,cy,cz)) score+=0x0000010;
      else if (isInner(cx,cy,cz)) score+=0x0000010;
      else score+=0x0000001;
    }
  }

  // Quick check for winner & forced moves
  {
    Token othercol = col==RED?BLUE:RED;
    bool forced=false;
    int idx = index(x,y,z);
    int num = sboard->solutionSpace[idx][0];
    for (int i=1;i<=num;i++) {
      int sol = sboard->solutionSpace[idx][i];
      if (hsums[sol]==col*4) return HEUR_WINNER;
      else if (hsums[sol]==othercol*3+col) forced=true;
    }
    if (forced) return HEUR_FORCED;
  }

  // Check for potential crossing solutions
  {
    for (int i=0;i<64;i++) {
      int val = this->board[i]&(RED|BLUE);
      if (val==NONE) {
        int ones=0;
        int twos=0;
        int num = sboard->solutionSpace[i][0];
        for (int j=1;j<=num;j++) {
          int sol = sboard->solutionSpace[i][j];
          if (hsums[sol]==col*2) twos++;
          else if (hsums[sol]==col*1) ones++;
        }
        if ((ones+twos)>=2) {
          score += (twos*0x10+ones)*0x100;
        }
      }
    }
  }

  return score;

  #if 0
  // Quick check for winner & forced moves
  {
    Token othercol = col==RED?BLUE:RED;
    bool forced=false;
    int idx = index(x,y,z);
    int num = sboard->solutionSpace[idx][0];
    for (int i=1;i<=num;i++) {
      int sol = sboard->solutionSpace[idx][i];
      int tmp=0;
      int availableNow=0;
      int availableLater=0;
      for (int j=0;j<4;j++) {
        int solidx = sboard->solutions[sol][j];
        int val = this->board[solidx]&(RED|BLUE);
        tmp += val;
        if (val==NONE) {
          int solx = GET_X(solidx);
          int soly = GET_Y(solidx);
          int solz = GET_Z(solidx);
          if (checkPosition(solx,soly)==solz) availableNow++;
          else availableLater++;
        }
      }
      if (tmp==col*4) return HEUR_WINNER;
      else if (tmp==othercol*3+col) forced=true;
    }
    if (forced) return HEUR_FORCED;
  }

  // Calculate total score of board
  int score=0;
  for (int i=0;i<76;i++) {
    int tmp=0;
    int colidx=-1;
    int availableNow=0;
    int availableLater=0;
    for (int j=0;j<4;j++) {
      int solidx = sboard->solutions[i][j];
      int val = this->board[solidx]&(RED|BLUE);
      tmp += val;
      if (tmp==col) colidx=j;
      if (val==NONE) {
        int solx = GET_X(solidx);
        int soly = GET_Y(solidx);
        int solz = GET_Z(solidx);
        if (checkPosition(solx,soly)==solz) availableNow++;
        else availableLater++;
      }
    }
    if (tmp==col*3 &&
             (availableNow+availableLater)>=1) score+=0x00100000;
    else if (tmp==col*2 &&
             (availableNow+availableLater)>=2) score+=0x0000100;
    else if (tmp==col &&
             (availableNow+availableLater)>=3) {
      
      int idx = sboard->solutions[i][colidx];
      int cx = GET_X(idx);
      int cy = GET_Y(idx);
      int cz = GET_Z(idx);
      if (isCorner(cx,cy,cz)) score+=0x0000010;
      else if (isInner(cx,cy,cz)) score+=0x0000010;
      else score+=0x0000001;
    }
  }

  return score;
#endif
}

//
// private methods
//

bool
Board::isCorner(int x, int y, int z)
{
  if ((x==0 || x==3) && (y==0 || y==3) && (z==0 || z==3)) return true;
  return false;
}

bool
Board::isInner(int x, int y, int z)
{
  if (x>0 && x<3 && y>0 && y<3 && z>0 && z<3) return true;
  return false;
}