#include <stdio.h>
#include <time.h>
#include <ctype.h>
#include <stdlib.h>

#define PATH 0 // ply==0 || path[0]==0x1450 && (ply==1 || path[1]==0x3122 && (ply==2 || path[2]==0x1122 && (ply==3 || path[3]==0x5443 && (ply==4))))

#define WHITE 16
#define BLACK 32
#define COLOR (WHITE|BLACK) // also used for edge guards

#define INF 8000

#define CAPTURED 255
#define MARGIN   30         // for futility pruning / lazy eval
#define STMKEY   123456789

#define KIWIPETE "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1"
#define FIDE     "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"

#define PST(PIECE, SQR) pstData[offs[PIECE] + SQR]
#define KEY(PIECE, SQR) zobrist[offs[PIECE] + SQR]

int pstData[7*128];
long long int zobrist[7*128];


unsigned char rawBoard[18*16];  // 0x88 board with 2-wide rim of edge guards
#define board (rawBoard + 2*17)

int stm; // side to move (WHITE or BLACK)

int location[48], offs[48], mvv[48]; // piece list

int firstDir[32] = { // offset of move list in steps[] table, per piece
  1, 1, 1, 1, 1, 1, 1, 1, 9, 9, 31, 31, 36, 36, 27, 18, // white pieces
  5, 5, 5, 5, 5, 5, 5, 5, 9, 9, 31, 31, 36, 36, 27, 18, // black pieces
};

int firstCapt[32] = { // offset of move list in steps[] table, per piece (captures)
  2, 2, 2, 2, 2, 2, 2, 2, 9, 9, 31, 31, 36, 36, 27, 18, // white pieces
  6, 6, 6, 6, 6, 6, 6, 6, 9, 9, 31, 31, 36, 36, 27, 18, // black pieces
};

signed char steps[] = {
  0,
  16, 15, 17, 0,                         //  1 wP
  -16, -15, -17, 0,                      //  5 bP
  31, -31, 33, -33, 18, -18, 14, -14, 0, //  9 N
  16, -16, 1, -1, 15, -15, 17, -17, 0,   // 18 K
  16, -16, 1, -1, 15, -15, 17, -17, 0,   // 27 Q   31 B
  16, -16, 1, -1, 0,                     // 36 R
   1, 5, 3, 7, 8, 4, 2, 6, 0,            // Q & B slides in terms of direction number
   1, 5, 3, 7, 0,                        // R slides in terms of direction number
};

unsigned char slideOffs[] = { // offset of board-size table in firstSlide[], per piece
  128, 128, 128, 128, 128, 128, 128, 128, 8, 8, 128, 128, 8, 8, 0, 0,
  136, 136, 136, 136, 136, 136, 136, 136, 8, 8, 128, 128, 8, 8, 0, 0,
};

unsigned char firstSlide[] = {
  // Queen                             // Rook
  45, 21, 21, 21, 21, 21, 21, 41,      69, 58, 58, 58, 58, 58, 58, 66,
  27,  0,  0,  0,  0,  0,  0, 15,      62, 49, 49, 49, 49, 49, 49, 54,
  27,  0,  0,  0,  0,  0,  0, 15,      62, 49, 49, 49, 49, 49, 49, 54,
  27,  0,  0,  0,  0,  0,  0, 15,      62, 49, 49, 49, 49, 49, 49, 54,
  27,  0,  0,  0,  0,  0,  0, 15,      62, 49, 49, 49, 49, 49, 49, 54,
  27,  0,  0,  0,  0,  0,  0, 15,      62, 49, 49, 49, 49, 49, 49, 54,
  27,  0,  0,  0,  0,  0,  0, 15,      62, 49, 49, 49, 49, 49, 49, 54,
  33,  9,  9,  9,  9,  9,  9, 37,      63, 50, 50, 50, 50, 50, 50, 55,
  // Bishop                             // unused
  84, 83, 83, 83, 83, 83, 83, 91,       0,  0,  0,  0,  0,  0,  0,  0,
  86, 72, 72, 72, 72, 72, 72, 80,       0,  0,  0,  0,  0,  0,  0,  0,
  86, 72, 72, 72, 72, 72, 72, 80,       0,  0,  0,  0,  0,  0,  0,  0,
  86, 72, 72, 72, 72, 72, 72, 80,       0,  0,  0,  0,  0,  0,  0,  0,
  86, 72, 72, 72, 72, 72, 72, 80,       0,  0,  0,  0,  0,  0,  0,  0,
  86, 72, 72, 72, 72, 72, 72, 80,       0,  0,  0,  0,  0,  0,  0,  0,
  86, 72, 72, 72, 72, 72, 72, 80,       0,  0,  0,  0,  0,  0,  0,  0,
  89, 77, 77, 77, 77, 77, 77, 81,       0,  0,  0,  0,  0,  0,  0,  0,
};

signed char slides[] = { // 0-terminated sets of directions sliders can move in
   1, 5, 3, 7, 8, 4, 2, 6, 0,   // 0   Q
   5, 3, 7, 4, 6, 0,            // 9
   1, 5, 7, 8, 6, 0,            // 15
   1, 3, 7, 8, 2, 0,            // 21
   1, 5, 3, 4, 2, 0,            // 27
   5, 3, 4, 0,                  // 33
   5, 7, 6, 0,                  // 37
   1, 7, 8, 0,                  // 41
   1, 3, 2, 0,                  // 45
   1, 5, 3, 7, 0,               // 49, 50  R
   1, 5, 7, 0,                  // 54, 55
   1, 3, 7, 0,                  // 58
   1, 5, 3, 0,                  // 62, 63
   1, 7, 0,                     // 66
   1, 3, 0,                     // 69
   8, 4, 2, 6, 0,               // 72  B
   4, 6, 0,                     // 77
   8, 6, 0,                     // 80, 81
   8, 2, 0,                     // 83, 84
   4, 2, 0,                     // 86
   4, 0,                        // 89
   8, 0,                        // 91
};

unsigned char firstLeap[] = {
  // King                             // Knight
  45, 21, 21, 21, 21, 21, 21, 41,     147,126, 96, 96, 96, 96,122,144,
  27,  0,  0,  0,  0,  0,  0, 15,     130,165, 72, 72, 72, 72,160,118,
  27,  0,  0,  0,  0,  0,  0, 15,     101, 79, 49, 49, 49, 49, 65, 91,
  27,  0,  0,  0,  0,  0,  0, 15,     101, 79, 49, 49, 49, 49, 65, 91,
  27,  0,  0,  0,  0,  0,  0, 15,     101, 79, 49, 49, 49, 49, 65, 91,
  27,  0,  0,  0,  0,  0,  0, 15,     101, 79, 49, 49, 49, 49, 65, 91,
  27,  0,  0,  0,  0,  0,  0, 15,     134,150, 58, 58, 58, 58,155,114,
  33,  9,  9,  9,  9,  9,  9, 37,     138,106, 86, 86, 86, 86,110,141,
  // white Pawn                       // black Pawn
  171,170,170,170,170,170,170,173,      8,  8,  8,  8,  8,  8,  8,  8,
  171,170,170,170,170,170,170,173,    178,175,175,175,175,175,175,176,
  171,170,170,170,170,170,170,173,    178,175,175,175,175,175,175,176,
  171,170,170,170,170,170,170,173,    178,175,175,175,175,175,175,176,
  171,170,170,170,170,170,170,173,    178,175,175,175,175,175,175,176,
  171,170,170,170,170,170,170,173,    178,175,175,175,175,175,175,176,
  171,170,170,170,170,170,170,173,    178,175,175,175,175,175,175,176,
    8,  8,  8,  8,  8,  8,  8,  8,    178,175,175,175,175,175,175,176,
};

signed char leaps[] = { // 0-terminated sets of directions leapers can move in
  16, -16, 1, -1, 15, -15, 17, -17, 0,   // 0  King
 -16, 1, -1, -15, -17, 0,                // 9
  16, -16, -1, 15, -17, 0,               // 15
  16, 1, -1, 15, 17, 0,                  // 21
  16, -16, 1, -15, 17, 0,                // 27
  -16, 1, -15, 0,                        // 33
  -16, -1, -17, 0,                       // 37
  16, -1, 15, 0,                         // 41
  16, 1, 17, 0,                          // 45
  31, -31, 33, -33, 18, -18, 14, -14, 0, // 49 Knight
  -31, -33, 18, -18, 14, -14, 0,         // 58         inner track
  31, -31, 33, -33, -18, 14, 0,          // 65
  31, 33, 18, -18, 14, -14, 0,           // 72
  31, -31, 33, -33, 18, -14, 0,          // 79
  -31, -33, -18, -14, 0,                 // 86         
  31, -33, -18, 14, 0,                   // 91
  31, 33, 18, 14, 0,                     // 96
  -31, 33, 18, -14, 0,                   // 101
  -31, -33, -14, 0,                      // 106
  -31, -33, -18, 0,                      // 110
  -33, -18, 14, 0,                       // 114
  31, -18, 14, 0,                        // 118
  31, 33, 14, 0,                         // 122
  31, 33, 18, 0,                         // 126
  33, 18, -14, 0,                        // 130
  -31, 18, -14, 0,                       // 134
  -31, -14, 0,                           // 138        corners
  -33, -18, 0,                           // 141
  31, 14, 0,                             // 144
  33, 18, 0,                             // 147
  -31, -33, 18, -14, 0,                  // 150
  -31, -33, -18, 14, 0,                  // 155
  31, 33, -18, 14, 0,                    // 160
  31, 33, 18, -14, 0,                    // 165
  15, 17, 0,                             // 170, 171 white Pawn
  15, 0,                                 // 173
  -15, -17, 0,                           // 175, 176 black Pawn
  -15, 0,                                // 178
};

unsigned int moveStack[10000];
int msp; // move stack pointer

int path[100], ply;
int pv[10000];
int *pvPtr = pv;
int followPV;

// Neighbor table

typedef union {
  long long int all;
  unsigned char d[8];
} Neighbor;

Neighbor neighbor[256];

int vec[8] = { 16, 17, 1, -15, -16, -17, -1, 15 };

void PrintNeighbor()
{ // for debugging only
  int r, f, i;
  for(i=0; i<8; i++) {
    for(r=8; r>=-1; r--) {
      for(f=-1; f<9; f++) {
        int s = 16*r + f & 255;
        printf("%4d", neighbor[s].d[i]);
      }
      printf("\n");
    }
    printf("\n");
  }
}

void Evacuate(int sqr)
{
  int d;
  for(d=0; d<4; d++) {
    int up = neighbor[sqr].d[d];
    int dn = neighbor[sqr].d[d+4];
    neighbor[up].d[d+4] = dn;
    neighbor[dn].d[d] = up;
  }
}

void Reoccupy(int sqr)
{
  int d;
  for(d=0; d<4; d++) {
    int up = neighbor[sqr].d[d];
    int dn = neighbor[sqr].d[d+4];
    neighbor[up].d[d+4] = neighbor[dn].d[d] = sqr;
  }
}

void Occupy(int sqr)
{
  int d;
  for(d=0; d<4; d++) {
    int dn, up = sqr, v = vec[d];
    while(!board[up+=v]) {}
    up &= 255; // Yegh!
    dn = neighbor[up].d[d+4];
    neighbor[up].d[d+4] = sqr;
    neighbor[dn].d[d] = sqr;
    neighbor[sqr].d[d+4] = dn;
    neighbor[sqr].d[d] = up;
  }
}

void InitNeighbor()
{ // initilizes a neighbor table for an empty board. (Opposit rim squares see each other.)
  int r, f, i;
  for(i=0; i<256; i++) neighbor[i].all = 0;
  for(r=0; r<8; r++) neighbor[16*r-1&255].d[2] = 16*r + 8, neighbor[16*r+8].d[6] = 16*r - 1;
  for(f=0; f<8; f++) neighbor[f-16 & 255].d[0] = 16*8 + f, neighbor[16*8+f].d[4] = f - 16;
  for(f=0; f<8; f++) neighbor[f-15 & 255].d[7] = 16*f +15, neighbor[16*f+15].d[3] = f - 15;
  for(f=0 ;f<8; f++) neighbor[f-17 & 255].d[1] = 136-16*f, neighbor[136-16*f].d[5] = f - 17;
  for(f=0; f<8; f++) neighbor[f+127].d[3] = 16*f - 8,  neighbor[16*f-8 & 255].d[7] = f + 127;
  for(f=0; f<8; f++) neighbor[f+129].d[5] = 95 - 16*f, neighbor[95-16*f & 255].d[1] = f + 129;
}

int nodeCnt, patCnt, genCnt, evalCnt, qsCnt, leafCnt, captCnt[2]; // for statistics

int pType[] = { 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6 };
int pieceVal[] = { 0, 90, 325, 350, 500, 950, 0 };

void Init()
{
  int i, r, f;
  char *p;
  // board with rim
  for(i=0; i<18*16; i++) rawBoard[i] = COLOR;
  for(i=0; i<16; i++) {
    offs[i+WHITE] = 128*pType[i];
    offs[i+BLACK] = 128*pType[i] + 8;
    mvv[i+WHITE] = mvv[i+BLACK] = 16*pType[i] << 24;
  }
  for(r=0; r<8; r++) for(f=0; f<8; f++) {
    int s = 16*r+f;
    int d = 14 - (r-3.5)*(r-3.5) - (f-4)*(f-4);
    board[s] = 0;
    for(i=1; i<6; i++) {
      pstData[128*i+s] =
      pstData[128*i+(s^0x70)+8] = pieceVal[i] + d*(i < 4) + 9*(i == 1)*r;
    }
    pstData[128*6+s] = pstData[128*6+(s^0x70)+8] = -d;
  }
  p = (char*) (zobrist + 128);
  for(i=0; i<6*8*128; i++) *p++ = rand()*rand() >> 6;
}

char *Move2text(int move)
{
  static char buf[10];
  sprintf(buf, "%c%d%c%d", (move >> 8 & 7) + 'a', (move >> 12 & 7) + 1, (move &7) + 'a', (move >> 4 & 7) + 1);
  return buf;
}

#define MOVE(F, T) (256*(F) + (T))

int CaptGen3()
{
  int i, first = msp;

  for(i=0; i<10; i++) {
    int piece = stm + i;
    int from = location[piece];
    if(from != CAPTURED) {
      int step, dir = firstCapt[piece-16]; // firstLeap[slideOffs[piece-16] + from];
      while((step = steps[dir++])) {
        int to = from + step;
        int victim = board[to];
        int h = victim ^ stm;          // gets >= COLOR if colr bits complement each other
        if(h >= COLOR) {               // target is foe
          if(h == COLOR+15) return 0;  // captures King
          moveStack[--first] = MOVE(from, to) + mvv[victim] - ((piece & 15) << 24);
        }
      }
    }
  }
  for(i=10; i<15; i++) {
    int piece = stm + i;
    int from = location[piece];
    if(from != CAPTURED) {
      int d, dir = firstSlide[slideOffs[piece-16] + from];
      while((d = slides[dir++])) {          // direction nr (+1)
        int to = neighbor[from].d[d-1];     // the directions were offset by 1 to avoid the 0 sentinel
        int victim = board[to];
        int h = victim ^ stm;
        if(h >= COLOR) {                         // target square is occupied
          if((victim & 15) == 15) return 0; // captures King
          moveStack[--first] = MOVE(from, to) + mvv[victim] - ((piece & 15) << 24);
        }
      }
    }
  }
  if(1) {
    int piece = stm + 15;
    int from = location[piece];
    int step, dir = 18;//firstLeap[from]; // location-dependent step list
    while((step = steps[dir++])) {
      int to = from + step;
      int victim = board[to];
      int h = victim ^ stm;          // gets >= COLOR if colr bits complement each other
      if(h >= COLOR) {               // target is foe
        if(h == COLOR+15) return 0;  // captures King
        moveStack[--first] = MOVE(from, to) + mvv[victim] - (15 << 24);
      }
    }
  }
  return first;
}

int CaptGen2()
{
  int i, first = msp;

  for(i=0; i<10; i++) {
    int piece = stm + i;
    int from = location[piece];
    if(from != CAPTURED) {
      int step, dir = firstCapt[piece-16];
      while((step = steps[dir++])) {
        int to = from + step;
        int victim = board[to];
        int h = victim ^ stm;          // gets >= COLOR if colr bits complement each other
        if(h >= COLOR) {               // target is foe
          if(h == COLOR+15) return 0;  // captures King
          moveStack[--first] = MOVE(from, to) + mvv[victim] - ((piece & 15) << 24);
        }
      }
    }
  }
  for(i=10; i<15; i++) {
    int piece = stm + i;
    int from = location[piece];
    if(from != CAPTURED) {
      int step, dir = firstCapt[piece-16];
      while((step = steps[dir++])) {
        int to = from;
        do {
          int victim = board[to += step];
          if(victim) {                         // target square is occupied
            if(victim & stm) break;            // own piece or edge guard
            if((victim & 15) == 15) return 0;  // captures King
            moveStack[--first] = MOVE(from, to) + mvv[victim] - ((piece & 15) << 24);
            break;
          }
        } while(dir >= 27);
      }
    }
  }
  if(1) {
    int piece = stm + 15;
    int from = location[piece];
    int step, dir = 18;
    while((step = steps[dir++])) {
      int to = from + step;
      int victim = board[to];
      int h = victim ^ stm;          // gets >= COLOR if colr bits complement each other
      if(h >= COLOR) {               // target is foe
        if(h == COLOR+15) return 0;  // captures King
        moveStack[--first] = MOVE(from, to) + mvv[victim] - (15 << 24);
      }
    }
  }
  return first;
}

int CaptGen()
{
  int i, first = msp;

  for(i=0; i<16; i++) {
    int piece = stm + i;
    int from = location[piece];
    if(from != CAPTURED) {
      int step, dir = firstCapt[piece-16];
      while((step = steps[dir++])) {
        int to = from;
        do {
          int victim = board[to += step];
          if(victim) {                         // target square is occupied
            if(victim & stm) break;            // own piece or edge guard
            if((victim & 15) == 15) return 0;  // captures King
            moveStack[--first] = MOVE(from, to) + mvv[victim] - ((piece & 15) << 24);
            break;
          }
        } while(dir >= 27);
      }
    }
  }
  return first;
}

int MoveGen()
{
  int i, first = msp;

  for(i=0; i<16; i++) {
    int piece = stm + i;
    int from = location[piece];
    if(from != CAPTURED) {
      int step, dir = firstDir[piece-16];
      while((step = steps[dir++])) {
        int to = from;
        do {
          int victim = board[to += step];
          if(victim) {                         // target square not empty
            if(victim & stm) break;            // own piece or edge guard
            if(!(piece & 8)) {                 // is Pawn
              if(!(step & 7)) break;           // straight
            }
            if((victim & 15) == 15) return 0;  // captures King
            moveStack[--first] = MOVE(from, to) + mvv[victim] - ((piece & 15) << 24);
            break;
          } else {                             // non-capture
            if(!(piece & 8)) {                 // is Pawn
              if(step & 7) break;              // diagonal
              if(from - 32 & 64 && !board[to + step])
                moveStack[msp++] = MOVE(from, to + step);
            }
            moveStack[msp++] = MOVE(from, to); // generate non-capture
          }
        } while(dir >= 27);
      }
    }
  }
  return first;
}

int Evaluate(int pstEval)
{
  return pstEval;
}

typedef struct {
  long long int hashKey, oldKey; // keys
  Neighbor savedNeighbor;        // 8 neighbors
  int pstEval, oldEval, curEval; // scores
  int alpha, beta;               // scores
  int from, to;                  // squares
  int piece, victim;             // pieces
  int depth;                     // depth
} UndoInfo;

int MakeMove(int move, UndoInfo *u)
{
  // decode the move
  u->to = move & 255;
  u->from = move >> 8 & 255;
  u->piece = board[u->from];
  u->victim = board[u->to];

  // update the incremental evaluation
  u->pstEval = -(u->oldEval + PST(u->piece, u->to) - PST(u->piece, u->from) + PST(u->victim, u->to));
//if(PATH) printf("     eval=%d beta=%d MARGIN=%d\n", u->pstEval, u->beta, MARGIN);
  if(u->depth <= 0 && u->pstEval > u->beta + MARGIN) return -INF-1; // futility (child will stand pat)

  // update hash key, and possibly abort on repetition
  u->hashKey =   u->oldKey  ^ KEY(u->piece, u->to) ^ KEY(u->piece, u->from) ^ KEY(u->victim, u->to);
  // if(REPEAT) return 0;

  // update board and piece list
  board[u->from] = 0;
  board[u->to]   = u->piece;
  location[u->piece]  = u->to;
  location[u->victim] = CAPTURED;

  Evacuate(u->from);
  if(!u->victim) u->savedNeighbor = neighbor[u->to], Occupy(u->to);
path[ply++] = move & 0xFFFF; captCnt[!u->victim]++;
  return INF+1; // kludge to indicate success
}

void UnMake(UndoInfo *u)
{
  // restore board and piece list
ply--;
  board[u->from] = u->piece;
  board[u->to]   = u->victim;
  location[u->piece]  = u->from;
  location[u->victim] = u->to;
  if(!u->victim) Evacuate(u->to), neighbor[u->to] = u->savedNeighbor;
  Reoccupy(u->from);
}

int Search(UndoInfo *u) // pass all parameters in a struct
{
  UndoInfo undo;
  int first, curMove, noncapts, searched, alpha = u->alpha;
  int *myPV = pvPtr;

  nodeCnt++;
  *pvPtr++ = 0; // empty PV

  // QS / stand pat
  if(u->depth <= 0) {
    qsCnt++;
    if(u->pstEval > alpha - MARGIN) { // don't bother with full eval if hopeless
      undo.curEval = Evaluate(u->pstEval); evalCnt++;
      if(undo.curEval > alpha) {
        if(undo.curEval >= u->beta) { patCnt++; return u->beta; }
        alpha = undo.curEval;
      }
    }
  } else if(u->pstEval > u->beta - MARGIN) { // null-move pruning
    int score;
    undo.hashKey =  u->hashKey ^ STMKEY;
    undo.pstEval = -u->pstEval;
    undo.alpha   = -u->beta;
    undo.beta    = 1 - u->beta;
    undo.depth   = (u->depth > 3 ? u->depth - 3 : 0);
    stm ^= COLOR;
    score = -Search(&undo);
    stm ^= COLOR;
    if(score >= u->beta) return u->beta;
  }

  // generate moves
  noncapts = msp += 70;          // reserve space for new move list
  first = (u->depth > 0 ? MoveGen() : CaptGen3());
  genCnt++;
  if(!first) { alpha = INF; goto abort; }  // King capture detected
  if(followPV >= 0) {                      // first branch
    int i, m = pv[followPV++];             // get the move
    if(m) {                                // move to follow
      m |= 255<<24;                        // assign highest sort priority
      for(i=first; i<msp; i++) {           // run through move list
        if(!(m - moveStack[i] & 0xFFFF)) { // search it amongst generated moves
          moveStack[--first] = m;          // prepend to move list
          moveStack[i] = 0;                // zap PV move in list
          break;
        }
      }
    } else followPV = -1;
  }

  // set child & make-move parameters that are always the same
  undo.oldKey  =  u->hashKey ^ STMKEY;
  undo.oldEval =  u->pstEval;
  undo.depth   =  u->depth - 1;
  undo.alpha   = -u->beta;
  stm ^= COLOR;
  searched = 0;

  // move loop
  for(curMove = first; curMove < msp; curMove++) {
    int score;
    unsigned int move = moveStack[curMove];
    // move picker
    if(curMove < noncapts) { // still has to be sorted
      int i, j = curMove;
      for(i=curMove+1; i<noncapts; i++) { // extract best capture
        unsigned int m = moveStack[i];
        if(m > move) j = i, move = m;
      }
      moveStack[j] = moveStack[curMove]; moveStack[curMove] = move;
    } else if(u->depth <= 0) { // in QS no non-captures at all
      break;
    }
    if(!move) continue;        // skip zapped moves

    // recursion
    undo.beta = -alpha;
    score = MakeMove(move, &undo); // rejected moves get their score here
    if(score < -INF) break;        // move is futile, and so will be all others
    if(score > INF) { // move successfully made
      searched++;
      score = -Search(&undo);
      UnMake(&undo);
    }
if(PATH) printf("%2d:%d %3d. %08x %s %5d %5d\n", ply, u->depth, curMove, move, Move2text(move), score, alpha), fflush(stdout);
    // minimaxing
    if(score > alpha) {
      int *p;
      if(score >= u->beta) {
        alpha = u->beta;
        break;
      }
      alpha = score;
      p = pvPtr; pvPtr = myPV;    // pop old PV
      *pvPtr++ = move;            // push new PV, starting with this move
      while((*pvPtr++ = *p++)) {} // and append child PV
    }
  }
  stm ^= COLOR;
 abort:
  leafCnt += !searched;
  msp = noncapts - 70; // pop move list
  pvPtr = myPV;        // pop PV (but remains above stack top)
  return alpha;
}

void SearchRoot(UndoInfo *u, int maxDepth)
{
  nodeCnt = patCnt = evalCnt = genCnt = qsCnt = leafCnt = captCnt[0] = captCnt[1] = 0;
  u->alpha = -INF;
  u->beta  = INF;
  followPV = -1;   // nothing to follow at d=1
  for(u->depth=1; u->depth<=maxDepth; u->depth++) { // iterative deepening
    int i, score;
    score = Search(u);
    printf("%2d %4d %9d %d", u->depth, score, nodeCnt, 0);
    for(i=0; pv[i]; i++) printf(" %s", Move2text(pv[i]));
    printf("\n"), fflush(stdout);
    followPV = 0;  // follow this PV on next search
  }
}

int Setup(UndoInfo *u, char *fen)
{
  static char pieces[] = "PPPPPPPPNNBBRRQK";
  int r, f, i;
  for(i=WHITE; i<COLOR; i++) location[i] = CAPTURED;
  for(r=0; r<8; r++) for(f=0; f<8; f++) board[16*r+f] = 0;
  InitNeighbor();
  u->pstEval = 0; u->hashKey = 0;

  r = 7; f = 0;
  while(*fen) {
    if(*fen == '/') r--, f = 0;
    else if(*fen > '0' && *fen <= '9') f += *fen - '0'; // empties
    else if(*fen >= 'A') {                              // piece
      int color = (*fen >= 'a' ? BLACK : WHITE);
      for(i=0; i<16; i++) {
        int sqr = 16*r + f;
        if(location[color+i] == CAPTURED && !(*fen - pieces[i] & 31)) {
          location[color+i] = sqr;
          board[16*r+f] = color + i;
          u->pstEval += PST(color + i, sqr)*(color == WHITE ? 1 : -1);
          u->hashKey ^= KEY(color + i, sqr);
          Occupy(sqr);
          break;
        }
      }
      f++;
    } else break;
    fen++;
  }
  while(*fen == ' ') fen++;
  if(*fen == 'b') u->pstEval *= -1;
  return (*fen == 'b' ? BLACK : WHITE);
}

UndoInfo root;

int main()
{
  time_t t;
  Init();
//int j, i = firstLeap[slideOffs[17] + 0x56]; while((j = leaps[i++])) printf(" %d. %d:%d\n", slideOffs[1], i, j);
//return;
  stm = Setup(&root, FIDE);
  stm = Setup(&root, KIWIPETE);
  t = clock();
  SearchRoot(&root, 8);
  t = clock() - t;
  printf("t = %6.3f sec\n", t * (1./CLOCKS_PER_SEC));
  printf("%10d nodes (%3.1f Mnps)\n%10d QS (%3.1f%%)\n", nodeCnt, nodeCnt*1e-6*CLOCKS_PER_SEC/t, qsCnt, qsCnt*100./nodeCnt);
  printf("%10d evals (%3.1f%%)\n%10d stand-pats (%3.1f%%)\n", evalCnt, evalCnt*100./qsCnt, patCnt, patCnt*100./qsCnt);
  printf("%10d leaves (%3.1f%%)\n", leafCnt, leafCnt*100./qsCnt);
  printf("%10d move gens\ncaptures: %3.1f%%\n", genCnt, captCnt[0]*100./(captCnt[0] + captCnt[1]));
  return 0;
}
