-
-
Save MatthewSteel/3158579 to your computer and use it in GitHub Desktop.
//Tic-tac-toe playing AI. Exhaustive tree-search. WTFPL | |
//Matthew Steel 2009, www.www.repsilat.com | |
#include <stdio.h> | |
char gridChar(int i) { | |
switch(i) { | |
case -1: | |
return 'X'; | |
case 0: | |
return ' '; | |
case 1: | |
return 'O'; | |
} | |
} | |
void draw(int b[9]) { | |
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(const int board[9]) { | |
//determines if a player has won, returns 0 otherwise. | |
unsigned 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) { | |
if(board[wins[i][0]] != 0 && | |
board[wins[i][0]] == board[wins[i][1]] && | |
board[wins[i][0]] == board[wins[i][2]]) | |
return board[wins[i][2]]; | |
} | |
return 0; | |
} | |
int minimax(int board[9], int player) { | |
//How is the position like for player (their turn) on board? | |
int winner = win(board); | |
if(winner != 0) return winner*player; | |
move = -1; | |
int score = -2;//Losing moves are preferred to no move | |
int i; | |
for(i = 0; i < 9; ++i) {//For all moves, | |
if(board[i] == 0) {//If legal, | |
board[i] = player;//Try the move | |
int thisScore = -minimax(board, player*-1); | |
if(thisScore > score) { | |
score = thisScore; | |
move = i; | |
}//Pick the one that's worst for the opponent | |
board[i] = 0;//Reset board after try | |
} | |
} | |
if(move == -1) return 0; | |
return score; | |
} | |
void computerMove(int board[9]) { | |
int move = -1; | |
int score = -2; | |
int i; | |
for(i = 0; i < 9; ++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 >= 9 || move < 0 && board[move] == 0); | |
board[move] = -1; | |
} | |
int main() { | |
int board[9] = {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 < 9 && 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; | |
} | |
} |
use system("pause")
Bug in Line-43
Initialize move integer as "int move".
Great implementation of min-max algorithm.
But why you are comparing 1-D Array (Board) with 2-D Array (Wins) in your win() method you could have just made your board as 2-D Array aswell like this unsigned board[3][3]; that would have made comparison much easier.
Thanks for this code. It is really good but I just don't get why have you used the - sign before the minimax function
Hey! Nice code!
The thing I thought a lot, and cant still understand is when the line 57 is executed. It seems it is executed when the game is tie, but line 52 wil never let line 57 get executed. Anyone could explain it?
Hey! Nice code!
The thing I thought a lot, and cant still understand is when the line 57 is executed. It seems it is executed when the game is tie, but line 52 wil never let line 57 get executed. Anyone could explain it?
It will happen at some point in the program, since if there are no moves left naturally move will be initialized as - 1 in one of the branches of the tree.
Bug in Line-43 Initialize move integer as "int move".
Guys keep this bug in mind and don't forget to initialize this before running. Just change move = -1 to int move = -1
Please tell guys how to hold the console output.