/* Quick-and-dirty othello/reversi implementation by     */
/* Jesper Antonsson, jesan733@student.liu.se . Please    */
/* feel free to do whatever you like with it, no         */
/* restrictions.                                         */

/* Some modificications by David Bergkvist (DB)          */
/* davbe128@student.liu.se                               */


#include <stdio.h>

#define BLACK 1
#define WHITE -1
#define EMPTY 0

int fliplist[64][64];      // used in makeMove to remember enough to do unmakeMove
int ply;
int heur[64] = {32,  2,  4,  4,  4,  4,  2, 32,
                 2, -8, -2, -2, -2, -2, -8,  2,
                 4, -2,  1,  1,  1,  1, -2,  4,
                 4, -2,  1,  1,  1,  1, -2,  4,
                 4, -2,  1,  1,  1,  1, -2,  4,
                 4, -2,  1,  1,  1,  1, -2,  4,
                 2, -8, -2, -2, -2, -2, -8,  2,
                 32, 2,  4,  4,  4,  4,  2, 32};

// added by DB, used to check if we can move to corner square first
int moveOrder[60] = {0,7,56,63, 		      				// 32
		     2,3,4,5, 16,24,32,40, 23,31,39,47, 58,59,60,61,		// 4
		     1,6,8,15,48,55,57,62,					// 2
		     18,19,20,21, 26,29,34,37, 42,43,44,45,	                // 1
		     10,11,12,13, 17,25,33,41, 22,30,38,46, 50,51,52,53,	// -2
		     9,14,49,54};

long long nodecount;
int targetDepth;
int board[64];
int filledAtRoot;
int bestMove;
int pvmat[60][60];     // "triangular" array for PV storing

// sets up initial position
initEngine() {
  int i;

  ply = 0;
  nodecount = 0;
  for(i=0; i<64; i++) 
      board[i] = EMPTY;

  board[3*8+3] = WHITE;
  board[4*8+4] = WHITE;
  board[3*8+4] = BLACK;
  board[4*8+3] = BLACK;
  filledAtRoot = 3;
}

void printBoard();

// Lousy implementation. :-) 
// Switching representation of board to bitboards 
// or 0x88 will make for better efficiency.
int makeMove(int color, int square)
{       
  int testsquare;
  int index = 0;
  if(board[square] != EMPTY)
    return 0;


  // test "right"
  testsquare = square + 1;
  while(testsquare%8 && board[testsquare] == -color)
    testsquare++;
  if(testsquare % 8 && board[testsquare] == color) {    
    testsquare--;
    for(; square < testsquare; testsquare--) {
      board[testsquare] = color;
      fliplist[ply][index++] = testsquare;
    }
  }

  // test "left"
  testsquare = square - 1;
  while((testsquare%8 != 7) && board[testsquare] == -color)
    testsquare--;
  if((testsquare%8 != 7) && board[testsquare] == color) {    
    testsquare++;
    for(; square > testsquare; testsquare++) {
      board[testsquare] = color;
      fliplist[ply][index++] = testsquare;
    }
  }

  // test "up"
  testsquare = square - 8;
  while(testsquare>0 && board[testsquare] == -color)
    testsquare -= 8;
  if(testsquare>0 && board[testsquare] == color) {    
    testsquare += 8;
    for(; square > testsquare; testsquare+=8) {
      board[testsquare] = color;
      fliplist[ply][index++] = testsquare;
    }
  }

  // test "down"
  testsquare = square + 8;
  while(testsquare<64 && board[testsquare] == -color)
    testsquare += 8;
  if(testsquare<64 && board[testsquare] == color) {    
    testsquare -= 8;
    for(; square < testsquare; testsquare-=8) {
      board[testsquare] = color;
      fliplist[ply][index++] = testsquare;
    }
  }

  // test "up-right"
  testsquare = square - 7;
  while(testsquare>0 && testsquare%8 && board[testsquare] == -color)
    testsquare -= 7;
  if(testsquare>0 && testsquare%8 && board[testsquare] == color) {    
    testsquare += 7;
    for(; square > testsquare; testsquare+=7) {
      board[testsquare] = color;
      fliplist[ply][index++] = testsquare;
    }
  }

  // test "down-right"
  testsquare = square + 9;
  while(testsquare<64 && testsquare%8 && board[testsquare] == -color)
    testsquare += 9;
  if(testsquare<64 && testsquare%8 && board[testsquare] == color) {    
    testsquare -= 9;
    for(; square < testsquare; testsquare-=9) {
      board[testsquare] = color;
      fliplist[ply][index++] = testsquare;
    }
  }

  // test "down-left"
  testsquare = square + 7;
  while(testsquare<64 && (testsquare%8 != 7) && board[testsquare] == -color)
    testsquare += 7;
  if(testsquare<64 && (testsquare%8 != 7) && board[testsquare] == color) {    
    testsquare -= 7;
    for(; square < testsquare; testsquare-=7) {
      board[testsquare] = color;
      fliplist[ply][index++] = testsquare;
    }
  }

  // test "up-left"
  testsquare = square - 9;
  while(testsquare>0 && (testsquare%8 != 7) && board[testsquare] == -color)
    testsquare -= 9;
  if(testsquare>0 && (testsquare%8 != 7) && board[testsquare] == color) {    
    testsquare += 9;
    for(; square > testsquare; testsquare+=9) {
      board[testsquare] = color;
      fliplist[ply][index++] = testsquare;
    }
  }

  if(index > 0) {
    board[square] = color;
    fliplist[ply++][index] = -1;  // end-of-list-marker and update ply
    nodecount++;
  }

  return index;               // 0 (false) if no flips, ie no move made
}
    
void unmakeMove(int square)
{
  int* elemp;
  ply--;
  elemp = &fliplist[ply][0];

  while(*elemp != -1) {
    board[*elemp] = -board[*elemp];      // flip
    elemp++;
  }

  board[square] = EMPTY;

}


int heuristics(int color) {
  int i, retval=0;
  for(i = 0; i < 64; i++)
    retval += heur[i]*board[i]*color;
  return retval;
}

// Obvious? :-)
void printMove(int pos) {
  char letters[]={'A','B','C','D','E','F','G','H'};
  printf("%c%d ",letters[pos/8], pos%8+1);
}

// Obvious? :-)
void printpv(int depth) {
  int i;
  for(i=0; i<depth; i++) 
    printMove(pvmat[0][i]);
}

void printBoard() {
  int row, col;
  printf("\n");
  for(row=7; row>=0; row--) {
    printf("%d ", row+1);
    for(col=0; col<=7; col++) {      
      if(board[col*8+row]==EMPTY)
        printf("- ");
      else if(board[col*8+row]==BLACK)
        printf("X ");
      else if(board[col*8+row]==WHITE)
        printf("0 ");
      else
        printf("%d",board[row*8+col]);
    }
    printf("\n");
  }
  printf("  A B C D E F G H\n\n");
}

int pieceCount(int color) {
  int i, retval=0;
  for(i=0; i<64; i++)
    if(board[i] == color)
      retval++;
  return retval;
}

int noPossibleMoves( int color ) {
  int i;
  for(i=0; i<60; i++)
    if(makeMove(color, i)) {
      unmakeMove(i);
      nodecount--;
      return 0;
    }
  return 1;
}    

// Simple negamax with alpha-beta pruning
int search(int color, int alpha, int beta) {
  int value, i, moveMade=0, k;

  if(ply == targetDepth)                               // if we have reached out target depth ...
    return heuristics(color);                          // then return a heuristic value.
  
  for(i=0; i<60; i++) {                
    if(makeMove(color, moveOrder[i])) {                  // and try making a move and if it could be done
      moveMade = 1;
      value = -search(-color, -beta, -alpha);            // then search recursively
      unmakeMove(moveOrder[i]);                                     // and when the search returned, retract the move
      
      if(value>alpha) {                                  // and check if the move was better
      
	pvmat[ply][ply]=moveOrder[i];
	for(k=ply+1; k<=targetDepth; k++)
	  pvmat[ply][k]=pvmat[ply+1][k];
	
	if(value>=beta)                                  // if it was better than beta ...
	  return beta;                                   // we return beta.
	alpha=value;                                     // Alpha tracks best value as well
      }   
    }
  }

  if(moveMade == 0) {                                  // if no move could be made ...
    if(noPossibleMoves(-color))                        // and the other player can't move either
      if(pieceCount(color) > pieceCount(-color))       // then the game is over and we count
        return 10000;                                  // pieces and return win/draw/loss scores
      else if(pieceCount(color) < pieceCount(-color))
        return -10000; 
      else 
        return 0;
    else {                                             // if other player could move, we should forfeit move
      ply++;
      alpha = -search(-color, -beta, -alpha);   
      ply--;
    }
  }

  return alpha;                                        // return best value
}

void getHumanMove(int color) {
  char input[10];

  printf("Input move (ex B3): ");
  scanf("%s", input);

  if(input[0]<='H' && input[0]>='A' && input[1]>='0' && input[1]<='8' &&
     makeMove(color, (input[0]-'A')*8 + input[1] - '0' - 1)) 
     ply--; 
  else
    getHumanMove(color);
}

void onesInHeuristics() {
  int i;
  for(i=0; i<64; i++)
    heur[i] = 1;
}

int main () {
  int x, count;
  char input[10];
  int maxDepth=0;
  int humanColor;

  input[0] = '\0';
  initEngine();

  printf("Give difficulty level (depth): ");
  scanf("%d", &maxDepth);  

  while(input[0] != 'Y' && input[0] != 'N') {
    printf("Do you want to start? (Y/N) ");
    scanf("%s", input);
  }

  printBoard();

  if(input[0] == 'Y') {
    humanColor = BLACK;
    getHumanMove(humanColor);
    printBoard();
    filledAtRoot++;
  }
  else 
    humanColor = WHITE;

  while(1) {
    nodecount = 0;
    if(maxDepth + filledAtRoot + 5 >= 64) {
      onesInHeuristics();
      maxDepth = 64 - filledAtRoot;
    }

    if(noPossibleMoves(-humanColor)) {
      if(noPossibleMoves(humanColor)) 
        break;
      printf("Can't move, forfeiting... \n");
    } else {
      printf("Depth   Nodes   Value   PV\n");
      for(targetDepth=1; targetDepth<=maxDepth; targetDepth++) {
        x = search(-humanColor, -10000, 1000);
        printf(" %2d %9lld\t%5d\t", targetDepth, nodecount, x);
	printpv(targetDepth);
	printf("\n");
      }
      makeMove(-humanColor, pvmat[0][0]);
      ply--;
      printBoard();
      if(++filledAtRoot == 64) 
        break;
    }
      
    if(noPossibleMoves(humanColor)) {
      if(noPossibleMoves(-humanColor))
        break;
      printf("You have no moves, so you have to forfeit this move.");      
    } else {
      getHumanMove(humanColor);
      printBoard();
      if(++filledAtRoot == 64)
        break;
    }
  }

  printf("Results: %d-%d (X-O)", pieceCount(BLACK), pieceCount(WHITE));
}