#include <stdio.h>

/* constants */

/* data types */
struct move {
    int x;
    int y;
    int dx;
    int dy;
    int distance;
    int score;
    int piece;
    };


/* global variables */

int board[8][8];
int notmoved[8][8];
char pieces[7][8]={"empty","pawn","rook","knight","bishop","queen","king"};
int values[7]={0,10,50,30,30,90,1000};
/* a pawn is ten times more valuable a free square around a king */

char initials[7]={' ','p','r','n','b','q','k'};

struct move openings[2][2]; /* two openings, each with two moves */

/* prototypes */
void setupboard(void);

struct move findmove(int piece,int x,int y,int rotation);
int makemove(struct move trymove);
void erasemove(struct move trymove,int taken);
int evaluate (int player);
struct move bestmove(int player,int level,int cutoff,int maxply);
void drawboard();
void humanmove();
int xcoord(char c);
int ycoord(char c);

/* function definitions */

/* place pieces on board */
void setupboard(void)
{
    int x,y; /* loop variables */

    for (x=0;x<8;x++)
	for (y=0;y<8;y++) {
	    board[x][y]=0;
	    notmoved[x][y]=1; /* no pieces so far have moved */
	    if (y==1)
		board[x][y]=1; /* white pawn */
	    if (y==6)
		board[x][y]=-1; /* black pawn */
	}
    board[0][0]=2; /* white rook */
    board[7][0]=2;
    board[0][7]=-2; /* black rook */
    board[7][7]=-2;
    board[1][0]=3; /* white knight */
    board[6][0]=3;
    board[1][7]=-3;
    board[6][7]=-3;
    board[2][0]=4;
    board[5][0]=4;
    board[2][7]=-4;
    board[5][7]=-4;
    board[3][0]=5;
    board[4][0]=6;
    board[3][7]=-5;
    board[4][7]=-6;

    /* define book openings */
    /* first opening, first move */
    openings[0][0].x=3; /* queen's pawn to D4 */
    openings[0][0].y=1;
    openings[0][0].dx=0;
    openings[0][0].dy=1;
    openings[0][0].distance=2;
    openings[0][0].score=0;
    openings[0][0].piece=1;
    /* first opening, second move */
    openings[0][1].x=2; /* pawn c2 to c4 */
    openings[0][1].y=1;
    openings[0][1].dx=0;
    openings[0][1].dy=1;
    openings[0][1].distance=2;
    openings[0][1].score=0;
    openings[0][1].piece=1;
    /* second opening, first move */
    openings[1][0].x=4; /* king's pawn to e4 */
    openings[1][0].y=1;
    openings[1][0].dx=0;
    openings[1][0].dy=1;
    openings[1][0].distance=2;
    openings[1][0].score=0;
    openings[1][0].piece=1;
    /* second opening, second move */
    openings[1][1].x=6;  /* king's knight to f3 */
    openings[1][1].y=0;
    openings[1][1].dx=-1;
    openings[1][1].dy=2;
    openings[1][1].distance=1;
    openings[1][1].score=0;
    openings[1][1].piece=3;



}

/* find how far a piece can move in a specified direction */
struct move findmove(int piece, int x, int y,int rotation)
{
    struct move foundmove;

    /* initialise the move's structure */
    foundmove.x=x;
    foundmove.y=y;
    foundmove.piece=piece;
    foundmove.score=0;
    foundmove.distance=0;
    foundmove.dx=0;
    foundmove.dy=0;

    int maxdist=8;


    if (piece<0) piece=-piece; /* convert to white piece for purposes of caclulation */

    if (piece==3) {
	/* special case for knight */
	switch (rotation) {
	    case 0:
		foundmove.dx=1;
		foundmove.dy=-2;

		break;
	    case 1:
		foundmove.dx=2;
		foundmove.dy=-1;

		break;
	    case 2:
		foundmove.dx=2;
		foundmove.dy=1;

		break;
	    case 3:
		foundmove.dx=1;
		foundmove.dy=2;

		break;
	    case 4:
		foundmove.dx=-1;
		foundmove.dy=2;

		break;
	    case 5:
		foundmove.dx=-2;
		foundmove.dy=1;

		break;
	    case 6:
		foundmove.dx=-2;
		foundmove.dy=-1;

		break;
	    case 7:
		foundmove.dx=-1;
		foundmove.dy=-2;

		break;
	    default:
		printf("Error in find move with knight\n");
		break;
	}
	maxdist=1; /* knight can only move once */
    }
    else {


	/* standard directions for pieces */
	if (rotation<=1 || rotation==7) foundmove.dy=-1;
	if (rotation>=1 && rotation<=3) foundmove.dx=1;
	if (rotation>=3 && rotation<=5) foundmove.dy=1;
	if (rotation>=5 && rotation<=7) foundmove.dx=-1;
    }
    if (piece==6) {
	maxdist=1; /* only one move if king */
	/* check for possibility of castling */
	if (rotation==2 || rotation==6) { /* if we're looking at a horizontal move */
	    if (foundmove.x==4 && ((foundmove.y==0 && foundmove.piece==6) || (foundmove.y==7 && foundmove.piece==-6))) {
		 /* if we've found the king in its starting position */
		if (notmoved[foundmove.x][foundmove.y]) { /* if it hasn't moved yet */
		    if (rotation==2) {
			/* looking to the right */
			if (board[5][foundmove.y]==0 && board[6][foundmove.y]==0 && notmoved[7][foundmove.y]) {
			    /* possible to castle to the right */
			    maxdist=2;
			}
		    }
		    /* looking to the left */
		    else {
			if (board[3][foundmove.y]==0 && board[2][foundmove.y]==0 && board[1][foundmove.y]==0 && notmoved[0][foundmove.y]) {
			    /* possible to castle to the left */
			    maxdist=3;;
			}
		    }
		}
	    }
	}
    }
    if (piece==2 && rotation%2!=0)

	return foundmove; /* rooks cannot move diagonally */
    if (piece==4 && rotation%2==0)
	return foundmove; /* and bishops can only move diagonally */

    if (piece!=1) {

	while ((x=x+foundmove.dx)>=0 && x<8 && (y=y+foundmove.dy)>=0 && y<8 && foundmove.distance<maxdist) {


	    if (board[x][y]*foundmove.piece>0) /* landed on own piece */
		return foundmove;
	    foundmove.distance++; /* we can move in this direction */
	    if (piece==6) { /* check for castling */
		foundmove.distance=maxdist;
		return foundmove;
	    }

	    if (board[x][y]*foundmove.piece<0) /* taken an opponent's piece */
		return foundmove; /* then can move no further */
	} /* otherwise continue searching in direction for as long as possible */

    }

    else {
	if (x+foundmove.dx<0 || x+foundmove.dx>7 || y+foundmove.dy<0 || y+foundmove.dy>7 || rotation==2 || rotation==6)
	/* move invalid if heading off board or horizontally */
	    return foundmove;
	if (foundmove.piece==1 && (rotation<3 || rotation>5))
	/* invalid if moving backwards */
	    return foundmove;

	if (foundmove.piece==-1 && (rotation>1 && rotation<7))
	/* again moving backwards */
	    return foundmove;
	if (rotation!=0 && rotation !=4) { /* moving diagonally */
	    if (board[x+foundmove.dx][y+foundmove.dy]*foundmove.piece<0) /* taken a piece */
		foundmove.distance=1; /* it's valid */

	    return foundmove;
	}
	if (board[x+foundmove.dx][y+foundmove.dy]==0) {
	    foundmove.distance=1; /* if no piece in the way, the move is valid */
	    if ((foundmove.piece==1 && y==1) || (foundmove.piece==-1 && y==6))
		/* pawn not yet moved */
		if (board[x+2*foundmove.dx][y+2*foundmove.dy]==0)
		    foundmove.distance=2;
	}
    }
    return foundmove;
}

/* given a valid move structure, makemove will alter the board accordingly */
/* returns the piece previously occupying the square moved to */
int makemove(struct move trymove)
{
    int taken;


    taken=board[trymove.x+trymove.dx*trymove.distance][trymove.y+trymove.dy*trymove.distance];
    board[trymove.x][trymove.y]=0;
    if (trymove.piece==1 && (trymove.y+trymove.dy*trymove.distance==7))
	trymove.piece=5; /* promotion to queen */
    if (trymove.piece==-1 && (trymove.y+trymove.dy*trymove.distance==0))
	trymove.piece=-5; /* promotion to black queen */

    board[trymove.x+trymove.dx*trymove.distance][trymove.y+trymove.dy*trymove.distance]=trymove.piece;
    if (trymove.piece==6 || trymove.piece==-6) {
	if (trymove.dx==1 && trymove.distance==2) {
	    /* castled to the right */
	    board[trymove.x+1][trymove.y]=board[7][trymove.y];
	    board[7][trymove.y]=0;
	}
	if (trymove.dx==-1 && trymove.distance==3) {
	    /* castled to the left */
	    board[trymove.x-2][trymove.y]=board[0][trymove.y];
	    board[0][trymove.y]=0;
	}
    }
    return taken;
}

/* erase move will take back a previously made move */
void erasemove(struct move trymove, int taken)
{
    board[trymove.x+trymove.dx*trymove.distance][trymove.y+trymove.dy*trymove.distance]=taken;
    board[trymove.x][trymove.y]=trymove.piece;


    if (trymove.piece==6 || trymove.piece==-6) {
	if (trymove.dx==1 && trymove.distance==2) {
	    /* castled to the right */
	    board[7][trymove.y]=board[trymove.x+1][trymove.y];

	    board[trymove.x+1][trymove.y]=0;
	}
	if (trymove.dx==-1 && trymove.distance==3) {
	    /* castled to the left */
	    board[0][trymove.y]=board[trymove.x-2][trymove.y];
	    board[trymove.x-2][trymove.y]=0;
	}
    }


}

/* evaluate returns a board score for player */
int evaluate (int player)
{
    int score=0;
    int x,y;
    int kx,ky; /* position of player's king */
    int previouspawn,currentpawn; /* flags for presence of pawns in adjacent ranks */
    int currentpiece; /* the type of piece at current square */

    kx=-1;
    ky=-1;
    previouspawn=1;
    /* pretend there's a pawn in an imaginary zeroeth (more correctly, -1th)
    so that the pawn in the first rank is not automatically devalued */
    for (x=0;x<8;x++) {
	currentpawn=0;
	for (y=0;y<8;y++) {
	    currentpiece=board[x][y]*player;
	    if (currentpiece<0) /* opponent's piece found */
		score-=values[-currentpiece]; /* decrease due to material value */

	    else score+=values[currentpiece]; /* increase due to material value */
	    /* look for king */
	    if (currentpiece==6) { /* king found */
		kx=x;ky=y; /* store coordinates */
	    }
	    else { /* look for pawn */
		if (currentpiece==1) { /* found pawn */
		    if (currentpawn)
			/* if we've already found a pawn in this rank,
			    then value of this one is devalued for
			    sharing the same rank */
			score-=1; /* value dropped by one  */
		    currentpawn=1; /* set "found a pawn in this rank" flag */
		    if (!previouspawn)
			/* if there was no pawn in the previous rank, the
			pawn is devalued by 1 */
			score-=1;
		}
	    }
	}
	previouspawn=currentpawn; /* set previouspawn flag on basis of whether a pawn was
	found in the rank we've just dealt with */
    }
    /* now increase score depending on the mobility of player's king */
    /* check squares in each direction in turn */
    if (kx>-1) {
	if (ky>0 && board[kx][ky-1]==0) /* if king can move up */
	    score+=1; /* score increases by a value of 1 for every square king can move into */
	if (ky>0 && kx<7 && board[kx+1][ky-1]==0) /* move up right */
	    score+=1;
	if (kx<7 && board[kx+1][ky]==0) /* move right */
	    score+=1;
	if (kx<7 && ky<7 && board[kx+1][ky+1]==0) /* move down right */
	    score+=1;
	if (ky<7 && board[kx][ky+1]==0) /* move down */
	    score+=1;
	if (kx>0 && ky<7 && board[kx-1][ky+1]==0) /* move down left */
	    score+=1;
	if (kx>0 && board[kx-1][ky]==0) /* move left */
	    score+=1;
	if (kx>0 && ky>0 && board[kx-1][ky-1]==0) /* move up left */
	    score+=1;
    }
    return score;
}

/* best move creates each move in turn and evaluates it */
struct move bestmove(int player, int level, int cutoff, int maxply)
{
    struct move current;
    struct move bestsofar;
    struct move opponents;

    int x,y,maxdist,rotation,piece,taken;

    if (level<maxply) {

	/* recursive search */
	bestsofar.score=-99999;

	for (x=0;x<8;x++)
	    for (y=0;y<8;y++) {
		/* work through each board position in turn */
		piece=board[x][y];
		if (piece*player>0) {

		    /* if piece belongs to current player, move it */
		    for (rotation=0;rotation<8;rotation++) {
			/* try each direction */
			current=findmove(piece,x,y,rotation);
			maxdist=current.distance;
			if (maxdist>0) {
			    for (current.distance=1;current.distance<=maxdist;current.distance++) {
				/* work in this direction for as long as it is legal */
				/* avoid checking a king moving two places to the left */
				if ((piece==6 || piece==-6) && rotation==6 && current.distance==2)
				    current.distance=maxdist;
				/* now prune out unecessary branches */
				if (bestsofar.score<cutoff) {
				    taken=makemove(current); /* make the current move */
				    if (taken!=0 && level==1) /* if we're taking a piece and we're at the top
				    of the recursion, then increase the number of ply we search by two	*/
					opponents=bestmove(-player,level+1,-bestsofar.score,maxply+2);
				    else
					opponents=bestmove(-player,level+1,-bestsofar.score,maxply); /* find opponent's best response */

				    erasemove(current,taken); /* take back move */
				    current.score=-opponents.score;
				    /* find out if human can take computer's
				    king at this point. Note it's human's turn
				    if level is an even number */
				    if (level%2==0 && taken==6) {
					/* if so, we must increase the score
					further so that computer doesn't assume
					situation can be rectified by it taking
					player's king next move */
					current.score=current.score+1000;
					if (level==2)
					    current.score=current.score+10000;
					    /* help to detect player getting
					    computer into checkmate */
				    }

				    if (current.score>bestsofar.score) {
					/* this move yields best score so far */
					bestsofar=current; /* store move and its score */
				    }
				}
			    }
			}
		    }
		}
	    }
    }
    else {
	/* reached bottom of recursion */

	bestsofar.score=-999;
	for (x=0;x<8;x++)
	    for (y=0;y<8;y++) {

		/* work through each board position in turn */
		piece=board[x][y];
		if (piece*player>0) {

		    /* if piece belongs to current player, move it */
		    for (rotation=0;rotation<8;rotation++) {
			/* try each direction */
			current=findmove(piece,x,y,rotation);
			maxdist=current.distance;
			if (maxdist>0) {
			    for (current.distance=1;current.distance<=maxdist;current.distance++) {
				/* work in this direction for as long as it is legal */
				/* prune out unecessary branches */
				if (bestsofar.score<cutoff) {

				    taken=makemove(current); /* make the current move */
				    current.score=evaluate(player); /* get a score for this move */
				    erasemove(current,taken); /* take move back */

				    if (current.score>bestsofar.score) {
					/* this move yields best score so far */
					bestsofar=current;
				    }
				}
			    }
			}
		    }
		}
	    }

    }
    return bestsofar;
}

void drawboard()
{
    int x,y;
    printf("\n\n  ABCDEFGH");
    for (y=0;y<8;y++) {
	printf("\n%2d",y+1);
	for (x=0;x<8;x++)
	    if (board[x][y]==0) {
		if ((x%2==0 && y%2==0) || (x%2==1 && y%2==1))
		    printf("%c7m",155); /* switch to reverse printing */
		printf(" %c0m",155); /* print a square and switch to normal printing */
	    } else {
		if (board[x][y]<0)
		    printf("%c",initials[-board[x][y]]);
		else
		    printf("%c7m%c%c0m",155,initials[board[x][y]],155);
	    }

    }

    printf("\n\n");
}

void humanmove()
{
    char from[3],to[3];
    int xf,yf,xt,yt,bad,rotation,distance;
    struct move human;


    do {
	bad=0; /* assume a legal move before checking */
	printf("Enter coordinates to move from\n");
	scanf("%3s",from);
	printf("And to move to\n");
	scanf("%3s",to);

	xf=xcoord(toupper(from[0]));
	yf=ycoord(from[1]);
	xt=xcoord(toupper(to[0]));
	yt=ycoord(to[1]);
	/* test legality of move */
	/* first test if coords within bounds of board */
	if (xf<0 || xf>7 || yf<0 || yf>7 || xt<0 || xt>7 || yt<0 || yt>7 ) bad=1;
	else {
	    bad=1; /* now assume an illegal move until proved otherwise */
	    /* now test that a black piece is there */
	    if (board[xf][yf]<0) {


		/* check each possible move in turn against move selected */
		for (rotation=0;rotation<8;rotation++) {
		    human=findmove(board[xf][yf],xf,yf,rotation);
		    if (human.distance>0) {
			for (distance=1;distance<=human.distance;distance++) {
			    if (human.x+human.dx*distance==xt && human.y+human.dy*distance==yt) {
				bad=0; /* we've found the legal move */
			    }
			}
		    }
		}
	    }
	}
	if (bad==1) printf("Invalid move\n");
    } while (bad!=0);
    printf("\n%s from %c%c to %c%c\n",pieces[-board[xf][yf]],xf+65,yf+49,xt+65,yt+49);
    /* move rook in the event of a castling move */
    if (board[xf][yf]==-6 && (xf-xt)<-1) {
	/* castling to the right */
	board[xt-1][yt]=board[7][yt];
	board[7][yt]=0;
    }
    if (board[xf][yf]==-6 && (xf-xt)>1) {
	/* castling to the left */
	board[xt+1][yt]=board[0][yt];
	board[0][yt]=0;
    }

    board[xt][yt]=board[xf][yf];
    board[xf][yf]=0;
    /* update notmoved array */
    notmoved[xt][yt]=0;
    notmoved[xf][yf]=0;
    if (board[xt][yt]==-1 && yt==0) {
	/* piece needs to be promoted */
	printf("Promoting your piece to a queen\n");
	board[xt][yt]=-5;
    }


}

int xcoord(char c)
{
    return c-65;
}

int ycoord(char c)
{
    return c-49;

}

void main()
{
    struct move computermove,checkmove;
    int ply,nummoves,opening,seed;

    setupboard();
    printf("Enter random number seed\n");
    scanf("%d",&seed);
    srand(seed);
    printf("Enter number of ply\n");
    scanf("%d",&ply);
    nummoves=1;

    do {
	drawboard();
	if (nummoves==1) {
	    opening=rand(1)%2; /* one of two openings */
	    computermove=openings[opening][0];
	} else if (nummoves==2) {
	    computermove=openings[opening][1];
	} else {

	    computermove=bestmove(1,1,99999,ply); /* make computers move */
	    /* 99999 is the initial cutoff value for pruning */
	}
	if (computermove.score>-5000) { /* player can't take king next move
	so computer is not in checkmate */
	    makemove(computermove);
	    /* update notmoved array to reflect change */
	    /* both square moved from and square moved to are modified */
	    notmoved[computermove.x][computermove.y]=0;
	    notmoved[computermove.x+computermove.dx*computermove.distance][computermove.y+computermove.dy*computermove.distance]=0;
	    drawboard();
	    printf("\n\nMy move:\n %s ",pieces[computermove.piece]);
	    printf("from %c%c",65+computermove.x,49+computermove.y);
	    printf(" to %c%c\n\n",65+computermove.x+computermove.dx*computermove.distance,49+computermove.y+computermove.dy*computermove.distance);
	    if (computermove.score<500) {
		/* ensure it hasn't put player in checkmate */
		/* then find out if player is in check. Do this by looking at
		computer's next move before player makes a response. If it's
		possible to take the king, then the player is in check */
		checkmove=bestmove(1,1,99999,1); /* only want to look one move ahead */

		if (checkmove.score>=500) /* it can take king */
		    printf("Check\n");
		humanmove();
		/* find if computer is in check. Do this by looking at
		player's next move before computer makes a response. If it's
		possible to take the king, then computer is in check */
		checkmove=bestmove(-1,1,99999,1); /* -1 to indicate human's move */
		if (checkmove.score>=500)
		    printf("Check\n");
	    }
	}
	nummoves++;

	/* if computer's score is 500 or greater, then it is in a position
	to take the player's king no matter what his response next move,
	so it must be checkmate. If it's -5000 or less, then the player
	could have taken its king next move, so it's in checkmate */
    } while (computermove.score<500 && computermove.score>-5000);
    printf("Checkmate\n");

}