Code:
#include <iostream>
#include <stack>
/* board representation
0 1 2
3 4 5
6 7 8
*/
int rays[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 board[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 }; //0 = unoccupied, 1 = o, 2 = x
int num_unoccupied = 9; //number of unoccupied squares
char symbols[3] = { ' ', 'o', 'x' };
int game_num = 0; // game number. Used to determine who goes first
int stm = 1; //side to move
int computer_side = 2;
std::stack<int> *undo_stack = NULL;
void make_move(int sq, int side) {
board[sq] = side;
--num_unoccupied;
undo_stack->push(sq);
stm ^= 0x3; //1 to 2, 2 to 1
}
void undo_move() { //undoes the last move
board[undo_stack->top()] = 0;
undo_stack->pop();
++num_unoccupied;
stm ^= 0x3; //1 to 2, 2 to 1
}
void print_board() {
std::cout << std::endl;
for (int i = 0; i < 9; ++i) {
if (i % 3 == 0) {
std::cout << std::endl;
}
std::cout << "[" << symbols[board[i]] << "]";
}
std::cout << std::endl;
}
int get_game_state() { // 0 = still going, 1 = o won, 2 = x won, 3 = draw
if (num_unoccupied == 0) {
return 3;
}
for (int i = 0; i < 8; ++i) { //see if ray i contains all the same sides
if (board[rays[i][0]] == board[rays[i][1]] && board[rays[i][1]] == board[rays[i][2]] && board[rays[i][0]] != 0) {
return board[rays[i][0]];
}
}
return 0;
}
int negamax() { /* -1 if loss for stm, 0 if draw, 1 if win */
/* terminating conditions */
int game_state = get_game_state();
if (game_state == 1 || game_state == 2) {
if (stm == game_state) {
return 1;
} else {
return -1;
}
} else if (game_state == 3) {
return 0;
}
/* the actual recursive part */
int scores[9]; // scores if move i is played. -2 = can't play, -1 = loss, 0 = draw, 1 = win
for (int i = 0; i < 9; ++i) {
if (board[i] == 0) {
make_move(i, stm);
scores[i] = -negamax(); /* the - in "nega"max */
undo_move();
} else {
scores[i] = -2;
}
}
int max_score = -3;
for (int i = 0; i < 9; ++i) {
if (scores[i] > max_score) {
max_score = scores[i];
}
}
return max_score;
}
void AI_make_move() {
int scores[9]; // scores if move i is played. -2 = can't play, -1 = loss, 0 = draw, 1 = win
for (int i = 0; i < 9; ++i) {
if (board[i] == 0) {
make_move(i, computer_side);
scores[i] = -negamax();
undo_move();
} else {
scores[i] = -2;
}
}
int max_score = -3;
int max_idx;
for (int i = 0; i < 9; ++i) {
if (scores[i] > max_score) {
max_score = scores[i];
max_idx = i;
}
}
print_board();
std::cout << "Analysis: " << std::endl;
for (int i = 0; i < 9; ++i) {
if (scores[i] != -2) {
std::cout << i << " : ";
switch(scores[i]) {
case 1:
std::cout << "win";
break;
case -1:
std::cout << "loss";
break;
default:
std::cout << "draw";
}
std::cout << std::endl;
}
}
make_move(max_idx, computer_side);
}
int main() {
std::cout << "Tic Tac Toe by Matthew Lai" << std::endl;
std::cout << "Ctrl+C to terminate." << std::endl;
while (true) { /* for every game */
/* clear the board */
for (int i = 0; i < 9; ++i) {
board[i] = 0;
}
num_unoccupied = 9;
if (undo_stack) {
delete undo_stack;
}
undo_stack = new std::stack<int>;
stm = 1;
if (game_num % 2 == 0) {
computer_side = 2;
} else {
computer_side = 1;
}
while (get_game_state() == 0) {
if (stm == computer_side) {
AI_make_move();
} else {
print_board();
int t = -1;
while ( t < 0 || t > 8 || board[t] != 0) {
std::cout << "Your move: ";
std::cin >> t;
}
make_move(t, computer_side ^ 0x3);
}
}
if (get_game_state() == computer_side) {
std::cout << "You lost." << std::endl;
} else if (get_game_state() == 3) {
std::cout << "Draw." << std::endl;
} else {
std::cout << "You won." << std::endl;
}
++game_num;
}
}
It implements minimax (the negamax flavour 
Making Tic Tac Toe Smarter
).
Originally Posted by abh!shek
