/*
        Tic - Tac - Toe!
        by Jim Schirle
        Finished on 11/3/98
        Simple minimaxing Tic-tac-toe that never loses
*/

/* Basic include files for input and output
        If you don't have dos.h or would like to compile this
        on another OS just remove the #include <dos.h> and
        then delete all of the clrscr(); */
#include <stdio.h>
#include <dos.h>

/* Defines all of the functions
        Descriptions are with the individual functions */
void initboard(void);
void playgame(int play, char who);
int boardfull(void);
int win(int who);
void compmove(int who);
void hummove(int who);
void output(void);
int minimax(int who);
int find(int a[9],int who);

/* Global array the stores the tic-tac-toe board */
int board[3][3];

/* Main function :
        inputs the number of player and who goes first
        calls the playgame function
        outputs the result of the game */
int main(void)
{
int play;
char c, who;
clrscr();
printf("Tic - Tac - Toe !\n");
printf("by Jim Schirle\n\n");
do
        {
        /* Initalize board */
        initboard();
        /* Prompt for number of players and input */
        printf("How many players (0-2)?");
        while ((play=getchar()-48)<0 || play>2);
        if (play==1)
                {
                printf("Who goes first (Computer/Human)?");
                while((who=toupper(getchar()))!='C' && who!='H');
                }
        clrscr();
        /* Plays game with specified number of players and who starts */
        playgame(play,who);
        clrscr();
        /* Do a final output of the board after end of game */
        output();
        /* Determine who won or if it was a tie and output */
        if (win(-1))
                {
                if(play!=1)printf("\nPlayer 1 won\n");
                else if(who=='C')printf("\nThe Computer won\n"); 
                else if(who=='H')printf("\nPlayer 1 won\n");
                }
        else if (win(1))
                {
                if(play!=1)printf("\nPlayer 2 won\n");
                else if(who=='C')printf("\nPlayer 1 won\n"); 
                else if(who=='H')printf("\nThe Computer won\n");
                }
        else
                printf("\nIt was a tie.\n");
        /* Prompt for another game */
        printf("\nWould you like to play again?\n");
        while ((c=toupper(getchar()))!='N' && c!='Y');
        }
while(toupper(c)=='Y');
}


/* Initboard sets all of the values in the board to 0 */
void initboard()
{
int i,j;
for(i=0;i<3;i++)
        for(j=0;j<3;j++)
                board[i][j]=0;
}

/* Playgame decides based upon the number of players and
        who goes first how to call compmove (computer move)
        and hummove (human move). It also tests for a win
        or an end of game */
void playgame(int play, char who)
{
switch (play)
        {
        case 0:         /* Zero players = computer vs. computer */
                compmove(-1);
                while(!boardfull() && !win(-1))
                        {
                        compmove(1);
                        if (win(1))
                                break;
                        compmove(-1);
                        }
                break;
        case 1:         /* One player = computer vs. human */
                if (who=='H') hummove(-1);
                else compmove(-1);
                while(!boardfull() && !win(-1))
                        {
                        if (who=='H') compmove(1);
                        else hummove(1);
                        if (win(1))
                                break;
                        if (who=='H') hummove(-1);
                        else compmove(-1);
                        }
                break;
        case 2:         /* Two players = human vs. human */
                hummove(-1);
                while(!boardfull() && !win(-1))
                        {
                        hummove(1);
                        if (win(1))
                                break;
                        hummove(-1);
                        }
                break;
        }
}

/* Boardfull tests to see if the board is full or not by
        an exhaustive search. If it finds an empty space
        it returns false. Otherwise it returns true. */
int boardfull()
{
int i,j;
for(i=0;i<3;i++)
        for(j=0;j<3;j++)
                if(board[i][j]==0)
                        return 0;
return -1;
}

/* Win test to see if a win has occured by who
        this is done by testing all of the possible
        wins in a game. */
int win(int who)
{
/* Test for one in middle for most prossible wins */
if (board[1][1]==who)
        {
        /* Test all wins that include middle */
        if (board[0][0]==who && board[2][2]==who)
                return 1;
        if (board[1][0]==who && board[1][2]==who)
                return 1;
        if (board[0][2]==who && board[2][0]==who)
                return 1;
        if (board[0][1]==who && board[2][1]==who)
                return 1;
        }
/* Test top left for top row and left column */
if (board[0][0]==who)
        {
        /* Test top row and left column */
        if (board[0][1]==who && board[0][2]==who)
                return 1;
        if (board[1][0]==who && board[2][0]==who)
                return 1;
        }
/* Test bottom right for bottom row and right column */
if (board[2][2]==who)
        {
/* Test bottom row and right column */
        if (board[2][0]==who && board[2][1]==who)
                return 1;
        if (board[0][2]==who && board[1][2]==who)
                return 1;
        }
/* Otherwise no win has occured */
return 0;
}

/* Prompts the player for a move, tests for validity, and
        makes the move */
void hummove(int who)
{
int move;
clrscr();
output();
printf("\nWhere do you want to move?");
while((move=getchar()-49)<0 || move>8);
while(board[move/3][move%3]!=0)
        {
        printf("\nInvalid Move.\n");
        printf("Where do you want to move?");
        while((move=getchar()-49)<0 || move>8);
        }
board[move/3][move%3]=who;
}

/* Outputs the board to the screen */
void output(void)
{
int i,j;
char out[12][24]={"       |       |       ",
                  "       |       |       ",
                  "       |       |       ",
                  "-----------------------",
                  "       |       |       ",
                  "       |       |       ",
                  "       |       |       ",
                  "-----------------------",
                  "       |       |       ",
                  "       |       |       ",
                  "       |       |       "};
for(i=0;i<3;i++)
        for(j=0;j<3;j++)
                {
                /* Put the square number in upper right corner */
                out[4*i][8*j+6]=i*3+j+49;
                /* Put 'X' or 'O' in the out array */
                if(board[i][j]==-1)
                        out[4*i+1][8*j+3]='X';
                else if(board[i][j]==1)
                        out[4*i+1][8*j+3]='O';
                }
/* Output the array to screen */
for(i=0;i<12;i++)
        printf("%s\n",out[i]);
}

/* Finds the best computer move for the given board
        using the minimax function */
void compmove(int who)
{
/* a[] is a list of the all the moves and it's score */
int i,j,a[9];
for(i=0;i<9;i++)
        a[i]=-who;
for(i=0;i<3;i++)
        for(j=0;j<3;j++)
                {
                /* Check for invalid move */
                if (board[i][j]!=0)
                        continue;
                /* Try a move */
                board[i][j]=who;
                /* Score this board with the trial move */
                a[i*3+j]=minimax(-who);
                /* Undo the move */
                board[i][j]=0;
                }
/* Find the best move in the array */
i=find(a,who);
/* Make the move */
board[i/3][i%3]=who;
}

/* Recursive minimax the finds the score of
        a branch of the move tree */
int minimax(int who)
{
/* Tie = boolean test to see if a tie move has been found
   Best = The best score so far */
int tie=0,i,j,best;
/* Test for a loss (win for one level up) */
if(win(-who))
        return -who;
/* Test for tie */
if(boardfull())
        return 0;
for(i=0;i<3;i++)
        for(j=0;j<3;j++)
                {
                /* Skip invalid moves */
                if (board[i][j]!=0)
                        continue;
                /* Try move */
                board[i][j]=who;
                /* Score this move */
                best=minimax(-who);
                /* Undo move */
                board[i][j]=0;
                /* Return the best move if it's a win
                        because it's not going to get better */
                if(best==who)
                        return who;
                /* At least one tie has been found */
                else if (best==0)
                        tie=-1;
                }
/* If a tie has been found return tie */
if(tie)
        return 0;
/* Return a loss */
else
        return -who;
}

/* Finds the best move for who in a[] */
int find(int a[9],int who)
{
int i,best,index=0;
best=-who;
for(i=0;i<9;i++)
        {
        if(a[i]==who)
                return i;
        if(a[i]==0 && best==-who)
                {
                best=0;
                index=i;
                }
        }
/* Returns the location of the best move */
return index;
}