/* 2006oct - Alain Brobecker */
/* 0: empty, 1:black, 2:white, so 3-player gives value for opponent */
/*halfmove;games;different pos;single pos;
  0;1;1;1;
  1;4;4;4;
  2;12;12;12;
  3;56;54;52;
  4;244;236;228;
  5;1396;1288;1192;
  6;8200;7092;6160;
  7;55092;42614;33344;*/   

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

#define MaxPly 8
#define MaxPosNb 600000

/**** Global variables ****/
int LegalMove;
unsigned char PlayerToMove;

/* This routine check in A if pawn (x,y) can capture oppenent's pawns
   in direction (dx,dy), and in such case sets A accordingly. */
void TestOneDir(x,y,dx,dy,A) int x,y,dx,dy; unsigned char A[10][10];{
  int x2,y2;
  x2=x;
  y2=y;
  while(A[x2+dx][y2+dy]==3-PlayerToMove) { x2+=dx; y2+=dy; }
  if((x2!=x) || (y2!=y)) { /* opponent has pawn(s) in this direction? */
    if(A[x2+dx][y2+dy]==PlayerToMove) { /* surrounded by player's? */
      LegalMove=TRUE;
      while(A[x2][y2]==3-PlayerToMove) {
        A[x2][y2]=PlayerToMove;
        x2-=dx;
        y2-=dy;
      }
    }
  }
}

/**** Print 8*8 central part of a 10*10 board ****/
void PrintBoard(A) unsigned char A[10][10]; {
  int x,y;
  for(y=1;y<9;y++) {
    for(x=1;x<9;x++) {
      switch(A[x][y]) {
        case 0:printf("."); break;
        case 1:printf("X"); break;
        case 2:printf("O"); break;
        default:printf("!!!error");
      }
    }
    printf("\n");
  }
}

/**** Copy a 10*10 board to another ****/
void CopyAToB(A,B) unsigned char A[10][10], B[10][10]; {
  int x,y;
  for(y=0;y<10;y++) { for(x=0;x<10;x++) { B[x][y]=A[x][y]; } }
}

/**** Packs 8*8 central part of a 10*10 board into 16 bytes ****/
void PackPosition(A,B) unsigned char A[10][10], B[]; {
  int x,y,i;
  unsigned char c;
  i=0;
  for(y=1;y<9;y++) {
    c=0; for(x=1;x<5;x++) { c=(c<<2)+A[x][y]; } B[i++]=c;
    c=0; for(x=5;x<9;x++) { c=(c<<2)+A[x][y]; } B[i++]=c;
  }
}

/**** Unpacks 16 bytes position into 8*8 central part of a 10*10 board ****/
void UnpackPosition(A,B) unsigned char A[],B[10][10]; {
  int x,y,i;
  unsigned char c;
  i=0;
  for(y=1;y<9;y++) {
    c=A[i++]; for(x=4;x>0;x--) { B[x][y]=c&3; c=c>>2; }
    c=A[i++]; for(x=8;x>4;x--) { B[x][y]=c&3; c=c>>2; }
  }
}

/**** Compare two 16 bytes positions ****/
int ComparePositions(A,B) unsigned char A[],B[]; {
  int c=0;
  int same=TRUE;
  while((c<16) && (same==TRUE)) { if(A[c]!=B[c]) { same=FALSE; } c++; }
  return(same);
}

/********************************************************************** MAIN */
int main() {
  unsigned char Board[10][10],NewBoard[10][10];
  unsigned char *Pos;
  /*unisgned char *Status; !!!To keep track of passed moves, draw, win...*/
  unsigned int *Occurences;
  int x,y,Ply,SrcPos,DestPos,CmpPos,SamePos,NbPos,NbSinglePos,NbLegalMoves;
  int StartPos[MaxPly+1];

  setbuf(stdout, NULL); /* no buffering for output! */
  
  Pos=(unsigned char *) malloc((unsigned int) MaxPosNb*16);
  Occurences=(unsigned int *) malloc((unsigned int) MaxPosNb*sizeof(unsigned int));
  printf("%d\n",(unsigned int) sizeof(unsigned int));
  
  /**** Initial position ****/  
  Pos[0]=0;  Pos[1]=0; Pos[2]=0;  Pos[3]=0;
  Pos[4]=0;  Pos[5]=0; Pos[6]=2;  Pos[7]=64;
  Pos[8]=1;  Pos[9]=128; Pos[10]=0; Pos[11]=0;
  Pos[12]=0; Pos[13]=0;  Pos[14]=0; Pos[15]=0;
  StartPos[0]=0;
  StartPos[1]=1;
  Occurences[0]=1;

  PlayerToMove=1;
  for(y=0;y<10;y++) { for(x=0;x<10;x++) { Board[x][y]=0; NewBoard[x][y]=0; } }

  for(Ply=1;Ply<MaxPly+1;Ply++) {
    NbPos=0;
    DestPos=StartPos[Ply];
    for(SrcPos=StartPos[Ply-1];SrcPos<StartPos[Ply];SrcPos++) {
      NbLegalMoves=0;
      UnpackPosition(Pos+(SrcPos<<4),Board);
      CopyAToB(Board,NewBoard);
      for(y=1;y<9;y++) {
        for(x=1;x<9;x++) {
          if(Board[x][y]==0) {
            LegalMove=FALSE;
            TestOneDir(x,y,0,1,NewBoard);
            TestOneDir(x,y,1,1,NewBoard);
            TestOneDir(x,y,1,0,NewBoard);
            TestOneDir(x,y,1,-1,NewBoard);
            TestOneDir(x,y,0,-1,NewBoard);
            TestOneDir(x,y,-1,-1,NewBoard);
            TestOneDir(x,y,-1,0,NewBoard);
            TestOneDir(x,y,-1,1,NewBoard);
            if(LegalMove==TRUE) {
              NbLegalMoves++;
              NbPos+=Occurences[SrcPos];
              NewBoard[x][y]=PlayerToMove;
              PackPosition(NewBoard,Pos+(DestPos<<4));
              if((x==1) && (y==1)) {
                printf("Taking corner (%d,%d)\n",x,y);
                PrintBoard(NewBoard); }
              /* test if the position already exists */
              SamePos=-1;
              CmpPos=StartPos[Ply];
              while((CmpPos<DestPos) && (SamePos==-1)) {
                if(ComparePositions(Pos+(DestPos<<4),Pos+(CmpPos<<4))==TRUE) {
                  SamePos=CmpPos;
                }
                CmpPos++;
              }
              if(SamePos==-1) {
                /* insert as new position */
                Occurences[DestPos]=Occurences[SrcPos];
                DestPos++;
              } else {
                /* actualise already existing position */
                Occurences[SamePos]+=Occurences[SrcPos];
              }
              CopyAToB(Board,NewBoard);
            }
          }
        } /*next x*/
      } /*next y*/
      if(NbLegalMoves==0) {
        printf("NoLegalMoves (%d,%d)\n",x,y);
        PrintBoard(NewBoard);
        /* !!! here copy the position anew and mark last move as passed, unless
           previous move was already passed, in such case game is finished & draw. */
      }
    } /*next SrcPos*/
    StartPos[Ply+1]=DestPos;
    NbPos=0;
    NbSinglePos=0;
    for(SrcPos=StartPos[Ply];SrcPos<DestPos;SrcPos++) {
      NbPos+=Occurences[SrcPos];
      if(Occurences[SrcPos]==1) { NbSinglePos++; }
    }
    printf("halfmove %d: %d games, %d different positions, %d single positions\n",Ply,NbPos,DestPos-StartPos[Ply],NbSinglePos);
    PlayerToMove=3-PlayerToMove;
  } /*next Ply*/
  return(0);
}