< Previous | Contents | Next >
This function receives the board and the computer’s piece. It returns the computer’s move. The first thing to notice is that I do not pass the board by reference.
int computerMove(vector<char> board, char computer)
214 Chapter 6 n References: Tic-Tac-Toe
Instead, I choose to pass by value, even though it’s not as efficient as passing by reference. I pass by value because I need to work with and modify a copy of the board as I place pieces in empty squares to determine the best computer move. By working with a copy, I keep the original vector that represents the board safe.
Now on to the guts of the function. Okay, how do I program a bit of AI so the computer puts up a decent fight? Well, I came up with a basic three-step strategy for choosing a move.
1. If the computer can win on this move, make that move.
2. Otherwise, if the human can win on his next move, block him.
3. Otherwise, take the best remaining open square. The best square is the center. The next best squares are the corners, and then the rest of the squares.
The next section of the function implements Step 1.
{
unsigned int move = 0; bool found = false;
//if computer can win on next move, that’s the move to make while (!found && move < board.size())
{
if (isLegal(move, board))
{
board[move] = computer;
found = winner(board) == computer; board[move] = EMPTY;
}
if (!found)
{
++move;
}
}
I begin to loop through all of the possible moves, 0–8. For each move, I test to see whether the move is legal. If it is, I put the computer’s piece in the
Introducing the Tic-Tac-Toe Game 215
corresponding square and check to see whether the move gives the computer a win. Then I undo the move by making that square empty again. If the move didn’t result in a win for the computer, I go on to the next empty square. However, if the move did give the computer a win, then the loop ends—and I’ve found the move (found is true) that I want the computer to make (square number move) to win the game.
Next, I check to see if I need to go on to Step 2 of my AI strategy. If I haven’t found a move yet (found is false), then I check to see whether the human can win on his next move.
//otherwise, if human can win on next move, that’s the move to make if (!found)
{
move = 0;
char human = opponent(computer);
while (!found && move < board.size())
{
if (isLegal(move, board))
{
board[move] = human;
found = winner(board) == human; board[move] = EMPTY;
}
if (!found)
{
++move;
}
}
}
I begin to loop through all of the possible moves, 0–8. For each move, I test to see whether the move is legal. If it is, I put the human’s piece in the corresponding square and check to see whether the move gives the human a win. Then I undo the move by making that square empty again. If the move didn’t result in a win for the human, I go on to the next empty square. However, if the move did give the human a win, then the loop ends—and I’ve found the
216 Chapter 6 n References: Tic-Tac-Toe
move (found is true) that I want the computer to make (square number move) to block the human from winning on his next move.
Next, I check to see if I need to go on to Step 3 of my AI strategy. If I haven’t found a move yet (found is false), then I look through the list of best moves, in order of desirability, and take the first legal one.
//otherwise, moving to the best open square is the move to make if (!found)
{
move = 0;
unsigned int i = 0;
const int BEST_MOVES[] = {4, 0, 2, 6, 8, 1, 3, 5, 7};
//pick best open square
while (!found && i < board.size())
{
move = BEST_MOVES[i];
if (isLegal(move, board))
{
found = true;
}
++i;
}
}
At this point in the function, I’ve found the move I want the computer to make—whether that’s a move that gives the computer a win, blocks a winning move for the human, or is simply the best empty square available. So, I have the computer announce the move and return the corresponding square number.
cout << "I shall take square number " << move << endl; return move;
}
Rea l Worl d
The Tic-Tac-Toe game considers only the next possible move. Programs that play serious games of strategy, such as chess, look far deeper into the consequences of individual moves and consider many levels of moves and countermoves. In fact, good computer chess programs can consider literally millions of board positions before making a move.
