/***************************************************************************/
/*                               micro-Max,                                */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller  */
/***************************************************************************/
/* version 3.2 (2000 characters) features:                                 */
/* - recursive negamax search                                              */
/* - quiescence search with recaptures                                     */
/* - recapture extensions                                                  */
/* - (internal) iterative deepening                                        */
/* - best-move-first 'sorting'                                             */
/* - a hash table storing score and best move                              */
/* - full FIDE rules (expt minor ptomotion) and move-legality checking     */

/* fused to generic Winboard driver */

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

#define EMPTY 0
#define WHITE 8
#define BLACK 16

#define STATE 64

/* make unique integer from engine move representation */
#define PACK_MOVE 256*K + L;

/* convert intger argument back to engine move representation */
#define UNPACK_MOVE(A) K = (A)>>8 & 255; L = (A) & 255;

/* Global variables visible to engine. Normally they */
/* would be replaced by the names under which these  */
/* are known to your engine, so that they can be     */
/* manipulated directly by the interface.            */

int Side;
int Move;
int PromPiece;
int Result;
int TimeLeft;
int MovesLeft;
int MaxDepth;
int Post;
int Fifty;
int UnderProm;

long long int rdtsc();
long long int Ticks, tlim;

int GameHistory[1024];
char HistoryBoards[1024][STATE];
int GamePtr, HistPtr;

#define F(I,S,N) for(I=S;I<N;I++)
#define W(A) while(A)
#define K(A,B) *(int*)(T+A+(B&8)+S*(B&7))
#define J(A) K(y+A,b[y])-K(x+A,u)-K(H+A,t)

int U=(1<<22)-1;
struct _ {int K,V;char X,Y,D;} *A;             /* hash table, 16M+8 entries*/

int V=112,M=136,S=128,I=8e3,C=799,Q,N,i;       /* V=0x70=rank mask, M=0x88 */

char O,K,L,
w[]={0,1,1,3,-1,3,5,9},                        /* relative piece values    */
o[]={-16,-15,-17,0,1,16,0,1,16,15,17,0,14,18,31,33,0, /* step-vector lists */
     7,-1,11,6,8,3,6,                          /* 1st dir. in o[] per piece*/
     6,3,5,7,4,5,3,6},                         /* initial piece setup      */
b[129],                                        /* board: half of 16x8+dummy*/
T[1035],                                       /* hash translation table   */

n[]=".?+nkbrq?*?NKBRQ";                        /* piece symbols on printout*/

D(k,q,l,e,J,Z,E,z,n)    /* recursive minimax search, k=moving side, n=depth*/
int k,q,l,e,J,Z,E,z,n;  /* (q,l)=window, e=current eval. score, E=e.p. sqr.*/
{                       /* e=score, z=prev.dest; J,Z=hashkeys; return score*/
 int j,r,m,v,d,h,i=8,F,G;
 char t,p,u,x,y,X,Y,H,B;
 struct _*a=A;
                                               /* lookup pos. in hash table*/
 j=(k*E^J)&U;                                  /* try 8 consec. locations  */
 W((h=A[++j].K)&&h-Z&&--i);                    /* first empty or match     */
 a+=i?j:0;                                     /* dummy A[0] if miss & full*/
 if(a->K)                                      /* hit: pos. is in hash tab */
 {d=a->D;v=a->V;X=a->X;                        /* examine stored data      */
  if(d>=n)                                     /* if depth sufficient:     */
  {if(v>=l|X&S&&v<=q|X&8)return v;             /* use if window compatible */
   d=n-1;                                      /* or use as iter. start    */
  }X&=~M;Y=a->Y;                               /*      with best-move hint */
  Y=d?Y:0;                                     /* don't try best at d=0    */
 }else d=X=Y=0;                                /* start iter., no best yet */
 N++;                                          /* node count (for timing)  */
 W(d++<n|z==8&(unsigned long long int)(rdtsc()-Ticks)<tlim&d<=MaxDepth)        /* iterative deepening loop */
 {x=B=X;                                       /* start scan at prev. best */
  Y|=8&Y>>4;                                   /* request try noncastl. 1st*/
  m=d>1?-I:e;                                  /* unconsidered:static eval */
  do{u=b[x];                                   /* scan board looking for   */
   if(u&k)                                     /*  own piece (inefficient!)*/
   {r=p=u&7;                                   /* p = piece type (set r>0) */
    j=o[p+16];                                 /* first step vector f.piece*/
    W(r=p>2&r<0?-r:-o[++j])                    /* loop over directions o[] */
    {A:                                        /* resume normal after best */
     y=x;F=G=S;                                /* (x,y)=move, (F,G)=castl.R*/
     do{H=y+=r;                                /* y traverses ray          */
      if(Y&8)H=y=Y&~M;                         /* sneak in prev. best move */
      if(y&M)break;                            /* board edge hit           */
      if(p<3&y==E)H=y^16;                      /* shift capt.sqr. H if e.p.*/
      t=b[H];if(t&k|p<3&!(r&7)!=!t)break;      /* capt. own, bad pawn mode */
      i=99*w[t&7];                             /* value of capt. piece t   */
      if(i<0||E-S&&b[E]&&y-E<2&E-y<2)m=I;      /* K capt. or bad castling  */
      if(m>=l)goto C;                          /* abort on fail high       */
    
      if(h=d-(y!=z))                           /* remaining depth(-recapt.)*/
      {v=p<6?b[x+8]-b[y+8]:0;                  /* center positional pts.   */
       b[G]=b[H]=b[x]=0;b[y]=u&31;             /* do move, strip virgin-bit*/
       if(!(G&M)){b[F]=k+6;v+=30;}             /* castling: put R & score  */
       if(p<3)                                 /* pawns:                   */
       {v-=9*(((x-2)&M||b[x-2]!=u)+            /* structure, undefended    */
              ((x+2)&M||b[x+2]!=u)-1);         /*        squares plus bias */
        if(y+r+1&S){b[y]|=7;i+=C;}             /* promote p to Q, add score*/
       }
       v=-D(24-k,-l-(l>e),m>q?-m:-q,-e-v-i,    /* recursive eval. of reply */
            J+J(0),Z+J(8)+G-S,F,y,h);          /* J,Z: hash keys           */
       v-=v>e;                                 /* delayed-gain penalty     */
       if(z==9)                                /* called as move-legality  */
       {if(v!=-I&x==K&y==L)                    /*   checker: if move found */
        {Q=-e-i;O=F;
         if((b[y]&7)!=p && PromPiece == 'n') UnderProm = y;
         if((b[y]&7)!=p) {printf("tellics promotion\n");fflush(stdout);};
         Fifty = t|p<3?0:Fifty+1;
                    return l;}                 /*   & not in check, signal */
        v=m;                                   /* (prevent fail-lows on    */
       }                                       /*   K-capt. replies)       */
       b[G]=k+38;b[F]=b[y]=0;b[x]=u;b[H]=t;    /* undo move,G can be dummy */
       if(Y&8){m=v;Y&=~8;goto A;}              /* best=1st done,redo normal*/
       if(v>m){m=v;X=x;Y=y|S&G;}               /* update max, mark with S  */
      }                                        /*          if non castling */
      t+=p<5;                                  /* fake capt. for nonsliding*/
      if(p<3&6*k+(y&V)==S                      /* pawn on 3rd/6th, or      */
          ||(u&~24)==36&j==7&&                 /* virgin K moving sideways,*/
          G&M&&b[G=(x|7)-(r>>1&7)]&32          /* 1st, virgin R in corner G*/
          &&!(b[G^1]|b[G^2])                   /* 2 empty sqrs. next to R  */
      ){F=y;t--;}                              /* unfake capt., enable e.p.*/
     }W(!t);                                   /* if not capt. continue ray*/
  }}}W((x=x+9&~M)-B);                          /* next sqr. of board, wrap */
C:if(m>I/4|m<-I/4)d=99;                        /* mate is indep. of depth  */
  m=m+I?m:-D(24-k,-I,I,0,J,Z,S,z,1)/2;         /* best loses K: (stale)mate*/
  if(!a->K|(a->X&M)!=M|a->D<=d)                /* if new/better type/depth:*/
  {a->K=Z;a->V=m;a->D=d;A->K=0;                /* store in hash,dummy stays*/
   a->X=X|8*(m>q)|S*(m<l);a->Y=Y;              /* empty, type (limit/exact)*/
  }                                            /*    encoded in X S,8 bits */
if(z==8&Post)printf("%2d %6d %8d %10d %c%c%c%c\n",d-1,m,(int)((rdtsc()-Ticks)/10000000LL),N,'a'+(X&7),'8'-(X>>4),'a'+(Y&7),'8'-(Y>>4&7)),fflush(stdout);
 }
if(z==8&Post)printf("tellics %2d %6d %8d %10d %c%c%c%c\n",d-1,m,(int)((rdtsc()-Ticks)/10000000LL),N,'a'+(X&7),'8'-(X>>4),'a'+(Y&7),'8'-(Y>>4&7)),fflush(stdout);
 if(z&8){K=X;L=Y&~M;}
 return m;                                     
}




/* Generic main() for Winboard-compatible engine     */
/* (Inspired by TSCP)                                */
/* Author: H.G. Muller                               */

/* The engine is invoked through the following       */
/* subroutines, that can draw on the global vaiables */
/* that are maintained by the interface:             */
/* Side         side to move                         */
/* Move         move input to or output from engine  */
/* PromPiece    requested piece on promotion move    */
/* TimeLeft     ms left to next time control         */
/* MovesLeft    nr of moves to play within TimeLeft  */
/* MaxDepth     search-depth limit in ply            */
/* Post         boolean to invite engine babble      */

/* InitEngine() progran start-up initialization      */
/* InitGame()   initialization to start new game     */
/*              (sets Side, but not time control)    */
/* Think()      think up move from current position  */
/*              (leaves move in Move, can be invalid */
/*               if position is check- or stalemate) */
/* DoMove()     perform the move in Move             */
/*              (togglese Side)                      */
/* ReadMove()   convert input move to engine format  */
/* PrintMove()  print Move on standard output        */
/* Legal()      check Move for legality              */
/* ClearBoard() make board empty                     */
/* PutPiece()   put a piece on the board             */

/* define this to the codes used in your engine,     */
/* if the engine hasn't defined it already.          */

int PrintResult(int s)
{
        int i, j, k, cnt=0;

        /* search last 50 states with this stm for third repeat */
        for(j=2; j<=100; j+=2)
        {
            for(k=0; k<STATE; k++)
                if(HistoryBoards[HistPtr][k] !=
                   HistoryBoards[HistPtr-j&1023][k] )
                   {
                     goto differs;}
            /* is the same, count it */
            if(++cnt == 2) /* third repeat */
            {
                printf("1/2-1/2 {Draw by repetition}\n");
                return 1;
            }
          differs: ;
        }
        cnt = D(s,-I,I,Q,1,49,O,10,2);
        if(cnt==0 && K==0 && L==0) {
                printf("1/2-1/2 {Stalemate}\n");
                return 2;
        }
        if(cnt==-I/2) {
                if (s == WHITE)
                        printf("0-1 {Black mates}\n");
                else
                        printf("1-0 {White mates}\n");
                return 3;
        }
        if(Fifty >=100) {
                printf("1/2-1/2 {Draw by fifty move rule}\n");
                return 4;
        }
        return 0;
}


InitEngine()
{
 int j;

 F(i,0,8)
 {F(j,0,8)b[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5);   /* center-pts table   */
 }                                                   /*(in unused half b[])*/
 F(i,M,1035)T[i]=rand()>>9;
}

InitGame()
{
 int j;

 F(i,0,128)b[i&~M]=0;
 F(i,0,8)
 {b[i]=(b[i+V]=o[i+24]+40)+8;b[i+16]=18;b[i+96]=9;   /* initial board setup*/
 }
 F(i,0,U+9)A[i].K=0;
 Side = WHITE; Q=0; O=S;
 Fifty = 0;
 UnderProm = -1;
}

void CopyBoard(int s)
{
        int j, k, cnt=0;

        /* copy game representation of engine to HistoryBoard */
        /* don't forget castling rights and e.p. state!       */
        for(j=0; j<64; j++)
            HistoryBoards[s][j] = b[j+(j&0x38)];       /* board squares  */
        if(!(O&M)) HistoryBoards[s][O+(O&7)>>1] |= 64; /* mark ep square */
}
                                         
int main(int argc, char **argv)
{
        int Computer, MaxTime, MaxMoves, TimeInc, sec;
	char line[256], command[256];
        int m, nr;

        if(argc>1 && sscanf(argv[1], "%d", &m)==1) U = (1<<m)-1;
        A = (struct _ *) calloc(U+9, sizeof(struct _));

	signal(SIGINT, SIG_IGN);
	printf("\n");
        InitEngine();
        InitGame();
        Computer = EMPTY;
        MaxTime  = 10000;  /* 10 sec */
        MaxDepth = 97;     /* maximum depth of your search */

        for (;;) {
		fflush(stdout);
                if (Side == Computer) {
                        /* think up & do move, measure time used  */
                        /* it is the responsibility of the engine */
                        /* to control its search time based on    */
                        /* MovesLeft, TimeLeft, MaxMoves, TimeInc */
                        /* Next 'MovesLeft' moves have to be done */
                        /* within TimeLeft+(MovesLeft-1)*TimeInc  */
                        /* If MovesLeft<0 all remaining moves of  */
                        /* the game have to be done in this time. */
                        /* If MaxMoves=1 any leftover time is lost*/
                        Ticks = rdtsc();
                        m = MovesLeft<=0 ? 40 : MovesLeft;
                        tlim = 350000LL*(TimeLeft+(m-1)*TimeInc)/(m+2);
                        PromPiece = 'q';
                        N=0;
                        nr = D(Side,-I,I,Q,1,1,O,8,0); /* or think up one */
                        F(i,0,U+9)A[i].K=0;         /* clear hash table   */
                        if (D(Side,-I,I,Q,1,1,O,9,2)==I) {
                            Side ^= 24;
                            if(UnderProm>=0 && UnderProm != L)
                            {    printf("tellics I hate under-promotions!\n");
                                 printf("resign\n");
                                 Computer = EMPTY;
                                 continue;
                            } else UnderProm = -1;
                            printf("move ");
                            printf("%c%c%c%c",'a'+(K&7),'8'-(K>>4),
                                          'a'+(L&7),'8'-(L>>4));
                            printf("\n");
                            m = (rdtsc() - Ticks)/1000000;

                            /* time-control accounting */
                            TimeLeft -= m;
                            TimeLeft += TimeInc;
                            if(--MovesLeft == 0) {
                                MovesLeft = MaxMoves;
                                if(MaxMoves == 1)
                                     TimeLeft  = MaxTime;
                                else TimeLeft += MaxTime;
                            }

                            GameHistory[GamePtr++] = PACK_MOVE;
                            CopyBoard(HistPtr=HistPtr+1&1023);
                            PrintResult(Side);
                        } else {
                            if(!PrintResult(Side))
                                printf("resign\n");
                            Computer = EMPTY;
                        }
                        continue;
		}
		if (!fgets(line, 256, stdin))
			return;
		if (line[0] == '\n')
			continue;
		sscanf(line, "%s", command);
		if (!strcmp(command, "xboard"))
			continue;
		if (!strcmp(command, "new")) {
                        /* start new game */
                        InitGame();
                        GamePtr   = 0;
                        HistPtr   = 0;
                        Computer  = BLACK;
                        TimeLeft  = MaxTime;
                        MovesLeft = MaxMoves;
                        for(nr=0; nr<1024; nr++)
                            for(m=0; m<STATE; m++)
                                HistoryBoards[nr][m] = 0;
			continue;
		}
		if (!strcmp(command, "quit"))
                        /* exit engine */
			return;
		if (!strcmp(command, "force")) {
                        /* computer plays neither */
                        Computer = EMPTY;
			continue;
		}
		if (!strcmp(command, "white")) {
                        /* set white to move in current position */
                        Side     = WHITE;
                        Computer = BLACK;
			continue;
		}
		if (!strcmp(command, "black")) {
                        /* set blck to move in current position */
                        Side     = BLACK;
                        Computer = WHITE;
			continue;
		}
		if (!strcmp(command, "st")) {
                        /* move-on-the-bell mode     */
                        /* indicated by MaxMoves = 1 */
                        sscanf(line, "st %d", &MaxTime);
                        MovesLeft = MaxMoves = 1;
                        TimeLeft  = MaxTime *= 1000;
                        TimeInc   = 0;
			continue;
		}
		if (!strcmp(command, "sd")) {
                        /* set depth limit (remains in force */
                        /* until next 'sd n' command)        */
                        sscanf(line, "sd %d", &MaxDepth);
			continue;
		}
                if (!strcmp(command, "level")) {
                        /* normal or blitz time control */
                        sec = 0;
                        if(sscanf(line, "level %d %d %d",
                                 &MaxMoves, &MaxTime, &TimeInc)!=3 &&
                           sscanf(line, "level %d %d:%d %d",
                                 &MaxMoves, &MaxTime, &sec, &TimeInc)!=4)
                             continue;
                        MovesLeft = MaxMoves;
                        TimeLeft  = MaxTime = 60000*MaxTime + 1000*sec;
                        TimeInc  *= 1000;
                        continue;
                }
		if (!strcmp(command, "time")) {
                        /* set time left on clock */
                        sscanf(line, "time %d", &TimeLeft);
                        TimeLeft  *= 10; /* centi-sec to ms */
			continue;
		}
		if (!strcmp(command, "otim")) {
                        /* opponent's time (not kept, so ignore) */
			continue;
		}
		if (!strcmp(command, "go")) {
                        /* set computer to play current side to move */
                        Computer = Side;
                        MovesLeft = -(GamePtr+(Side==WHITE)>>1);
                        while(MaxMoves>0 && MovesLeft<=0)
                            MovesLeft += MaxMoves;
			continue;
		}
		if (!strcmp(command, "hint")) {
                        Ticks = rdtsc(); tlim = 10000000000LL;
                        D(Side,-I,I,Q,1,1,O,8,0);
                        if (K==0 && L==0)
				continue;
                        printf("Hint: ");
                        printf("%c%c%c%c",'a'+(K&7),'8'-(K>>4),
                                          'a'+(L&7),'8'-(L>>4));
                        printf("\n");
			continue;
		}
                if (!strcmp(command, "undo")   && (nr=1) ||
                    !strcmp(command, "remove") && (nr=2)   ) {
                        /* 'take back' moves by replaying game */
                        /* from history until desired ply      */
                        if (GamePtr < nr)
				continue;
                        GamePtr -= nr;
                        HistPtr -= nr;   /* erase history boards */
                        while(nr-- > 0)  
                            for(m=0; m<STATE; m++)
                                HistoryBoards[HistPtr+nr+1&1023][m] = 0;
                        InitGame();
                        for(nr=0; nr<GamePtr; nr++) {
                            UNPACK_MOVE(GameHistory[nr]);
                            D(Side,-I,I,Q,1,nr,O,9,2);
                            Side ^= 24;
                        }
                        F(i,0,U+9)A[i].K=0;         /* clear hash table   */
			continue;
		}
		if (!strcmp(command, "post")) {
                        Post = 1;
			continue;
		}
		if (!strcmp(command, "nopost")) {
                        Post = 0;
			continue;
		}
                if (!strcmp(command, "edit")) {
                        int color = WHITE;

                        while(fgets(line, 256, stdin)) {
                                m = line[0];
                                if(m=='.') break;
                                if(m=='#') {
                                        for(i=0; i<128; i++) b[i&0x77]=0;
                                        continue;
                                }
                                if(m=='c') {
                                        color = WHITE+BLACK - color;
                                        continue;
                                }
                                if((m=='P' || m=='N' || m=='B' ||
                                    m=='R' || m=='Q' || m=='K')
                                    && line[1] >= 'a' && line[1] <= 'h'
                                    && line[2] >= '1' && line[2] <= '8') {
                                        m = line[1]-16*line[2]+C;
                                        switch(line[0])
                                        {
                                        case 'P':
                                            if(color==WHITE) b[m]=9;
                                            else b[m]=18;
                                            break;
                                        case 'N':
                                            b[m]=3+color;
                                            break;
                                        case 'B':
                                            b[m]=5+color;
                                            break;
                                        case 'R':
                                            b[m]=6+color;
                                            if((m==0x00 || m==0x07) && color==BLACK ||
                                               (m==0x70 || m==0x77) && color==WHITE)
                                                b[m] += 32;
                                            break;
                                        case 'Q':
                                            b[m]=7+color;
                                            break;
                                        case 'K':
                                            b[m]=4+color;
                                            if(m==0x04 && color==BLACK ||
                                               m==0x74 && color==WHITE)
                                                b[m] += 32;
                                            break;
                                        }
                                        continue;
                                }
                        }
			continue;
		}
                /* command not recoognized, assume input move */
                m = line[0]<'a' | line[0]>'h' | line[1]<'1' | line[1]>'8' |
                    line[2]<'a' | line[2]>'h' | line[3]<'1' | line[3]>'8';
                PromPiece = line[4];
                {char *c=line; K=c[0]-16*c[1]+C;L=c[2]-16*c[3]+C; }
                F(i,0,U+9)A[i].K=0;         /* clear hash table   */
                if (m)
                        /* doesn't have move syntax */
			printf("Error (unknown command): %s\n", command);
                else if(D(Side,-I,I,Q,1,900,O,9,2)!=I)
                        /* did have move syntax, but illegal move */
                        printf("Illegal move:%s\n", line);
                else {  /* legal move, perform it */
                        GameHistory[GamePtr++] = PACK_MOVE;
                        Side ^= 24;
                        CopyBoard(HistPtr=HistPtr+1&1023);
                        if(PrintResult(Side)) Computer = EMPTY;
		}
	}
}