Hunter Liu's Website

19. Week 10 Tuesday: Connect Four, Continued

Last week, we began coding our game of Connect Four. Recall that we had written up a main program alongside a skeleton for the Board class, very similar to what we had done for Tic-Tac-Toe. We then began filling in the member functions for this class one at a time; we finished the constructor, the print_board function, and the place_marker function. We need only complete the is_full function and the has_won function.

Let’s start with the is_full function, since that’s the more straightfoward of the two. We need to determine if the board is full or not, and there are two ways to do this: either we can scan the topmost row of the board and see if there are any spaces, or we can check the number of pieces in each column of the board and see if they match the number of rows. I’ll implement it two ways here just for fun:

1bool Board::is_full() {
2    // searches for a space in the top row of the board. 
3    size_t index = rows[0].find(" "); 
4
5    // check if index is -1. If yes, then there are no spaces, 
6    // and so the board is full; otherwise, there is one space,
7    // so the board is not full. 
8    return index == -1; 
9} 

 1bool Board::is_full() {
 2    // check every column. If the length of the column 
 3    // (as a string) is exactly 6, then we've filled up every 
 4    // slot in the column. But if it isn't, then there's still 
 5    // room for more, and we know the board isn't full. 
 6    for(int i = 0; i < 7; i++) {
 7        if(columns[i].length() < 6) {
 8            return false; 
 9        } 
10    } 
11
12    return true; 
13} 

This now ensures that the game will end after every spot on the board is filled up. You can test this if you want, but this is somewhat difficult and annoying since it takes 42 turns to fill up the board. But now the only way for the game to end is for a draw to occur, even if one or both players form four in a row.

It now remains to determine whether or not there’s a winner.

Recall that I made the prescient decision to add a char parameter to the has_won member function. This makes it so that we don’t have to check four-in-a-rows of multiple different characters in the same function. Wheras in Tic-Tac-Toe, we could brute force these conditions (there weren’t too many), we should be a little bit more clever this time around.

We can leverage the find function from string to identify four copies of the same character. Our pseudocode is as follows:

1. Given the parameter marker, create a string target consisting of four marker’s in a row (i.e. “OOOO” or “XXXX”).
2. For each row on the board:
   • Use the find function in the string library to search for target within the given row.
   • If there’s a match, return true.
3. For each column on the board, do the same thing as in step 2.
4. Somehow ??? handle the diagonals.

Let’s push off the diagonal connect-fours until later and first get the horizontal and vertical connect-fours working.

 1bool Board::has_won(char marker) {
 2    // four markers 
 3    string target; 
 4    for(int i = 0; i < 4; i++) {
 5        target.push_back(marker); 
 6    } 
 7
 8    // check every row for 
 9    for(int i = 0; i < 6; i++) {
10        if(rows[i].find(target) != -1) {
11            return true; 
12        } 
13    } 
14
15    // and checking every column 
16    for(int i = 0; i < 7; i++) {
17        if(columns[i].find(target) != -1) {
18            return true; 
19        } 
20    } 
21
22    // if we didn't find a connect four, this player did not win. 
23    return false; 
24} 

Test this thoroughly and make sure that it works for both players! This is considerably less tedious than checking that the is_full function works by hand.

Now we’re faced with the very last part of making Connect Four work according to the rules: joining four of the same markers diagonally. Let’s start with the diagonals that go down and to the right. One such diagonal is marked below with asterisks; row and column indices are marked.

    +-------+
    |*      |0
    | *     |1
    |  *    |2
    |   *   |3
    |    *  |4
    |     * |5
    +-------+
     0123456

We should copy these characters into a string, then use the find function to determine if it contains the target. In fact, the “first” and “last” diagonals we need to check are marked below:

    +-------+
    |   *   |0
    |    *  |1
    |*    * |2
    | *    *|3
    |  *    |4
    |   *   |5
    +-------+
     0123456

The first diagonal starts at row 2, column 0, then makes its way down to row 5 and column 3. The last diagonal starts at row 0 and column 3, then makes its way down to row 3 and column 6. In fact, we can write the following pseudocode to describe how to check each down-and-right diagonal:

1. Initialise start_row = 2 and start_col = 0.
2. While start_col <= 3:
   • Initialise an empty string diagonal.
   • Initialise row to start_row and col to start_col.
   • While row < 6 and col < 7, repeat:
     • push_back the character at row and col to diagonal.
     • Increment both row and col by one.
   • If diagonal contains the string target, we found a winner!
   • If row > 0, decrement start_row. Otherwise, increment start_col.

Think carefully about what this code is doing. It begins with (row, col) = (2, 0). It marches this down the lowest diagonal, appending characters from the board to the string diagonal, including (3, 1), then (4, 2), and finally (5, 3). It then checks if this diagonal contains the target string, then moves on to the next diagonal.

In code, this looks like:

 1int start_row = 2, start_col = 0; 
 2while(start_col <= 3) {
 3    string diagonal; 
 4    int row = start_row, col = start_col; 
 5    while(row < 6 && col < 7) { 
 6        diagonal.push_back(rows[row].at(col)); 
 7        row++; col++; 
 8    }
 9
10    if(diagonal.find(target) != -1) {
11        return true; 
12    } 
13
14    if(start_row > 0) {
15        start_row--; 
16    } else {
17        start_col++; 
18    } 
19} 

This should go between the two for loops in the function has_won but before the final return statement.

Input Validation

Now supposedly all the game logic is in place! You should carefully test your code by playing several games of Connect Four and making sure the game ends when it’s supposed to.

Unfortunately, our game completely fails when the player inputs invalid moves. Maybe they play a move in a column that’s already full. Maybe they play a move in a column that doesn’t exist. Worst of all, maybe they play a move in a column that’s not a number. The first causes a logical error — although our game doesn’t crash, its logic falls apart due to the funky game state that we’re not expecting or accounting for. The third also causes a logical error — the game doesn’t crash, but it’s caught in an infinite loop because the cin input buffer has a non-numeric character that never gets flushed out. The second is a runtime error, as it causes our program to access an invalid array index!

To fix these, we need to implement input validation. Rather than just assuming the user will provide valid input, we need to check the state of the cin buffer and avoid making moves in non-existent or full columns.

Currently, we have the following code to ask for a move:

1// ask the player for a column
2cout << "It's player " << curr_player 
3     << "'s turn." << endl; 
4cout << "Enter a column: "; 
5int column; cin >> column; 

Let’s wrap the cin statement in a while loop and begin by addressing the worst scenario: when the user fails to input an integer. We should check if cin.fail() is true. If it is, we should print a warning and ignore everything in the input buffer up to the next newline character:

 1cout << "It's player " << curr_player 
 2     << "'s turn." << endl; 
 3int column; 
 4while(true) {
 5    cout << "Enter a column: "; 
 6    cin >> column; 
 7
 8    if(cin.fail()) {
 9        cout << "That's not a valid number." << endl; 
10        cin.clear();             // resets cin.fail() 
11        cin.ignore(10000, '\n'); // ignores next \n 
12    } else {
13        break;
14    } 
15} 

Note that I used a while(true). This will continue indefinitely. I want to say “while the user has not entered valid input”, but I don’t know how to express this as a boolean value. There are some clever ways around this, but this is a natural method for me since we can group all of our validation checks together.

The break statement says that as long as the user enters an integer (hence column will contain a value), we should exit the loop and move on with the game loop. However, there is a slight issue: if the user enters 1a, then the 1 is read just fine and cin.fail() is false, yet when the next player comes to play a move, it notifies them that they’ve entered an invalid number! The fix is to clear out the input buffer immediately after cin >> column.

 1cout << "It's player " << curr_player 
 2     << "'s turn." << endl; 
 3int column; 
 4while(true) {
 5    cout << "Enter a column: "; 
 6    cin >> column; 
 7    cin.ignore(10000, '\n'); // ignores next \n 
 8
 9    if(cin.fail()) {
10        cout << "That's not a valid number." << endl; 
11        cin.clear();             // resets cin.fail() 
12    } else {
13        break;
14    } 
15} 

Let’s now add a way to check that the user’s input is a valid column. This ought to be a new member function in the Board class. Under the public section in the hpp file, let’s add a function declaration as follows:

1/** 
2 * Determines whether or not a move can be played in the given 
3 * column. Returns false if the column is either out of bounds or 
4 * is full of pieces already. 
5 */ 
6bool valid_column(int column); 

The implementation can be done in one line, if you delete the comments:

1bool Board::valid_column(int column) {
2    // valid index in our array 
3    return column > 0 && column <= 7 && 
4
5    // the column isn't full of pieces already. 
6           columns[column - 1].length() < 6; 
7} 

Our input validation loop can now be written as:

 1cout << "It's player " << curr_player 
 2     << "'s turn." << endl; 
 3int column; 
 4while(true) {
 5    cout << "Enter a column: "; 
 6    cin >> column; 
 7    cin.ignore(10000, '\n'); // ignores next \n 
 8
 9    if(cin.fail()) {
10        cout << "That's not a valid number." << endl; 
11        cin.clear(); // resets cin.fail() 
12    } else if(!board.valid_column(column)) {
13        cout << "That's not a legal move." << endl; 
14    } else {
15        break;
16    } 
17} 

At the end of this fat while loop, column should contain a valid number input by the user, and we’re no longer allowed to enter columns that don’t exist or are full of pieces! I think our Connect Four game should finally be fully functional.