Tic tac toe anyone?
Yeah, I'm looking at this tic-tac-toe game code (for just DOS window, etc. no graphical implementation) and I was trying to figure out how the computer picked its move. I thought I had it, but I then destroyed my own theory, sadly. I'm just not sure how the number is picked for the computers best move. Can anyone explain maybe how this thing works? I just hate recursion sometimes.
/*
--------------------------------------------------
| "TicTacToe.c" |
| Copyright 2002 Omid(Eli) David |
| |
| Website: http://www.cs.biu.ac.il/~davoudo |
| Email: davoudo@macs.biu.ac.il |
| |
| Bar-Ilan University, Israel |
--------------------------------------------------
*/
/*
------------------------------------------------------------
| This tic-tac-toe file can be studied as an introdution to |
| basic game tree search in NegaMax method. |
| After understanding the basic concepts here, it will be |
| easier for you to start learning chess algorithms, which |
| are advanced versions of DFS (depth first search) |
| algorithm. |
| After studying this file, I recommend that you learn the |
| AlphaBeta algorithm in the article "Introduction to Chess |
| Tree Search" which can be found at my website. |
| Good luck! |
------------------------------------------------------------
*/
#include
#include
using namespace std;
// definitions
#define HUMAN 0
#define COMPUTER 1
#define EMPTY 2
#define LOSE -1 // the side to move has lost the game
#define DRAW 0 // game drawn
#define CONT 2 // game hasn't ended yet
// the board
/* it's an array of 9, each square can have the value HUMAN,
COMPUTER, or EMPTY */
int pos[9];
// function declarations
int human_move();
void print_board();
int computer_move();
int dfs_search(int side);
int check_result(int side);
/*
------------------------------------------------------------
| main() gets computer and human moves, and checks if the |
| game has ended. |
------------------------------------------------------------
*/
int main()
{
int side; // the side to move. can be HUMAN, COMPUTER or EMPTY
int result;
/* result from point of view of side to move. can be DRAW,
LOSE, or CONT. it can't be a win since if it's your
turn to move, and you haven't moved yet, you can't possibly
win! */
int move; // an integer between 0 to 8. the square to mark
int i;
string ans;
// Introduction
cout << "You are: X" << endl;
cout << "Computer is: O" << endl << endl;
cout << "To move, enter each square's number (-1 to exit):" << endl;
cout << "\t0 1 2" << endl;
cout << "\t3 4 5" << endl;
cout << "\t6 7 8" << endl;
ans = "Y";
while ( ans == "y" || ans == "Y" ) {
for(i = 0; i < 9; ++i)
pos[i] = EMPTY; // initialize the board to EMPTY
result = CONT; // the game is being continued (hasn't ended)
// who starts the game
cout << endl << "Who starts the game, human or computer (h/c)? " << endl;
cin >> ans;
if (ans == "h" || ans == "H")
side = HUMAN;
else
side = COMPUTER;
cout << "_____________________________________________" << endl;
print_board(); // print the board
while (result == CONT) { // while the game hasn't ended
if (side == HUMAN) {
move = human_move(); // get human's move
if (move == -1)
return 0;
}
else
move = computer_move(); // get computer's move
pos[move] = side; // execute the move (mark on the board)
side ^= 1; // reverse the side
print_board();
result = check_result(side); // check if the game has ended
}
// if result is DRAW, the game is drawn. else check who has lost
if (result == DRAW)
cout << "Game drawn." << endl;
else if (side == COMPUTER)
cout << "You won!" << endl;
else
cout << "Computer won!" << endl;
cout << endl << "Start a new game (y/n)? ";
cin >> ans;
}
return 0;
}
/*
------------------------------------------------------------
| human_move() returns user's move, after checking for it's |
| legality. It returns -1 for exit. |
------------------------------------------------------------
*/
int human_move()
{
int move;
do {
cout << "\tYour move: ";
cin >> move;
if (move == -1)
return -1;
}
while (pos[move] != EMPTY); // checking legality
return move;
}
/*
------------------------------------------------------------
| print_board() prints the board. putting an 'X' for human, |
| an 'O' for computer, and a '-' for empty square. |
------------------------------------------------------------
*/
void print_board()
{
int i;
for(i = 0; i < 9; ++i) {
if (pos[i] == EMPTY)
cout << "- ";
else if (pos[i] == HUMAN)
cout << "X ";
else
cout << "O ";
if ( (i + 1) % 3 == 0)
cout << endl;
}
}
/*
------------------------------------------------------------
| computer_move() checks for all legal moves in the current |
| position. then for each of them it calls the dfs_search() |
| function to get the moves' score. And finally it returns |
| the move with the best score. |
------------------------------------------------------------
*/
int computer_move()
{
int best_move; // best move so far
int best_score = -100; // best score so far
int score; // current score
int i;
for(i = 0; i < 9; ++i) {
if (pos[i] == EMPTY) { // if a legal move can be made
pos[i] = COMPUTER; // mark the move
score = -dfs_search(HUMAN);
/* Here we use NegaMax which means negating the score.
For example if your opponent is winning, it means
that you are losing, or in other words the worse
the situation of your opponent is, the better your
position is. That's why we use the negative of the
score from point of view of the opponent. */
pos[i] = EMPTY; // take back the move
if (score > best_score) {
/* if this move's score is better than what we've
had so far, this is the best move. */
best_score = score;
best_move = i;
}
}
}
cout << "Computer's move: " << best_move << endl;
return best_move; // return the best move found
}
/*
------------------------------------------------------------
| dfs_search() gets the side to move, find all legal moves |
| for him, and for each move, it recursively calls itself. |
| It returns a score for the position. |
| This recursive function continues on each variation until |
| the game's end is found in that variation. Which means |
| that the variation continues until check_result() returns |
| a value other than CONT. |
| Note that this can be done in tic-tac-toe, since it's a |
| deterministic game. For games like chess or checkers we |
| can't continue the variation until reaching the game's end |
| so we have to cut the variation at some point. |
------------------------------------------------------------
*/
int dfs_search(int side)
{
int best_score = -100;
int score;
int result;
int i;
result = check_result(side);
if (result != CONT)
return result; // return the result
/* this section is similar to the section in computer_move()
function. The difference is that here we are interested
only in the best score, not the move. The NegaMax algorithm
used here, is explained in computer_move() function. */
for(i = 0; i < 9; ++i) {
if (pos[i] == EMPTY) {
pos[i] = side;
score = -dfs_search(side ^ 1);
pos[i] = EMPTY;
if (score > best_score)
best_score = score;
}
}
return best_score; // return the best score
}
/*
------------------------------------------------------------
| check_result() checks the position to find out whether the |
| side to move has lost, the game is drawn, or it is in |
| progress. The position can't be a win for the side to |
| move! |
------------------------------------------------------------
*/
int check_result(int side)
{
int xside = side ^ 1; // xside is opponent's side
int i;
// checking rows
if (pos[0] == xside && pos[1] == xside && pos[2] == xside)
return LOSE;
if (pos[3] == xside && pos[4] == xside && pos[5] == xside)
return LOSE;
if (pos[6] == xside && pos[7] == xside && pos[8] == xside)
return LOSE;
// checking columns
if (pos[0] == xside && pos[3] == xside && pos[6] == xside)
return LOSE;
if (pos[1] == xside && pos[4] == xside && pos[7] == xside)
return LOSE;
if (pos[2] == xside && pos[5] == xside && pos[8] == xside)
return LOSE;
// checking diagonals
if (pos[0] == xside && pos[4] == xside && pos[8] == xside)
return LOSE;
if (pos[2] == xside && pos[4] == xside && pos[6] == xside)
return LOSE;
// checking for draw
// if an empty square is found, then the game hasn't ended yet
for(i = 0; i < 9; ++i)
if (pos[i] == EMPTY)
return CONT;
return DRAW; // no winner and no empty square, means draw!
}
