Code:
#include <stdio.h>
#include <stdlib.h>
#include <curses.h>
#define BOARDROW 7
#define BOARDCOLUMN 7
#define pos_infinity 50000
#define neg_infinity -50000
#define MAX 1
#define MIN 0
int changeboard(int oldboard[BOARDROW][BOARDCOLUMN],int newboard[BOARDROW][BOARDCOLUMN], int position, int player)
{
int i, j;
// Initialize the newboard
for(i = 0; i < BOARDROW; i++)
for(j = 0; j < BOARDCOLUMN; j++)
newboard[i][j] = oldboard[i][j];
i = 1;
// Check if the column is full
if (newboard[BOARDROW - i][position] != 0)
return(0);
else
{
// Drop the piece down the column
while ((newboard[BOARDROW - i][position] == 0) && (i >= BOARDROW))
i++;
newboard[BOARDROW -i + 1][position] = player;
}
return(1);
}
int key(int number, int number2, int of, int obf, int ob,
int obb, int m, int mb, int player, int computer, int direction)
{
if (direction == 2)
{
if (number >= 4)
return(pos_infinity);
else if ((number == 3) && (obf >= 1))
{
return(600);
}
else
return(0);
}
else if (number2 > 0)
{
if ((number2 >=4) || (number >= 4))
return(pos_infinity);
if ((number2 + number) >= 3)
{
if (obf == 1)
{
return(700);
}
else if (of == 1)
return(600);
else if (obf == 2)
return(100);
else if ((ob == 2) && (mb > 0) && (obb > 0))
return(20);
else
return(10);
}
else if ((number2 + number) == 2)
{
if ((obf == 1) && (mb > 0) && (obb > 0))
return(100);
else if ((obf == 1) && ((mb > 0) || (obb > 0)))
return(80);
else if ((obf == 1) && ((m > 0) || (ob > 0)))
return(20);
else if ((of == 1) && (mb > 0) && (obb > 0))
return(20);
else if ((of == 1) && ((mb > 0) || (obb > 0)))
return(10);
else if ((of == 1) && ((m > 0) || (ob > 0)))
return(5);
else if (of == 1)
return(0);
else if (obf == 2)
return(25);
else if ((ob == 2) && (mb > 0) && (obb > 0))
return(5);
else
return(0);
}
else
return(0);
}
if (number >= 4)
return(pos_infinity);
else if ((of == 0) && (ob == 0))
return(0);
else if (number == 3)
{
if ((obb > 0) && (obf > 0))
return(3000);
else
return(600);
}
else if (number == 2)
{
if ((ob + of) < 2)
return(0);
else if ((obb > 1) && (obf > 1))
return(100);
else if (((obb > 1) || (obf > 1)) && (((ob > 1) && (obb > 1)) || ((of > 1) && (obf > 1))))
return(50);
else if (((obb > 0) || (obf > 0)) && (((ob > 1) && (obb > 0)) || ((of > 1) && (obf > 0))))
return(40);
else if ((obb > 0) || (obf > 0))
return(20);
else if ((of > 1) && (ob > 1))
return(10);
else if ((of > 1) || (ob > 1))
return(5);
else if ((of > 0) || (ob > 0))
return (3);
else
return(2);
}
else if (number == 1)
{
if ((ob + of) < 3)
return(0);
else if ((obb > 1) && (obf > 1))
return(10);
else
return(0);
}
player = player + 1;
computer = computer + 1;
return(0);
}
int analyze(int i, int j, int computer, int plyr, int EMPTY, int *of, int *ob,
int *whos, int *obf, int *obb1, int *obb2, int *lastpiece, int *number,
int *number2, int *compscore, int *plyrscore, int *m, int *mb,
int board[BOARDROW][BOARDCOLUMN], int direction)
{
int newscore;
if (board[i][j] == EMPTY) // checks if position is empty
{
if (((i == 0) || (board[i-1][j] != EMPTY)) && (*obb1 == *ob))
(*obb1)++; // Check if the position underneath is occupied and increment paramters
else if ((i == 0) || (board[i-1][j] != EMPTY))
(*obb2)++;
else
*obb2 = 0;
*ob = *ob + 1;
*lastpiece = EMPTY;
}
else if (board[i][j] == computer) // If the position is occupied by computer piece
{
if (*lastpiece == computer)
(*number)++; // If the last piece was computer increment number in sequence
else if (*lastpiece == plyr) // If the last piece was players find score for player sequence and reinitalize parameters
{
newscore = key(*number,*number2,*of,*obf, 0,0, *m, *mb, plyr, computer, direction);
if (newscore == pos_infinity)
return(neg_infinity);
else
{
*plyrscore = *plyrscore + newscore;
*number = 1;
*of = 0;
*obf = 0;
*ob = 0;
*obb1 = 0;
*obb2 = 0;
*whos = computer;
*lastpiece = computer;
*m = 0;
*mb = 0;
*number2 = 0;
}
}
/* If the last piece was empty and the last sequence was players then find the
score for plyr sequence. If the last sequence
was computers then there are middle positions empty bewteen the sequence.*/
else if (*lastpiece == EMPTY)
{
if (*whos == computer)
{
if (*number2 > 0)
{
newscore = key(*number,*number2, *of,*obf, *ob, *obb1, *m, *mb, computer, computer, direction);
if (newscore == pos_infinity)
return(pos_infinity);
else
*compscore = *compscore + newscore;
*number2= 0;
*m = 0;
*mb = 0;
}
else
{
*number2 = *number;
*m = *of;
*mb = *obf;
}
}
else if (*whos == plyr)
{
newscore = key(*number,*number2, *of,*obf, *ob, *obb1, *m, *mb, plyr, computer, direction);
if (newscore == pos_infinity)
return(neg_infinity);
else
*plyrscore = *plyrscore + newscore;
*m = 0;
*mb = 0;
*number2 = 0;
}
*of = *ob;
if (*ob == *obb1)
*obf = *obb1;
else
*obf = *obb2;
*obb1 = 0;
*obb2 = 0;
*ob = 0;
*lastpiece = computer;
*number = 1;
*whos = computer;
}
}
else if (board[i][j] == plyr) // If the position is occupied by player piece
{
// If the last piece was players then update the number in the sequence
if (*lastpiece == plyr)
(*number)++;
// If the last piece was computers find score for computer sequence.
else if (*lastpiece == computer)
{
newscore = key(*number,*number2, *of,*obf, 0,0, *m, *mb, computer, computer, direction);
if (newscore == pos_infinity)
return(pos_infinity);
else
{
*compscore = *compscore + newscore;
*number = 1;
*of = 0;
*obf = 0;
*ob = 0;
*obb1 = 0;
*obb2 = 0;
*whos = plyr;
*lastpiece = plyr;
*mb = 0;
*m = 0;
*number2 = 0;
}
}
// If the last piece was empty if the last sequence was computers then find the
// score for computer sequence and initialize parameters. If the last sequence
// was players then there are middle positions empty bewteen the sequence.
else if (*lastpiece == EMPTY)
{
if (*whos == plyr)
{
if (*number2 > 0)
{
newscore = key(*number,*number2,*of,*obf, *ob, *obb1, *m, *mb, plyr, computer, direction);
if (newscore == pos_infinity)
return(neg_infinity);
else
*plyrscore = *plyrscore + newscore;
*number2 = 0;
*m = 0;
*mb = 0;
}
else
{
*number2 = *number;
*m = *of;
*mb = *obf;
}
}
else if (*whos == computer)
{
newscore = key(*number,*number2, *of,*obf, *ob, *obb1, *m, *mb, computer, computer, direction);
if (newscore == pos_infinity)
return(pos_infinity);
else
*compscore = *compscore + newscore;
*number2 = 0;
*m = 0;
*mb = 0;
}
*of = *ob;
if (*ob == *obb1)
*obf = *obb1;
else
*obf = *obb2;
*obb1 = 0;
*obb2 = 0;
*ob = 0;
*lastpiece = plyr;
*whos = plyr;
*number = 1;
}
}
return(0);
}
int score_direction(int board[BOARDROW][BOARDCOLUMN], int computer, int plyr, int EMPTY, int direction)
{
int k,i,j;
int compscore=0; // Score of computer positions on board
int plyrscore=0; // Score of player positions on board
int number; // Number of consecutive pieces of board
int number2; // If spaces seperate two sequences of one kind of pieces this will contain the first number of pieces */
int lastpiece; // The last piece visited
int whos; // Was the last sequence of pieces computers or players?
int of; // Number of open spaces in front of a sequence of pieces
int ob; // Number of open spaces in behind of a sequence of pieces
int obf; // Number of open spaces in front of a sequence that have pieces underneath them */
int obb1; // Number of open spaces in behind of a sequence that have pieces underneath them */
int obb2; // Same as above, but to be able to keep data on two sequencs
int m; // Number of open spaces bewteen two sequences of the same player
int mb; // Number of open spaces bewteen two sequences of the same player with pieces underneath them
int check; // Check for return of pos_infinity
int newscore; // The score of a sequence of pieces on the board
for (k = 0; k < 7; k++) // Go through the lines of the board
{
if (direction == 1) // If checking horizontal each line starts at (k,0)
{
i = k;
j = 0;
}
else if (direction == 2) // If checking horizontal each line starts at (0,k)
{
j = k;
i = 0;
}
else if (direction == 3) // If checking diagonally we have to go through the cases
{
switch(k)
{
case 0: i = 0;
j = 3;
break;
case 1: i = 0;
j = 2;
break;
case 2: i = 0;
j = 1;
break;
case 3: i = 0;
j = 0;
break;
case 4: i = 1;
j = 0;
break;
case 5: i = 2;
j = 0;
break;
case 6: i = -1;
j = -1;
break;
}
}
else if (direction == 4) // If checking diagonally we have to go through the cases
{
switch(k)
{
case 0: i = 0;
j = 3;
break;
case 1: i = 0;
j = 4;
break;
case 2: i = 0;
j = 5;
break;
case 3: i = 0;
j = 6;
break;
case 4: i = 1;
j = 6;
break;
case 5: i = 2;
j = 6;
break;
case 6: i = -1;
j = -1;
break;
}
}
// Initialize varibales each time through the loop
m = 0;
mb = 0;
ob = 0;
of = 0;
obf = 0;
obb1 = 0;
obb2 = 0;
number = 0;
number2 = 0;
whos = EMPTY;
lastpiece = EMPTY;
while ((j < BOARDCOLUMN) && (i < BOARDROW) && (i >= 0) && (j >= 0)) //go through until outside the board
{
check = analyze(i,j,computer,plyr,EMPTY,&of,&ob,&whos,&obf,
&obb1,&obb2,&lastpiece,&number,&number2,
&compscore,&plyrscore,&m,&mb,board, direction);
if ((check == pos_infinity) || (check == neg_infinity)) //this returns a win or loss after the check
return(check);
else
{
if (direction == 1) //move on to next piece
j++;
else if (direction == 2)
i++;
else if (direction == 3)
{
i++;
j++;
}
else if (direction == 4)
{
i++;
j--;
}
}
}
// When finished getting the score for one line of the last sequence of dropped pieces, add the score to the correct player's score
if (whos == computer)
{
newscore = key(number,number2,of,obf,ob,obb1,m,mb,computer,computer, direction);
if (newscore == pos_infinity)
return(pos_infinity);
compscore = compscore + newscore;
}
else
{
newscore = key(number,number2,of,obf,ob,obb1,m,mb,plyr,computer, direction);
if (newscore == pos_infinity)
return(neg_infinity);
plyrscore = plyrscore + newscore;
}
}
return(compscore - plyrscore); //returns the total score
}
int score(int board[BOARDROW][BOARDCOLUMN], int computer, int plyr, int EMPTY)
{
int horiz; // horizontal score
int vert; //vertical score
int diag1; //diagonal score
int diag2; //other diagonal score
// checks the score returns the score for each direction
horiz = score_direction(board, computer, plyr, EMPTY,1);
if ((horiz == pos_infinity) || (horiz == neg_infinity))
return(horiz);
vert = score_direction(board, computer, plyr, EMPTY, 2);
if ((vert == pos_infinity) || (vert == neg_infinity))
return(vert);
diag1 = score_direction(board, computer, plyr, EMPTY,3);
if ((diag1 == pos_infinity) || (diag1 == neg_infinity))
return(diag1);
diag2 = score_direction(board, computer, plyr, EMPTY,4);
if ((diag2 == pos_infinity) || (diag2 == neg_infinity))
return(diag2);
return(horiz + vert + diag1 + diag2); //total score
}
int quickcheck(int board[BOARDROW][BOARDCOLUMN], int computer, int plyr, int EMPTY)
{
int scoreboard;
scoreboard = score(board, computer, plyr, EMPTY); //score of the board
if ((scoreboard == pos_infinity) || (scoreboard == neg_infinity)) //tells if someone has won
return(scoreboard);
else
return(0);
}
int minimaxAB(int computer, int plyr, int EMPTY, int depth, int max_depth,
int min_or_max, int board[BOARDROW][BOARDCOLUMN], int A,
int B, int *position, int player)
{
int alpha;
int newalpha; //alpha of child node
int beta;
int newbeta; //beta of child node
int newboard[BOARDROW][BOARDCOLUMN]; //creates a new board with new piece dropped
int i;
int legal; //checks if move is legal. i.e. if the space is empty or not
int finished; //reached a leaf node with a win or loss
int newposition; //best score position for child nodes
if (depth == max_depth) //if max depth is reached, get the score
return(score(board, computer, plyr, EMPTY));
else
{
finished = quickcheck(board, computer, plyr, EMPTY); //checks for win or loss
if ((finished == pos_infinity) || (finished == neg_infinity))
return(finished);
alpha = A;
beta = B;
if (min_or_max == MIN) //looks to see if node is a max or a min
{
for (i = 0; i < BOARDCOLUMN; i++)
{
legal = changeboard(board, newboard, i, player);
if (legal)
{
newbeta = minimaxAB(computer, plyr, EMPTY, depth + 1, max_depth, MAX, newboard, alpha, beta, &newposition, -player);
if (newbeta < beta) //if beta score of child is < beta score of parent, change parent beta and record the position
{
beta = newbeta;
*position = i;
}
if (alpha >= beta) //if alpha > beta, prune
return(alpha);
}
}
return(beta); //returns the min score of child beta
}
else
{
for(i = 0; i < BOARDCOLUMN; i++)
{
legal = changeboard(board, newboard, i, player);
if (legal)
{
newalpha = minimaxAB(computer, plyr, EMPTY, depth + 1, max_depth, MIN, newboard, alpha, beta,
&newposition, -player);
if (newalpha > alpha) // if alpha score of child > parent alpha, change parent alpha and record the position
{
alpha = newalpha;
*position = i;
}
if (alpha >= beta) //if alpha > beta, prune
return(beta);
}
}
return(alpha); //return max score of child alpha
}
}
}
int play(int computer, int plyr, int EMPTY, int previousColumn, int board[BOARDROW][BOARDCOLUMN])
{
int position=-1;
int score;
int k;
if (previousColumn == -1) //returns the middle of the board on the first move of the game
position =3;
else
{
score = minimaxAB(computer, plyr, EMPTY, 0, 1, MAX, board, neg_infinity, pos_infinity, &position, computer); //checks for the win
if (score == pos_infinity)
return(position);
else
position = -1;
minimaxAB(computer, plyr, EMPTY, 0, 5, MAX, board, neg_infinity, pos_infinity, &position, computer); //looks ahead 5 moves using alphabeta
if (position == -1) //finds move to avoid a quick loss
{
minimaxAB(computer, plyr, EMPTY, 0, 4, MAX, board, neg_infinity, pos_infinity, &position, computer);
}
if (position == -1)
{
minimaxAB(computer, plyr, EMPTY, 0, 3, MAX, board, neg_infinity, pos_infinity, &position, computer);
}
if (position == -1)
{
minimaxAB(computer, plyr, EMPTY, 0, 2, MAX, board, neg_infinity, pos_infinity, &position, computer);
}
if (position == -1)
{
minimaxAB(computer, plyr, EMPTY, 0, 1, MAX, board, neg_infinity, pos_infinity, &position, computer);
}
if (position == -1)
{
for (k=0; position == -1; k++)
{
if (board[BOARDROW-1][k] == EMPTY) // checks for valid column
position = k; //chooses a column with empty space
}
}
}
return(position);
}
int new_board(int board[BOARDROW][BOARDCOLUMN], int position, int player)
{
int i;
i = 1;
if (board[BOARDROW - i][position] != 0) //checks to see if column is full
return(0);
else
{
while ((board[BOARDROW - i][position] == 0) && (i >= BOARDROW)) //put piece in column
i++;
board[BOARDROW -i + 1][position] = player;
}
return(1);
}
void drawboard(int board[BOARDROW][BOARDCOLUMN])
{
int i;
int j;
system("clear");
printf(" 1 2 3 4 5 6 7\n");
for (i = BOARDROW - 1; i >= 0; i--)
{
printf("| ");
for (j = 0; j < BOARDCOLUMN; j++)
{
if (board[i][j] == -1)
printf("O");
else if (board[i][j] == 1)
printf("X");
else
printf(" ");
printf(" | ");
}
printf("\n");
}
}
int ask(int board[BOARDROW][BOARDCOLUMN], int plyr)
{
int answer;
int i;
int correct = 1;
int legal;
char buffer[8];
do
{
printf("Pick a column to drop a piece: ");
i = scanf("%i", &answer);
if (i != 1)
{
printf("You must enter an integer!\n");
correct = 0;
scanf("%s", buffer);
}
else if ((answer > BOARDCOLUMN) || (answer <= 0))
{
printf("You must enter an integer bewteen 1 and 7\n");
correct = 0;
}
else
{
correct = 1;
answer = answer - 1;
legal = new_board(board,answer,plyr);
if (legal == 0)
{
printf("That column is full! Please try again\n");
correct = 0;
}
}
}while (correct == 0);
return(answer);
}
int isfull(int board[BOARDROW][BOARDCOLUMN], int EMPTY)
{
int j;
for (j = 0; j < BOARDCOLUMN; j++)
if (board[BOARDROW - 1][j] == EMPTY)
return(0);
return(1);
}
int main()
{
static int board[BOARDROW][BOARDCOLUMN] = {0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0};
int start;
int ok;
int correct = 1;
int computer;
int plyr;
int EMPTY;
int qcheck;
int legal;
int comploss=0;
char buffer[8];
int position;
system("clear");
do
{
printf("If you want the computer to go first, enter -1; if you want to go first, enter 1: ");
ok = scanf("%i", &start);
if (ok != 1)
{
printf("You must enter an integer!\n");
correct = 0;
ok = scanf("%s", buffer);
}
else if ((start != 1) && (start != -1))
{
printf("You must enter 1 or -1\n");
correct = 0;
}
else
correct = 1;
}while (correct == 0);
if (start == 1)
{
plyr = 1;
computer = -1;
EMPTY = 0;
}
else
{
plyr = -1;
computer = 1;
EMPTY = 0;
position = play(computer, plyr, EMPTY, -1, board);
new_board(board, position, computer);
}
do
{
drawboard(board);
ask(board, plyr);
position = play(computer, plyr, EMPTY, 3, board);
legal = new_board(board, position, computer);
if (!legal)
{
comploss = 1;
break;
}
qcheck = quickcheck(board, computer, plyr, EMPTY);
}while((!isfull(board,EMPTY)) && (qcheck != neg_infinity) && (qcheck != pos_infinity));
drawboard(board);
if (comploss == 1)
printf("\nIllegal move! Computer loses!\n");
else if (isfull(board, EMPTY))
printf("\nThe game is a tie\n");
else if (qcheck == neg_infinity)
printf("\nYou won the game\n");
else
printf("\nSorry, you lose the game\n");
return(0);
}
