#ifndef GLOBAL_H
#define GLOBAL_H
#include <stdio.h>
#include <stdarg.h>
#include <unistd.h>
#include <string.h>

typedef unsigned long unsigned_32;
typedef unsigned long long unsigned_64;

int silent_search = 1;

FILE *debugFile;

void printf_u(const char *format, ... ) {
  char buf[1024] = "";
  va_list ap;

  va_start(ap, format);
  vsprintf(buf, format, ap);
  va_end(ap);

  if ( silent_search ) {
    write(fileno(debugFile), buf, strlen(buf));
  } else {
    write(fileno(stdout), buf, strlen(buf));
  }
}

#endif
#ifndef TIMER_H
#define TIMER_H

#include <time.h>
#include <sys/time.h>
#include <unistd.h>

#define T_ACCURACY (100)
class Timer {
  public:
    long time();
    inline long accuracy() {return T_ACCURACY;}
};

long Timer::time() {
  long ctime = clock()*T_ACCURACY/CLOCKS_PER_SEC;

  return ctime;
}

#endif
#ifndef BOOK_H
#define BOOK_H

char bookString[] =
"1.b1d3 a6d3 2.b7b6 a5c5 3.f1d3 a3d3\n"
"1.c1c3 a3b2 2.b1d3 g3d3\n"
;

#endif
#ifndef EVAL_H
#define EVAL_H

int SquareWeights[] = {
  -1,  0,  0,  0,  0,  0, -1,
  0,  1,  1,  1,  1,  1,  0,
  0,  1,  2,  2,  2,  1,  0,
  0,  1,  2,  2,  2,  1,  0,
  0,  1,  2,  2,  2,  1,  0,
  0,  1,  1,  1,  1,  1,  0,
  -1,  0,  0,  0,  0,  0, -1};

int MoveDest[] = {
  0, 1, 1, 1, 1, 1, 0,
  1, 3, 2, 2, 2, 3, 1,
  1, 2, 2, 2, 2, 2, 1,
  1, 2, 2, 5, 2, 2, 1,
  1, 2, 2, 2, 2, 2, 1,
  1, 3, 2, 2, 2, 3, 1,
  0, 1, 1, 1, 1, 1, 0};

int ConnectivityVSPosition[5][5] = {
  { 0, -2, -2, -1,  0},
  {-1,  0,  0,  0,  1},
  {-1,  0,  0,  0,  1},
  {-1,  0,  0,  0,  1},
  { 0,  1,  2,  2,  0}};

int PointWeight = 211;
int CrushingPointSpreadWeight = 3000;
int PieceCountWeight = 188;
int MobilityWeight = 18;
int CaptureValue = 13;
int ConnectivityWeight = 32;
int AntiConnectivityWeight = 11;
int HungPiecePenalty = -26;
int ToMoveBonus = 1600;
int PositionalWeight = 140;

int CVPWeight = 3;
int ConnectivityCategories[] = {12, 30};
int PointCategories[] = {3, 7};

int AverageConnectionWeight = 190;
int BlockedBy2Penalty = 300;
int BlockedBy3Penalty = 1300;


#endif
#ifndef BOARD_H
#define BOARD_H

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SIZE (7)
#define PIECE_TABLE_SIZE (48)
#define NUM_PIECES (8)
#define COLOR_MASK (0x30)
#define MAX_MOVES (200)

#define EMPTY (0)

#define POINTS_FOR_WIN (12)

#define FromPos(x) ( (x) & 0x3F )
#define ToPos(x) ( ((x) & 0xFC0) >> 6 )
#define PackMove(f, t) ( ((t)<<6) | (f) )
#define GetColor(p) ( (p) & COLOR_MASK )
#define SwapColor(p) ( COLOR_MASK - (p) )

unsigned_64 turnRand[2];
unsigned_64 randTable[SIZE*SIZE][2];

int rankLookup[] = {
  0, 0, 0, 0, 0, 0, 0,
  1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2,
  3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6};

int fileLookup[] = {
  0, 1, 2, 3, 4, 5, 6,
  0, 1, 2, 3, 4, 5, 6,
  0, 1, 2, 3, 4, 5, 6,
  0, 1, 2, 3, 4, 5, 6,
  0, 1, 2, 3, 4, 5, 6,
  0, 1, 2, 3, 4, 5, 6,
  0, 1, 2, 3, 4, 5, 6};

int diag1Lookup[] = {
  0, 1, 2, 3,  4,  5,  6,
  1, 2, 3, 4,  5,  6,  7,
  2, 3, 4, 5,  6,  7,  8,
  3, 4, 5, 6,  7,  8,  9,
  4, 5, 6, 7,  8,  9, 10,
  5, 6, 7, 8,  9, 10, 11,
  6, 7, 8, 9, 10, 11, 12};

int diag2Lookup[] = {
  6,  5,  4, 3, 2, 1, 0,
  7,  6,  5, 4, 3, 2, 1,
  8,  7,  6, 5, 4, 3, 2,
  9,  8,  7, 6, 5, 4, 3,
  10,  9,  8, 7, 6, 5, 4,
  11, 10,  9, 8, 7, 6, 5,
  12, 11, 10, 9, 8, 7, 6};

int edgeSquares[] = {
  1, 1, 1, 1, 1, 1, 1,
  1, 0, 0, 0, 0, 0, 1,
  1, 0, 0, 0, 0, 0, 1,
  1, 0, 0, 0, 0, 0, 1,
  1, 0, 0, 0, 0, 0, 1,
  1, 0, 0, 0, 0, 0, 1,
  1, 1, 1, 1, 1, 1, 1};

int cornerSquares[] = {
  1, 0, 0, 0, 0, 0, 1,
  0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 0, 0, 0, 1};

/**
 * IMPORTANT!!!
 * If you change these values, then the get_legal_moves and
 * get_moves_mobility both need to be changed because they depend
 * directly on these values
 */
int dirs[] = {-1, 1, -SIZE, SIZE, -SIZE+1, SIZE-1, -SIZE-1, SIZE+1};

int squarePoints[] = {
  0, 0, 0, 0, 0, 0, 0,
  0, 3, 0, 0, 0, 3, 0,
  0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 7, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0,
  0, 3, 0, 0, 0, 3, 0,
  0, 0, 0, 0, 0, 0, 0};

/**
 * The indices for this array are:
 * posotion, distance, direction
 */
char moveTables[SIZE*SIZE][SIZE][8];

unsigned_64 interpose[SIZE*SIZE][SIZE*SIZE];
unsigned_64 blocking_mask[SIZE*SIZE];

class Board {

  friend int eval(Board &);

  public:
  void init();
  void init(char *);
  void make_move(int);
  void unmake_move(int);
  int isLegal(int);
  int get_legal_moves(int *);
  int get_moves_mobility(int);
  int countGroups(int);
  void print();
  void print_u();
  void printLoaps(FILE *);
  int gameResult();
  unsigned_64 getHash() {return p1hash^p2hash^turnRand[turn];}

  void computeDistances();
  int pieceDistance(int, int);
  int getSSD(int);
  int checkDistances();

  void changeTurn() {turn = 1-turn;}

  int turn;
  int board[SIZE*SIZE];
  int points[2];
  int pCounts[2];
  unsigned_64 bitPieces[2];

  //pieceTable is a piece list
  //Each board[i] is an index into this list
  int pieceTable[PIECE_TABLE_SIZE];

  unsigned_64 p1hash;
  unsigned_64 p2hash;

  int moveNumber;
  double timeLeft[2];

  private:

  int rankCount[SIZE];
  int fileCount[SIZE];
  int diag1Count[SIZE*2];
  int diag2Count[SIZE*2];

  int pieceDistances[PIECE_TABLE_SIZE];
  int visited[SIZE*SIZE];
  int groups[NUM_PIECES+1];

  void addPiece(int, int);
  void gameOverSearch(int, int, int);
  int isRightDistance(int);

  void updateDistances(int, int, int);
  void removeDistances(int);
  void addDistances(int);

  /**
   * Checks to see if the specified move in the specified direction
   * by the specified color is blocked by a piece of the opposite  color
   * NOTE: This function doesn't do any bounds checking.  The to and
   * from squares must be on the board and they must be in the
   * direction indicated by dir.
   */
  int isBlocked(int from, int to, int dir, int color, int oppcolor) {
    from += dir;
    while ( from != to ) {
      if ( GetColor(board[from]) == oppcolor ) return true;
      from += dir;
    }
    return GetColor(board[to]) == color;
  }

};

void moveToStr(int move, char *str) {
  int from = FromPos(move);
  int to = ToPos(move);

  str[0] = from%SIZE+'a';
  str[1] = from/SIZE+'1';
  str[2] = to%SIZE+'a';
  str[3] = to/SIZE+'1';
  str[4] = 0;
}

int strToMove(char *str) {
  int from;
  int to;

  from = SIZE*(str[1]-'1');
  from += str[0]-'a';
  to = SIZE*(str[3]-'1');
  to += str[2]-'a';
  return PackMove(from, to);
}

unsigned int popcount(unsigned_64 b) {
  unsigned int n;
  for (n = 0; b != 0; n++, b &= (b - 1));
  return n;
}

unsigned_32 Random32(void) {
  static unsigned long x[55] = {
    1410651636UL, 3012776752UL, 3497475623UL, 2892145026UL, 1571949714UL,
    3253082284UL, 3489895018UL, 387949491UL, 2597396737UL, 1981903553UL,
    3160251843UL, 129444464UL, 1851443344UL, 4156445905UL, 224604922UL,
    1455067070UL, 3953493484UL, 1460937157UL, 2528362617UL, 317430674UL,
    3229354360UL, 117491133UL, 832845075UL, 1961600170UL, 1321557429UL,
    747750121UL, 545747446UL, 810476036UL, 503334515UL, 4088144633UL,
    2824216555UL, 3738252341UL, 3493754131UL, 3672533954UL, 29494241UL,
    1180928407UL, 4213624418UL, 33062851UL, 3221315737UL, 1145213552UL,
    2957984897UL, 4078668503UL, 2262661702UL, 65478801UL, 2527208841UL,
    1960622036UL, 315685891UL, 1196037864UL, 804614524UL, 1421733266UL,
    2017105031UL, 3882325900UL, 810735053UL, 384606609UL, 2393861397UL };
  static int init = 1;
  static unsigned long y[55];
  static int j, k;
  unsigned long ul;

  if (init)
  {
    int i;

    init = 0;
    for (i = 0; i < 55; i++) y[i] = x[i];
    j = 24 - 1;
    k = 55 - 1;
  }

  ul = (y[k] += y[j]);
  if (--j < 0) j = 55 - 1;
  if (--k < 0) k = 55 - 1;
  return((unsigned int)ul);
}
unsigned_64 Random64(void) {
  unsigned_64 result;
  unsigned long r1, r2;

  r1=Random32();
  r2=Random32();
  result=(unsigned_64)(r1|((unsigned_64)r2<<32));
  return (result);
}
void initRandomTables() {
  turnRand[0] = Random64();
  turnRand[1] = Random64();
  for ( int i = 0; i < 2; i++ ) {
    for ( int j = 0; j < SIZE*SIZE; j++ ) {
      randTable[j][i] = Random64();
    }
  }
}

void initMoveTables() {
  memset(moveTables, -1, sizeof(moveTables));
  for ( int y = 0; y < SIZE; y++ ) {
    for ( int x = 0; x < SIZE; x++ ) {
      int pos = y*SIZE+x;

      unsigned_64 temp = 0ULL;
      if ( x == 0 && y == 0 ) {
        temp |= (1ULL << (pos+1));
        temp |= (1ULL << (pos+SIZE));
        temp |= (1ULL << (pos+SIZE+1));
      } else if ( x == 0 && y == SIZE-1 ) {
        temp |= (1ULL << (pos+1));
        temp |= (1ULL << (pos-SIZE));
        temp |= (1ULL << (pos-SIZE+1));
      } else if ( x == SIZE-1 && y == 0 ) {
        temp |= (1ULL << (pos-1));
        temp |= (1ULL << (pos+SIZE));
        temp |= (1ULL << (pos+SIZE-1));
      } else if ( x == SIZE-1 && y == SIZE-1 ) {
        temp |= (1ULL << (pos-1));
        temp |= (1ULL << (pos-SIZE));
        temp |= (1ULL << (pos-SIZE-1));
      } else if ( x == 0 ) {
        temp |= (1ULL << (pos-SIZE+1));
        temp |= (1ULL << (pos+1));
        temp |= (1ULL << (pos+SIZE+1));
      } else if ( x == SIZE-1 ) {
        temp |= (1ULL << (pos-SIZE-1));
        temp |= (1ULL << (pos-1));
        temp |= (1ULL << (pos+SIZE-1));
      } else if ( y == 0 ) {
        temp |= (1ULL << (pos+SIZE-1));
        temp |= (1ULL << (pos+SIZE));
        temp |= (1ULL << (pos+SIZE+1));
      } else if ( y == SIZE-1 ) {
        temp |= (1ULL << (pos-SIZE-1));
        temp |= (1ULL << (pos-SIZE));
        temp |= (1ULL << (pos-SIZE+1));
      }
      blocking_mask[pos] = temp;

      for ( int dy = -1; dy <= 1; dy++ ) {
        for ( int dx = -1; dx <= 1; dx++ ) {
          if ( dx == 0 && dy == 0 ) continue;
          int dir = dy*SIZE+dx;
          int dirInd = 0;
          for ( int t = 0; t < 8; t++ ) {
            if ( dir == dirs[t] ) {
              dirInd = t;
              break;
            }
          }

          unsigned_64 squares = 0;

          for ( int i = 0; i < SIZE; i++ ) {
            int x2 = x+i*dx;
            int y2 = y+i*dy;
            if ( x2 < 0 || x2 >= SIZE ||
                y2 < 0 || y2 >= SIZE ) {
              break;
            }
            int pos2 = pos+dir*i;

            if ( i == 0 ) {
              interpose[pos][pos2] = 0ULL;
            } else {
              moveTables[pos][i][dirInd] = pos2;
              interpose[pos][pos2] = squares;
              squares |= (1ULL << pos2);
            }

          }
        }
      }
    }
  }
}

/**
 * Color is 0x10 or 0x20
 */
int Board::pieceDistance(int piece, int color) {
  int x = fileLookup[pieceTable[piece]];
  int y = rankLookup[pieceTable[piece]];
  int end = color+NUM_PIECES;
  int total = 0;
  for ( int i = color; i < end; i++ ) {
    if ( i == piece || pieceTable[i] == -1 ) continue;
    int pos = pieceTable[i];
    int y2 = rankLookup[pos];
    int x2 = fileLookup[pos];
    int dx = x2-x;
    int dy = y2-y;
    total += dx*dx + dy*dy;
  }
  return total;
}

int Board::getSSD(int c) {
  int color = ((c+1) << 4);
  int end = color+NUM_PIECES;
  int total = 0;
  for ( int i = color; i < end; i++ ) {
    if ( pieceTable[i] == -1 ) continue;
    total += pieceDistance(i, color);
  }
  return total;
}

void Board::computeDistances() {
  int color = 0x10;
  int end = color+NUM_PIECES;
  for ( int i = color; i < end; i++ ) {
    if ( pieceTable[i] == -1 ) continue;
    pieceDistances[i] = pieceDistance(i, color);
  }

  color = 0x20;
  end = color+NUM_PIECES;
  for ( int i = color; i < end; i++ ) {
    if ( pieceTable[i] == -1 ) continue;
    pieceDistances[i] = pieceDistance(i, color);
  }
}

int Board::checkDistances() {
  int ok = 1;
  int incr = 0;
  int real = getSSD(0);

  int i = 0x10;
  int end = i+NUM_PIECES;
  for ( ; i < end; i++ ) {
    if ( pieceTable[i] == -1 ) continue;
    incr += pieceDistances[i];
  }

  if ( real != incr ) {
    ok = 0;
    printf_u("P1 distance problem %d %d\n", real, incr);
    print_u();
  }

  incr = 0;
  real = getSSD(1);
  i = 0x20;
  end = i+NUM_PIECES;
  for ( ; i < end; i++ ) {
    if ( pieceTable[i] == -1 ) continue;
    incr += pieceDistances[i];
  }

  if ( real != incr ) {
    ok = 0;
    printf_u("P2 distance problem %d %d\n", real, incr);
    print_u();
  }

  return ok;
}

void Board::init() {
  for ( int i = 0; i < SIZE*SIZE; i++ ) {
    board[i] = EMPTY;
  }
  for ( int i = 0; i < PIECE_TABLE_SIZE; i++ ) {
    pieceTable[i] = -1;
  }	
  memset(rankCount, 0, SIZE*sizeof(int));
  memset(fileCount, 0, SIZE*sizeof(int));
  memset(diag1Count, 0, SIZE*2*sizeof(int));
  memset(diag2Count, 0, SIZE*2*sizeof(int));

  moveNumber = 1;
  pCounts[0] = pCounts[1] = 0;
  bitPieces[0] = bitPieces[1] = 0ULL;
  points[0] = 0;
  points[1] = 0;
  timeLeft[0] = 60.0;
  timeLeft[1] = 60.0;
  p1hash = 0;
  p2hash = 0;
  turn = 0;
  int ind = 0x10;
  addPiece(1, ind++);
  addPiece(2, ind++);
  addPiece(4, ind++);
  addPiece(5, ind++);
  addPiece(43, ind++);
  addPiece(44, ind++);
  addPiece(46, ind++);
  addPiece(47, ind++);

  ind = 0x20;
  addPiece(7, ind++);
  addPiece(14, ind++);
  addPiece(28, ind++);
  addPiece(35, ind++);
  addPiece(13, ind++);
  addPiece(20, ind++);
  addPiece(34, ind++);
  addPiece(41, ind++);

  computeDistances();
}
void Board::init(char *fname) {
  FILE *f;
  if ( (f = fopen(fname, "r")) != NULL ) {
    for ( int i = 0; i < SIZE*SIZE; i++ ) {
      board[i] = EMPTY;
    }
    for ( int i = 0; i < PIECE_TABLE_SIZE; i++ ) {
      pieceTable[i] = -1;
    }	
    memset(rankCount, 0, SIZE*sizeof(int));
    memset(fileCount, 0, SIZE*sizeof(int));
    memset(diag1Count, 0, SIZE*2*sizeof(int));
    memset(diag2Count, 0, SIZE*2*sizeof(int));

    pCounts[0] = pCounts[1] = 0;
    bitPieces[0] = bitPieces[1] = 0ULL;
    points[0] = 0;
    points[1] = 0;
    p1hash = 0;
    p2hash = 0;
    turn = 0;

    int p1Count = 0x10;
    int p2Count = 0x20;
    char line[64];
    char *token;

    printf_u("Started reading %s\n", fname);

    //Parse the first line
    fgets(line, 64, f);
    line[strlen(line)-1] = 0;
    printf_u("%s\n", line);
    token = strtok(line, " \t");
    turn = atoi(token)-1;
    token = strtok(NULL, " \t");
    moveNumber = atoi(token);

    //Parse the second line
    fgets(line, 64, f);
    line[strlen(line)-1] = 0;
    printf_u("%s\n", line);
    token = strtok(line, " \t");
    int temp = atoi(token)-1;
    token = strtok(NULL, " \t");
    points[temp] = atoi(token);
    token = strtok(NULL, " \t");
    timeLeft[temp] = atof(token);

    //Parse the third line
    fgets(line, 64, f);
    line[strlen(line)-1] = 0;
    printf_u("%s\n", line);
    token = strtok(line, " \t");
    temp = atoi(token)-1;
    token = strtok(NULL, " \t");
    points[temp] = atoi(token);
    token = strtok(NULL, " \t");
    timeLeft[temp] = atof(token);

    for ( int i = SIZE-1; i >= 0; i-- ) {
      fgets(line, 64, f);
      line[strlen(line)-1] = 0;
      printf_u("%s\n", line);
      for ( int j = 0; j < SIZE; j++ ) {
        if ( line[j] == '1' ) {
          addPiece(i*SIZE+j, p1Count++);
        } else if ( line[j] == '2' ) {
          addPiece(i*SIZE+j, p2Count++);
        }
      }
    }

    printf_u("Done reading file\n");
    fclose(f);

    computeDistances();
  } else {
    printf_u("Could not open file %s\n", fname);
  }
}
void Board::print() {
  printf("%d %d\n", turn+1, moveNumber);
  printf("1 %d %.2f\n", points[0], timeLeft[0]);
  printf("2 %d %.2f\n", points[1], timeLeft[1]);
  for ( int r = SIZE-1; r >= 0; r-- ) {
    printf("%d ", r+1);
    for ( int c = 0; c < SIZE; c++ ) {
      int p = board[r*SIZE + c];
      //			printf("%02d ", p);
      switch ( GetColor(p) ) {
        case 0x10:
          printf("1 ");
          break;
        case 0x20:
          printf("2 ");
          break;
        default:
          printf(". ");
      }
    }
    printf("\n");
  }
  printf("  ");
  for ( int c = 0; c < SIZE; c++ ) {
    printf("%c ", 'a'+c);
  }
  printf("\n");
  printf("Turn %d\n", turn);
  printf("0x%LX\n", p1hash);
  printf("0x%LX\n", p2hash);
}
void Board::print_u() {
  printf_u("%d %d\n", turn+1, moveNumber);
  printf_u("1 %d %.2f\n", points[0], timeLeft[0]);
  printf_u("2 %d %.2f\n", points[1], timeLeft[1]);
  for ( int r = SIZE-1; r >= 0; r-- ) {
    printf_u("%d ", r+1);
    for ( int c = 0; c < SIZE; c++ ) {
      int p = board[r*SIZE + c];
      switch ( GetColor(p) ) {
        case 0x10:
          printf_u("1 ");
          break;
        case 0x20:
          printf_u("2 ");
          break;
        default:
          printf_u(". ");
      }
    }
    printf_u("\n");
  }
  printf_u("  ");
  for ( int c = 0; c < SIZE; c++ ) {
    printf_u("%c ", 'a'+c);
  }
  printf_u("\n");
  printf_u("Turn %d\n", turn);
  printf_u("0x%LX\n", p1hash);
  printf_u("0x%LX\n", p2hash);
  for ( int j = 0x10; j < 0x10+NUM_PIECES; j++ ) {
    if ( pieceTable[j] == -1 ) continue;
    printf_u("%d pieceDistances[%x] = %d\n", pieceTable[j], j, pieceDistances[j]);
  }
  printf_u("\n");
  for ( int j = 0x20; j < 0x20+NUM_PIECES; j++ ) {
    if ( pieceTable[j] == -1 ) continue;
    printf_u("%d pieceDistances[%x] = %d\n", pieceTable[j], j, pieceDistances[j]);
  }
}
void Board::printLoaps(FILE *out) {
  fprintf(out, "%d %d\n", turn+1, moveNumber);
  fprintf(out, "1 %d %.2f\n", points[0], timeLeft[0]);
  fprintf(out, "2 %d %.2f\n", points[1], timeLeft[1]);
  for ( int r = SIZE-1; r >= 0; r-- ) {
    for ( int c = 0; c < SIZE; c++ ) {
      int p = board[r*SIZE + c];
      switch ( GetColor(p) ) {
        case 0x10:
          fprintf(out, "1");
          break;
        case 0x20:
          fprintf(out, "2");
          break;
        default:
          fprintf(out, ".");
      }
    }
    fprintf(out, "\n");
  }
}
void Board::addPiece(int square, int color) {
  board[square] = color;
  pieceTable[color] = square;
  rankCount[rankLookup[square]]++;
  fileCount[fileLookup[square]]++;
  diag1Count[diag1Lookup[square]]++;
  diag2Count[diag2Lookup[square]]++;
  int ind = ((color&COLOR_MASK)>>4)-1;
  if ( ind == 0 ) {
    p1hash ^= randTable[square][ind];
  } else {
    p2hash ^= randTable[square][ind];
  }
  bitPieces[ind] |= (1ULL << square);
  pCounts[ind]++;
}

inline int distSquared(int x1, int y1, int x2, int y2) {
  int dx = x2-x1;
  int dy = y2-y1;
  return dx*dx + dy*dy;
}

void Board::updateDistances(int oldPos, int newPos, int ind) {
  int oldX = fileLookup[oldPos];
  int oldY = rankLookup[oldPos];
  int newX = fileLookup[newPos];
  int newY = rankLookup[newPos];
  int color = GetColor(ind);
  int end = color+NUM_PIECES;

  pieceDistances[ind] = 0;
  for ( int i = color; i < end; i++ ) {
    if ( i == ind || pieceTable[i] == -1 ) continue;
    int pos = pieceTable[i];
    int x2 = fileLookup[pos];
    int y2 = rankLookup[pos];

    int dist = distSquared(oldX, oldY, x2, y2);
    pieceDistances[i] -= dist;

    dist = distSquared(newX, newY, x2, y2);
    pieceDistances[i] += dist;
    pieceDistances[ind] += dist;

  }
}

void Board::removeDistances(int ind) {
  int x = fileLookup[pieceTable[ind]];
  int y = rankLookup[pieceTable[ind]];
  int color = GetColor(ind);
  int end = color+NUM_PIECES;
  for ( int i = color; i < end; i++ ) {
    int pos = pieceTable[i];
    if ( i == ind || pos == -1 ) continue;
    int x2 = fileLookup[pos];
    int y2 = rankLookup[pos];

    int dist = distSquared(x, y, x2, y2);
    pieceDistances[i] -= dist;
  }
  pieceDistances[ind] = 0;
}

void Board::addDistances(int ind) {
  int x = fileLookup[pieceTable[ind]];
  int y = rankLookup[pieceTable[ind]];
  int color = GetColor(ind);
  int end = color+NUM_PIECES;
  pieceDistances[ind] = 0;
  for ( int i = color; i < end; i++ ) {
    int pos = pieceTable[i];
    if ( i == ind || pos == -1 ) continue;
    int x2 = fileLookup[pos];
    int y2 = rankLookup[pos];

    int dist = distSquared(x, y, x2, y2);
    pieceDistances[i] += dist;
    pieceDistances[ind] += dist;
  }
}

void Board::make_move(int move) {
  int from = FromPos(move);
  int to = ToPos(move);

  if ( turn == 1 ) {
    moveNumber++;
  }
  points[turn] += squarePoints[to];
  if ( board[to] == EMPTY ) {
    rankCount[rankLookup[to]]++;
    fileCount[fileLookup[to]]++;
    diag1Count[diag1Lookup[to]]++;
    diag2Count[diag2Lookup[to]]++;
    if ( turn == 0 ) {
      p1hash ^= randTable[to][0];
    } else {
      p2hash ^= randTable[to][1];
    }
  } else {
    p1hash ^= randTable[to][0];
    p2hash ^= randTable[to][1];
    bitPieces[1-turn] &= ~(1ULL << to);
    removeDistances(board[to]);
    pieceTable[board[to]] = -1;
    points[turn]++;
    pCounts[1-turn]--;
  }

  if ( turn == 0 ) {
    p1hash ^= randTable[from][0];
  } else {
    p2hash ^= randTable[from][1];
  }
  bitPieces[turn] &= ~(1ULL << from);
  bitPieces[turn] |= (1ULL << to);
  rankCount[rankLookup[from]]--;
  fileCount[fileLookup[from]]--;
  diag1Count[diag1Lookup[from]]--;
  diag2Count[diag2Lookup[from]]--;

  board[to] = board[from];
  pieceTable[board[to]] = to;
  updateDistances(from, to, board[to]);
  board[from] = EMPTY;
  changeTurn();
}
void Board::unmake_move(int move) {
  int from = FromPos(move);
  int to = ToPos(move);

  if ( turn == 0 ) {
    moveNumber--;
  }
  changeTurn();
  board[from] = board[to];
  pieceTable[board[from]] = from;
  updateDistances(to, from, board[from]);
  if ( turn == 0 ) {
    p1hash ^= randTable[from][0];
  } else {
    p2hash ^= randTable[from][1];
  }
  bitPieces[turn] &= ~(1ULL << to);
  bitPieces[turn] |= (1ULL << from);

  if ( isRightDistance(move) ) {
    rankCount[rankLookup[to]]--;
    fileCount[fileLookup[to]]--;
    diag1Count[diag1Lookup[to]]--;
    diag2Count[diag2Lookup[to]]--;
    if ( turn == 0 ) {
      p1hash ^= randTable[to][0];
    } else {
      p2hash ^= randTable[to][1];
    }
    board[to] = EMPTY;
  } else {
    //Undoing a capture
    int i = (2-turn) << 4;
    int end = i+NUM_PIECES;
    for ( ; i < end; i++ ) {
      if ( pieceTable[i] == -1 ) {
        pieceTable[i] = to;
        board[to] = i;
        break;
      }
    }
    addDistances(board[to]);
    p1hash ^= randTable[to][0];
    p2hash ^= randTable[to][1];
    bitPieces[1-turn] |= (1ULL << to);
    points[turn]--;
    pCounts[1-turn]++;
  }

  rankCount[rankLookup[from]]++;
  fileCount[fileLookup[from]]++;
  diag1Count[diag1Lookup[from]]++;
  diag2Count[diag2Lookup[from]]++;

  points[turn] -= squarePoints[to];
}
int Board::isRightDistance(int move) {
  int from = FromPos(move);
  int to = ToPos(move);
  int fRow = rankLookup[from]; //from/SIZE;
  int fCol = fileLookup[from]; //from%SIZE;
  int tRow = rankLookup[to]; //to/SIZE;
  int tCol = fileLookup[to]; //to%SIZE;
  int fd1 = diag1Lookup[from];
  int td1 = diag1Lookup[to];
  int fd2 = diag2Lookup[from];
  int td2 = diag2Lookup[to];

  if ( fRow == tRow ) {
    //Same row
    if ( abs(fCol - tCol) != rankCount[fRow] ) return 0;
  } else if ( fCol == tCol ) {
    //Same column
    if ( abs(fRow - tRow) != fileCount[fCol] ) return 0;
  } else if ( fd1 == td1 ) {
    //Same diagonal
    if ( (abs(fd2 - td2)>>1) != diag1Count[fd1] ) return 0;
  } else if ( fd2 == td2 ) {
    //Same diagonal
    if ( (abs(fd1 - td1)>>1) != diag2Count[fd2] ) return 0;
  }
  return 1;
}
int Board::isLegal(int move) {
  if ( (move & (~0xFFF)) != 0 ) return 0;
  int from = FromPos(move);
  if ( from >= SIZE*SIZE ) return 0;
  int color = GetColor(board[from]);
  if ( ((turn+1) << 4) != color ) return 0;
  int to = ToPos(move);
  if ( to >= SIZE*SIZE ) return 0;
  int fRow = rankLookup[from]; //from/SIZE;
  int fCol = fileLookup[from]; //from%SIZE;
  int tRow = rankLookup[to]; //to/SIZE;
  int tCol = fileLookup[to]; //to%SIZE;
  int fd1 = diag1Lookup[from];
  int td1 = diag1Lookup[to];
  int fd2 = diag2Lookup[from];
  int td2 = diag2Lookup[to];
  int dir = 1;

  //Check for land on own piece
  if ( GetColor(board[to]) == color ) return 0;

  if ( fRow == tRow ) {
    //Same row
    if ( abs(fCol - tCol) != rankCount[fRow] ) return 0;

    dir = to>from ? 1 : -1;
  } else if ( fCol == tCol ) {
    //Same column
    if ( abs(fRow - tRow) != fileCount[fCol] ) return 0;

    dir = to>from ? SIZE : -SIZE;
  } else if ( fd1 == td1 ) {
    //Same diagonal
    if ( (abs(fd2 - td2)>>1) != diag1Count[fd1] ) return 0;

    dir = to>from ? SIZE-1 : -SIZE+1;
  } else if ( fd2 == td2 ) {
    //Same diagonal
    if ( (abs(fd1 - td1)>>1) != diag2Count[fd2] ) return 0;

    dir = to>from ? SIZE+1 : -SIZE-1;
  } else {
    return 0;
  }

  return (((interpose[from][to]&bitPieces[1-turn]) == 0) && (GetColor(board[to]) != color));
}

void Board::gameOverSearch(int pos, int color, int num) {
  int p;
  int r = rankLookup[pos];
  int c = fileLookup[pos];

  groups[num]++;
  visited[pos] = num;

  if ( r > 0 ) {
    p = pos-SIZE-1;
    if ( c > 0 ) {
      if ( GetColor(board[p]) == color && !visited[p] ) {
        gameOverSearch(p, color, num);
      }
    }
    p++;
    if ( GetColor(board[p]) == color && !visited[p] ) {
      gameOverSearch(p, color, num);
    }
    if ( c < SIZE-1 ) {
      p++;
      if ( GetColor(board[p]) == color && !visited[p] ) {
        gameOverSearch(p, color, num);
      }
    }
  }
  if ( r < SIZE-1 ) {
    p = pos+SIZE-1;
    if ( c > 0 ) {
      if ( GetColor(board[p]) == color && !visited[p] ) {
        gameOverSearch(p, color, num);
      }
    }
    p++;
    if ( GetColor(board[p]) == color && !visited[p] ) {
      gameOverSearch(p, color, num);
    }
    if ( c < SIZE-1 ) {
      p++;
      if ( GetColor(board[p]) == color && !visited[p] ) {
        gameOverSearch(p, color, num);
      }
    }
  }
  if ( c > 0 ) {
    p = pos-1;
    if ( GetColor(board[p]) == color && !visited[p] ) {
      gameOverSearch(p, color, num);
    }
  }
  if ( c < SIZE-1 ) {
    p = pos+1;
    if ( GetColor(board[p]) == color && !visited[p] ) {
      gameOverSearch(p, color, num);
    }
  }
}

/**
 * Returns:
 *   0 if player 1 won
 *   1 if player 2 won
 *   2 if game is draw
 *   -1 if game not over
 */
int Board::gameResult() {
  if ( moveNumber > 50 ) {
    return 2;
  }

  int ind = 0x10;
  int color = ind;
  int over;
  memset(visited, 0, SIZE*SIZE*sizeof(int));

  int pos;
  for ( int i = 0; i < NUM_PIECES; i++, ind++ ) {
    pos = pieceTable[ind];
    if ( pos != -1 ) {
      break;
    }
  }
  gameOverSearch(pos, color, 1);
  ind++;
  over = 1;
  for ( int i = 1; i < NUM_PIECES; i++, ind++ ) {
    pos = pieceTable[ind];
    if ( pos != -1 ) {
      if ( !visited[pos] ) {
        over = 0;
      }
    }
  }
  if ( over ) {
    if ( points[0]+POINTS_FOR_WIN > points[1] ) {
      return 0;
    } else if ( points[0]+POINTS_FOR_WIN < points[1] ) {
      return 1;
    } else {
      return 2;
    }
  }

  color = ind = 0x20;
  for ( int i = 0; i < NUM_PIECES; i++, ind++ ) {
    pos = pieceTable[ind];
    if ( pos != -1 ) {
      break;
    }
  }
  gameOverSearch(pos, color, 1);
  ind++;
  for ( int i = 1; i < NUM_PIECES; i++, ind++ ) {
    pos = pieceTable[ind];
    if ( pos != -1 ) {
      if ( !visited[pos] ) {
        return -1;
      }
    }
  }

  if ( points[1]+POINTS_FOR_WIN > points[0] ) {
    return 1;
  } else if ( points[1]+POINTS_FOR_WIN < points[0] ) {
    return 0;
  } else {
    return 2;
  }
}
int Board::countGroups(int color) {
  int ind = color;
  int count = 0;
  memset(visited, 0, SIZE*SIZE*sizeof(int));

  int pos;
  for ( int i = 0; i < NUM_PIECES; i++, ind++ ) {
    pos = pieceTable[ind];
    if ( pos != -1 && !visited[pos] ) {
      count++;
      groups[count] = 0;
      gameOverSearch(pos, color, count);
    }
  }
  return count;
}
int Board::get_legal_moves(int *list) {
  int ind = (turn+1) << 4;
  int end = ind+NUM_PIECES;
  int color = GetColor(ind);
  int oppturn = 1-turn;
  int movecount = 0;

  for ( ; ind < end; ind++ ) {
    int pos = pieceTable[ind];
    if ( pos != -1 ) {
      int dist = rankCount[rankLookup[pos]];
      int dir = dirs[0];
      int to = moveTables[pos][dist][0];
      if ( dist < SIZE ) {
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          list[movecount++] = PackMove(pos, to);
        }

        dir = dirs[1];
        to = moveTables[pos][dist][1];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          list[movecount++] = PackMove(pos, to);
        }
      }

      dist = fileCount[fileLookup[pos]];
      if ( dist < SIZE ) {
        dir = dirs[2];
        to = moveTables[pos][dist][2];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          list[movecount++] = PackMove(pos, to);
        }

        dir = dirs[3];
        to = moveTables[pos][dist][3];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          list[movecount++] = PackMove(pos, to);
        }
      }

      dist = diag1Count[diag1Lookup[pos]];
      if ( dist < SIZE ) {
        dir = dirs[4];
        to = moveTables[pos][dist][4];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          list[movecount++] = PackMove(pos, to);
        }

        dir = dirs[5];
        to = moveTables[pos][dist][5];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          list[movecount++] = PackMove(pos, to);
        }
      }

      dist = diag2Count[diag2Lookup[pos]];
      if ( dist < SIZE ) {
        dir = dirs[6];
        to = moveTables[pos][dist][6];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          list[movecount++] = PackMove(pos, to);
        }

        dir = dirs[7];
        to = moveTables[pos][dist][7];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          list[movecount++] = PackMove(pos, to);
        }
      }
    }
  }
  return movecount;
}

int Board::get_moves_mobility(int player) {
  int ind = (player+1) << 4;
  int color = GetColor(ind);
  int oppturn = 1-player;
  int score = 0;
  int hung = 0;

  int end = ind + NUM_PIECES;
  for ( ; ind < end; ind++ ) {
    int pos = pieceTable[ind];
    if ( pos != -1 ) {
      int mobility = 0;
      int dist = rankCount[rankLookup[pos]];
      int dir = dirs[0];
      int to = moveTables[pos][dist][0];
      if ( dist < SIZE) {
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          score += MoveDest[to];
          if ( board[to] != EMPTY ) {
            score += CaptureValue;
          }
          mobility++;
        }

        dir = dirs[1];
        to = moveTables[pos][dist][1];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          score += MoveDest[to];
          if ( board[to] != EMPTY ) {
            score += CaptureValue;
          }
          mobility++;
        }
      }

      dist = fileCount[fileLookup[pos]];
      if ( dist < SIZE) {
        dir = dirs[2];
        to = moveTables[pos][dist][2];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          score += MoveDest[to];
          if ( board[to] != EMPTY ) {
            score += CaptureValue;
          }
          mobility++;
        }

        dir = dirs[3];
        to = moveTables[pos][dist][3];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          score += MoveDest[to];
          if ( board[to] != EMPTY ) {
            score += CaptureValue;
          }
          mobility++;
        }
      }

      dist = diag1Count[diag1Lookup[pos]];
      if ( dist < SIZE) {
        dir = dirs[4];
        to = moveTables[pos][dist][4];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          score += MoveDest[to];
          if ( board[to] != EMPTY ) {
            score += CaptureValue;
          }
          mobility++;
        }

        dir = dirs[5];
        to = moveTables[pos][dist][5];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          score += MoveDest[to];
          if ( board[to] != EMPTY ) {
            score += CaptureValue;
          }
          mobility++;
        }
      }

      dist = diag2Count[diag2Lookup[pos]];
      if ( dist < SIZE) {
        dir = dirs[6];
        to = moveTables[pos][dist][6];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          score += MoveDest[to];
          if ( board[to] != EMPTY ) {
            score += CaptureValue;
          }
          mobility++;
        }

        dir = dirs[7];
        to = moveTables[pos][dist][7];
        if ( to != -1 && ((interpose[pos][to]&bitPieces[oppturn]) == 0) && (GetColor(board[to]) != color) ) {
          score += MoveDest[to];
          if ( board[to] != EMPTY ) {
            score += CaptureValue;
          }
          mobility++;
        }
      }

      if ( mobility <= 3 ) {
        hung += HungPiecePenalty*(4-mobility);
      }
    }
  }
  score *= MobilityWeight;
  score += hung;
  return score;
}
#endif
#ifndef HASH_H
#define HASH_H

struct HashEntry {
  unsigned_64 key    : 44;
  int type   : 4;
  int depth  : 8;
  int move   : 13;
  int value;
};

class HashTable {
  HashEntry *table;

  public:
  long hash_hits;
  long collisions;
  long hash_probes;
  int hash_table_size;
  int bitcount;

  HashTable(unsigned long size);
  ~HashTable();
  void store(Board &, int, int, int, int);
  void lookup(Board &, int *, int *, int *, int *);
};

HashTable::HashTable(unsigned long size) {
  int i;

  hash_table_size = size;
  for ( i = 31; i > 0; i-- ) {
    if ( (1<<i)&size )
      break;
  }
  if ( (1<<i)^size ) {
    printf("Number was not a power of 2\n");
  }
  bitcount = i;
  table = new HashEntry[hash_table_size];
  if ( table == NULL ) {
    printf("Out of memory!\n");
    exit(0);
  }
  for ( i = 0; i < hash_table_size; i++ ) {
    table[i].type = 0;
    table[i].depth = 0;
    table[i].key = 0;
    table[i].value = 0;
  }
}
HashTable::~HashTable() {
  delete [] table;
}
void HashTable::store(Board &b, int type, int score, int bestmove, int depth) {
  unsigned int index;

  index = b.getHash()&(hash_table_size-1);

  if ( table[index].type == 0 || table[index].depth <= depth ) {
    table[index].key = b.getHash()>>bitcount;
    table[index].type = type;
    table[index].value = score;
    table[index].depth = depth;
    table[index].move = bestmove;
  }
}
void HashTable::lookup(Board &b, int *type, int *value, int *move, int *depth) {
  unsigned int index;

  hash_probes++;
  index = b.getHash()&(hash_table_size-1);
  if ( table[index].type != 0 ) {
    if ( table[index].key == b.getHash()>>bitcount ) {
      hash_hits++;
      *move = table[index].move;
      *value = table[index].value;
      *type = table[index].type;
      *depth = table[index].depth;
      return;
    } else
      collisions++;
  }
  *move = -1;
  *depth = -1;
}

#endif
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>
#include <unistd.h>
#include <stdarg.h>
#include <time.h>
#include <ctype.h>

#include <vector>
#include <list>
#include <algorithm>

using namespace std;

#define HISTORY_SIZE (4096)
#define MAX_DEPTH (64)
#define NUM_KILLERS (4)
#define INF (1000000)

#define TIME (1)
#define DEPTH (2)

#define HASHTYPE unsigned long

#define HINDEX_BITCOUNT (21)  //Must be log2(HASHSIZE)
#define HASHSIZE (2097152)
#define PV (1)
#define LOWER_BOUND (2)
#define UPPER_BOUND (3)
#define EXACT (4)

#define EVAL_CACHE_SIZE (16)

void print_bitboard(unsigned_64 b) {
  int j;

  for ( j = 0; j < SIZE*SIZE; j++ ) {
    if ( b & (1ULL << j) ) {
      printf("1 ");
    } else {
      printf("0 ");
    }
    if ( j%SIZE == SIZE-1 ) printf("\n");
  }
  putchar('\n');
}

typedef struct {
  int cmove;
  int argmove[MAX_DEPTH];
} Line;

struct Tree {
  int killers[NUM_KILLERS];
  int moves[MAX_MOVES];
  int tmove;

  int phase;
  int *cur_move_ptr;
  int *end_move_ptr;
  int move_count;
};

struct EvalCacheEntry {
  unsigned_64 lock;
  int ssd;
  int pos;
  int con;
};

EvalCacheEntry p1Cache[EVAL_CACHE_SIZE];
EvalCacheEntry p2Cache[EVAL_CACHE_SIZE];
unsigned long cacheHits = 0;
unsigned long cacheProbes = 0;

Board search_board;

int abort_search;
int debug = 0;

int search_type = DEPTH;
long search_start_time;
long search_time = 200;
int search_depth = 5;
int search_score;
int search_best;

int use_book = 1;
int rand_eval = 1;

long max_ply;
unsigned long node_count;
unsigned long qs_node_count;
unsigned long next_time_check;
unsigned long transpositions;
unsigned long hash_cutoff;
unsigned long firstMoveCutoffs;

unsigned long special_count;
unsigned long killer_count;
unsigned long history_count;
unsigned long null_move_cutoffs;
unsigned long hash_moves_tried;

long qs_start;

int history[HISTORY_SIZE];

HashTable *ht;
Timer timer;
Tree tree[MAX_DEPTH];
int game_record[100];
int game_mc;

///////////////////////////

int flipHorizTable[] = {
  42, 43, 44, 45, 46, 47, 48,
  35, 36, 37, 38, 39, 40, 41,
  28, 29, 30, 31, 32, 33, 34,
  21, 22, 23, 24, 25, 26, 27,
  14, 15, 16, 17, 18, 19, 20,
  7,  8,  9, 10, 11, 12, 13,
  0,  1,  2,  3,  4,  5,  6,
};

int flipVertTable[] = {
  6,  5,  4,  3,  2,  1,  0,
  13, 12, 11, 10,  9,  8,  7,
  20, 19, 18, 17, 16, 15, 14,
  27, 26, 25, 24, 23, 22, 21,
  34, 33, 32, 31, 30, 29, 28,
  41, 40, 39, 38, 37, 36, 35,
  48, 47, 46, 45, 44, 43, 42,
};

char game_history_filename[] = "game_record.bin";
vector<unsigned_64> game_history;

void readGameHistory() {
  FILE *f;
  unsigned_64 hash;
  if ( (f = fopen(game_history_filename, "r")) != NULL ) {
    printf_u("Reading game_record\n");
    while ( fread(&hash, sizeof(unsigned_64), 1, f) == 1 ) {
      game_history.push_back(hash);
    }
    fclose(f);
  }
}

int flipHoriz(int move) {
  int from = flipHorizTable[FromPos(move)];
  int to = flipHorizTable[ToPos(move)];
  return PackMove(from, to);
}

int flipVert(int move) {
  int from = flipVertTable[FromPos(move)];
  int to = flipVertTable[ToPos(move)];
  return PackMove(from, to);
}

int flipBoth(int move) {
  int from = flipHorizTable[flipVertTable[FromPos(move)]];
  int to = flipHorizTable[flipVertTable[ToPos(move)]];
  return PackMove(from, to);
}

struct BookEntry {
  unsigned_64 key;
  int value;
  int next;
};

#define INDEX_SIZE (4096)

class Book {
  int index[INDEX_SIZE];
  vector<BookEntry> data;
  public:
  Book();
  int read(char *);
  void writeBook(char *);
  int lookup(unsigned_64, int &);
  void add(unsigned_64, int);
  void load(char *lines);
};

Book::Book() {
  for ( int i = 0; i < INDEX_SIZE; i++ ) {
    index[i] = -1;
  }
}
int Book::read(char *fname) {
  FILE *f;
  BookEntry entry;

  if ( (f = fopen(fname, "rb")) != NULL ) {
    fread(index, sizeof(int), INDEX_SIZE, f);
    while ( fread(&entry, sizeof(BookEntry), 1, f) == 1 ) {
      data.push_back(entry);
    }
    fclose(f);
    return 1;
  }
  return 0;
}
void Book::writeBook(char *fname) {
  FILE *f;
  if ( (f = fopen(fname, "wb")) != NULL ) {
    fwrite(index, sizeof(int), INDEX_SIZE, f);
    for ( unsigned int i = 0; i < data.size(); i++ ) {
      fwrite(&(data[i]), sizeof(BookEntry), 1, f);
    }
    fclose(f);
  }
}
int Book::lookup(unsigned_64 hash, int &value) {
  int ind = index[hash&0xFFF];

  while ( ind != -1 ) {
    if ( data[ind].key == hash ) {
      //Entry in book
      value = data[ind].value;
      return 1;
    }
    ind = data[ind].next;
  }
  return 0;
}
void Book::add(unsigned_64 hash, int value) {
  BookEntry entry;
  int ind = hash&0xFFF;
  int location = data.size();

  if ( index[ind] != -1 ) {
    ind = index[ind];
    while ( data[ind].next != -1 ) {
      if ( data[ind].key == hash ) {
        //Entry already in book
        return;
      }
      ind = data[ind].next;
    }
    if ( data[ind].key == hash ) {
      //Entry already in book
      return;
    }
    data[ind].next = location;
  } else {
    index[ind] = location;
  }
  entry.key = hash;
  entry.value = value;
  entry.next = -1;
  data.push_back(entry);

}
void Book::load(char *lines) {
  Board b, bh, bv, bb;
  char *ptr = lines;
  int newLineFlag = 0;
  int moves[50];
  int moveCount = 0;
  int val;

  //	printf("Loading %s\n", lines);
  b.init();
  bh.init();
  bv.init();
  bb.init();
  while ( 1 ) {
    int moveNum = 0;

    //Parse the move number
    while ( isdigit(*ptr) ) {
      moveNum *= 10;
      moveNum += *ptr++ - '0';
    }

    int numPeriods = 0;
    while ( *ptr == '.' ) {
      numPeriods++;
      ptr++;
    }

    if ( newLineFlag ) {
      moveNum = (moveNum-1)*2;
      if ( numPeriods > 1 ) {
        moveNum++;
      }
      while ( moveCount > moveNum ) {
        moveCount--;
        b.unmake_move(moves[moveCount]);
        bh.unmake_move(flipHoriz(moves[moveCount]));
        bv.unmake_move(flipVert(moves[moveCount]));
        bb.unmake_move(flipBoth(moves[moveCount]));
      }
      newLineFlag = 0;
    }

    if ( !(isalpha(ptr[0]) && isdigit(ptr[1]) &&
          isalpha(ptr[2]) && isdigit(ptr[3])) ) {
      printf_u("Error: Expected move\n");
      return;
    }
    moves[moveCount] = strToMove(ptr);

    ////////////////////////////////////////
    //REMOVE THIS BEFORE CONTEST!!!!!!!!!!!!
    ////////////////////////////////////////
    if ( !b.isLegal(moves[moveCount]) ) {
      printf("Illegal move %c%c%c%c%c in book\n", ptr[0], ptr[1], ptr[2], ptr[3], ptr[4]);
      return;
    }
    b.make_move(moves[moveCount]);
    bh.make_move(flipHoriz(moves[moveCount]));
    bv.make_move(flipVert(moves[moveCount]));
    bb.make_move(flipBoth(moves[moveCount]));

    moveCount++;

    ptr += 4;
    val = 0;
    switch ( *ptr ) {
      case '?':
        val = -1;
        ptr++;
        break;
      case '!':
        val = 1;
        ptr++;
        break;
    }

    add(b.getHash(), val);
    add(bh.getHash(), val);
    add(bv.getHash(), val);
    add(bb.getHash(), val);

    while ( !isalnum(*ptr) ) {
      if ( *ptr == '\n' ) {
        newLineFlag = 1;
      } else if ( *ptr == 0 ) {
        return;
      }
      ptr++;
    }
  }
}

Book book;

int getBookMove(Board b) {
  char str[16];
  int moves[500];
  int good[500];
  int goodCount = 0;
  int count = b.get_legal_moves(moves);
  int max = -10;
  int value;

  for ( int i = 0; i < count; i++ ) {
    b.make_move(moves[i]);
    unsigned_64 hash = b.getHash();
    moveToStr(moves[i], str);
    if ( book.lookup(hash, value) ) {
      if ( find(game_history.begin(), game_history.end(), hash) != game_history.end() ) {
        value = -10;
      }
      good[i] = value;
      if ( value > max ) {
        max = value;
      }
    } else {
      good[i] = -10;
    }
    b.unmake_move(moves[i]);
  }

  if ( max < 0 ) return -1;

  for ( int i = 0; i < count; i++ ) {
    if ( good[i] == max ) {
      moveToStr(moves[i], str);
      goodCount++;
    }
  }
  int ind = rand()%goodCount;
  for ( int i = 0; i < count; i++ ) {
    if ( good[i] == max ) {
      if ( ind == 0 ) {
        return moves[i];
      }
      ind--;
    }
  }
  return -1;
}

void clearKillers() {
  int i, j;

  for ( i = 0; i < MAX_DEPTH; i++ )
    for ( j = 0; j < NUM_KILLERS; j++ )
      tree[i].killers[j] = -1;
}
inline void clearHistory() {
  memset(history, 0, sizeof(history));
}

void calcBlocking(Board &b, int color, int &block2, int &block3) {
  int i = ((color+1) << 4);
  int end = i+NUM_PIECES;
  block2 = 0;
  block3 = 0;
  for ( ; i < end; i++ ) {
    if ( b.pieceTable[i] == -1 ) continue;
    int pos = b.pieceTable[i];
    if ( edgeSquares[pos] ) {
      int blocked = popcount(blocking_mask[pos]&b.bitPieces[1-color]);
      if ( blocked == 3 ) {
        block3++;
        if ( cornerSquares[pos] ) {
          block3++;
        }
      } else if ( blocked == 2 && (blocking_mask[pos]&b.bitPieces[color]) == 0ULL ) {
        if ( cornerSquares[pos] ) {
          block3++;
        } else {
          block2++;
        }
      }
    }
  }
}

//Gets the index into the PrimaryGoal table for the specified
//categories.
inline int getCategoryIndex(int diff, int categories[]) {
  int ind = 0;
  int sign = 1;
  if ( diff < 0 ) {
    sign = -1;
    diff = -diff;
  }
  if ( diff > categories[0] ) {
    ind++;
  }
  if ( diff > categories[1] ) {
    ind++;
  }
  return ind*sign + 2;
}

inline EvalCacheEntry * probeEvalCache(unsigned_64 key, EvalCacheEntry *cache) {
  int ind = key%EVAL_CACHE_SIZE;
  return cache[ind].lock == key ? &(cache[ind]) : NULL;
}
inline void storeEvalCache(unsigned_64 key, EvalCacheEntry *cache, EvalCacheEntry *entry) {
  int ind = key%EVAL_CACHE_SIZE;
  cache[ind].lock = key;
  cache[ind].ssd = entry->ssd;
  cache[ind].pos = entry->pos;
  cache[ind].con = entry->con;
}

int eval(Board &b) {
  int p1 = 0;
  int p2 = 0;
  int end;
  int i;

  int winMargin = 0;
  if ( b.points[0]-b.points[1] >= POINTS_FOR_WIN ) {
    if ( b.turn == 0 || b.points[0]-b.points[1] > POINTS_FOR_WIN+8 ) {
      winMargin = 1;
      p1 += CrushingPointSpreadWeight;
    }
  } else if ( b.points[1]-b.points[0] >= POINTS_FOR_WIN ) {
    if ( b.turn == 1 || b.points[1]-b.points[0] > POINTS_FOR_WIN+8 ) {
      winMargin = -1;
      p2 += CrushingPointSpreadWeight;
    }
  }

  EvalCacheEntry p1Entry;
  EvalCacheEntry p2Entry;
  p1Entry.ssd = 0; //sum squared distances
  p1Entry.pos = 0;
  p1Entry.con = 0;
  p2Entry.ssd = 0;
  p2Entry.pos = 0;
  p2Entry.con = 0;

  cacheProbes++;
  EvalCacheEntry *entry = probeEvalCache(b.p1hash, p1Cache);
  if ( entry == NULL ) {
    i = 0x10;
    end = i+NUM_PIECES;
    for ( ; i < end; i++ ) {
      if ( b.pieceTable[i] == -1 ) continue;
      int pos = b.pieceTable[i];
      p1Entry.ssd += b.pieceDistances[i];
      p1Entry.pos += SquareWeights[pos];
      for ( int j = i+1; j < end; j++ ) {
        if ( b.pieceTable[j] == -1 ) continue;
        int tp2 = b.pieceTable[j];
        if ( abs(rankLookup[pos]-rankLookup[tp2]) <= 1 &&
            abs(fileLookup[pos]-fileLookup[tp2]) <= 1 ) {
          p1Entry.con += 2;
        }
      }
    }
    p1Entry.ssd /= b.pCounts[0];

    storeEvalCache(b.p1hash, p1Cache, &p1Entry);//p1ssd, p1pos, p1con, p1block2, p1block3);
  } else {
    cacheHits++;
    p1Entry.ssd = entry->ssd;
    p1Entry.pos = entry->pos;
    p1Entry.con = entry->con;
  }

  entry = probeEvalCache(b.p2hash, p2Cache);
  if ( entry == NULL ) {
    i = 0x20;
    end = i+NUM_PIECES;
    for ( ; i < end; i++ ) {
      if ( b.pieceTable[i] == -1 ) continue;
      int pos = b.pieceTable[i];
      p2Entry.ssd += b.pieceDistances[i];
      p2Entry.pos += SquareWeights[pos];
      for ( int j = i+1; j < end; j++ ) {
        if ( b.pieceTable[j] == -1 ) continue;
        int tp2 = b.pieceTable[j];
        if ( abs(rankLookup[pos]-rankLookup[tp2]) <= 1 &&
            abs(fileLookup[pos]-fileLookup[tp2]) <= 1 ) {
          p2Entry.con += 2;
        }
      }
    }
    p2Entry.ssd /= b.pCounts[1];
    storeEvalCache(b.p2hash, p2Cache, &p2Entry);//p2ssd, p2pos, p2con);
  } else {
    cacheHits++;
    p2Entry.ssd = entry->ssd;
    p2Entry.pos = entry->pos;
    p2Entry.con = entry->con;
  }

  int ci = getCategoryIndex(p2Entry.ssd-p1Entry.ssd, ConnectivityCategories);
  int pi = getCategoryIndex(b.points[0]-b.points[1], PointCategories);
  int cwm = ConnectivityVSPosition[ci][pi]*CVPWeight;

  //Blocking
  int p1block2, p1block3;
  int p2block2, p2block3;

  calcBlocking(b, 0, p1block2, p1block3);
  calcBlocking(b, 1, p2block2, p2block3);

  if ( winMargin != -1 ) {
    p1 -= (ConnectivityWeight-cwm)*p1Entry.ssd;
    p1 += p1Entry.con*AverageConnectionWeight/b.pCounts[0];

    //Player 2 gets penalties for blocked pieces only when he
    //doesn't have a crushing point advantage
    p2 -= p2block2*BlockedBy2Penalty + p2block3*BlockedBy3Penalty;
  } else {
    p1 += AntiConnectivityWeight*p1Entry.ssd;
  }

  if ( winMargin != 1 ) {
    p2 -= (ConnectivityWeight-cwm)*p2Entry.ssd;
    p2 += p2Entry.con*AverageConnectionWeight/b.pCounts[1];

    //Player 1 gets penalties for blocked pieces only when he
    //doesn't have a crushing point advantage
    p1 -= p1block2*BlockedBy2Penalty + p1block3*BlockedBy3Penalty;
  } else {
    p2 += AntiConnectivityWeight*p2Entry.ssd;
  }

  p1 += p1Entry.pos*PositionalWeight;
  p2 += p2Entry.pos*PositionalWeight;

  p1 += b.points[0]*(PointWeight+cwm);
  p2 += b.points[1]*(PointWeight+cwm);

  //Mobility
  p1 += b.get_moves_mobility(0);
  p2 += b.get_moves_mobility(1);

  p1 += b.pCounts[0]*PieceCountWeight;
  p2 += b.pCounts[1]*PieceCountWeight;

  int randTerm = 0;
  if ( rand_eval ) {
    randTerm = (rand()%20)-10;
  }
  if ( b.turn == 0 ) {
    int value = p1 - p2 + randTerm - ToMoveBonus;
    return value;
  } else {
    int value = p2 - p1 + randTerm + ToMoveBonus;
    return value;
  }
}

inline int isKiller(int ply, int bestmove) {
  if ( bestmove == -1 ) return 0;
  for ( int j = 0; j < NUM_KILLERS; j++ ) {
    if ( bestmove == tree[ply].killers[j] ) {
      return 1;
    }
  }
  return 0;
}
void updateKillers(int ply, int bestmove) {
  int j;
  for ( j = 0; j < NUM_KILLERS; j++ ) {
    if ( tree[ply].killers[j] == -1 ) {
      tree[ply].killers[j] = bestmove;
      return;
    }
    if ( tree[ply].killers[j] == bestmove ) {
      return;
    }
  }
  for ( j = NUM_KILLERS-1; j > 0; j-- ) {
    tree[ply].killers[j] = tree[ply].killers[j-1];
  }
  tree[ply].killers[0] = bestmove;
}
int next_move(int ply) {
  Tree *tptr = &(tree[ply]);

  switch ( tptr->phase ) {
    case 0:
      tptr->phase++;
      tptr->cur_move_ptr = tptr->killers;
      tptr->end_move_ptr = tptr->killers+NUM_KILLERS;

      //Hash move
      if ( search_board.isLegal(tptr->tmove) ) {
        hash_moves_tried++;
        return tptr->tmove;
      }
    case 1:
      //Killers
      while ( tptr->cur_move_ptr < tptr->end_move_ptr ) {
        int move = *(tptr->cur_move_ptr);
        tptr->cur_move_ptr++;
        if ( move != -1 && move != tptr->tmove &&
            search_board.isLegal(move) ) {
          return move;
        }
      }
      tptr->phase++;
    case 2:
      //Movegen and set up for history
      tptr->move_count = search_board.get_legal_moves(tptr->moves);
      tptr->phase++;
      tptr->cur_move_ptr = tptr->moves;
      tptr->end_move_ptr = tptr->moves+tptr->move_count;;
    case 3:
      //History moves
      if ( tptr->cur_move_ptr-tptr->moves < 4 ) {
        int max = -1;
        int *bestmove = NULL;
        int *move;
        int *endptr = tptr->end_move_ptr;
        int temp;
        for ( move = tptr->cur_move_ptr; move < endptr; move++ ) {
          if ( *move == tptr->tmove || isKiller(ply, *move) ) {
            temp = *(tptr->cur_move_ptr);
            *(tptr->cur_move_ptr++) = *move;
            *move = temp;
            continue;
          }
          if ( history[*move] > max ) {
            max = history[*move];
            bestmove = move;
          }
        }
        if ( bestmove != NULL ) {
          temp = *bestmove;
          *bestmove = *(tptr->cur_move_ptr);
          *(tptr->cur_move_ptr++) = temp;
          return temp;
        }

        return -1;
      } else {
        tptr->phase++;
      }
    case 4:
      //Everything else
      if ( tptr->cur_move_ptr < tptr->end_move_ptr ) {
        int move = *tptr->cur_move_ptr++;
        return move;
      }
  }

  return -1;
}
int search(int ply, int depth, int extensions, int alpha, int beta, int canNull, Line *pline) {
  Line line;
  int bestmove = -1;
  int curmove;
  int a;
  int best, value;
  int type = 0, hash_depth = 0;
  int foundpv = 0;

  if ( ply > max_ply ) max_ply = ply;
  line.argmove[0] = -1;
  pline->cmove = 0;

  int result = search_board.gameResult();
  if ( result != -1 ) {
    if ( result == search_board.turn ) {
      return INF;
    } else if ( result == 1-search_board.turn ) {
      return -INF;
    } else {
      return 0;
    }
  }

  a = alpha;
  node_count++;
  if ( search_type == TIME && node_count < next_time_check ) {
    next_time_check = node_count+1000;
    if ( timer.time() > search_start_time+search_time ) {
      abort_search = 1;
      return 0;
    }
  }

  tree[ply].tmove = -1;
  best = 0;
  ht->lookup(search_board, &type, &best, &tree[ply].tmove, &hash_depth);
  if ( ply > 0 && (best > INF-1000 || best < -INF+1000) ) {
    special_count++;
    return best;
  }
  if ( hash_depth >= depth && ply > 0 ) {
    if ( type == EXACT ) {
      transpositions++;
      return best;
    } else if ( type == LOWER_BOUND ) {
      if ( best > alpha ) {
        alpha = best;
      }
    } else if ( type == UPPER_BOUND ) {
      if ( best <= alpha ) {
        hash_cutoff++;
        return best;
      } else if ( best < beta ) {
        beta = best;
      }
    }
    if ( alpha >= beta ) {
      hash_cutoff++;
      return best;
    }
  }

  if ( depth <= 0 || ply >= MAX_DEPTH-5 ) {
    pline->cmove = 0;
    value = eval(search_board);
    return value;
  }

  //Try a null move
  if ( !canNull ) {
    int r = 2;
    if ( depth > 6 ) {
      r = 4;
    }
    if ( depth > r+1 ) {
      search_board.changeTurn();
      value = -search(ply+1, depth-r-1, extensions, -beta, -beta+1, 0, &line);
      search_board.changeTurn();

      if ( value >= beta ) {
        null_move_cutoffs++;
        return beta;
      }
    }
  }

  //Internal iterative deepening
  if ( tree[ply].tmove == -1 && depth > 2 ) {
    search(ply+1, depth-2, extensions, alpha, beta, 0, &line);
    if ( search_board.isLegal(line.argmove[0]) ) {
      tree[ply].tmove = line.argmove[0];
    }
  }

  best = -INF;
  tree[ply].phase = 0;
  tree[ply].move_count = -1;
  int movesSearched = 0;
  while ( (curmove = next_move(ply)) >= 0 ) {
    if ( best > alpha ) {
      foundpv = 1;
      alpha = best;
    }

    search_board.make_move(curmove);

    if ( foundpv == 1 ) {
      value = -search(ply+1, depth-1, extensions, -alpha-1, -alpha, 1, &line);
      if ( (value > alpha) && (value < beta) ) {
        value = -search(ply+1, depth-1, extensions, -beta, -alpha, 1, &line);
      }
    } else {
      value = -search(ply+1, depth-1, extensions, -beta, -alpha, 1, &line);
    }

    search_board.unmake_move(curmove);

    movesSearched++;

    if ( abort_search ) {
      return 0;
    }

    if ( value > best ) {
      best = value;
      bestmove = curmove;
      pline->argmove[0] = curmove;
      memcpy(pline->argmove + 1, line.argmove, line.cmove*sizeof(int));
      pline->cmove = line.cmove+1;
      if ( best >= beta || best >= INF-1 ) goto Done;
    }
  }

Done:
  if ( movesSearched == 0 ) {
    return -INF;
  }

  if ( movesSearched == 1 && tree[ply].move_count > 1 ) {
    firstMoveCutoffs++;
  }

  if ( best > INF-1000 )
    best--;
  else if ( best < -INF+1000 )
    best++;

  if ( best <= a ) {
    ht->store(search_board, UPPER_BOUND, best, bestmove, depth);
  } else if ( best >= beta ) {
    updateKillers(ply, bestmove);

    //Increment the history table
    if ( bestmove >= 0 ) {
      history[bestmove]+=depth;
    }
    ht->store(search_board, LOWER_BOUND, best, bestmove, depth);
  } else {
    ht->store(search_board, EXACT, best, bestmove, depth);
    if ( best > INF-1000 ) {
      updateKillers(ply, bestmove);
    }
  }
  return best;
}

/**
 * Root search does several things differently.
 * 1. It doesn't call get_legal_moves.  It expects the caller to have
 * passed a list of legal moves as a parameter.
 * 2. It removes moves from the movelist when it finds that they
 * lose.
 */
int root_search(int depth, int alpha, int beta, Line *pline, list<int> &moves) {
  list<int>::iterator iter;
  char str[16];
  Line line;
  int bestmove = -1;
  int curmove;
  int a;
  int best, value;
  int foundpv = 0;

  pline->cmove = 0;

  a = alpha;

  best = -INF;
  int movesSearched = 0;

  for ( iter = moves.begin(); iter != moves.end(); ) {
    curmove = *iter;
    if ( best > alpha ) {
      foundpv = 1;
      alpha = best;
    }

    search_board.make_move(curmove);

    if ( foundpv == 1 ) {
      value = -search(1, depth-1, 0, -alpha-1, -alpha, 0, &line);
      if ( (value > alpha) && (value < beta) ) {
        value = -search(1, depth-1, 0, -beta, -alpha, 0, &line);
      }
    } else {
      value = -search(1, depth-1, 0, -beta, -alpha, 0, &line);
    }

    search_board.unmake_move(curmove);
    movesSearched++;

    if ( abort_search ) {
      return best;
    }

    moveToStr(curmove, str);
    printf_u("%s %d, ", str, value);

    if ( value > best ) {
      //Put the move at the front of the list for the next iteration
      iter = moves.erase(iter);
      if ( value > -INF+1000 ) {
        moves.push_front(curmove);
      }

      best = value;
      bestmove = curmove;
      pline->argmove[0] = curmove;
      memcpy(pline->argmove + 1, line.argmove, line.cmove*sizeof(int));
      pline->cmove = line.cmove+1;
      if ( best >= beta || best == INF-1 ) {
        printf_u("Broke early because of best %d\n", best);
        goto Done;
      }
    } else if ( value < -INF+1000 ) {
      if ( moves.size() > 1 ) {
        printf_u("removed ");
        iter = moves.erase(iter);
      }
    } else {
      iter++;
    }
  }

Done:
  printf_u("\n%d moves searched\n", movesSearched);
  if ( movesSearched == 0 ) {
    printf_u("Player can't move in root_search\n");
    return -INF;
  }

  if ( movesSearched == 1 && tree[0].move_count > 1 ) {
    firstMoveCutoffs++;
  }

  if ( best > INF-1000 )
    best--;
  else if ( best < -INF+1000 )
    best++;

  return best;
}

int iterate_search(Board &b, Line *pv) {
  Line oldline;
  char str[64];
  int moves[MAX_MOVES];
  list<int> move_list;
  int movecount;
  int best_move = 0, last_best = -INF;
  int depth;
  int best;
  int alpha = -INF, beta = INF;
  int total_count;
  unsigned long last_nc = 1, nc;

  search_board = b;
  search_start_time = timer.time();
  depth = 1;
  movecount = b.get_legal_moves(moves);

  // Remove moves that are listed bad in book
  for ( int i = 0; i < movecount; i++ ) {
    b.make_move(moves[i]);
    unsigned_64 hash = b.getHash();
    moveToStr(moves[i], str);
    if ( book.lookup(hash, best) ) {
      if ( best == 1 ) {
        move_list.push_front(moves[i]);
        printf_u("%s preferred\n", str);
      } else if ( best == 0 ) {
        move_list.push_front(moves[i]);
        printf_u("%s good\n", str);
      } else {
        printf_u("%s BAD\n", str);
      }
    } else {
      move_list.push_back(moves[i]);
      printf_u("%s normal\n", str);
    }
    b.unmake_move(moves[i]);
  }
  if ( move_list.empty() ) {
    for ( int i = 0; i < movecount; i++ ) {
      move_list.push_front(moves[i]);
    }
  }

  while ( depth < MAX_DEPTH ) {
    best = -INF-1;
    abort_search = 0;
    total_count = 0;

    unsigned long start_count = node_count;

    printf_u("Ply %d\n", depth);
    best = root_search(depth, -INF, INF, &oldline, move_list);

    best_move = oldline.argmove[0];

    // Break only if the search was aborted and we hadn't already
    // found a winning move.
    if ( abort_search && best < INF-1000 ) {
      break;
    }

    if ( last_best != -INF ) {
      alpha = best;
      beta = best+1;
    }

    last_best = best_move;
    search_score = best;

    nc = node_count-start_count;
    memcpy(pv, &oldline, sizeof(Line));
    printf_u("%d %d %lu %lu ", depth, search_score, timer.time()-search_start_time, node_count);
    for ( int j = 0; j < oldline.cmove; j++ ) {
      moveToStr(oldline.argmove[j], str);
      printf_u("%s ", str);
    }
    printf_u("bf %f bf2 %f\n", exp((double)log(node_count)/((double)depth)),
        (double)nc/(double)last_nc);

    last_nc = nc;

    if ( best > INF-1000 || best < -INF+1000 || move_list.size() == 1 ) {
      break;
    }

    depth++;
    if ( search_type == DEPTH && depth > search_depth ) {
      break;
    }
  }
  printf_u("%lu nodes in %.2f seconds at %f nps\n", node_count, (timer.time()-search_start_time)/100.0, node_count*100.0/(timer.time()-search_start_time));
  printf_u("%lu qs nodes %.2f%%\n", qs_node_count, (float)100.0*qs_node_count/node_count);
  printf_u("%lu hash moves tried, %lu first move cutoffs\n", hash_moves_tried, firstMoveCutoffs);
  printf_u("%lu hash cutoffs %lu transpositions\n", hash_cutoff, transpositions);
  return last_best;
}

int run_search(Board &b) {
  Line pv;
  char str[64];
  int i, move;

  ht->hash_probes = 0;
  ht->hash_hits = 0;
  ht->collisions = 0;
  hash_cutoff = 0;
  transpositions = 0;
  node_count = 0;
  next_time_check = 1000;
  qs_node_count = 0;
  max_ply = 0;
  killer_count = 0;
  history_count = 0;
  special_count = 0;
  null_move_cutoffs = 0;
  hash_moves_tried = 0;
  firstMoveCutoffs = 0;
  clearKillers();
  clearHistory();

  move = iterate_search(b, &pv);
  for ( i = 0; i < pv.cmove; i++ ) {
    moveToStr(pv.argmove[i], str);
    printf_u("%s ", str);
  }
  printf_u("\n");
  printf_u("%lu null move cutoffs\n", null_move_cutoffs);
  return move;
}

void printBook(Board &b) {
  char str[16];
  int moves[MAX_MOVES];
  int movecount = b.get_legal_moves(moves);
  int best = 0;
  list<int> win;
  list<int> good;
  list<int> unknown;
  list<int> bad;

  // Remove moves that are listed bad in book
  for ( int i = 0; i < movecount; i++ ) {
    b.make_move(moves[i]);
    unsigned_64 hash = b.getHash();
    if ( book.lookup(hash, best) ) {
      if ( best == 1 ) {
        win.push_back(moves[i]);
      } else if ( best == 0 ) {
        good.push_back(moves[i]);
      } else {
        bad.push_back(moves[i]);
      }
    } else {
      unknown.push_back(moves[i]);
    }
    b.unmake_move(moves[i]);
  }
  list<int>::iterator iter;
  printf_u("Wins:\n");
  for ( iter = win.begin(); iter != win.end(); iter++ ) {
    moveToStr(*iter, str);
    printf_u("%s ", str);
  }
  printf_u("\nGood:\n");
  for ( iter = good.begin(); iter != good.end(); iter++ ) {
    moveToStr(*iter, str);
    printf_u("%s ", str);
  }
  printf_u("\nUnknkown (ugly):\n");
  for ( iter = unknown.begin(); iter != unknown.end(); iter++ ) {
    moveToStr(*iter, str);
    printf_u("%s ", str);
  }
  printf_u("\nBad:\n");
  for ( iter = bad.begin(); iter != bad.end(); iter++ ) {
    moveToStr(*iter, str);
    printf_u("%s ", str);
  }
  printf_u("\n");
}

void interactive(char *posFile) {
  Board b;
  int moves[500];
  int moveList[100];
  int movecount = 0;
  int count;
  char str[256];

  silent_search = 0;

  ht = new HashTable(HASHSIZE);
  b.init();

  if ( posFile[0] != 0 ) {
    b.init(posFile);
  }

  while ( 1 ) {
    b.print();
    count = b.get_legal_moves(moves);
    int result = b.gameResult();
    if ( result > -1 ) {
      printf("Game over ");
      if ( result == 0 ) {
        printf("2-0\n");
      } else if ( result == 1 ) {
        printf("0-2\n");
      } else {
        printf("1-1\n");
      }
    }
    printf("Enter move: ");
    fgets(str, 256, stdin);
    str[strlen(str)-1] = 0;

    if ( strcmp(str, "quit") == 0 ) {
      break;
    } else if ( strcmp(str, "new") == 0 ) {
      b.init();
    } else if ( strncmp(str, "load", 4) == 0 ) {
      b.init(str+5);
    } else if ( strcmp(str, "undo") == 0 ) {
      movecount--;
      moveToStr(moveList[movecount], str);
      b.unmake_move(moveList[movecount]);
    } else if ( strncmp(str, "sd", 2) == 0 ) {
      search_type = DEPTH;
      search_depth = atoi(str+3);
    } else if ( strncmp(str, "stime", 5) == 0 ) {
      search_type = TIME;
      search_time = atoi(str+6);
    } else if ( strcmp(str, "moves") == 0 ) {
      count = b.get_legal_moves(moves);
      for ( int i = 0; i < count; i++ ) {
        moveToStr(moves[i], str);

        b.make_move(moves[i]);
        moveToStr(moves[i], str);
        printf("%s\n", str);
        b.unmake_move(moves[i]);
      }
    } else if ( strcmp(str, "eval") == 0 ) {
      printf("Value %d\n", eval(b));
    } else if ( strcmp(str, "b") == 0 ) {
      printBook(b);
    } else if ( strcmp(str, "go") == 0 ) {
      int move = -1;

      //Check book first
      if ( use_book ) {
        printf_u("Probing book\n");
        move = getBookMove(b);
      }
      cacheHits = 0;
      cacheProbes = 0;
      if ( move == -1 ) {
        move = run_search(b);
      } else {
        moveToStr(move, str);
        printf_u("Book move %s\n", str);
      }

      b.make_move(move);
      printf("%lu hits of %lu probes %.2f%%\n", cacheHits, cacheProbes, 100.0*cacheHits/cacheProbes);
      moveList[movecount++] = move;
    } else {
      int move = strToMove(str);
      int flag = 0;
      for ( int i = 0; i < count; i++ ) {
        if ( move == moves[i] ) {
          flag = 1;
          break;
        }
      }
      if ( flag ) {
        b.make_move(move);
        moveList[movecount++] = move;
      } else {
        printf("Illegal move\n");
      }
    }
  }
}
void nonInteractive(char *myname, char *gameFile) {
  Board b;
  char str[16];
  int move = -1;

  silent_search = 1;

  printf_u("%s initBoard %s\n", myname, gameFile);
  b.init(gameFile);
  if ( search_type == -1 ) {
    search_type = TIME;
    search_time = (long)b.timeLeft[b.turn]*100;
    search_time /= 15;
    if ( search_time > 20 ) {
      search_time -= 10;
    }
  }

  //Check book first
  if ( use_book ) {
    printf_u("Probing book\n");
    move = getBookMove(b);
  }
  if ( move != -1 ) {
    moveToStr(move, str);
    printf_u("Book move %s\n", str);
  } else {
    ht = new HashTable(HASHSIZE);
    move = run_search(b);
    moveToStr(move, str);
  }
  b.make_move(move);
  FILE *f;
  if ( (f = fopen(game_history_filename, "a")) != NULL ) {
    unsigned_64 hash = b.getHash();
    fwrite(&hash, sizeof(unsigned_64), 1, f);
    printf_u("Wrote game_record\n");
    fclose(f);
  }
  printf("%c%c %c%c\n", str[0], str[1], str[2], str[3]);
}

int main(int argc, char *argv[]) {
  memset(p1Cache, 0, sizeof(p1Cache));
  memset(p2Cache, 0, sizeof(p2Cache));
  initMoveTables();
  srand(time(NULL));
  initRandomTables();

  debugFile = fopen("DEBUG", "a");
  silent_search = 1;

  readGameHistory();
  if ( !book.read("book-elopes.bin") ) {
    book.load(bookString);
    book.writeBook("book-elopes.bin");
  }

  char filename[256] = "";
  int mode = 0;
  int opt;

  search_type = -1;
  do {
    opt = getopt(argc, argv, "irbd:t:");
    switch ( opt ) {
      case 'd':
        search_type = DEPTH;
        search_depth = atoi(optarg);
        break;
      case 't':
        search_type = TIME;
        search_time = atoi(optarg);
        break;
      case 'i':
        mode = 1;
        break;
      case 'b':
        use_book = 0;
        break;
      case 'r':
        rand_eval = 1-rand_eval;
        break;
    }
  } while ( opt != -1 );

  if ( optind >= argc ) {
    mode = 1;
  } else {
    strncpy(filename, argv[optind], 256);
  }

  if ( mode == 0 ) {
    nonInteractive(argv[0], argv[optind]);
  } else if ( mode == 1 ) {
    if ( search_type == -1 ) {
      search_type = DEPTH;
      search_depth = 5;
    }
    interactive(filename);
  }

  fclose(debugFile);

}