Step-by-Step Tic-Tac-Toe
Overview (Step 0)
One of the most challenging aspects of learning to program is not the strange and unfamiliar syntax of the language, but
rather the strange and unfamiliar way of thinking about problems. We take so much for granted when we communicate
with one another, because we know the person we’re communicating with will be able to fill in the gaps. A computer, however,
being a machine, must have everything explained to it literally, and in great detail. This forces us to think carefully about
our problems, and to become comfortable with breaking a problem down into many discrete parts.
How do we break things down? What is the “right” way to convert an idea into a working piece of code? Unfortunately, there is no general answer to that question. Just like there are many ways to express an idea in natural language to your friend, there are many ways to express your idea in a programming language to a computer. Some ways will be more efficient, some will feel awkward, and some will simply not communicate the message effectively. What is needed is practice. Practice taking a problem and identifying the sub-problems contained within it. Practice solving those sub-problems. Use the tools that the language gives you. Get comfortable with how they work, and what their limitations are. More than anything else, you will find that practice helps you refine your technique. If you practice regularly, your programs will improve.
Planning is Key
I’ve designed this tutorial as a way to share with you the process that I use to implement ideas in code. In this case, we’ll be dealing with a relatively simple idea (on the surface): creating an interactive game of Tic-Tac-Toe in which the user and the computer compete with one another to win the game. Like most problems, this problem has many sub-problems hiding inside of it. Before reading on, can you think of any? What functionality would we need? What are the rules of the game? What information would we be required to keep track of? How will we know when the game is over? How will we know who has won? Whose turn it is?
When faced with a problem like this one, the first thing you should ask yourself is: do I understand what is being asked of me? Are the requirements clear? What hidden assumptions am I making? Am I assuming, for example, that the user will always go first? Am I assuming that the size of the board is always 3x3? You are certainly making assumptions. Good programmers are aware of the assumptions they make. Examine those assumptions: they often tell you about things you’ll need to consider when implementing your solution in code.
Describe the Problem
So, how does Tic-tac-toe work?
It’s a game, played on a 3x3 grid, where two players take turns claiming cells on the grid using their symbol (traditionally using an ‘x’ for one player and an ‘o’ for the other) in an attempt to be the first player to mark three adjacent cells . The group of three cells can be either all in the same row, all in the same column, or along either of the two principal diagonals of the grid. The game ends when the first player successfully marks three adjacent cells (in which case that player is the winner), or when all cells have been claimed and no valid moves remain (in which case the game results in a tie, or draw).
Once you feel you understand the problem, you should take a moment to think about what might be the simplest thing you could build that might help you get further along. This is where you begin to break the problem of “implementing Tic-tac-toe in c++” into smaller sub-problems like: “i need a way to display a tic-tac-toe board to the user” and “i need a way to ask the user for the next move,” “i need a way for the computer to determine its own next move,” and “i need a way to know when the game is over.” Take a moment to mentally expand this list of sub-problems for yourself before reading on. What else will you need in order to actually be able to have the computer and the user play Tic-tac-toe with each other?
So now you have a list of sub-problems you feel are important pieces of the bigger solution. It may turn out that some of those sub-problems themselves need to be broken down into sub-problems, but for now, let’s see if we can focus on arranging what we have into a scaffold, or blue-print of our final solution.
Converting to Code
All of this work, so far, and we haven’t written 1 line of c++. A better way of looking at it is: we haven’t wasted 1 second writing code we might possibly never use, or want. But eventually, we need to write code. Let’s do something now that will clearly be useful at this point, since we know we’re going to need it for everything else down the line: let’s figure out the minimal amount of code we’ll need to just draw a tic-tac-toe board.
We don’t need to make it perfect. In fact, since we don’t have the rest of the functionality in place yet to play the game, we probably can’t make it perfect, since so many important decisions have yet to be made. All it has to do at this point is look roughly like a tic-tac-toe board and we’ll be happy. This is a sketch. We’ll put in the details as we go along.
Since drawing the board is a nice, self-contained piece of functionality, it makes sense to implement it as a function, which is what we’ll do.
Before that, however, let’s spend a few moments thinking about the main part of the program that will call the function:
#include <iostream>
using namespace std;
int main (int argc, char* argv[])
{
// State variables
//
// Board:
// 0 1 2
// +---+---+---+
// 0 | | | x | x = board[0][2]
// +---+---+---+
// 1 | | | |
// +---+---+---+
// 2 | | | |
// +---+---+---+
int board[3][3];
drawBoard(board);
}OK - We’ve defined a really simple program that does just two things: (1) it declares a 2-dimensional array (3x3) of integers
which we’ll use to represent the current “state” of each of the cells on our board. Hopefully you’ve thought a bit about the
cells in the planning phase above. They can be in one of three states: “empty”, “owned by the player”, “owned by the computer”.
When it comes to drawing the board, we’ll represent those three states with either an empty space, an x, or an o.
The second thing this program does is call a (currently non-existant) function drawBoard(board), passing it
the 2D array of integers we just defined. This seems reasonable: in order to properly draw the board, we’re going to need to
know the current state of each of the cells in the board – and that is what our board variable holds.
Notice that I’ve described things using comments. Just seeing int board[3][3]; might not tell you much in a few months.
Having those comments to remind you of the assumptions you made when setting up the board will be a big help down the
road.
Let’s take a crack at implementing the drawBoard function now. To start with, we’ll entirely ignore the board parameter – we
haven’t initialized it to anything, and have not spent any time thinking about exactly how we’ll represent everything. For right
now we just want to get a 3x3 grid up on the screen. Here it is:
void drawBoard(int board[][3]) {
cout << " " << " A B C " << endl;
cout << " " << "+---+---+---+" << endl;
for (int row = 0; row < 3; row++) {
cout << row << " " << "| | | |" << endl;
cout << " " << " " << "+---+---+---+" << endl;
}
}It’s a void function, because it doesn’t return anything: it simply draws our board on the screen. It accepts a single parameter, which is the 2-dimensional array (3x3) that we will eventually use to know what to put in each of the cells, based on the current “state” of each cell on the board. Our board is always 3x3, so we’ll make that assumption in this function, which saves us having to provide a second “size” parameter.
In the function body we draw a 3x3 grid of cells using ASCII characters to form the “board”. I’ve included a little extra in the way of labeling, such that each of the columns can be identified by a letter (“A”, “B”, “C”) and each of the rows by a number (“1”, “2”, “3”). I chose this because that’s how you’d access the cells if you were using a spreadsheet program like Excel. Making choices that the user is likely to already be familiar with is always a good idea: it cuts down on the amount of learning your users will have to do in order to use your program.
Click to download the program in its current state.
Step 1: Making the board work
Alright, so we’ve got a board displaying now, and it looks good: except all the cells are empty. If we agree that cells can be in one of three positions, we could use an integer to define it. Perhaps 0 means “empty”, 1 means “owned by the user”, and 2 means “owned by the computer.” If that’s the case, we’d better make sure we use the same mapping in our board parameter, so that the information that gets passed to drawBoard matches our assumptions. If we assume board contains the mapping as we just described it, we could improve our drawBoard function to better reflect the current state
of the board (as represented by the board parameter). How would you do it? Think about it before you read on.
void drawBoard(int board[][3]) {
cout << " " << " A B C " << endl;
cout << " " << "+---+---+---+" << endl;
for (int row = 0; row < 3; row++) {
cout << row << " ";
for (int col = 0; col < 3; col++) {
switch (board[row][col]) {
case 1: cout << "| " << "x" << " "; break;
case 2: cout << "| " << "o" << " "; break;
default:cout << "| " << " " << " "; break;
}
}
cout << "|" << endl;
cout << " " << " " << "+---+---+---+" << endl;
}
}We’ve made the decision here that cells with a 1, which we said above represent cells owned by the user, will be represented on the board by the character x, and cells with a 2, which we said above represent cells owned by the computer, will be represented on the board by the character o. That’s fine, of course, but it’s an example of some of the things we should be thinking about in
the planning phase. We’re also using raw numbers (e.g.: 1 and 2) to represent states. We could (and probably should!) use
an enum for this instead, but we can get to that later. We’re sketching.
Let’s write a few tests to check how our board performs under different scenarios. In our main function, we’ll first initialize the board to all zeros (empty), and then fill in a few cells with arbitrary values:
...
// Each board square will be in one of three possible
// states: 0=empty, 1=owned by 'x' (user), 2=owned by 'o' (computer).
int board[3][3] = {};
// Let's test our board by filling in a few cells randomly
board[0][0] = 1;
board[1][1] = 1;
board[2][2] = 1;
board[0][2] = 2;
board[2][0] = 2;
drawBoard(board);
...Click to download the program in its current state.
Step 2: Program Flow
Alright, at this point you should have convinced yourself that the board works as expected, as long as the inputs
correspond to our assumptions. Let’s revisit the main function and try to determine what the program flow looks
like as a whole. In this exercise, we’re going to think about what it means to play tic-tac-toe: what happens,
what order do things happen in, and how do we know when we’re done?
For complicated programs, this kind of thinking is best done well away from a keyboard, where you’re less tempted to start writing code. Use a pencil and paper, a whiteboard, or anything where you can really explore the problem and draw pictures and diagrams to describe what is going on.
Since Tic-tac-toe is relatively simple, I like to organize my thoughts by inserting comments directly in the
main function. These serve as placeholders for things I’ll come back and implement. Generally, each of these
comments represents one of the sub-problems we talked about in Step 0.
Remember, the specifics of the program flow will change and evolve as you get into your implementation. These comments are here to help you remember the big picture. It’s fine if they change over the course of building out the program.
What are the main steps of the program? At the highest level, they could be described as:
- We’ll need to determine who goes first. Either the user or the computer.
- We’ll need to play the game, with each user taking turns making moves
- We’ll need to say who won
Right there, we’ve identified a couple of pieces of information we’ll need to keep track of. Can you think of what they are?
- We need a way to store “whose turn is it right now?” A
boolvariable might work nicely here, since there are only two options: the user or the computer - We need a loop of some sort to help us progress through the game, since it is a turn-based game.
- We’ll need a way to keep track of “is the game over?” A
boolvariable might work nicely here too, for now, since the game is either over, or it isn’t. When it comes time to say “who won” there are actually 3 outcomes: theuser, thecomputer, or adrawor tie. So we might have to update this use anintorenum.
Before we move on, let’s take a moment to dig into step (2) a bit more. What does “we’ll need to play the game” really mean? Well, we could think of it as the following four things happening again and again, in a loop, as long as the game isn’t over:
- we draw the board in its current state
- current player makes a move
- we check if the current player just won the game
- we swap the current player so the other player becomes the current player
And look - we already have (1) in place! That’s our drawBoard function. Cool! Now we can start to arrange all of this information in our main function, and our game’s main loop is really starting to take shape:
int main (int argc, char* argv[])
{
// State variables
//
// Board:
// 0 1 2
// +---+---+---+
// 0 | | | x | x = board[0][2]
// +---+---+---+
// 1 | | | |
// +---+---+---+
// 2 | | | |
// +---+---+---+
//
// Each board square will be in one of three possible
// states: 0=empty, 1=owned by 'x', 2=owned by 'o'.
int board[3][3] = {};
// Flag to determine whether or not the game is finished
// false: game should end: someone has won or there are no more valid moves
// true: game may continue
bool gameIsValid = true;
// Flag to determine whose turn it is
// false: it is the computer's turn to make a move
// true: it is the player's turn to make a move
bool playerTurn = true;
/* Game Flow */
// 1. determine who goes first
// 2. Enter the main game "loop"
while (gameIsValid) {
// a. draw the board
drawBoard(board);
// b. current player makes a move
// c. check if the current player has just won
// d. swap current player
}
// 3. print final game result message
}Click to download the program in its current state.
Step 3: Start filling in the gaps
Now that we’ve laid everything out, and have spent time thinking about the problem and planning our solution, it’s time to start imeplementing our solution in code. Fortunately, thanks to the work we’ve done so far, we now have a blueprint for what needs to be done, so all we really have to do is think of a good way to implement it. Let’s start with something easy: determining who goes first.
This is really just a coin flip. Either the user will go first, or the computer will go first. We could use a randomly generated number to ensure this happens with equal probability.
We know how to implement a random number generator for values between 0 and some_number, exclusive:
int val = rand() % some_num; So in this case, since we want to generate either a 0 or a 1 for our boolean playerTurn variable, we could do:
playerTurn = rand() % 2;That should do it! But we have to remember two things: we need to #include <cstdlib> to get access to the rand() function, and we need to remember to randomize the seed via srand() so that we actually get random numbers. Remember also that if you choose to use the current time in seconds as your seed, you’ll need to #include <ctime> as well: srand(time()).
So, with that in place, our game loop now looks like:
...
/* Game Flow */
// 1. determine who goes first
playerTurn = rand() % 2; // coin flip
// 2. Enter the main game "loop"
while (gameIsValid) {
// a. draw the board
drawBoard(board);
// b. current player makes a move
// c. check if the current player has just won
// d. swap current player
}
// 3. print final game result message
...Click to download the program in its current state.
Step 4: Getting Input from the User
According to our blueprint, the next unfinished task is the task of the “current player makes a move.” As you think about this, you should realize that this step actually has two different interpretations: the current player might be the user on one turn, and the computer on the next. Making a move has very different implications depending on who our current player is. How could we structure this portion of our program to account for this? One way would be to just write everything we need for both implementations right there, in the main loop.
That would not be very clean, though, and it would make our main loop harder to understand. It would be much nicer if we could find a way to structure things so that “getting the next move” was a function. We want our functions to have good design, though, and that means making sure each function does one thing, and only one thing. So in this case, we probably want to have two functions: one to ask the user for the next move when it’s the user’s turn, and one to calculate the next move when it’s the computer’s turn.
Since we already have the playerTurn variable telling us whose turn it is, something like this would be really nice:
if (playerTurn) {
// Some function for asking the user what the next move should be...
nextPlayerMove(board);
} else {
// Some function for determining what the next move should be...
nextComputerMove(board);
}That’s the wonderful thing about breaking problems down into sub-problems. We can sit here and think specifically about individual things like “how would i like this to work?” without worrying too much about all of the other parts of the problem.
In this case, we can calculate the player’s next move by calling a function we’ll write (playerNextMove) and the computer’s next move by calling a different function we’ll write (computerNextMove). You may notice I’ve included the board as a parameter to each function. Why? Well - because it seemed useful to me, based on thinking about what it means to choose a valid move. The key word here is valid: our user is not free to choose any cell on the board at any time! The user may only choose spaces that have not previously been chosen. In other words: we need to know which cells are empty in order to be certain that the user has given us good input. Since board is our container for information about the current state of every cell, it makes sense that we provide it to the function.
Another thing to note about the idea of validation. Validating user input, in this case, is entirely part of “getting the next player move.” As such, we should handle validation inside the playerNextMove() function, and not pollute the outside world with the concern of validating the result. In other words, the rest of the program should be able to confidently assume that the result of calling playerNextMove() leaves the board in a valid state.
There’s some nice symmetry to our implementation now. Looking at the code, it reads (almost) like English:
If it is now the player’s turn, get the player’s next move using the current state of the board. Otherwise (else), it must be the computer’s turn, so get the computer’s next move using the current state of the board.
Let’s turn now to the nextPlayerMove() function. Since we’re passing the current state of the board via board, and since board is an array, we can manipulate the variable directly to update the state, once we’ve validated the user input. So, in other words, nextPlayerMove() can be a void function since we’ll directly update board:
void nextPlayerMove(int board[][3]) {
int row, col; // containers to hold input from the user
// our implementation here
//...
// at the end, we'll want to directly update board with the validated
// move so that it gets recorded as the new current state of the board:
board[row][col] = 1; // 1 means our user, 'x' when we draw the board. Really wish we'd used
// an enum here instead of these magic numbers! We'll have to fix this
}OK, again, we’ve created a scaffold or blueprint of what we want to have happen in this function. It allows us to now focus on the implementation. We could simply cin the values for starters, but – have we thought about how we want the user to give us input? The board we drew earlier uses letters for columns and rows for numbers, like Excel. We’d better use the same assumptions here when we’re asking the user to enter input. It would be easier for us if everything were numbers (since those can be used as direct array indices), but it’s easier for our user if we use one letter and one number. Well, we know there’s a very limited number of “correct” values, so we could simply translate for the user:
void nextPlayerMove(int board[][3]) {
int row, col; // containers to hold input from the user
char col_c; // container to hold the character input from the user
cin >> col_c >> row; // obtain input from user (e.g.: A 1)
// Translate character input for column into numeric equivalent
if (col_c == 'a' || col_c == 'A') { col = 0; }
else if (col_c == 'b' || col_c == 'B') { col = 1; }
else if (col_c == 'c' || col_c == 'C') { col = 2; }
else {
cout << "! Invalid column value entered. Your choices are: [A, B, C] " << endl;
}
// the rest of our implementation
// ...
// at the end, we'll want to directly update board with the validated
// move so that it gets recorded as the new current state of the board:
board[row][col] = 1; // 1 means our user, 'x' when we draw the board. Really wish we'd used
// an enum here instead of these magic numbers! We'll have to fix this
}Validating the row input should be much easier, since it was given to us directly as an integer:
// Validate the provided row value
if (row < 0 || row > 2) {
cout << "! Invalid row value entered. Your choices are: [0, 1, 2] " << endl;
}Now, we said earlier that we want the result of calling nextPlayerMove to be a valid update to the current state of the board. In other words, we need to handle all validation inside this function. What should we do, then, when the user gives us bad input? Well, one solution would be to implement a loop, and continue to ask the user for input until the user finally gives us something that validates. That would be a good solution, in this case, because all of the logic for handling user input and validation of that input is neatly wrapped up in one function. The rest of the program can call this function and be confident we’ll leave the board in a good (valid) state. See if you can figure out how to implement the loop necessary to ensure that all of the input is properly valid. Keep in mind the three criteria:
- The coordinate of the row must be between 0 and 2
- The coordinate of the column must be between 0 and 2 (but given as A, B, or C)
- The value of the corresponding location in
boardmust be empty (0)
When you’ve worked on it a bit, compare what you have to this complete example:
/**
* Get the next move from the player, and make sure that the
* desired move is valid. Validity means:
* - column value is within bounds [A, B, C]
* - row value is within bounds [0, 1, 2]
* - the selected cell is empty board[row][col] == 0
* Once input has been validated, update the board.
*
* @param int[3][3] board The current state of the board
* @return void
*/
void nextPlayerMove(int board[][3]) {
bool col_valid; // Flag for column validity
bool row_valid; // Flag for row validity
char col_c; // container for the character value of the column
int col; // container for the integer value of the column
int row; // container for the integer value of the row
cout << "Your turn. Where would you like to move next?" << endl;
cout << "Type your move as two characters separated by a space (ex: A 1)" << endl;
do {
col_valid = true; // assume correct input until proven wrong via tests later
row_valid = true; // ...
// Obtain input from the user (one character for column, one int for row)
cin >> col_c >> row;
// Validate the provided column value
if (col_c == 'a' || col_c == 'A') { col = 0; }
else if (col_c == 'b' || col_c == 'B') { col = 1; }
else if (col_c == 'c' || col_c == 'C') { col = 2; }
else {
cout << "! Invalid column value entered. Your choices are: [A, B, C] " << endl;
col_valid = false;
}
// Validate the provided row value
if (row < 0 || row > 2) {
cout << "! Invalid row value entered. Your choices are: [0, 1, 2] " << endl;
row_valid = false;
}
// Ensure that the choice corresponds to an empty cell
if (row_valid && col_valid && board[row][col] != 0) {
cout << "! That cell is not empty. Please try a different cell " << endl;
col_valid = false;
row_valid = false;
}
} while (!col_valid || !row_valid);
// Update the board with the user's latest choice
board[row][col] = 1; // user is always 'x'
}Click to download the program in its current state.
Step 5: Adding Intelligence
At some point, the computer is going to have to make a move. We’ve just finished the part of the program that allows us to get information from the user, via cin, and to validate that information. Clearly, we can’t take the same approach when it’s the computer’s turn. It’s up to us, the developers, to write the logic the computer will use to make its move.
Before we get too wrapped up in how difficult that sounds, let’s follow the principles that have successfully gotten us this far: do the minimum amount of work to be able to test and move on. We can always make the program smarter, or more efficient, later. For now, let’s do the minimum: have the computer choose a random empty cell every time it’s its turn.
THAT’s a problem we can solve. In fact, why don’t you do it now. Here’s a scaffold for you:
/**
* Determine the next move the computer should make. For now
* the strategy will be simple: randomly pick an available
* cell.
* Once a cell has been picked, update the board
*
* @param int[3][3] board The current state of the board
* @return void
*/
void nextComputerMove(int board[][3]) {
int row, col;
// Choose an *available* cell at random from the board
// Update the board state
board[row][col] = 2; // computer is always 'o'. Ugh, again with the magic numbers.
// We'll definitely have to fix this in a future step.
}When you’re done, compare your solution to this working example (If you cheat, it’s not hurting me, just you…)
/**
* Determine the next move the computer should make. For now
* the strategy will be simple: randomly pick an available
* cell.
* Once a cell has been picked, update the board
*
* @param int[3][3] board The current state of the board
* @return void
*/
void nextComputerMove(int board[][3]) {
int row, col;
do {
row = rand() % 3; // Choose a random row
col = rand() % 3; // Choose a random column
} while (board[row][col] != 0); // If taken, try again
// Update the board state
board[row][col] = 2; // computer is always 'o'. Super ugly magic numbers
// make an appearance again. We'll fix this next
}Great. We’ve just programmed some “artificial intelligence” into our game. It now makes a move all by itself! It’s not very “smart,” but we’ll get there.
Notice how all of the functions I’ve written have lots of comments? Each one has a little block comment on top that describes what it does, and most of them have inline comments to clarify the intention of individual lines. I bet it made it easier for you to follow. You should program this way too. Make things easier on yourself and others.
Before we finish, let’s make sure we can call this function from our main function:
...
if (playerTurn) {
// Some function for asking the user what the next move should be...
nextPlayerMove(board);
} else {
// Some function for determining what the next move should be...
nextComputerMove(board);
}
...Click to download the program in its current state.
Step 5.5: Cleaning up our act
We’ve done pretty well so far, but there is one problem with our code that you might have spotted, and that we should address before we go further: we use a lot of magic numbers instead of enum values. enum was designed to allow programmers to avoid putting random “magic” numeric values all throughout their programs. Here’s a perfect example of the problem:
// Update the board state
board[row][col] = 2; // computer is 2, uses symbol 'o' when drawn on board.We’re trying to say that the computer should be marked as the owner of this cell. But it is not clear just by looking at it that 2 means “computer”. If we had an enum, defined outside of main and outside of any functions so that we can use it anywhere, like this:
/**
* Enumerate the possible states of a cell in the game.
*/
enum {EMPTY, USER, COMPUTER}; // the compiler assigns EMPTY=0, USER=1, and COMPUTER=2… then we could use words instead of numbers in our program, and things would be much clearer:
// Update the board state
board[row][col] = COMPUTER; // computer owns this cell now.Nothing changed behind the scenes - the compiler still sees an integer. But we as programmers can deal with words that we’re much more comfortable with. Why don’t you take a moment to update your code to use the enum above, and make it much clearer and easier to maintain.
Step 6: Knowing when to Quit
Well, we’ve come a long way so far: we’ve got a program that can hold and display the internal state of the game, a way to ask for and validate user input, and even a way for the computer to “intelligently” choose its own moves. According to our blueprint, what we need now is a way to know when the game is over.
Let’s do the same thing we did earlier: plan how we’d like it to look, and then structure the implementation to make that work.
The relevant portion of our main loop looks like this, in blueprint form:
...
// c. check if the current player has just won
// d. swap current player
}
// 3. print final game result messageWell, what if we had a function called isGameOver that would be able to determine whether or not the game was still valid? That would be useful here. It would be even more useful if that function also told us how the game ended, particularly because we’ll soon need to know that information in order to print the final game message. Perhaps the two could be combined into one, since we’ll discover how the game ended in the process of determining if it in fact ended at all.
Let’s review the four possible states the game can be in:
- In progress - the game has not ended yet: no one has won, and there are valid moves left
- User won - the user has successfully marked 3 cells in a row
- Computer won - the computer has successfully marked 3 cells in a row
- Draw - neither the user or the computer was successful, but there are no valid moves left
Hmm.. this seems like another good use case for using an enum. Let’s define one for this:
/**
* Enumerate possible states the game can be in. The game is either
* IN_PROGRESS - neither player has won, and there are still valid moves
* USER_WON - user won by matching three in a row
* COMPUTER_WON - computer won by matching three in a row
* DRAW - neither player has won, but there are no valid moves left
*
* See the function `isGameOver` for related logic
*/
enum {IN_PROGRESS=0, USER_WON=USER, COMPUTER_WON=COMPUTER, DRAW};Notice how we manually specified values this time? This allows us to specify that PROGRESS should be 0, and USER_WON should be set to whatever USER is (defined in the other enum), and COMPUTER_WON should be set to whatever USER is, etc. Remember, enums just provide aliases for integer values.
So, we might design a function called isGameOver to return an int value that was one of IN_PROGRESS, USER_WON, COMPUTER_WON, or DRAW to account for each of the four possible outcomes. Such a function would, of course, need to be given the current state of the board (board) so that it could do the calculations. This seems reasonable. If we did have such a function, our game flow blueprint could be updated as follows:
...
// c. check if the game should end
if (isGameOver(board) > 0) {
break; // game is no longer in progress, break out of game loop
} else {
// d. swap current player (and stay in loop to continue playing)
}
...Notice I changed the text of the blueprint to “check if the game should end” because it more directly corresponds with what we actually want now. As I said in step 0, blueprints are just that: guides. As the program evolves, they may change.
While we’re here - let’s just handle (d.) since it is so simple. Our playerTurn variable is holding information on whether or not it is currently the player’s turn (true) or the computer’s turn (false). To swap players after a turn, we simply need to set the value of playerTurn to true if it was false, or to false if it was true. Why don’t you do that now.
OK, so now we need to actually implement this isGameOver function we’ve been talking about. We know it returns an integer. We know the value of that integer will be IN_PROGRESS, USER_WON, COMPUTER_WON, or DRAW depending on whether the game is still in progress, the user has won, the computer has won, or the game ended in a tie. We know it needs to be given the current state of the board in order to figure any of this out. Here’s a reasonable scaffold for the isGameOver function. Use your knowledge of logic, of tic-tac-toe rules, and of multi-dimensional arrays to determine how to get the computer to know when the game is over.
/**
* Determine the status of the game given the current state
* of the board. The status can be one of 4 values:
* IN_PROGRESS - valid: no one has won yet, and there are valid moves remaining
* USER_WON - invalid, user has won
* COMPUTER_WON - invalid, computer has won
* DRAW - invalid, draw - no one has won but there are no valid moves remaining
*
* @param int[3][3] board The current state of the board
* @return int The status of the board in its current state
*/
int isGameOver (int board[][3]) {
// your implementation here:
// one suggested approach:
// For each of the two players, determine if that player has "won". If it has, return the appropriate enum value
// If no one has won, determine if there are any moves left.
// If there are valid moves left, return the enum value for game in progress
// If there are no valid moves left, return the enum value for a draw (tie)
}Click to download the program in its current state.
Step 7: Printing the final message
We only have one piece of our original blueprint left! Once the game ends, we want to display a message to the user that let’s them know the outcome. Let’s think for a moment about what that might involve:
- We need to know how the game ended (did the user win? was it a tie?)
- We want to show the final state of the board so the user can see exactly how things ended
- We want to tell the user something if they won, and something else if they lost
As you might have already noticed, we’ve already implemented a lot of what we need in that list. Our isGameOver function from Step 6 will tell us how the game ended (by returning either USER_WON, COMPUTER_WON, or DRAW), and we can show the final state of the board by calling our trusty drawBoard function and passing it, as you’d expect, the board variable which holds the final state of the board.
One challenge we’ll face though, with our current design, is the fact that we’re not capturing the result of isGameOver. Instead we’re feeding it directly into the condition of an if statement. That will work for the purposes of the if statement, but we want that value later too - so that we can determine which final message to display.
There are two things we could do here to improve our code. First we should update the logic in (c.) so that we can use an enum value instead of a “magic” number. Let’s change the condition in the if to the following, which is equivalent, but more clear:
if (isGameOver(board) != IN_PROGRESS) {But this still feels awkward. Remember in Step 0 when I said writing code was like speaking to another person, and that some things just don’t feel right at times? This is one of those times, at least for me. The phrasing just seems a bit off:
If is the game over based on the current status of the board is not in progress, stop executing the game loop.
Weird. And we still have the problem that we’re passing the result of the isGameOver function directly into the condition of the if rather than capturing it in a variable that will allow us to use it later. We certainly want to fix that, which means we need to create a new variable to determine the status of the game. Now, what should we call it?
Speaking completely honestly, naming things is one of the hardest problems in practical computer science. It’s surprisingly hard to give things meaningful, unambiguous names that will be understood and interpreted the same way by everyone who reads them. Take our current situation, for example. We’d like to have a variable to hold the status of the game at the end of every loop iteration, and to use that variable to (1) determine whether or not to continue looping, and (2) determine which message to show to the user once the game has ended. This variable needs to hold the current status of the game, so gameStatus seems like a good choice. What type should it be? Well, the game status has been encoded into an enumeration of integers, so gameStatus should probably be an int so that it can faithfully store that information.
Notice though, that we already have the concept of game status in our code, but we’ve given it a different name: gameIsValid. Similar concept, different name. Do we need both? Do they serve the same purpose? Can we acheive a more natural phrasing with one or the other? These are the kinds of questions you can start to ask yourself once your program is farther along, and you are more certain that you really understand the problem (and your own solution to it).
In this case, gameIsValid is a boolean variable that we set up way back in Step 2, because, while we were writing our blueprint, we wanted a way to tell whether the main game loop should continue looping or exit. It has served us well up until now, but now that our program has taken shape, we’d really prefer to hold onto more information than bool gameIsValid is capable of. We can also see that, if we used gameStatus, we could simulate gameIsValid by simply checking whether gameStatus == IN_PROGRESS). That’s starting to feel a bit more natural. Let’s eliminate gameIsValid, then, and replace it with our new-and-improved gameStatus variable:
// Variable to hold the current status of the game. See the
// enum declaration at the top of this file for the possible
// values of status.
int gameStatus = IN_PROGRESS;We’ve set it’s default value to IN_PROGRESS since that’s the way the game begins. Now, we also need to update the condition on our main loop:
...
// 2. Enter the main game "loop"
while (gameStatus == IN_PROGRESS) {
// a. draw the board
drawBoard(board);
...Now our main game loop will continue to execute as long as the game’s status is still IN_PROGRESS after each turn. This feels right. We just need to make sure we’re updating gameStatus somewhere in the loop. Let’s change (c.) to the following:
...
// c. Check the current status of the game to determine
// if the game can continue...
gameStatus = isGameOver(board);
...Why does this work? Well, we know isGameOver will return either IN_PROGRESS, USER_WON, COMPUTER_WON, or DRAW, and we know our loop is set to continue looping as long as the return value is IN_PROGRESS. Our awkward quote from above has turned into the much more readable:
If the game status is not “in progress”, stop executing the game loop
OK. Better and better.
The only thing left to do from our original blueprint is “(3.): display a specific message depending on how the game ended.” That’s simple enough now that we have our gameStatus variable, and we can either do it in our main loop, or in a function, if we felt like. Here’s one example of how it might look, implemented in the main loop, and using our last blueprint entry as the guide for where the code should go:
// 3. print final game result message
cout << "Game over! Here's what the final board looked like:" << endl << endl;
drawBoard(board);
cout << endl;
switch (gameStatus) {
case USER_WON: cout << "^.^ Congratulations! ^.^ You win! ^.^ " << endl; break;
case COMPUTER_WON: cout << "~.~ Sorry! ~.~ You lose! ~.~ " << endl; break;
case DRAW: cout << "O.o Whoa, that was close! O.o You tied! O.o " << endl; break;
default: cout << "Hmm... something really went wrong here. Please let my programmer know. " << endl;
}
cout << endl;I’ve chosen to use a switch statement because I realized that I wanted to always choose one out of a set of possible options. Remember that an enum just provides aliases for integers, so it’s perfectly legal (and a common practice) to use enum values to represent the cases in a switch statement. It makes the code a lot more readable than, say case 1:, case 2:, etc.
Well now - we have a nice looking main function which is readable, easy to understand, and clearly implements the main idea of the game. Read through it once, and see if you find it easy to follow what’s going on:
int main (int argc, char* argv[])
{
// State variables
//
// Board:
// 0 1 2
// +---+---+---+
// 0 | | | x | x = board[0][2]
// +---+---+---+
// 1 | | | |
// +---+---+---+
// 2 | | | |
// +---+---+---+
//
// Each board square will be in one of three possible
// states: 0=empty, 1=owned by 'x', 2=owned by 'o'.
int board[3][3] = {};
// Variable to hold the current status of the game. See the
// enum declaration at the top of this file for the possible
// values of status.
int gameStatus = IN_PROGRESS;
// Flag to determine whose turn it is
// false: it is the computer's turn to make a move
// true: it is the player's turn to make a move
bool playerTurn = true;
/* Game Flow */
// 1. determine who goes first
playerTurn = rand() % 2; // coin flip
// 2. Enter the main game "loop"
while (gameStatus == IN_PROGRESS) {
// a. draw the board
drawBoard(board);
// b. current player makes a move
// the logic here depends on whether or not the
// computer or the player is the current player
if (playerTurn) {
// Some function for asking the user what the next move should be...
nextPlayerMove(board);
} else {
// Some function for determining what the next move should be...
nextComputerMove(board);
}
// c. Check the current status of the game to determine
// if the game can continue...
gameStatus = isGameOver(board);
// d. swap current player
playerTurn = (playerTurn) ? false : true;
}
// 3. print final game result message
cout << "Game over! Here's what the final board looked like:" << endl;
cout << endl;
drawBoard(board);
cout << endl;
switch (gameStatus) {
case USER_WON: cout << "^.^ Congratulations! ^.^ You win! ^.^ " << endl; break;
case COMPUTER_WON: cout << "~.~ Sorry! ~.~ You lose! ~.~ " << endl; break;
case DRAW: cout << "O.o Whoa, that was close! O.o You tied! O.o " << endl; break;
default: cout << "Hmm... something really went wrong here. Please let my programmer know. " << endl;
}
cout << endl;
}Notice how the comments help? Think of food. Flavor isn’t required for nutrition, but food is much more enjoyable to eat when it has been well seasoned. Comments are like seasoning. They are not required for the code to function, but the code is much easier to read when it has been well commented.
Click to download the program in its current state.
Step 8: Getting Strategic
Alright, so we’ve got a game, and it plays the user… randomly. Let’s see if we can do better. As with everything else we’ve done so far, don’t get hung up on the idea that it has to play perfectly - let’s get there in steps. The first thing to do might be to examine the moves YOU make when you play. How do YOU try to win? Are there any obvious things you do or don’t do? Are all squares equivalent?
Recall what you implemented earlier to determine whether or not the game was over. Since you now know are only a limited number of ways to win the game, how can you use that information to help your program make “smarter” choices about what its next move should be?
If your answer to the question “are all squares equivalent” was: ‘no’, then one way to play “better than random” would be to make your program choose those squares, if they are available. If they are not available, then your program could default to playing randomly.
At a minimum you should implement this.
Beyond this, you may consider how you actually play the game against a human opponent: most likely you primarily engage in two activities: offense and defense. That is, at every turn, you check to see if you can make a move that will allow you to win (offense), and, if no such move exists, you then check to see if you can make a move that will prevent the opponent from winning (defense). If such a move exists, you take it, blocking your opponent. How could you implement a function to handle this? In other words, how would you write a function to determine if, given the current state of the board, there is a move you could make that would allow you to win? Could you write the function in such a way that you could reuse the same logic for determining if the opponent can win? Since the rules for “can win” are the same for each player, it seems like this should be possible.
What would such a function return? It makes sense that it should “suggest” the next move to make. That is, it should return the cell that the player should claim in order to either win, or prevent the opponent from winning (depending on who we’re calculating for). Since we’ve used a 2-dimensional array, the unique location of the cell to claim involves 2 pieces of information: the row, and the column. We can’t return two integers from a function, so we’ll need to define some structure to hold this combined information. This is a perfect use-case for a struct. Here’s an example that might do the job for us:
/**
* Container to represent a single cell on the board. This makes
* it possible to use a board location as the return value of a
* function ex: `playerCanWin`.
*/
struct Cell {
Cell(int r, int c): row(r), col(c) {};
int row;
int col;
};With this in hand, we could write a function that returns a “Cell” object, which we could then inspect using the dot (.) operator to find the row and column values of the cell. Now we just need to implement the function for whether or not a given player can win. There are many ways to do this, so I’ll give you the structure, and let you fill in the details:
/**
* Determine whether a user could win by claiming
* one more cell along any of the possible winning
* axes.
* There are 8 possible winning axes. The user can
* win if the sum of the cells on that axis is currently
* 2 and if one of the cells is empty (=0).
*
* @param int[3][3] board The current state of the board
* @param int which Which player (USER or COMPUTER)
* @return cell The location of the cell the user could win with
*/
Cell playerCanWin(int board[][3], int whichPlayer) {
// Iterate through the 8 possible winning axes
// Rows,
// Columns,
// and Diagonals
// if a winning move is possible for the current player, return the index of the cell:
// return Cell(<somerow>,<somecol>);
// No possible winning move for this player on this turn
return Cell(-1,-1);
}The code that calls this function could then check the return value, and if the row & column were >= 0, know that a winning move is possible and take the appropriate action:
...
Cell c = playerCanWin(board, COMPUTER);
// If the computer can win, then make it happen:
if (c.row >= 0 && c.col >= 0) {
board[c.row][c.col] = COMPUTER; // claim the square for the computer
}
...Finally, what happens if there are no opportunities for either offense or defense? That is, what if there is no move that you can make that will win the game for you, and there is no move your opponent could make that would win the game for them? Well, in this case, you should “fall back” to playing strategically – picking squares that will best set you up for a winning move on a later turn. We’ve already covered this in the beginning of this section. The ideal solution would be to find a way to encapsulate your three strategies: random, strategic (smart), and offense+defense (let’s call it “genious”) so that they can be chained together to form a working strategy for all situations.
The flow for choosing how to play a square might be: First play offense + defense, then if that doesn’t work, pick a strategic square, then, if all the strategic squares are taken, pick a random square. It would be very hard to beat an opponent who uses this strategy.