//Tic-tac-toe playing AI. Exhaustive tree-search. WTFPL
//adapted from
//Matthew Steel 2009, www.www.repsilat.com
#include <stdio.h>
#define BOARDSIZE 9
char gridChar(int i) {
switch(i) {
case -1:
return 'X';
case 0:
return ' ';
case 1:
return 'O';
}
return ' ';
}
void draw(int *b) {
printf(" %c | %c | %c\n",gridChar(b[0]),gridChar(b[1]),gridChar(b[2]));
printf("---+---+---\n");
printf(" %c | %c | %c\n",gridChar(b[3]),gridChar(b[4]),gridChar(b[5]));
printf("---+---+---\n");
printf(" %c | %c | %c\n",gridChar(b[6]),gridChar(b[7]),gridChar(b[8]));
}
int win(int * board) {
//determines if a player has won, returns 0 otherwise.
//kind of inelegant and non-scalable to hard-code wins
unsigned int wins[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
int i;
for(i = 0; i < 8; ++i) {
//for the given current winning board
does our board have matching pieces at each of those locations?
unsigned int curwin0 = wins[i][0];
unsigned int curwin1 = wins[i][1];
unsigned int curwin2 = wins[i][2];
if(board[curwin0] != 0 &&
board[curwin0] == board[curwin1] &&
board[curwin0] == board[curwin2])
return board[curwin2]; //if yes, return the player (-1 or 1) who wins
}
return 0;
}
//minimax in a single recursive function
you call max if it is your move and min if it is your opponent’s move.
int minimax(int * board, int player) {
//How is the position like for player (their turn) on board?
int winner = win(board); //is the board a win?
if(winner != 0) return winner*player; //base case
int curbestmove = -1; //the best move possible
int curbestscore = -2;//Losing moves are preferred to no move
int i;
for(i = 0; i < BOARDSIZE; ++i) {//For all moves,
if(board[i] == 0) {//If legal,
board[i] = player;//Try the move
draw(board);
getchar();
int thisScore = -1 * minimax(board, player*-1);
if(thisScore > curbestscore) {
curbestscore = thisScore;
curbestmove = i;
}//Pick the one that's worst for the opponent
board[i] = 0;//Reset board after try
}
}
if(curbestmove == -1) return 0;
return curbestscore;
}
void computerMove(int * board) {
int move = -1;
int score = -2;
int i;
//333 Project: This loop is the easiest part to parallelize
for(i = 0; i < BOARDSIZE; ++i) {
if(board[i] == 0) {
board[i] = 1;
int tempScore = -minimax(board, -1);
board[i] = 0;
if(tempScore > score) {
score = tempScore;
move = i;
}
}
}
//returns a score based on minimax tree at a given node.
board[move] = 1;
}
void playerMove(int board[9]) {
int move = 0;
do {
printf("\nInput move ([0..8]): ");
scanf("%d", &move);
printf("\n");
} while ((move >= BOARDSIZE || move < 0) && board[move] == 0);
board[move] = -1;
}
int main() {
int board[BOARDSIZE] = {0,0,0,0,0,0,0,0,0};
//computer squares are 1, player squares are -1.
printf("Computer: O, You: X\nPlay (1)st or (2)nd? ");
int player=0;
scanf("%d",&player);
printf("\n");
unsigned turn;
for(turn = 0; turn < BOARDSIZE && win(board) == 0; ++turn) {
if((turn+player) % 2 == 0)
computerMove(board);
else {
draw(board);
playerMove(board);
}
}
switch(win(board)) {
case 0:
printf("A draw. How droll.\n");
break;
case 1:
draw(board);
printf("You lose.\n");
break;
case -1:
printf("You win. Inconceivable!\n");
break;
}
}
You have attempted of activities on this page