Hunter Liu's Website

16. Week 8 Thursday: Tic-Tac-Toe

≪ 15. Week 8 Tuesday: Midterm 2 Review | Table of Contents | 17. Week 9 Tuesday: Pointers ≫

Hopefully the midterm went well for you all! Let’s synthesise some of our skills and do an extended example today: we’ll try to create a working game of tic-tac-toe using object-oriented programming (i.e. classes). This is a considerably more complex example than some of the other problems we’ve looked at in the past, and hopefully this will demonstrate good practises in regards to incremental programming, writing modular code, and writing extensible code.

Let’s begin by first giving a somewhat detailed outline of how a single round of tic-tac-toe works.

  1. Create an empty \(3\times 3\) board of characters, to be filled by X’s and O’s.
  2. Repeat the following \(9\) times:
    • Display the game board.
    • Ask the current player which square they’d like to place their move in.
    • Fill in the provided square with an X on odd turns and an O on even turns.
    • Check if the player just won. If they did, tell them they won and end the game.
  3. If all \(9\) turns were completed without a winner, the game is a draw.

It’s really tempting to just jump right in and try to make it all work from the confines of the main program, but this isn’t a good choice in the long run, and we’ll see this at work soon.

There’s one object at the centre of the game: the \(3\times 3\) board itself. At almost every step of the way, we’re performing an action that directly involves the Tic-Tac-Toe board, whether we’re displaying the board, playing a move, or checking for a winner. This indicates that we should create a class for the game board, add these “actions” as member functions, and fill those in incrementally.

There are certainly other complex nouns present in our game outline, and there’s an art to determining which ones get to become classes in our code and which ones don’t. For instance, we may think that the player deserves to have a class. However, all the player does is input their move, nothing else; we don’t really need a class to do this, we just need a cin statement.

Thus, let us collect the core components of the Board class. It should contain a single private member variable, representing the \(3\times 3\) grid of squares. I’ll elect to use a vector<string> to represent the board: each string contains three characters, representing one row of the board. This vector of strings should therefore contain three strings: one for each column. (Alternatively, you could use vector<vector<char>>, but this is ugly.)

Next, we need to have a constructor. All it should do is set up this vector<string> to actually contain \(3\) strings of \(3\) spaces each, i.e. to create the empty board. (Otherwise, the board is empty not only of O’s and X’s but of squares as well!)

After that, we’ll need a way to (A) display the board, which neither returns anything nor needs any parameters, (B) play a move for a player, which requires a mark (O or X), a row, and a column, but returns nothing, and (C) determine if someone won the game or not, which returns a boolean and doesn’t need to accept any parameters.

We can therefore cobble together the header file for this class.

Board.hpp 
 1#ifndef BOARD_HPP 
 2#define BOARD_HPP 
 3
 4#include <string> 
 5#include <vector> 
 6using namespace std; 
 7
 8class Board {
 9public: 
10    /** 
11     * Creates a new empty tic-tac-toe board. 
12     */ 
13    Board(); 
14
15    /** 
16     * Prints out the current board to cout. 
17     */ 
18    void print(); 
19
20    /** 
21     * Places the given marker at the specified 
22     * row and column. 
23     */ 
24    void play_move(char marker, int row, int col); 
25
26    /** 
27     * Determines if someone has won the game yet. 
28     */ 
29    bool has_winner(); 
30
31private: 
32    vector<string> board; 
33}; 
34
35#endif

Let’s assemble a barebones cpp file so that all the definitions of each function and whatnot are there. We won’t fill them out yet, we just want the code to compile so we can begin implementing these functionalities one at a time.

Board.cpp skeleton 
 1#include "Board.hpp" 
 2
 3#include <iostream> 
 4#include <string> 
 5#include <vector> 
 6
 7using namespace std; 
 8
 9Board::Board() { 
10    // TODO 
11} 
12 
13void Board::print() {
14    // TODO 
15} 
16
17void Board::play_move(char marker, int row, int col) {
18    // TODO 
19} 
20
21bool Board::has_winner() {
22    return false; 
23}

Note that I’ve added a return value for has_winner so my code compiles no matter what. Of course, nothing is going to work, but that’s okay! This skeleton will let us write up a main program according to our pseudocode, then slowly fill in the missing definitions so that things start working.

Let’s write the main program right away:

 1#include "Board.hpp"
 2#include <iostream> 
 3
 4using namespace std; 
 5
 6int main() {
 7    // 1. create an empty board. 
 8    Board game_board; 
 9
10    // maybe print a welcome message for fun. 
11    cout << "Welcome to tic-tac-toe!" << endl; 
12
13    // 2. repeat 9 moves: 
14    for(int i = 1; i <= 9; i++) {
15        // first, print the current board. 
16        game_board.print(); 
17
18        // then, indicate who's playing and ask for a move.
19        char marker; 
20        if(i % 2 == 1) {    // X on odd, O on even. 
21            marker = 'X'; 
22        } else {
23            marker = 'O'; 
24        } 
25
26        cout << "It's player " << marker << "'s turn!" << endl; 
27        cout << "Which row? "; 
28        int row; cin >> row; 
29        cout << "Which column? "; 
30        int col; cin >> col; 
31
32        // play the user's move 
33        game_board.play_move(marker, row, col); 
34
35        // if there's a winner, print it out 
36        // and exit the program! 
37        if(game_board.has_winner()) { 
38            cout << "Player " << marker << " wins!" << endl; 
39            return 0; 
40        } 
41    } 
42
43    // 3. if we exited the for loop, then all 9 moves 
44    // have been made... it's a draw. 
45    cout << "It's a draw!" << endl; 
46    return 0; 
47}

This code compiles, which is great! But of course it doesn’t work at all: we end up entering 18 numbers with no real meaning, and we don’t see the board at all. Let’s first write our constructor. We won’t be able to make any of the other member functions of the Board class work if the underlying vector<string> is empty. In an empty board, we just need to make 3 copies of strings " " (three spaces).

1Board::Board() {
2    for(int i = 0; i < 3; i++) {
3        //               123 spaces
4        board.push_back("   "); 
5    } 
6}

For good measure, we should build and run the code to make sure nothing breaks. This way, we’ll know exactly where any errors or bugs are, and we won’t have to go back through and hunt for them later.

Next, let’s print out a nice-looking board for the players to look at. I want the board to look something like this:

O| |O
-+-+- 
 |X|X
-+-+- 
X|O|

Of course, we won’t have any O’s or X’s to look at, but you get the idea. Every row should alternate between a character in the string and a vertical bar. In between each row, I want a separator -+-+-. Thus, we may construct the following code:

 1void Board::print() {
 2    // for every row, repeat: 
 3    //      for every character in the row's string, repeat: 
 4    //          print the character, followed by a | 
 5    //      print -+-+-, except for the last row. 
 6    for(int i = 0; i < 3; i++) {
 7        string row = board.at(i); 
 8        cout << row.at(0) << '|' 
 9             << row.at(1) << '|' 
10             << row.at(2) << endl; 
11
12        if(i != 2) {
13            cout << "-+-+-" << endl; 
14        } 
15    } 
16}

Building and running this again, we’re now seeing an (empty) board every time we try to make a move. Our moves aren’t doing anything yet, so let’s implement our play_move function. This isn’t too hard: get the provided row and the provided column, then replace the corresponding character with an O or an X.

1void Board::play_move(char marker, int row, int col) {
2    board.at(row - 1).at(col - 1) = marker; 
3}

Two things to note: first and foremost, one may be tempted to simplify this code by writing

1void Board::play_move(char marker, int row, int col) {
2    string s = board.at(row - 1); 
3    s.at(col - 1) = marker; 
4}

However, this makes s a copy of the row in the board — changes to s don’t affect the actual rows of the board.

Second, notice that I’ve had to subtract 1, i.e. I’m using row - 1 and col - 1. This is because when we play tic-tac-toe, it’s more natural to say “row 1, column 3” over “row 0, column 2”, at least for most people. Without this, we’re likely to run into indexing issues! (One could also make this numbering clear when printing out the board.)

Now we’re in business! Whenever we play a move, it shows up on the board when it’s the next player’s turn!

Our last job is to figure out how to detect a winner. This can be done with brute force: check if the two diagonals are all the same character, if the three rows are all the same character, and if three columns are the same character. If any of these are true, then we have a winner.

Think about how you should write this code. We could have 8 really fat if statements lying around, but with a few loops and a few extra variables, this becomes much more manageable.

 1bool Board::has_winner() {
 2    // check the diagonals! 
 3    // middle character of middle row. 
 4    char middle = board.at(1).at(1); 
 5    if(middle != ' ') { // if the middle is empty, no diagonals. 
 6        if(board.at(0).at(0) == middle && 
 7                board.at(2).at(2) == middle) { 
 8            return true; 
 9        } 
10
11        if(board.at(0).at(2) == middle && 
12                board.at(2).at(0) == middle) {
13            return true; 
14        } 
15    } 
16
17    // check each row. 
18    for(int row = 0; row < 3; row++) {
19        string s = board.at(row); 
20        char c = s.at(0); 
21        if(c != ' ' && c == s.at(1) && c == s.at(2)) { 
22            return true; 
23        } 
24    } 
25
26    // check each column. 
27    for(int col = 0; col < 3; col++) {
28        char c = board.at(0).at(col); 
29        if(c != ' ' && c == board.at(1).at(col) && 
30                c == board.at(2).at(col)) {
31            return true; 
32        } 
33    } 
34
35    // after checking all the above cases, we know there's 
36    // no winner! 
37    return false; 
38}

That was a little bit rough, but it’s ultimately pretty straightforward logic. Check the eight lines one at a time. Now our game is fully functional!

Except for a few things.

  1. If the player is nasty and picks a row and column that already have markers in them, it overwrites the previous player’s move.
  2. If the player is a moron and enters a row or column that’s not between 1 and 3, the program crashes from an index out of bounds error.
  3. If the player smashes their keyboard in frustration and enters a non-numeric character, the program gets stuck because cin never moves past the faulty input.

These three issues are issues of input validation. To address the first issue, we need a way to check if a square on the board has already been filled up. That should be another member function! For the others, we should wrap the user’s input in a while loop and repeatedly ask for a move until the user complies. This would be a lot to put in the main function, so maybe it’s a good idea to write a separate function altogether that just handles playing a single move.

Finally, what if our players want to play a match, best 3 out of 5, alternating who goes first? What if our players are snazzy and want to use markers that aren’t O’s or X’s? What if they don’t want to stop playing? What if a lonely guy wants to play against a computer?

Although we have put together a functional core for our game of tic-tac-toe, there are still a lot of ways that we can extend our program’s functionality. Perhaps I’ll continue with this next week…

But for today, there’s one thing I’d like to emphasise: the process of incremental programming. We didn’t try to fill out our program all in one go. We started by writing an outline of how tic-tac-toe works at a very broad level, then broke our program into modular chunks that we could write out independently of one another. We then filled them in one by one, starting with a skeleton, then a main function, then each piece of the skeleton, until everything was completed.