/*
 * CSC180: Boardbot
 * Steven Kodani
 *
 * Boardbot is a class project for CSC180. It plays a game called Sidestep
 * by using minimax to search for optimal moves. In addition to minimax, 
 * Boardbot implements alpha beta pruning, iterative deepening, and
 * a history table.
 */

#include <time.h>
#include <string>

struct move
{ int x, y, dX, dY; };

//Game information
int board[5][6];
char inputBuffer[256];
int maxDepth;
int historyTable[5][6][5][6];

//For time checking
time_t start, end;
int timeElapsed;
int allowableTime = 5;
bool timeUp;
        
//Player move functions
void playerMove();
move getMove();
bool determineLegal(move m);
int letterToIndex(char c);
int numberToIndex(char c);

//Computer move functions
void computerMove();
int min(int depth, int parentBest);
int max(int depth, int parentBest);
void generateMoves(int playerSign, move moves[50], int& moveCount);
int evaluate();
char indexToLetter(int i);
char indexToNumber(int i);

//Utilities
void initBoard();
void executeMove(move m);
void retractMove(move m, int replacement);
void printBoard();
int checkMoves(int playerSign);
int determineGameOver();
bool displayGameOver();

/*
 * Main method for Boardbot - starts up the game and then alternates
 * between player moves and computer moves.
 */
int main(int argc, char** argv) 
{
    initBoard();
    
    printf("Please indicate if the Computer (C) or Player (P) should go first: ");
    scanf("%s", inputBuffer);
    
    //Prompt for starting play until input is valid
    while(inputBuffer[0]!='C' && inputBuffer[0]!='P')
    {
        printf("Invalid input. Please try again: ");
        scanf("%s", inputBuffer);
    }
    
    if(inputBuffer[0]=='C')
    {
        printf("Computer goes first\n");
        computerMove();
    }
    else
        printf("Player goes first\n");
    
    //Alternate between player and computer moves until the game is over
    while(1)
    {
        playerMove();
        if(displayGameOver())
            break;
        
        computerMove();
        if(displayGameOver())
            break;
    }
    
    return (EXIT_SUCCESS);
}

//Print the board and prompt the user for a valid move
void playerMove()
{
    printBoard();
    
    move m = getMove();
    while(!determineLegal(m))
    {
        printf("Selected move is not legal.\n");
        m = getMove();
    }
    executeMove(m);
}

//Reads in a move from the player and checks for validity (but not legality)
move getMove()
{
    printf("Please enter your move: ");
    scanf("%s", inputBuffer);
    
    int x = letterToIndex(inputBuffer[0]);
    int y = numberToIndex(inputBuffer[1]);
    int dX = letterToIndex(inputBuffer[2]);
    int dY = numberToIndex(inputBuffer[3]);
    
    //Check for valid input
    while(x==-1 || y==-1 || dX==-1 || dY==-1)
    {
        printf("Selected move is invalid.\n");
        printf("Please enter your move: ");
        scanf("%s", inputBuffer);
        
        x = letterToIndex(inputBuffer[0]);
        y = numberToIndex(inputBuffer[1]);
        dX = letterToIndex(inputBuffer[2]);
        dY = numberToIndex(inputBuffer[3]);
    }
    
    struct move result = {x, y, dX, dY};
    return result;
}

//Determines if a player move is legal - returns true if move is legal
bool determineLegal(move m)
{
    int pieceType = board[m.x][m.y];
    
    switch(pieceType)
    {
        case -3: //Player's king
            if((m.x==(m.dX+1)) && m.y==m.dY)
                return true;
            else 
                return false;
            
        case -2: //Player's soldier
            int dirY;
            //Forward is positive, backwards negative
            m.y>m.dY ? dirY = 1 : dirY = -1;
            
            //Check for collision with other pieces
            if(m.x==m.dX) //If the soldier is moving strait
            {
                if(dirY==1) //If going forwards
                {
                    for(int i=m.y-1;i>m.dY;i--)
                        if(board[m.x][i]!=0)
                            return false;
                }
                else //If going backwards
                {
                    for(int i=m.y+1;i<m.dY;i++)
                        if(board[m.x][i]!=0)
                            return false;
                }
            }
            else //If the soldier is moving diagonal
            {
                if(abs(m.x-m.dX)!=abs(m.y-m.dY))
                    return false;
                
                int dirX;
                m.x<m.dX ? dirX = 1 : dirX = -1;
                
                int i=m.x+dirX;
                int j=m.y-dirY;
                
                if(dirY==1 && dirX==1) //Forward right
                    while(i<m.dX && j>m.dY)
                    {
                        if(board[i][j]!=0)
                            return false;
                        i++; j--;
                    }
                else if(dirY==1 && dirX==-1) //Forward left
                    while(i>m.dX && j>m.dY)
                    {
                        if(board[i][j]!=0)
                            return false;
                        i--; j--;
                    }
                else if(dirY==-1 && dirX==1) //Backward right
                    while(i<m.dX && j<m.dY)
                    {
                        if(board[i][j]!=0)
                            return false;
                        i++; j++;
                    }
                else if(dirY==-1 && dirX==-1) //Backward left
                    while(i>m.dX && j<m.dY)
                    {
                        if(board[i][j]!=0)
                            return false;
                        i--; j++;
                    }
            }
            
            //If the destination was empty
            if(board[m.dX][m.dY]==0)
            {
                if(dirY==1) //If going forwards
                    return true;
                else
                    return false;
            }

            //If an opponent's piece was captured
            if(board[m.dX][m.dY]>0)
                return true;

            return false;
            
        case -1: //Player's pawn
            if((m.x==m.dX) && (m.y==(m.dY+1)) && (board[m.dX][m.dY]==0))
                return true;
            else if(((m.x==m.dX+1) || (m.x==m.dX-1)) && (m.y==(m.dY+1)) &&
                    (board[m.dX][m.dY]>0))
                return true;
            else 
                return false;
            
        case 0: //No piece selected
            return false;
        case 1: //Computer's pawn
            return false;
        case 2: //Computer's soldior
            return false;
        case 3: //Computer's king
            return false;
    }
}

//Translates a player input dimension into an array index
int letterToIndex(char c)
{
    switch(c)
    {
        case 'A':
            return 0;
        case 'B':
            return 1;
        case 'C':
            return 2;
        case 'D':
            return 3;
        case 'E':
            return 4;   
        default:
            return -1;
    }
}

//Translates a player input dimension into an array index
int numberToIndex(char c)
{
    switch(c)
    {
        case '1':
            return 5;
        case '2':
            return 4;
        case '3':
            return 3;
        case '4':
            return 2;
        case '5':
            return 1;   
        case '6':
            return 0;
        default:
            return -1;
    }
}

//Calculates and executes the optimal move for the computer
void computerMove()
{
    int bestScore;
    int finalBest = 0;
    move bestMove, finalMove;
    move moves[50];
    int moveCount = 0;
    int depth = 0;
    int plies = 0;
    
    //Start the clock
    time(&start);
    timeUp = false;
    
    //Clear the history table
    for(int x=0;x<5;x++)
        for(int y=0;y<6;y++)
            for(int dX=0;dX<5;dX++)
                for(int dY=0;dY<6;dY++)
                    historyTable[x][y][dX][dY] = 0;
    
    //Iterative deepening
    for(int j=3;j<30;j++)
    {
        maxDepth = j;
        bestScore = -9999;
        
        generateMoves(1, moves, moveCount);
        for(int i=0;i<moveCount;i++)
        {
            move m = moves[i];
            int destinationPiece = board[m.dX][m.dY];
            executeMove(m);
            int tempScore = min(depth+1, bestScore);
            if(tempScore >= bestScore)
            {
                bestScore = tempScore;
                bestMove = m;
            }
            retractMove(m, destinationPiece);
            
            if(timeUp)
                break;
        }
        if(timeUp)
            break;
        
        //Store the best move for this iteration
        finalMove = bestMove;
        finalBest = bestScore;
        plies = j;
    }
    
    //Print the board and execute the best move from the last complete iteration
    printBoard();
    executeMove(finalMove);
    printf("I made the following move: %c%c%c%c (%c%c%c%c)\n",
            indexToLetter(finalMove.x),
            indexToNumber(finalMove.y),
            indexToLetter(finalMove.dX),
            indexToNumber(finalMove.dY),
            indexToLetter(4-finalMove.x),
            indexToNumber(5-finalMove.y),
            indexToLetter(4-finalMove.dX),
            indexToNumber(5-finalMove.dY));
    printf("Calculation time: %d seconds Plies: %d Heuristic: %d\n",
            timeElapsed, plies, finalBest);
}

//Finds the player's best move at a given ply
int min(int depth, int parentBest)
{
    //Check the clock
    time(&end);
    timeElapsed = end - start;
    if(timeElapsed >= allowableTime)
        timeUp = true;
    
    else if(determineGameOver()<0) //if human loses
        return 9999 - depth;
    
    if(depth==maxDepth)
        return evaluate();
    
    int bestScore = 9999;
    move bestMove;
    move moves[50];
    move l, m;
    int moveCount = 0;
    
    generateMoves(-1, moves, moveCount);
    
    //Sort based on history table
    bool swapped;
    int n = moveCount;
    do
    {
        swapped = false;
        n = n - 1;
        for(int i=0;i<n;i++)
        {
            l = moves[i];
            m = moves[i+1];
            if(historyTable[l.x][l.y][l.dX][l.dY]<historyTable[m.x][m.y][m.dX][m.dY])
            {
                moves[i] = m;
                moves[i+1] = l;
                swapped = true;
            }
        }
    }
    while(swapped);
    
    //Find the worst available move at this ply
    for(int i=0;i<moveCount;i++)
    {
        m = moves[i];
        int destinationPiece = board[m.dX][m.dY];
        executeMove(m);
        int tempScore = max(depth+1, bestScore);
        
        if(tempScore <= bestScore)
        {
            bestScore = tempScore;
            bestMove = m;
        }
        retractMove(m, destinationPiece);
        
        if(bestScore < parentBest)
        {
            historyTable[m.x][m.y][m.dX][m.dY] += 1;
            break;
        }
        
        if(timeUp)
            break;
    }
    return bestScore;
}

//Finds the computer's best move at a given ply
int max(int depth, int parentBest)
{
    //Check the clock
    time(&end);
    timeElapsed = end - start;
    if(timeElapsed >= allowableTime)
        timeUp = true;
    
    if(determineGameOver()>0) //If computer loses
        return -9999 + depth;
    
    if(depth==maxDepth)
        return evaluate();
    
    int bestScore = -9999;
    move bestMove;
    move moves[50];
    move l, m;
    int moveCount = 0;
    
    generateMoves(1, moves, moveCount);
    
    //Sort based on history table
    bool swapped;
    int n = moveCount;
    do
    {
        swapped = false;
        n = n - 1;
        for(int i=0;i<n;i++)
        {
            l = moves[i];
            m = moves[i+1];
            if(historyTable[l.x][l.y][l.dX][l.dY]<historyTable[m.x][m.y][m.dX][m.dY])
            {
                moves[i] = m;
                moves[i+1] = l;
                swapped = true;
            }
        }
    }
    while(swapped);
    
    //Find the best available move at this ply
    for(int i=0;i<moveCount;i++)
    {
        m = moves[i];
        int destinationPiece = board[m.dX][m.dY];
        executeMove(m);
        int tempScore = min(depth+1, bestScore);
        
        if(tempScore >= bestScore)
        {
            bestScore = tempScore;
            bestMove = m;
        }
        retractMove(m, destinationPiece);
        
        if(bestScore > parentBest)
        {
            historyTable[m.x][m.y][m.dX][m.dY] += 1;
            break;
        }
        
        if(timeUp)
            break;
    }
    return bestScore;
}

/*
 * Generates moves available for a given player based on the state of the
 * global board array. Player sign indicates which player the moves should be
 * generated for (-1 for player, 1 for computer). The moves array will hold
 * the moves and moveCount will be the number of moves found.
 */
void generateMoves(int playerSign, move moves[50], int& moveCount)
{
    moveCount = 0;
    int pieceType;

    //For each position on the board
    for(int x=0;x<5;x++)
        for(int y=0;y<6;y++)
        {
            pieceType = board[x][y];
            pieceType *= playerSign;
            
            switch(pieceType)
            {
                case 3: //Kings
                    //If the king hasn't reached the side of the board
                    if((playerSign==-1 && x>=0) || (playerSign==1 && x<=4))
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = x+playerSign; moves[moveCount].dY = y;
                        moveCount++;
                    }
                    break;
                case 2: //Soldiers
                    int tX; int tY;
                    
                    //Forward
                    
                    //Strait forward
                    tX = x; tY = y + playerSign;
                    while((0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = tX; moves[moveCount].dY = tY;
                        moveCount++;
                        
                        tY += playerSign;
                    }
                    if((0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = tX; moves[moveCount].dY = tY;
                        moveCount++;
                    }
                    
                    //Diagonal right
                    tX = x - playerSign; tY = y + playerSign;
                    while((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = tX; moves[moveCount].dY = tY;
                        moveCount++;
                        
                        tX -= playerSign; 
                        tY += playerSign;
                    }
                    if((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = tX; moves[moveCount].dY = tY;
                        moveCount++;
                    }
                    
                    //Diagonal left
                    tX = x + playerSign; tY = y + playerSign;
                    while((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = tX; moves[moveCount].dY = tY;
                        moveCount++;
                        
                        tX += playerSign; 
                        tY += playerSign;
                    }
                    if((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = tX; moves[moveCount].dY = tY;
                        moveCount++;
                    }
                    
                    //Backward
                    
                    //Strait backward
                    tX = x; tY = y - playerSign;
                    while((0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        tY -= playerSign;
                    }
                    if((0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = tX; moves[moveCount].dY = tY;
                        moveCount++;
                    }
                    
                    //Diagonal right
                    tX = x - playerSign; tY = y - playerSign;
                    while((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        tX -= playerSign; 
                        tY -= playerSign;
                    }
                    if((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = tX; moves[moveCount].dY = tY;
                        moveCount++;
                    }
                    
                    //Diagonal left
                    tX = x + playerSign; tY = y - playerSign;
                    while((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        tX += playerSign; 
                        tY -= playerSign;
                    }
                    if((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = tX; moves[moveCount].dY = tY;
                        moveCount++;
                    }
                    break;
                    
                case 1: //Pawns
                    //Forward move
                    if(board[x][y+playerSign]==0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = x; moves[moveCount].dY = y+playerSign;
                        moveCount++;
                    }
                    //Diagonal capture
                    if((board[x+1][y+playerSign]*playerSign)<0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = x+1; moves[moveCount].dY = y+playerSign;
                        moveCount++;
                    }
                    //Diagonal capture
                    if((board[x-1][y+playerSign]*playerSign)<0)
                    {
                        moves[moveCount].x = x; moves[moveCount].y = y;
                        moves[moveCount].dX = x-1; moves[moveCount].dY = y+playerSign;
                        moveCount++;
                    }
                    break;
            }
        }
}

/*
 * Returns an evaluation of the board. The higher the number returned, the more
 * optimal that board state is for the computer. The evaluation is based
 * on the number of pieces remaining in the game and how far each piece is
 * across the board.
 */
int evaluate()
{
    int playerPoints = 0;
    int computerPoints = 0;
    int piecePoints;
    
    //For each position on the board
    for(int i=0;i<5;i++)
        for(int j=0;j<6;j++)
            if(board[i][j]>0) //Computer piece found
            {
                piecePoints = board[i][j];
                if(piecePoints==1) //Pawn
                {
                    piecePoints *= 5-j;
                    piecePoints++;
                    if(i==0 || i==4)
                        piecePoints--;
                }
                else if(piecePoints==2) //Soldier
                {
                    if(j<3)
                        piecePoints *=5;
                    else if(j<5)
                        piecePoints *=3;
                }
                
                computerPoints += piecePoints;
            }
            else if(board[i][j]<0) //Player piece found
            {
                piecePoints = board[i][j];
                if(piecePoints==-1) //Pawn
                {
                    piecePoints *= j;
                    piecePoints--;
                    if(i==0 || i==4)
                        piecePoints++;
                }
                else if(piecePoints==-2) //Soldier
                {
                    if(j>2)
                        piecePoints *= 5;
                    else if(j>0)
                        piecePoints *= 3;
                }
                
                playerPoints += piecePoints;
            }
    
    return computerPoints + playerPoints;
}

//Converts a board array index to a readable position dimension
char indexToLetter(int i)
{
    switch(i)
    {
        case 0:
            return 'A';
        case 1:
            return 'B';
        case 2:
            return 'C';
        case 3:
            return 'D';
        case 4:
            return 'E';   
        default:
            return '0';
    }
}

//Converts a board array index to a readable position dimension
char indexToNumber(int i)
{
    switch(i)
    {
        case 5:
            return '1';
        case 4:
            return '2';
        case 3:
            return '3';
        case 2:
            return '4';
        case 1:
            return '5';   
        case 0:
            return '6';
        default:
            return '0';
    }
}

//Initializes the board by setting the pieces in their initial positions
void initBoard()
{
    for(int i=0;i<5;i++)
    {
        //Blank spaces
        board[i][2] = 0;
        board[i][3] = 0;
        
        //Pawns
        board[i][1] = 1;
        board[i][4] = -1;
        
        //Soldiors
        board[i][0] = 2;
        board[i][5] = -2;
    }
    
    //Kings
    board[0][0] = 3;
    board[4][5] = -3;
}

//Executes a given move on the board
void executeMove(move m)
{
    board[m.dX][m.dY] = board[m.x][m.y];
    board[m.x][m.y] = 0;
}

//Retracts a given move on the board
void retractMove(move m, int replacement)
{
    board[m.x][m.y] = board[m.dX][m.dY];
    board[m.dX][m.dY] = replacement;
}

//Prints the board to the console
void printBoard()
{
    printf("\n");
    //For each position on the board
    for(int i=0;i<6;i++)
    {
        //Print the row number
        printf("%d ", abs(6-i));
        for(int j=0;j<5;j++)
        {
            int pieceType = board[j][i];
            switch(pieceType)
            {
                case -3:
                    printf("k"); break;
                case -2:
                    printf("s"); break;
                case -1:
                    printf("p"); break;
                case 0:
                    printf("-"); break;
                case 1:
                    printf("P"); break;
                case 2:
                    printf("S"); break;
                case 3:
                    printf("K"); break;
            }
            printf(" ");
        }
        if(i==0)
            printf("  computer");
        
        if(i==5)
            printf("  human");
        
        printf("\n");
    }
    printf("-----------\n  A B C D E\n\n");
}

/*
 * Checks to see if the specified player can make any more moves. Returns
 * 1 if the player can make at least one more move or 0 if the player
 * cannot make any moves. If the computer's moves are to be checked then
 * playerSign should be 1 and if the player's moves are to be checked
 * then the playerSign should be -1.
 */
int checkMoves(int playerSign)
{
    int pieceType;

    //For each board position
    for(int x=0;x<5;x++)
        for(int y=0;y<6;y++)
        {
            pieceType = board[x][y];
            pieceType *= playerSign;
            
            switch(pieceType)
            {
                case 3: //Kings
                    //If the king hasn't reached the side of the board
                    if((playerSign==-1 && x>=0) || (playerSign==1 && x<=4))
                        return 1;
                    break;
                case 2: //Soldiers
                    int tX; int tY;
                    
                    //Forward
                    
                    //Strait forward
                    tX = x; tY = y + playerSign;
                    while((0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        return 1;
                        tY += playerSign;
                    }
                    if((0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                        return 1;
                    
                    //Diagonal right
                    tX = x - playerSign; tY = y + playerSign;
                    while((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        return 1;
                        tX -= playerSign; 
                        tY += playerSign;
                    }
                    if((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                        return 1;
                    
                    //Diagonal left
                    tX = x + playerSign; tY = y + playerSign;
                    while((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        return 1;
                        tX += playerSign; 
                        tY += playerSign;
                    }
                    if((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                        return 1;
                    
                    //Backward
                    
                    //Strait backward
                    tX = x; tY = y - playerSign;
                    while((0<=tY && tY<=5) && board[tX][tY]==0)
                        tY -= playerSign;
                    if((0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                        return 1;
                    
                    //Diagonal right
                    tX = x - playerSign; tY = y - playerSign;
                    while((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        tX -= playerSign; 
                        tY -= playerSign;
                    }
                    if((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                        return 1;
                    
                    //Diagonal left
                    tX = x + playerSign; tY = y - playerSign;
                    while((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]==0)
                    {
                        tX += playerSign; 
                        tY -= playerSign;
                    }
                    if((0<=tX && tX<=4) && (0<=tY && tY<=5) && board[tX][tY]*playerSign<0)
                        return 1;
                    break;
                    
                case 1: //Pawns
                    //Forward move
                    if(board[x][y+playerSign]==0)
                        return 1;
                    //Diagonal capture
                    if((board[x+1][y+playerSign]*playerSign)<0)
                        return 1;
                    //Diagonal capture
                    if((board[x-1][y+playerSign]*playerSign)<0)
                        return 1;
                    break;
            }
        }
    return 0;
}

/*
 * Determines if the game over based on the global board array. The game is over
 * when either king is capture or when a player is unable to  make a move. This
 * function will return 1 if the computer lost due to king capture, -1 if the
 * player lost due to king capture, 2 if the computer lost due to no available
 * moves, and -2 if the player lost due to no available moves.
 */
int determineGameOver()
{
    bool playerKingFound = false;
    bool computerKingFound = false;
    
    //Search for kings
    for(int i=0;i<5;i++)
        for(int j=0;j<6;j++)
        {
            if(board[i][j]==3)
                computerKingFound = true;
            
            if(board[i][j]==-3)
                playerKingFound = true;
        }
    
    if(!playerKingFound)
        return -1;
    
    if(!computerKingFound)
        return 1;
    
    if(checkMoves(-1)==0)
        return -2;
    
    if(checkMoves(1)==0)
        return 2;
    
    return 0;
}

/*
 * Uses the determineGameOver() method to see if the game is over. If the game
 * is over then a message will be displayed describing how the game ended. This
 * function acts as a wrapper and should be used after each move (and not in
 * minimax). This function will return true if the game ended.
 */
bool displayGameOver()
{
    int gameOverResult = determineGameOver();
    
    if(gameOverResult!=0)
    {
        printBoard();
        
        switch(gameOverResult)
        {
            case -1:
                printf("The player's king has been captured. The computer won!\n");
                break;
            case 1:
                printf("The computer's king has been captured. The player won!\n");
                break;
            case -2:
                printf("The player can not move. The computer won!");
                break;
            case 2:
                printf("The computer can not move. The player won!");
                break;
        }
        
        return true;
    }
    
    return false;
}