// A small chess program by Jonathan Kreuzer
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

const int HASH_SIZE = 400000;
const int INVALID=32, IV=32, EMPTY=0, WHITE=8, BLACK=16, WH=8, BL=16, PAWN=0, KNIG=1, BISH=2, ROOK=3, QUEE=4, KING=5;
const int TIME = 300000;
const int B_QS = 4, B_KS = 8, W_QS = 1, W_KS = 2;
const int N_dirs[8] = {-21, -19, -12, -8, 8, 12, 19, 21};
const int K_dirs[8] = {1, 9, 10, 11, -1, -9, -10, -11};
const int Q_dirs[8] = {1, -1, 9, -9, -10, 10, -11, 11};
const int R_dirs[4] = {1, -1,  -10, 10};
const int B_dirs[4] = {9, -9, -11, 11};
const int P_dirs[8] = {-10, -20, -9, -11, 10, 20, 9, 11};
int inline SRC   ( int Move ) {return (Move&127);}
int inline DST   ( int Move ) {return ((Move>>7)&127);}
int inline PROMO ( int Move ) {return ((Move>>14)&3);}
int inline VALUE ( int Move ) {return ((Move>>16)&16383);}
int inline SWITCH ( int Color ){return Color^(WHITE|BLACK);}
int inline File ( int Sq ) {return (Sq-20)%10;}
int inline Rank ( int Sq ) {return (Sq-10)/10;}
int inline SQ ( int file, int rank) {return 21+file+rank*10;}
int EvalSq [ 26 * 128 ];
int SetCastle[120];
const unsigned char StartBoard[120] = { IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV,
	IV, ROOK|BL, KNIG|BL, BISH|BL, QUEE|BL, KING|BL, BISH|BL, KNIG|BL, ROOK|BL, IV,
	IV, PAWN|BL, PAWN|BL, PAWN|BL, PAWN|BL, PAWN|BL, PAWN|BL, PAWN|BL, PAWN|BL, IV,
	IV, 0, 0, 0, 0, 0, 0, 0, 0, IV, IV, 0, 0, 0, 0, 0, 0, 0, 0, IV, IV, 0, 0, 0, 0, 0, 0, 0, 0, IV, IV, 0, 0, 0, 0, 0, 0, 0, 0, IV,
	IV, PAWN|WH, PAWN|WH, PAWN|WH, PAWN|WH, PAWN|WH, PAWN|WH, PAWN|WH, PAWN|WH, IV,
	IV, ROOK|WH, KNIG|WH, BISH|WH, QUEE|WH, KING|WH, BISH|WH, KNIG|WH, ROOK|WH, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV, IV };
const int PieceValues[8]    = { 100, 328, 330, 522, 952, 5000 };
const int MPieceValues[8]   = {  00, 328, 330, 522, 952,   00 };
const int KingEval[10] = { 0, 8, 12, 5, 0, 0, 5, 14, 9, 0};
const int CentEval[10] = { 0,-6, -3, -1, 0, 0, -1, -3, -6, 0};
const int Cent[10]	   = { 0, 1, 2, 2, 3, 3, 2, 1, 1, 0};
void SendThinking ( int move, int Depth, int Eval, __int64 Nodes, int bFinished );

struct SBoard 
	{
	unsigned char m_Sqs[120];
	int stm, Eval, EPsq, Castling, WKsq, BKsq, WMat, BMat, nMoves, nLastCapOrPawn;

	void Init()	{
		int sq, pc;
		for (sq = 0; sq < 120; sq++) m_Sqs[sq] = StartBoard [ sq ];
		Eval = 0; nMoves = 0;
		Castling = 0;
		stm = WHITE;
		WKsq = 95; BKsq = 25;
		BMat = WMat = 2*PieceValues[BISH]+2*PieceValues[KNIG]+2*PieceValues[ROOK]+PieceValues[QUEE];
		for (sq = 0; sq < 120; sq++) SetCastle[sq] = 0;
		SetCastle[21] = B_QS; SetCastle[28] = B_KS; SetCastle[25] = B_QS|B_KS; SetCastle[91] = W_QS; SetCastle[98] = W_KS; SetCastle[95] = W_QS|W_KS;
		// Evaluation is incremental and uses the piece square table in EvalSq arrays.
		for (pc = 0; pc < 8; pc++)
			for (sq = 0; sq < 120; sq++) {
				EvalSq[ ((pc|WHITE)<<7)+sq ] = PieceValues[pc];
				EvalSq[ ((pc|BLACK)<<7)+sq ] = -PieceValues[pc];
				if (pc == PAWN) 
					{EvalSq[ ((pc|WHITE)<<7)+sq ] += (9-Rank(sq)) * Cent[File(sq)];
					 EvalSq[ ((pc|BLACK)<<7)+sq ] -=   Rank(sq)   * Cent[File(sq)];}
				else if (pc == KING) {}
				else{if (pc!=ROOK && Rank(sq)==8) EvalSq[ ((pc|WHITE)<<7)+sq ] -= 8;
					 if (pc!=ROOK && Rank(sq)==1) EvalSq[ ((pc|BLACK)<<7)+sq ] += 8;
					 EvalSq[ ((pc|WHITE)<<7)+sq ] += CentEval[ File(sq) ];
					 EvalSq[ ((pc|BLACK)<<7)+sq ] -= CentEval[ File(sq) ];
					}
			EvalSq[ (0<<7)+sq ] = (Rank(sq)-9)*2 + KingEval[File(sq)]; // King Values depend on stage
			EvalSq[ (1<<7)+sq ] = (Rank(sq))*2 - KingEval[File(sq)];
			EvalSq[ (2<<7)+sq ] = 2*CentEval[ File(sq) ];
			EvalSq[ (3<<7)+sq ] = -2*CentEval[ File(sq) ];
			}
		}
	int CanCastleKS ( const int Color) {
		if (Color == WHITE && !(Castling&W_KS) && m_Sqs[ WKsq+1 ] == EMPTY && !ColorAttacksSq(BLACK, WKsq+1) && m_Sqs[ WKsq+2 ] == EMPTY ) return 1; 
		if (Color == BLACK && !(Castling&B_KS) && m_Sqs[ BKsq+1 ] == EMPTY && !ColorAttacksSq(WHITE, BKsq+1) && m_Sqs[ BKsq+2 ] == EMPTY ) return 1; 
		return 0; }
	int CanCastleQS ( const int Color) {
		if (Color == WHITE && !(Castling&W_QS) && m_Sqs[ WKsq-1 ] == EMPTY && !ColorAttacksSq(BLACK, WKsq-1) && m_Sqs[ WKsq-2 ] == EMPTY && m_Sqs[ WKsq-3 ] == EMPTY) return 1;
		if (Color == BLACK && !(Castling&B_QS) && m_Sqs[ BKsq-1 ] == EMPTY && !ColorAttacksSq(BLACK, BKsq-1) && m_Sqs[ BKsq-2 ] == EMPTY && m_Sqs[ BKsq-3 ] == EMPTY) return 1;
		return 0; }
	void AdjustMat ( int Dst, const int Mul )	{
		if (m_Sqs[ Dst ]&WHITE) WMat += Mul*MPieceValues[ (m_Sqs[ Dst ]&7) ];
		else BMat += Mul*MPieceValues[ (m_Sqs[ Dst ]&7) ];
		}
	void MovePiece (const int Src, const int Dst, const int Promo) {
		int Piece = m_Sqs [Src];
		Eval += EvalSq [ (Piece<<7) + Dst ] - EvalSq [ (Piece<<7) + Src ];
		if (m_Sqs[ Dst ] != EMPTY) 
			{ Eval -= EvalSq [ (m_Sqs[ Dst ]<<7) + Dst ];
			  AdjustMat ( Dst, -1); }
		m_Sqs[Dst] = Piece;
		m_Sqs[Src] = EMPTY; 
		if (Piece == (KING|WH) ) WKsq = Dst;
		if (Piece == (KING|BL) ) BKsq = Dst;
		if ((Piece&7) == PAWN ) {
			if (Dst < 30 || Dst > 90) {m_Sqs[Dst] += Promo + 1;
									   AdjustMat ( Dst, 1 );
									   Eval += EvalSq [ (m_Sqs[Dst]<<7) + Dst ] - EvalSq [ (Piece<<7) + Dst ]; }
			if ( Dst == EPsq ) {EPsq = Src+File(Dst)-File(Src);
								Eval -= EvalSq [ (m_Sqs[ EPsq ]<<7) + EPsq ];
								m_Sqs [ EPsq ] = EMPTY;}
			if ( abs(Src-Dst)==20) EPsq = ((Src + Dst)>>1); else EPsq = 0;
			}
		else EPsq = 0;
		}
	void DoMove ( const int Move )	{
		int Dst = DST(Move), Src = SRC(Move);
		Castling |= SetCastle[ Src ] | SetCastle[ Dst ];
		nMoves++;
		stm = SWITCH (stm);
		if ((m_Sqs [Src]&7) == KING) {
			if (Dst == Src-2) {MovePiece (Src, Src-2, 0); MovePiece (Src-4, Src-1, 0); return; }
			if (Dst == Src+2) {MovePiece (Src, Src+2, 0); MovePiece (Src+3, Src+1, 0); return; } }
		MovePiece (Src, Dst, PROMO(Move));
		}
	int CheckDirec ( int Sq, const int Dir, const int Piece1, const int Piece2) {
		Sq += Dir;
		while ( m_Sqs[ Sq ] == EMPTY ) Sq += Dir;
		if ( m_Sqs[ Sq ] == Piece1 || m_Sqs[ Sq ] == Piece2) return 1; else	return 0;
		}
	int ColorAttacksSq ( int Color, int Sq)	{
		int i;
		for (i = 0; i < 8; i++) if (m_Sqs[Sq+N_dirs[i]] == (KNIG|Color)) return 1;
		for (i = 0; i < 8; i++) if (m_Sqs[Sq+K_dirs[i]] == (KING|Color)) return 1;
		for (i = 0; i < 4; i++) if (CheckDirec (Sq, R_dirs[i], (QUEE|Color), (ROOK|Color)) ) return 1;
		for (i = 0; i < 4; i++) if (CheckDirec (Sq, B_dirs[i], (QUEE|Color), (BISH|Color)) ) return 1;
		int n = (Color == WHITE) ? 4:0;
		for (i = 2; i <= 3; i++) if (m_Sqs[Sq+P_dirs[i + n]] == (PAWN|Color)) return 1;
		return 0;
		}
	int IsCheck (int color) {return (color == WHITE) ? ColorAttacksSq(BLACK, WKsq) : ColorAttacksSq(WHITE, BKsq);}
	int Evaluate() {
		if (WMat < 1400 && BMat < 1400) return Eval + EvalSq[ (2<<7)+WKsq ] + EvalSq[ (3<<7)+BKsq ];
		return Eval + EvalSq[ (0<<7)+WKsq ] + EvalSq[ (1<<7)+BKsq ]; }
};

struct SMovelist 
	{
	int m_Moves[256];
	int m_nMoves, m_nAttacks, m_bCaps;
	unsigned char *m_pSqs;

	void inline AddMove (int Src, int Dst) { if (m_bCaps) return;
											 m_Moves[ m_nMoves++ ] = Src + (Dst<<7) + (3<<14) + (200<<16); }
	void inline AddAtkMove (int Src, int Dst) {	m_Moves[ m_nMoves++ ] = Src + (Dst<<7)  + (3<<14) + ( (200+PieceValues[(m_pSqs[Dst]&7)]) << 16); }
	void inline GenPieceMoves ( const int MoveArray[], const int bSlide, const int nDirs, int Sq, SBoard &Board, const int COLOR ) {
		for (int i = 0; i < nDirs; i++) {
			int tempSq = Sq + MoveArray[i];
			if (bSlide)
				while ( Board.m_Sqs [ tempSq ] == EMPTY ) {
					AddMove (Sq, tempSq);
					tempSq += MoveArray[i];
					}
			if ( Board.m_Sqs[tempSq]&SWITCH(COLOR) ) AddAtkMove ( Sq, tempSq );
			else if (Board.m_Sqs[tempSq] == EMPTY )	AddMove (Sq, tempSq);
			}
		}
	void inline GenPawnMoves (  const int MoveArray[], int Sq, SBoard &Board, const int COLOR  ) 	{
		int n = (COLOR == BLACK) ? 4:0;
		if ( Board.m_Sqs[ Sq+P_dirs[n+0] ] == EMPTY ) {
			if ( StartBoard[Sq]==(PAWN|SWITCH(COLOR))) AddAtkMove (Sq, Sq+P_dirs[n+0]); else AddMove (Sq, Sq+P_dirs[n+0]);
			if ( StartBoard[Sq]==(PAWN|COLOR) && Board.m_Sqs[ Sq+P_dirs[n+1] ] == EMPTY) AddMove (Sq, Sq+P_dirs[n+1]); 			
			}
		if ( Sq+P_dirs[n+2] == Board.EPsq || (Board.m_Sqs[ Sq+P_dirs[n+2] ]&SWITCH(COLOR)) ) AddAtkMove (Sq, Sq+P_dirs[n+2]);
		if ( Sq+P_dirs[n+3] == Board.EPsq || (Board.m_Sqs[ Sq+P_dirs[n+3] ]&SWITCH(COLOR)) ) AddAtkMove (Sq, Sq+P_dirs[n+3]);
		}
	void Generate ( SBoard &Board, int bCaps )	{
		m_nMoves = 0;
		m_bCaps = bCaps;
		m_pSqs = Board.m_Sqs;
		int Color = Board.stm;
		for ( int Sq = 20; Sq < 100; Sq ++)
			switch (Board.m_Sqs[ Sq ]^Color )	{
				case PAWN: GenPawnMoves  ( P_dirs, Sq, Board, Color ); break;
				case KNIG: GenPieceMoves ( N_dirs, 0, 8, Sq, Board, Color ); break;
				case BISH: GenPieceMoves ( B_dirs, 1, 4, Sq, Board, Color ); break;
				case ROOK: GenPieceMoves ( R_dirs, 1, 4, Sq, Board, Color ); break;
				case QUEE: GenPieceMoves ( Q_dirs, 1, 8, Sq, Board, Color ); break;
				case KING: GenPieceMoves ( K_dirs, 0, 8, Sq, Board, Color ); 
					if ( !Board.IsCheck (Color) ) {
						if ( Board.CanCastleQS ( Color ) ) AddMove (Sq, Sq-2); 
						if ( Board.CanCastleKS ( Color ) ) AddMove (Sq, Sq+2);}
					break;
				};
		}
	void ScoreMoves ( SBoard &Board, const int Color, int BestMove ) {
		for (int i = 0; i < m_nMoves; i++) {
			int Dst = DST (m_Moves[i]), Src = SRC(m_Moves[i]);
			int Piece = Board.m_Sqs[ Src ];
			if (Color == WHITE) m_Moves[i] += ((EvalSq [ (Piece<<7) + Dst ] - EvalSq [ (Piece<<7) + Src ])<<16);
			if (Color == BLACK) m_Moves[i] -= ((EvalSq [ (Piece<<7) + Dst ] - EvalSq [ (Piece<<7) + Src ])<<16);
			if ( (m_Moves[i]&65535) == (BestMove&65535) ) m_Moves[i] += (2048<<16);
			}
		}
	int GetNextMove ( int &nMove ) 	{
		int Max = -1, Next = -1;
		for (int i = 0; i < m_nMoves; i++) 
			if (m_Moves[i] && VALUE(m_Moves[i]) > Max) {
				nMove = m_Moves[i];
				Next = i;
				Max = VALUE(nMove);}
		if (Next == -1) return 0;
		m_Moves[Next] = 0;
		return 1;
		}
};

__int64 RepNum[ 2000 ];
int inline Repetition ( const __int64 HashKey, int nStart, int ahead)  {
	int i = (nStart > 0) ? nStart : 0;	
	if ((i&1) != (ahead&1)) i++;
    for ( ; i < ahead; i+=2) if (RepNum[i] == HashKey) return true;                
    return false;
    }
void inline AddRepBoard ( const __int64 HashKey, int ahead ) {RepNum[ ahead ] = HashKey;}

unsigned __int64 HashFunction [128][16], HashSTM;
struct TEntry
	{
	unsigned long m_checksum;
	short m_eval,  m_bestmove;
	char  m_depth, m_failtype, m_ahead, m_age; 

	void inline Read ( unsigned long CheckSum, short alpha, short beta, int &bestmove, int &value, int depth, int ahead) {
		if (m_checksum == CheckSum ) {
			if (m_depth >= depth) {
				int tempVal = m_eval;
			    if (abs (m_eval) > 18000) {
					if (m_eval > 0) tempVal = m_eval - ahead + m_ahead;
					if (m_eval < 0) tempVal = m_eval + ahead - m_ahead;
					}
			   switch ( m_failtype ) {
					case 0: value = tempVal; break; 
					case 1: if (tempVal <= alpha) value = tempVal; 	break;
					case 2: if (tempVal >= beta) value = tempVal;	break;
					}
               }                                             
			if (depth > 2) bestmove = m_bestmove; 
			}
		}
	void inline Write ( unsigned long CheckSum, short alpha, short beta, int &bestmove, int &value, int depth, int ahead) {
		m_checksum = CheckSum;
		m_eval = value;
		m_ahead = ahead;
		m_depth = depth;
		m_bestmove = (bestmove & 65535);
		if (value <= alpha) m_failtype = 1; else if (value >= beta)  m_failtype = 2; else m_failtype = 0;
		}
	static void Create_HashFunction () {
		for (int i = 0; i <128; i++)
        for (int x = 0; x < 16; x++)	{
			HashFunction [i][x]  = rand() + (rand()*256) + (rand()*65536);
			HashFunction [i][x] <<= 32;
			HashFunction [i][x]  += rand() + (rand()*256) + (rand()*65536);
			}
		HashSTM = HashFunction[0][0];
		}  
	static unsigned __int64 HashBoard (const SBoard &Board) {
		unsigned __int64 CheckSum = 0;
	    for (int index = 21; index <= 99; index++) {
			int nPiece =  Board.m_Sqs [ index ];
			if (nPiece == INVALID) continue;
			if (nPiece != EMPTY) CheckSum ^= HashFunction [ index ][ (nPiece&15) ];
			}
		if (Board.stm == BLACK) CheckSum ^= HashSTM;			
		return CheckSum;
		}
	static AddRepBoard ( );
	};
TEntry TTable[ HASH_SIZE ];

__int64 g_Nodes, g_CheckNodes;
int g_MaxTime;
clock_t g_start;

int ABSearch ( SBoard &InBoard, int alpha, int beta, int depth, int ahead, int &BestMove, int bNull )
{
	SMovelist Moves;
	SBoard Board;
	int Color = InBoard.stm, Eval, NextBest = 0, nMove, bInCheck = InBoard.IsCheck (Color);
	__int64 n64Hash;

	if ( g_Nodes > g_CheckNodes ) {
		g_CheckNodes = g_Nodes+10000;
		if ((clock()-g_start) > g_MaxTime) return TIME;
		}
	if ( (!bInCheck && depth <= 0) || depth < 0 || ahead > 32 ) {
		int Eval = (InBoard.stm == WHITE) ? InBoard.Evaluate() : -InBoard.Evaluate();
		if (Eval > alpha) alpha = Eval;
		if (alpha >= beta) return beta;
		Moves.Generate ( InBoard, 1 );
		}
	else {
		if (bNull && depth > 2 && !bInCheck
			&& ((Color==WHITE && InBoard.WMat > 400) || (Color==BLACK && InBoard.BMat > 400))) {
			InBoard.stm = SWITCH (InBoard.stm);
			Eval = -ABSearch ( InBoard, -beta, -beta+1, depth-3, ahead, NextBest, false);
			InBoard.stm = SWITCH (InBoard.stm);
			if (Eval == -TIME) return TIME;
			if (Eval >= beta) return beta;
			}
		Moves.Generate ( InBoard, 0 );
		}
	
	if (BestMove < 100 && depth > 2) {Eval = ABSearch ( InBoard, alpha, beta, depth-2, ahead+1, BestMove, true); 
									  if (Eval == TIME) return TIME;}
	Moves.ScoreMoves ( InBoard, Color, BestMove );

	BestMove = 0;
	while ( Moves.GetNextMove ( nMove ) ) {
		Board = InBoard;
		Board.DoMove ( nMove );
		g_Nodes++;
		if ( Board.IsCheck ( Color ) ) continue;
		NextBest = 0; Eval = -32000;

		if (depth > 1) {
			n64Hash = TEntry::HashBoard ( Board );
			if (Repetition  ( n64Hash, Board.nMoves - 40, Board.nMoves)) Eval = 0;
			else {AddRepBoard ( n64Hash, Board.nMoves);
				  TTable [ ((unsigned long)n64Hash) % HASH_SIZE ].Read ( (unsigned long)(n64Hash>>32), alpha, beta, NextBest, Eval, depth-1, ahead);
				}
			}
		if (Eval == -32000) 
			{Eval = -ABSearch (Board, -beta, -alpha, (bInCheck)?(depth):(depth-1), ahead+1, NextBest, true );
			 if (Eval == -TIME) return TIME;}
		if (depth > 1) TTable [ ((unsigned long)n64Hash) % HASH_SIZE ].Write  ( (unsigned long)(n64Hash>>32), alpha, beta, NextBest, Eval, depth-1, ahead);	

		if ( Eval > alpha) {
			if (ahead == 0) SendThinking ( nMove, depth, Eval, g_Nodes, false);
			BestMove =  nMove;
			alpha = Eval;
			if (alpha >= beta) return beta;
			}
		if (BestMove == 0) BestMove = 1; 
		}

	if ( !Moves.m_bCaps && BestMove == 0) {return (bInCheck) ? -20000+ahead : 0;}
	return alpha;
}

void ComputerMove( SBoard &Board, int &Move, int &Eval ) 
{
	g_Nodes = 0;
	g_CheckNodes = g_Nodes+10000;
	g_start = clock();
	int SearchEval, SearchMove;
	for (int nDepth = 2; nDepth < 16; nDepth++)	{
		SearchEval = ABSearch (Board, -30000, 20001-nDepth, nDepth, 0, SearchMove, false);
		if (SearchEval != TIME) Eval = SearchEval;
		if (SearchMove > 100) {	Move = SearchMove;
								SendThinking ( Move ,nDepth, Eval, g_Nodes, true);}
		if ((clock()-g_start) > (g_MaxTime/2)) break;
		if (abs(Eval)>= (20001-nDepth)) break;
		}
}

#include "winboard.cpp"
int main ( ) {
	TEntry::Create_HashFunction ( );
	WinboardLoop ( );
return 1;
}