Hunter Liu's Website

18. Week 9 Thursday: Connect Four

≪ 17. Week 9 Tuesday: Pointers | Table of Contents

Last week, we coded a somewhat functional game of tic tac toe from scratch. This time, let’s create a slightly more sophisticated game: Connect Four. Hopefully this is something you’ve played before; I’m anticipating that this will take more than one discussion to complete.

Let’s begin with the basics and write out a somewhat detailed outline of how the game proceeds. The gameplay loop is fundamentally very similar to that of Tic-Tac-Toe:

  1. Initialise an empty \(6\times 7\) grid for the game.
  2. While the board is not full, alternate turns between players:
    • Display the current state of the game.
    • Ask the current player (X or O, since I’m unoriginal) which column they would like to play a move in.
    • Drop an X or an O into the lowest empty slot on the given column.
    • Check if someone has connected four tokens in a row. If yes, end the game.
  3. If the board fills up and there’s no winner, it’s a draw.

Just like in Tic-Tac-Toe, there’s a single noun performing complex actions throughout the program: the game board. This board needs to be able to:

This board also needs to remember the \(6\times 7\) grid of empty or nonempty pieces that have already been played.

It is here that we are presented with a design choice: what’s a good way to store the board in a variable? We have several choices:

There are some other options, but I think these are the three that come to mind first. Maybe using a single string of 42 characters is not a great idea, so let’s consider the remaining two choices.

Creating a separate string for each row is natural to most of us, as our written language is arranged in the same way. This has the benefit of making the “display” function relatively straightforward to implement, especially if we design the display of the board in a compatible way. However, adding pieces to the board will take a bit of thought.

On the other hand, creating one string per column makes adding pieces to the board much easier, especially if we don’t include the spaces! All we’d have to do is push_back an X or an O onto the top of any given column and we’d be happy. However, printing out the board will be somewhat challenging, since we’d have to go across every single column and worry about which pieces are there and which ones aren’t.

In either case, determining if there’s a winner or not is challenging. When we store the rows, we can go across without any trouble, but dealing with indices going up and down might be tough. Likewise, if we store the columns, going up and down may not be hard, but going across will be tricky. (Invariably, the diagonals will be quite tricky.)

Here’s an idea: why not do it both ways? We’ll store two copies of the board: one which remembers the rows in its full glory, which will make printing and checking for horizontal Connect Fours easy, and another that remembers the columns sans spaces, which will make adding pieces to the board and checking for vertical Connect Fours easy. I don’t think there’s a good way around checking the diagonal Connect Fours, but such is life.

As before, let’s write our header file for the Board class first, which will represent the game board.

Board.hpp 
 1#ifndef BOARD_HPP 
 2#define BOARD_HPP 
 3
 4#include <string> 
 5
 6using namespace std; 
 7
 8class Board {
 9public: 
10    /** 
11     * Creates a new empty Connect Four board. 
12     */ 
13    Board(); 
14
15    /** 
16     * Prints out the current contents of the Connect Four board 
17     * to the screen. 
18     */ 
19    void print_board(); 
20
21    /** 
22     * Determines whether or not the board is full. 
23     */ 
24    bool is_full(); 
25
26    /** 
27     * Places the provided marker at the bottom of the specified 
28     * column of the board. 
29     */ 
30    void place_marker(char marker, int column); 
31
32    /** 
33     * Determines if the given marker has a connect four or not. 
34     */ 
35    bool has_won(char marker); 
36
37private: 
38    // 6 rows and 7 columns! 
39    string rows[6]; 
40    string columns[7]; 
41
42}; 
43
44#endif

Note that I’ve decided to pass in the parameter marker into the has_won function to eventually make our lives a little bit easier. Let’s fill out the skeleton of the implementation file now.

Board.cpp 
 1#include "Board.hpp" 
 2
 3Board::Board() {
 4    // TODO 
 5} 
 6
 7void Board::print_board() {
 8    // TODO 
 9} 
10
11bool Board::is_full() {
12    // TODO 
13    return false; 
14} 
15
16void Board::place_marker(char marker, int column) {
17    // TODO 
18} 
19
20bool Board::has_won(char marker) {
21    // TODO 
22    return false; 
23}

Finally, let’s create the main program without filling in any of these functions just yet.

 1#include <iostream> 
 2#include "Board.hpp" 
 3
 4using namespace std; 
 5
 6int main() {
 7    cout << "Welcome to Connect Four!" << endl; 
 8
 9    // create an empty board 
10    Board board; 
11
12    // while the board is not full, play moves, starting with X. 
13    char curr_player = 'X'; 
14    while(!board.is_full()) {
15        // display the board 
16        board.print_board(); 
17
18        // ask the player for a column
19        cout << "It's player " << curr_player 
20             << "'s turn." << endl; 
21        cout << "Enter a column: "; 
22        int column; cin >> column; 
23
24        // play the current player's marker on the board. 
25        board.place_marker(curr_player, column); 
26
27        // check for a win. 
28        if(board.has_won(curr_player)) {
29            cout << "Player " << curr_player 
30                 << " wins!" << endl; 
31            return 0; 
32        } 
33
34        // swap the marker! 
35        if(curr_player == 'X') { 
36            curr_player = 'O'; 
37        } else { 
38            curr_player = 'X'; 
39        } 
40    } // end of big while loop. 
41
42    // if we're out here, it's a draw. 
43    cout << "It's a draw...." << endl; 
44    return 0; 
45}

Just like with Tic-Tac-Toe, we’ve produced a skeleton of code that compiles with no problems, but is missing all of its functionality. We should therefore begin filling in the pieces of the Board class, one at a time, until the program is fully functional.

The Constructor and RAII Again

We’ve been saying to use initialisation lists whenever possible, but what happens to these array member variables, and what should we put in the initialisation list? What happens if we don’t put anything at all?

On one hand, arrays are glorified pointers in C++, and we know that unitialised pointers are complete garbage. But arrays are an exception! Here, string rows[6]; for instance asks C++ to set aside a contiguous block of 6 string variables back-to-back. This memory is allocated for the program, and since resource acquisition is initialisation, all six strings are initialised automatically to empty strings. A similar story happens for string columns[7];. In particular, we don’t really need to worry about initialisation lists in this case — C++ has it taken care of by default.

It makes sense to leave all the columns empty, but I want to have 6 rows full of spaces. Remember, the columns only remember the non-space characters at the bottom of the board while the rows remember everything. Thus, the constructor comes out as:

1Board::Board() {
2    // set all 6 rows equal to seven spaces. 
3    for(int i = 0; i < 6; i++) {
4        //         1234567
5        rows[i] = "       "; 
6    } 
7}

(The code should continue to compile here.)

Display and Placing Markers

Setting up the board properly is completely invisible to the main program. Our Connect Four is just as shabby as before, so let’s add in the display itself. I’m going to aim for a display that looks like the following:

+-------+
|       |
|       |
| O     |
| XX    |
|XOOXO  |
|OXOOXXO|
+-------+
 1234567

I’ve labelled the columns at the bottom here so that the user can easily tell which column is which. Let’s implement this in the print_board function. I need to first print out the top “wall”, then print out the contents of the board, followed by the bottom “wall” and the column labels.

 1void Board::print_board() {
 2    // top wall 
 3    cout << "+-------+" << endl; 
 4
 5    // all the actual rows. 
 6    for(int i = 0; i < 6; i++) {
 7        cout << "|" << rows[i] << "|" << endl; 
 8    } 
 9
10    // bottom wall and column labels 
11    cout << "+-------+" << endl; 
12    cout << " 1234567 " << endl; 
13}

Beautiful! Now our game prints out an empty board at the end of each turn. Let’s now incorporate our first actual interactive component: updating the board when the user makes a move. All I have to do is push_back the provided marker onto the string in the provided column.

1void Board::place_marker(char marker, int column) {
2    columns[column].push_back(marker); 
3}

This code, though in perfect correspondence with what I just said, does not work. First and foremost, we can’t see any changes, and that’s because the rows and columns are two separate copies of the board. I need to adjust the corresponding character in the corresponding row too. Second, there’s an off-by-one error: column to humans starts at 1, but the computer indexes the array starting at 0.

In fact, running this code now and playing something in column 7 creates a cryptic error — this is your operating system stepping in and killing your program rather than the C++ program itself catching itself before a mistake.

1void Board::place_marker(char marker, int column) {
2    // the row is the height of the current column. 
3    int row = columns[column - 1].length(); 
4    rows[row].at(column - 1) = marker; 
5
6    columns[column - 1].push_back(marker); 
7}

Now we’ve got some actual gameplay happening!

I don’t expect us to get any farther than this during our discussion, so I’ll save the remaining things for next time (: