15 Tic-tac-toe
At the climax of the 1983 film WarGames, the computer that’s about to start World War III is directed to play a game of tic-tac-toe with itself. Recognizing that the game is silly because experienced players often end play in a draw, the computer determines that nuclear war is futile. It decides not to blow up the world. This conclusion should add some excitement to this chapter, because you can equate any game of tic-tac-toe—even one simulated on a computer—to nuclear war.
Game play for tic-tac-toe is simple. It’s easy to code. If you haven’t yet done so, now is the time to write your own version of the game. Of course, it’s made more complex when you consider such tasks as:
The biggest hurdle you face when programming a text-mode game like tic-tac-toe is that I/O in C isn’t interactive. Unless you use a third-party library, such as Ncurses, you must rely upon stream I/O for your programs. It can work, but stream I/O brings potential problems to the table that the code must deal with, lest everything get hinky for the user.
15.1 A silly kids’ game
No one knows the exact origins of the game tic-tac-toe, so I thought I’d make up some interesting facts: in ancient Egypt, a game similar to tic-tac-toe was played on a wooden peg board with tokens carved from the severed toes of enemy soldiers. The Romans enjoyed a game of tria ordine, which involved lining up pebbles on a marble tablet. The prize was to slap your opponent in the face. And in medieval Europe, Norwegian children played a game of tossing fish into baskets, which has nothing to do with tic-tac-toe, but it smelled terrible.
The earliest written reference to tic-tac-toe comes from the late 1800s using the name noughts and crosses. Even today, that is the game’s name in the Commonwealth outside America. The US name tic-tac-toe, originally tick-tack-toe, came about in the early 20th century. The first tic-tac-toe computer program was programmed in the early 1950s.
That’s your history lesson for today—some parts true, but others mostly false.
15.1.1 Playing tic-tac-toe
I’m obligated by the Computer Authors Guild to explain the game of tic-tac-toe despite your complete familiarity with it. Even so, remember that—unlike playing on a piece of paper, in the dirt, or on a fogged mirror—coding the game requires that you review the game play.
Figure 15.1 shows the standard tic-tac-toe grid: two vertical lines intersecting two horizontal lines. This grid holds nine squares, which become the battlefield. These are numbered in the figure, one through nine, also with handy mnemonics for each square’s location: top, middle, and bottom with left, center, and right.
Figure 15.1 The tic-tac-toe game grid, squares numbered and labeled
Players take turns setting a mark into one of the nine grid squares. After choosing who goes first (an advantage), the players alternatively mark an X or O in the squares. Traditionally, the first player marks X, though this choice isn’t a rule.
The winner is the first player to place three of their marks in a row. If this goal fails, the game is a tie, or “cat’s game.” All but the stupidest humans can achieve a tie, so desperate adults play with small kids to make themselves feel victorious.
Experienced players know that going first is advantageous. Further, marking the center square during the first turn, or ply, is the best strategy. Otherwise, good players attempt to set a triangle of squares, as illustrated in figure 15.2, which guarantees a win because their opponent can block only one of the legs.
Figure 15.2 Arrangements for a winning triangle
Regardless of the strategy, tic-tac-toe has only eight paths to victory: three rows, three columns, or two diagonals. Despite the variety of games, only these eight possibilities define a winner. Because of the nine squares in the grid, victory is achieved in nine or fewer moves, making the game easy to learn, quick to play, and fun for a short measure of time.
15.1.2 Approaching the game mathematically
As a nerd, I’m compelled to discuss the mathematical details regarding the game of tic-tac-toe. Some of these details come into play when you code your own game—specifically, if you dare to code a computer opponent and make it somewhat intelligent.
The total number of permutations possible for a game of tic-tac-toe is 19,683. Don’t trust me; someone else did the math. The number accounts for each of nine grid squares holding either an X or an O or being blank. Keep in mind that the game grid is ternary, not binary. I touch upon this point again at the end of this section.
The 19,683 number doesn’t account for actual game play, because X and O follow each other and eliminate squares; the number of permutations is reduced as play moves forward. In practice, the game has 3,200 possible permutations. Removing those situations where the game is already won or tied drops the number further to 2,460.
A final reduction is made by eliminating duplicates due to rotating or mirroring the game grid. When these repetitions are removed, the total number of tic-tac-toe game permutations drops to 120. As this value is a lot easier to handle than 19,683, many programmers opt to create all 120 permutations in memory and use this database to guide the computer during game play.
The coding approach to handle 120 permutations is to create a game tree. This structure contains all possible game plays from which the program can choose a path to victory. In a way, this approach works like a giant cheat sheet, with the computer cribbing its next move based on all the possibilities, with a bias toward exploring only those paths to victory or a tie.
My approach to the computer’s game play isn’t as smart as following a game tree. Instead, I chose to emulate the way people play the game: move to win or move to block. Later in this chapter, I expand upon this technique.
Finally, it’s important to remember that the game gird is ternary: blank, X, or O. Obviously, you use an array to store values in the grid. I originally used values 0, 1, and 2 for blank, X, and O, respectively. This approach made the math more difficult when examining rows, columns, and diagonals. So, I instead used 0 for blank, but -1 for O and +1 for X. You can read more about these choices in the next section.
15.2 The basic game
For my implementation of tic-tac-toe, I began by coding the game grid. In fact, I’ve written many programs that output tic-tac-toe grids, but never bothered writing any game play, probably because the game itself isn’t rewarding to play.
At the core of any interactive text mode game is a game play loop. It accepts input for new moves, updates the grid, and determines when a winning condition occurs. It’s the winning condition that breaks the loop, though other options for bailing out are also provided.
For this first round, I’m coding a human-versus-human version of the game. It features functions that output the game grid, prompt for input, and determine a winner. An updated version that adds the computer as an opponent is covered later in this chapter.
15.2.1 Creating the game grid
Programming a tic-tac-toe grid is one of the basic duties beginners perform when learning C programming. After all, the grid represents a real-life example of a two-dimensional array, with rows and columns. It can be implemented in several ways, as shown in figure 15.3.
Figure 15.3 Various options for presenting a text-mode tic-tac-toe game grid
I experimented with each of the varieties shown in figure 15.3 before I decided it would be more fun to use color text to show the grid. Color text output is covered in chapter 13. It involves sending ANSI escape sequences to standard output, which are interpreted by most terminals as color. The grid I chose is shown in the lower right in figure 15.3, the color-coded squares.
Seven color constants are created to achieve the colors I want, as shown in table 15.1. Two different values are used for each of the three square possibilities: blank, X, and O. The alternating values help set a checkerboard pattern, which helps me avoid adding ugly ASCII line art to build the game grid.
Table 15.1 Color constants and their values used to create the tic-tac-toe game grid
Each sequence sets a foreground or foreground-background combination. The background colors are used, every other square, to create the checkerboard pattern. The final reset[] sequence removes color from the output, which avoids color spill between lines in the output.
The next listing shows the source code for ttt01.c, the foundation upon which all code in this chapter is built. The showgrid() function outputs the game grid with alternating colors, numbering each position, one through nine. A switch-case test determines whether the square is occupied with an O (-1), an X (+1), or a blank (0). In the main() function, the grid is initialized in the grid[] array and then output. The purpose of this tiny program is to ensure that the output looks good.
Listing 15.1 Source code for ttt01.c
#include <stdio.h> void showgrid(int *g) ❶ { const char bfwb[] = "x1b[32;47m"; ❷ const char bf[] = "x1b[32m"; const char xfwb[] = "x1b[31;47m"; const char xf[] = "x1b[31m"; const char ofwb[] = "x1b[34;47m"; const char of[] = "x1b[34m"; const char reset[] = "x1b[0m"; int x; for( x=0; x<9; x++ ) ❸ { switch( *(g+x) ) ❹ { case -1: ❺ if( x%2 ) ❻ printf("%s O %s",ofwb,reset); else ❼ printf("%s O %s",of,reset); break; case 1: ❽ if( x%2 ) printf("%s X %s",xfwb,reset); else printf("%s X %s",xf,reset); break; default: ❾ if( x%2 ) printf("%s %d %s",bfwb,x+1,reset); else printf("%s %d %s",bf,x+1,reset); } if( (x+1)%3==0 ) ❿ putchar(' '); } putchar(' '); } int main() { int grid[] = { ⓫ 0, 0, 0, 0, 0, 0, 0, 0, 0 }; puts("Tic-Tac-Toe"); showgrid(grid); ⓬ return(0); }
❶ The grid[] array is passed as an integer pointer.
❷ Constants to define colors for grid output
❸ Loops through the entire grid, nine squares
❹ Tests the value of each square: -1 for O, +1 for X, and 0 for blank
❻ Outputs the square with a background (and the O)
❼ Outputs the square without a background
❽ Repeats the same output for X
❾ Numbers the unoccupied squares, adding 1 for human eyeballs
❿ Every third square, adds a newline
⓫ The game grid is initialized here.
The showgrid() function processes squares in the game grid. For each possible value—-1, +1, or 0—two options are available for output. The first is triggered for odd-numbered squares, where a background color is applied. For even squares, no background color is used. The effect is to output the current state of play in a consistent pattern, with no extra text characters required to build the grid.
Tic-Tac-Toe 1 2 3 4 5 6 7 8 9
The numbers in the grid help reference squares as the game progresses. Eventually, they’re replaced by X and O characters, which not only informs the user that the same square can’t be played twice but also shows the game’s progress.
You can stop here and just admire your work. But no. The next step is to add game play.
15.2.2 Adding game play
I’m unsure whether every game works this way, but all the text-mode games I’ve written contain a primary game play loop. The loop checks for input, updates the game field, and determines when the game is over.
Generally, the game play loop is endless. The terminating condition is winning the game, losing the game, or the player giving up.
To update the existing ttt01.c code, the game play loop must display the grid, prompt for input, and then update the grid[] array. This loop is shown in the next listing, added just below the puts() statement that outputs the game title. Two integer variables must be declared: ply and p.
Listing 15.2 The game play loop in the main() function
ply = 0; ❶ while(1) ❷ { showgrid(grid); ❸ p = prompt(ply); ❹ if( p==0 ) ❺ break; grid[p-1] = ply%2 ? -1 : 1; ❻ ply++; ❼ }
❶ Turns, or plies, start at zero.
❷ The loop is endless, relying on a win or exit command to break.
❹ Accepts input, returning the square to place a token
❺ If the user inputs zero, the game quits.
❻ Sets the token on the grid, subtracts one from p to obtain the array offset, and uses the current ply to determine whether O (-1) or X (+1) has played
❼ Increments the ply to the next turn
The prompt() function obtains user input, either the square in which to place a mark or zero to exit the game. The zero return value is tested to break the loop, ending the game. Otherwise, the grid[] array is updated.
The value of variable ply (the current turn) determines whether X or O is playing. It’s assumed that X goes first. When ply%2 is 0, then O or -1 is generated in the grid; otherwise, X or +1 is set.
A text mode game must rely upon stream I/O to do its thing. Such a trick is possible if input is limited and makes sense to the user. For my tic-tac-toe game, numeric input is all that’s allowed. I rely upon the scanf() function, which I detest, but it does the job.
The following listing shows the prompt() function, which is called from the main() function in the endless while loop, shown earlier in listing 15.2. The function’s argument is the current ply, the game’s next turn. This value is tested to determine whether X or O is playing. Input ranges from 1 through 9 (human numbers, not the actual array offsets), with 0 indicating the player wants to quit. Out-of-range values are interpreted as 0.
Listing 15.3 The prompt() function
int prompt(int p)
{
int square;
printf("%c's turn: Pick a square, 0 to quit: ",
p%2 ? 'O' : 'X' ❶
);
scanf("%d",&square); ❷
if( square<0 || square>9 ) ❸
return(0);
return(square);
}❶ Uses the ply value in variable p to determine which is the current play, X or O
❸ For out of range values, returns 0 (exit)
The main() function uses the return value from prompt() to set X or O into the grid. The complete source code is available in the online repository as ttt02.c. Here’s a sample run:
Tic-Tac-Toe 1 2 3 4 5 6 7 8 9 X's turn: Pick a square, 0 to quit: 5 1 2 3 4 X 6 7 8 9 O's turn: Pick a square, 0 to quit: 1 O 2 3 4 X 6 7 8 9 X's turn: Pick a square, 0 to quit: 2 O X 3 4 X 6 7 8 9 O's turn: Pick a square, 0 to quit: 5 O X 3 4 O 6 7 8 9 X's turn: Pick a square, 0 to quit: 0
The code successfully places an X or O on the grid, taking turns. What’s missing from the code is the capability to determine when a square is already occupied. As you can see from this sample run, O was able to capture the center square after it was already taken by X. The code also lacks a method to determine when the game is over; game play continues until the user inputs zero to quit.
15.2.3 Limiting the input to free squares
The ttt02.c code has plenty of room for improvement. The priority for me at this point is to restrict play to only blank squares in the grid. For example, if the center square is occupied by an X, player O is unable to choose the square. This update requires a few modifications. To prevent squares from being retaken, the prompt() function must be updated as well as the game play loop in the main() function.
The updated prompt() function is shown next. The grid[] array must be passed as an argument so that the function can determine whether a square is occupied. Further, -1 is added as a return value to flag that a square is occupied or an input value is out of range. Otherwise, the return values are 1 through 9 to select an open square, or 0 to quit.
Listing 15.4 The updated prompt() function
int prompt(int p, int *g) ❶ { int square; printf("%c's turn: Pick a square, 0 to quit: ", p%2 ? 'O' : 'X' ); scanf("%d",&square); if( square<0 || square>9 ) { puts("Value out of range"); ❷ return(-1); ❸ } if( square==0 ) ❹ return(square); if( *(g+square-1) != 0 ) ❺ { printf("Square %d is occupied, try again ", ❻ square ); return(-1); ❼ } return(square); ❽ }
❶ Array grid[] is used as pointer variable g here.
❷ Informs the user that the value is out of range
❸ Returns -1 for invalid input
❹ Tests for the 0 to quit here; otherwise, the value is returned and used improperly on array grid[]
❺ If the value chosen is occupied, or not zero; note that 1 is subtracted because the input is 1 through 9, though the array elements are numbered 0 through 8.
❻ Informs the user that the square is occupied and to try again
❼ Returns -1 for invalid input
❽ Returns the square chosen, which is unoccupied
To make the updated prompt() function work, the statement that calls the function must be modified. Bad input must be dealt with right away. Therefore, I chose to set the function into a while loop, where the return value from prompt() is the condition:
while( (p = prompt(ply,grid)) == -1 )
;The while loop repeatedly calls the prompt() function as long as the value returned is -1. Only valid input—0 or an open square number—breaks the loop. The remainder of the main() function is unchanged.
The updated source code is found in the online repository as ttt03.c. Here is a sample run:
Tic-Tac-Toe 1 2 3 4 5 6 7 8 9 X's turn: Pick a square, 0 to quit: 5 1 2 3 4 X 6 7 8 9 O's turn: Pick a square, 0 to quit: 5 Square 5 is occupied, try again O's turn: Pick a square, 0 to quit: 1 O 2 3 4 X 6 7 8 9 X's turn: Pick a square, 0 to quit: 9 O 2 3 4 X 6 7 8 X O's turn: Pick a square, 0 to quit: 0
At the second move, the program successfully prevents O from choosing X’s square. It outputs a message displaying the issue and urges the player to try again.
15.2.4 Determining the winner
The game works so far, with players able to go back-and-forth choosing squares and setting their marks. But the code doesn’t know when you’ve won. Further, because the game play loop is infinite, eventually you run out of open squares and the game doesn’t stop, nor does the program know when to call a tie, or cat’s game. Fixing is in order.
To determine a winner, I wrote the winner() function. It examines the eight slices through the game grid where a win is possible, as illustrated in figure 15.4. For a slice to identify as a winner, all of its squares must contain the same value—+1 for X or -1 for O. The total for a given slice must be either +3 or -3 to win the game.
Figure 15.4 The eight slices defining a win in tic-tac-toe
The winner() function accepts the game grid as an argument. Each square is examined as columns, rows, and diagonals, as shown in figure 15.4. The notation to do the math was clunky in the function’s original version. For example, to test the left column, I used the following statement:
slice[0] = *(g+0) + *(g+3) + *(g+6);
Element 0 of the slice[] array holds the total for the first column—squares 0, 3, and 6. However, I find the *(g+n) notation to be clumsy and confusing: each square is represented by integer pointer g, plus an offset into the array. Because I constantly had to refer to a map (see figure 15.1) when writing the code, I opted to create some defined constants to reference the various squares more easily:
#define TL *(g+0) #define TC *(g+1) #define TR *(g+2) #define ML *(g+3) #define MC *(g+4) #define MR *(g+5) #define BL *(g+6) #define BC *(g+7) #define BR *(g+8)
The mnemonics of these defined constants, also appearing in figure 15.1, make it easier to define the slices. They also play a role later in the program’s development, when the computer is attempting to block or make a win.
The next listing shows the winner() function. Its argument is the game grid. The slice[] array contains the totals of the eight possible winning combinations, totaling the values in each of the three squares for each slice. If a slice contains all the same tokens, its value is -3 for an O win or +3 for an X win. A for loop tests these possibilities. When a win occurs, the function returns 1, or 0 otherwise.
Listing 15.5 The winner() function
int winner(int *g)
{
int slice[8]; ❶
int x;
slice[0] = TL + ML + BL; ❷
slice[1] = TC + MC + BC;
slice[2] = TR + MR + BR;
slice[3] = TL + TC + TR;
slice[4] = ML + MC + MR;
slice[5] = BL + BC + BR;
slice[6] = TL + MC + BR;
slice[7] = TR + MC + BL;
for( x=0; x<8; x++ ) ❸
{
if( slice[x]==-3 ) ❹
{
showgrid(g); ❺
puts(">>> O wins!"); ❻
return(1); ❼
}
if( slice[x]==3 ) ❽
{
showgrid(g);
puts(">>> X wins!");
return(1);
}
}
return(0); ❾
}❶ Eight possible ways to win; the slice[] array holds the totals.
❷ Tallies the columns, rows, and diagonals for each slice
❺ Outputs the winning game grid
❼ Exits with 1, meaning a player has 1
❽ Repeats the same sequence for an X victory
The winner() function must be integrated into the main() function within the game play loop to report a victory. It also provides another way to terminate the loop beyond the user typing zero to quit the game.
After the winner() function is added, another change to the game play loop is to set a termination condition for the while loop. After all, only nine plies (turns) are possible for a game of tic-tac-toe, assuming it’s a draw.
After the game play loop, I added another if test to determine whether the game was a draw. These items are called out in the next code listing, which shows the updated code from the main() function.
Listing 15.6 Updating the game play loop in the main() function
ply = 0;
while(ply<9) ❶
{
showgrid(grid);
while( (p = prompt(ply,grid)) == -1 )
;
if( p==0 )
break;
grid[p-1] = ply%2 ? -1 : 1;
if( winner(grid) ) ❷
break; ❸
ply++;
}
if( ply==9 ) ❹
{
showgrid(grid); ❺
puts("Cat's game!"); ❻
}❶ Limits the loop to nine turns
❷ Calls the winner() function, which returns 1 when a win is detected
❹ Tests to see whether the loop terminated in a no-win
❺ Outputs the grid to show the draw
The complete update is found in the online repository as ttt04.c. The game now allows two players to compete. It accurately reports a winner and determines when the game ends in a draw. Here is sample output:
Tic-Tac-Toe 1 2 3 4 5 6 7 8 9 X's turn: Pick a square, 0 to quit: 5 1 2 3 4 X 6 7 8 9 O's turn: Pick a square, 0 to quit: 2 1 O 3 4 X 6 7 8 9 X's turn: Pick a square, 0 to quit: 1 X O 3 4 X 6 7 8 9 O's turn: Pick a square, 0 to quit: 9 X O 3 4 X 6 7 8 O X's turn: Pick a square, 0 to quit: 4 X O 3 X X 6 7 8 O O's turn: Pick a square, 0 to quit: 7 X O 3 X X 6 O 8 O X's turn: Pick a square, 0 to quit: 6 X O 3 X X X O 8 O >>> X wins!
Think of all the paper you can save when you play tic-tac-toe on the computer! Of course, most users don’t want to play against a human challenger, probably because they have no friends. The true foe for a game of tic-tac-toe is . . . a computer.
15.3 The computer plays
In the movie WarGames, the genius programmer is asked whether his game of tic-tac-toe has a configuration where the computer can play itself. It does. The key is to enter zero for the number of players. The computer plays itself, realizes that the game is futile, and we go to DEFCON 5.
Obviously, anyone who codes a computer version of tic-tac-toe is compelled to provide the same “number of players equals zero” option available to our intrepid cinematic heroes. Who doesn’t want to see the computer battle wits with itself? This feature not only makes the game more interesting but also tests the programmer’s logic: when the computer plays against itself, does the game always end in a draw?
15.3.1 Choosing the number of players
The decision tree required to set the number of players for the tic-tac-toe program certainly is ugly. I tried making it beautiful, but with three options to sift through, the coding choices are limited.
The prompt is easy enough to code:
Number of players (0, 1, 2):
Set in the main() function, immediately after the program’s title is output, the prompt asks for the number of players: 0, 1, or 2. If an invalid number is input, the program quits.
In the game play loop, however, decisions are made based on the number of players:
-
When the number of players is 0, the computer plays every turn.
-
When the number of players is 1, the computer alternates every other turn.
-
When the number of players is 2, humans take turns, as in the ttt04.c version of the game.
The following listing shows the updated main() function. The number of players is input, and then an if-else contraption sifts through the players, ensuring that human and computer take their turns. If the player count is 1, play alternates between computer and player, with the player going first.
Listing 15.7 The updated main() function
int main()
{
int grid[] = {
0, 0, 0,
0, 0, 0,
0, 0, 0
};
int ply,p,players; ❶
srand( (unsigned)time(NULL) ); ❷
puts("Tic-Tac-Toe");
printf("Number of players (0, 1, 2): "); ❸
scanf("%d",&players);
if( players<0 || players>2 ) ❹
return(1);
ply = 0;
while(ply<9)
{
showgrid(grid);
if( players==0 ) ❺
{
p = computer(grid); ❻
}
else if( players==1 ) ❼
{
if( ply%2 ) ❽
{
p = computer(grid);
}
else ❾
{
while( (p = prompt(ply,grid)) == -1 )
;
}
}
else ❿
{
while( (p = prompt(ply,grid)) == -1 )
;
}
if( p==0 )
break;
grid[p-1] = ply%2 ? -1 : 1;
if( winner(grid) )
break;
ply++;
}
if( ply==9 )
{
showgrid(grid);
puts("Cat's game!");
}
return(0);
}❶ Variable players tracks the number of players: 0, 1, or 2.
❷ Seeds the randomizer for computer play
❹ Exits the program upon invalid input
❻ The computer always plays itself, every turn.
❽ On odd turns, the computer plays.
❾ The prompt() function handles the player’s turn.
❿ For two players, the prompt() function handles both turns.
The computer() function handles the computer’s play, even when both players are the computer. The prompt() function deals with human player interaction.
The code isn’t done. The computer() function must be written, which is covered in the next section. To complete the update from this section, however, you must add directives to include the stdlib.h and time.h header files, which support the srand() statement in the main() function, as well as the rand() statement in the computer() function.
15.3.2 Coding a dumb opponent
At this point in the game’s development, the computer() function need not harbor insidious intelligence nor an intimate knowledge of how to win the game. So, I coded a purely random selection routine, as shown in the next listing. The function tests for an available random square in the grid and sets its token at that location. The random value is returned—in a range compatible with the human player’s choice—where the token is set in the main() function.
Listing 15.8 The computer() function
int computer(int *g)
{
int r;
do
{
r = rand() % 9; ❶
} while( *(g+r) != 0 ); ❷
r++; ❸
printf("The computer moves to square %d
",r); ❹
return(r);
}❶ Generates a random value, 0 through 8
❷ Confirms that the square is empty, or keeps looping otherwise
❸ Increments the square value for humans as well as for consistency with the prompt() function
The complete code, including the updated main() function from the preceding section as well as the computer() function, is available in the online repository as ttt05.c.
At this point in the program’s evolution, the computer always goes second, playing O for its moves. Here is some sample output:
Tic-Tac-Toe Number of players (0, 1, 2): 1 1 2 3 4 5 6 7 8 9 X's turn: Pick a square, 0 to quit: 5 1 2 3 4 X 6 7 8 9 The computer moves to square 6 1 2 3 4 X O 7 8 9 X's turn: Pick a square, 0 to quit: 3 1 2 X 4 X O 7 8 9 The computer moves to square 2 1 O X 4 X O 7 8 9 X's turn: Pick a square, 0 to quit: 7 1 O X 4 X O X 8 9 >>> X wins!
It’s possible to attribute some intelligence to the admittedly dumb computer() function, but nothing of the sort exists. I’d provide a sample run that makes you believe the computer is smart, but instead run the code on your own, setting 0 as the number of players, and review the output. Occasionally, it seems like the computer is being smart. Trust me—it’s not.
The computer complains that it’s unfair that it always goes second in a one-on-one battle. To remedy this situation, update the main() function from ttt05.c so that a random choice is made, determining which player goes first: computer or human.
Here is the first part of the output from my solution:
Tic-Tac-Toe Number of players (0, 1, 2): 1 A flip of the bitcoin says that the computer goes first 1 2 3 4 5 6 7 8 9 The computer moves to square 3 1 2 X 4 5 6 7 8 9
The random choice of who goes first is required only when one player is selected, a human-versus-computer battle. My solution is found in the online repository as ttt06.c.
15.3.3 Adding some intelligence
Most of the nerds who program a computer to play tic-tac-toe use a game tree. They plot every move and its consequences, all 120 or so permutations of the game. I looked into this approach, but it seemed like a lot of work. Being lazy, I instead rolled my own approach for the computer to play, and hopefully win, tic-tac-toe.
My code has three pieces of intelligence for the computer player. First, if it’s the first turn (ply zero) and the computer moves first, it should snag the center square. This update is made to the computer() function:
if( p==0 )
{
puts("The computer snags the center");
return(5);
}Variable p is the current ply value from the game play loop in the main() function. When its value is 0, the computer is taking the first turn and all squares are open. A message is output, and the function returns 5, the center square. The value should be 4, because this is the offset in the grid[] array, but the computer() function must be compatible with the user’s prompt() function and return values in the range 1 through 9. (Remember that prompt() returns 0 to quit the game.)
This if test can be improved to check the center square during the second ply: if the computer goes second but its human opponent is too stupid to grab the center square, it should take it. Here is the update to the if decision:
if( p==0 || (p==1 && MC==0) )
{
puts("The computer snags the center");
return(5);
}The if condition reads, “If it’s the first turn—or if it’s the second turn and the center square (MC) remains empty—grab the center square.” The center square is a position of strength in this game. In fact, taking the center is one of the first tricks a kid learns when first playing tic-tac-toe.
The second iota of intelligence is to play a corner square when the center square is taken. This move provides the best defense when moving second. The if decision here is an easy one:
if( p==1 && TL==0 )
{
puts("The computer moves to square 1");
return(1);
}The if condition reads, “If it’s the second ply (turn) and the top-left (TL) square is empty, take it.” The value 1 is returned. At this point in the computer() function, the center square has already been taken—guaranteed. The preceding if condition rules out MC as anything other than 0. Therefore, on the second ply, p==1, the top-left (TL) square is most likely empty. The if condition tests for it anyway and defensively moves to the top-left square.
The third piece of intelligence consists of a game grid scan for moves to block or moves to win. Before the computer resorts to a random move, it scans all eight possible winning slices on the game grid. If any of these slices contains two of the same tokens plus an empty square, the empty square is filled so that the computer wins or blocks a win.
I originally wrote two functions, towin() and toblock(), to carry out the game grid scan. Eventually, it dawned on me that both functions work the same, just look for different values. The towin() function wants the computer’s tokens to add up to 2 or -2; the toblock() function wants the opponent’s tokens to add up to 2 or -2. I wrote the three() function to handle both conditions:
int three(int *g, int p)
The function’s arguments are g, the game grid, and p, the token to look for: -1 for O and +1 for X.
The three() function’s statements are repetitive, with each block representing one of the eight slices that establish a win. Defined constants shown earlier in this chapter represent the specific squares. Here is a typical block:
if( TL + ML + BL == p*2 )
{
if( TL==0 ) return 0;
if( ML==0 ) return 3;
if( BL==0 ) return 6;
}Defined constants TL, ML, and BL represent the first column in the grid. If their total is equal to two times variable p, the column contains two matching tokens and a blank. This result holds true whether p is -1 for O or +1 for X.
After a slice is identified as a potential win or block, the function returns a value representing the blank square: If it’s the top-left square, TL, 0 is returned. If the middle-left square is blank, ML==0, its offset is returned. This logic allows the computer to either win or block, depending on the value of variable p.
The three() function continues with similar tests for each of the eight slices. The value returned is the square to choose, reported to the computer() function shown in the next listing. The code first checks for a win, and then for a block. If neither test is successful (-1 is returned), the computer randomly chooses an available square, as before.
Listing 15.9 The updated computer() function
int computer(int p,int *g) ❶ { int r; if( p==0 || (p==1 && MC==0) ) ❷ { puts("The computer snags the center"); return(5); } if( p==1 && TL==0 ) ❸ { puts("The computer moves to square 1"); return(1); } if( p%2 ) ❹ r = three(g,-1); ❺ else r = three(g,1); ❻ if( r==-1 ) ❼ { if( p%2 ) ❽ r = three(g,1); ❾ else r = three(g,-1); ❿ } if( r==-1 ) ⓫ { do { r = rand() % 9; } while( *(g+r) != 0 ); } r++; ⓬ printf("The computer moves to square %d ",r); ⓭ return(r); }
❶ Variable p is the current ply and g is the game grid.
❷ Grabs the center square if it’s empty
❸ On the second turn, grabs the corner square if it’s empty
❹ Detects a win using the ply value: 0 means it’s O’s turn, 1 for X.
❼ If a win isn’t detected, three() returns -1; checks for a block (you want to win before you block).
❽ Determines whether X or O is moving next
⓫ If r is equal to -1e, the computer hasn’t won or blocked; time for a random square pick.
⓬ Increments r to represent the proper offset, 1 through 9
The smarts in the computer() function work from the top down: first comes the center square check, and then the computer tries to grab the corner square. After that, the three() function is checked first to win and then to block. When these efforts fail, shown by the value -1 returned, the computer uses the randomizer.
The main() function must also be updated, reflecting the new argument for the computer() function. Two updates are required to modify this statement:
p = computer(grid);
p = computer(ply,grid);
The ply argument is used in the computer() function for its call to the three() function. It’s this variable’s value that determines whether the function is blocking or winning because, in the program, X always moves first.
All changes, including the full three() function, are found in the online repository in the source code file ttt07.c. The computer player isn’t perfectly intelligent, but it’s smart enough to prove a challenge—for at least a few games and definitely to defeat a small child or stupid adult.
The true test, of course, is when the computer plays itself. In theory, it should tie each time. But the program still uses random-number generation to plot its initial game. Specifically, in the computer-to-computer output shown here, see how the computer grabs the center square as well as the upper-left square? These are advantageous and defensive moves, respectively:
Tic-Tac-Toe Number of players (0, 1, 2): 0 1 2 3 4 5 6 7 8 9 The computer snags the center 1 2 3 4 X 6 7 8 9 The computer moves to square 1 O 2 3 4 X 6 7 8 9 The computer moves to square 3 O 2 X 4 X 6 7 8 9 The computer moves to square 7 O 2 X 4 X 6 O 8 9 The computer moves to square 4 O 2 X X X 6 O 8 9 The computer moves to square 6 O 2 X X X O O 8 9 The computer moves to square 9 O 2 X X X O O 8 X The computer moves to square 8 O 2 X X X O O O X The computer moves to square 2 O X X X X O O O X Cat's game!
From the output, you can see that the computer did well against itself. It’s not exactly smart, but it’s challenging enough—and the game ended in a tie.
Further updates to the code at this point would lead to a game tree strategy, where you map out the best second, third, and fourth moves in a complex tree decision structure-thing. At some point, however, playing the game employs the tactics of blocking and winning.
One devious improvement I considered was to have the computer cheat. It could, for example, replace an opponent’s token with its own or prevent an opponent from selecting a winning square. Though such a modification would be fun, it involves rewriting a lot of the existing code. I leave this task up to you, though not as an official exercise.