Project: Tic-Tac-Toe

This module has no new statement to learn. It has one program to build: a game of Tic-Tac-Toe that two people can play by clicking, and then a computer that plays against you.

Almost everything in it comes from earlier modules. Module 13 gave you the board. Module 11 gave you the loop that searches. Module 7 gave you the habit of testing a function before trusting it. Two things are new: a type for an answer that may not exist, and a way for the lab to call your function when the picture is clicked. The rest of the lesson is about how to arrange what you already know.

A game is a few small functions

A game looks like one big thing. Written as one big main it would be a hundred lines that nobody could test. So the first step is not to write code. It is to ask what questions the program has to answer, and to give each question a function.

Decomposition is the name for this: splitting a program into functions that each answer one question, or do one job. For Tic-Tac-Toe the list is short.

Every one of them takes the state of the game, or a part of it, as a parameter. Module 13 ended with a struct that holds this state, and this module uses it unchanged. The program below is that model, with one small function added that answers one small question: what does this board look like as text?

#include <iostream>
#include <string>
#include <vector>

enum class Mark { Empty, X, O };

struct Board {
    std::vector<Mark> cells;
    Mark turn;
};

Board new_board() {
    Board board{};
    for (int i = 0; i < 9; ++i) {
        board.cells.push_back(Mark::Empty);
    }
    board.turn = Mark::X;
    return board;
}

bool place(Board& board, int position) {
    if (position < 0 || position > 8) {
        return false;
    }
    if (board.cells[position] != Mark::Empty) {
        return false;
    }
    board.cells[position] = board.turn;
    if (board.turn == Mark::X) {
        board.turn = Mark::O;
    } else {
        board.turn = Mark::X;
    }
    return true;
}

std::string mark_text(Mark mark) {
    switch (mark) {
        case Mark::X:
            return "X";
        case Mark::O:
            return "O";
        case Mark::Empty:
            return ".";
    }
    return "?";
}

void print_board(const Board& board) {
    for (int i = 0; i < 9; ++i) {
        std::cout << mark_text(board.cells[i]);
        if (i % 3 == 2) {
            std::cout << "\n";
        }
    }
}

int main() {
    Board board = new_board();
    place(board, 4);
    place(board, 0);
    place(board, 8);
    print_board(board);
    std::cout << "Next: " << mark_text(board.turn) << "\n";
}

O..
.X.
..X
Next: O

The nine cells are numbered 0 to 8, row by row.

0 1 2
3 4 5
6 7 8

place is the function from module 13. It refuses a position outside 0 to 8 and a cell that is taken. Otherwise it puts the mark whose turn it is into the cell and passes the turn to the other mark.

mark_text is the name function of module 13: a Mark cannot be printed, so a function turns it into text. print_board goes over the nine positions and ends the line after positions 2, 5 and 8, which are the ones where i % 3 is 2.

Notice what the first lines of the functions say. place takes a Board&, because its job is to change the caller's board. print_board takes a const Board&, because it only looks. A reader can tell which functions are able to change the game without reading a single body. In the whole project only one function will take a Board&.

Small functions have a second advantage. Each one can be given a board built by hand and its answer compared with the answer you expect. A function that answers one question has one kind of test.

A value, or nothing

Some questions do not always have an answer. "Which mark has won?" has none while the game is still going. "Which cell was clicked?" has none when the click was beside the board.

Module 11 met this problem in searching, and solved it with a special number: a search returned a position, or -1 for "not found". That works for positions, because -1 is never a position. It does not work when every number is a possible answer.

The library has a type for exactly this. A std::optional<int> holds an int, or nothing. It comes from the header <optional>.

#include <iostream>
#include <optional>
#include <vector>

// Returns: the first temperature lower than limit, or nothing if there is none.
std::optional<int> first_below(const std::vector<int>& temps, int limit) {
    for (int t : temps) {
        if (t < limit) {
            return t;
        }
    }
    return std::nullopt;
}

int main() {
    std::vector<int> week = {4, 2, -1, 3, -6};

    std::optional<int> frost = first_below(week, 0);
    if (frost) {
        std::cout << "First frost: " << *frost << " degrees\n";
        std::cout << "Five degrees warmer: " << *frost + 5 << "\n";
    } else {
        std::cout << "No frost\n";
    }

    std::optional<int> hard_frost = first_below(week, -10);
    if (hard_frost) {
        std::cout << "First hard frost: " << *hard_frost << " degrees\n";
    } else {
        std::cout << "No hard frost\n";
    }
}

First frost: -1 degrees
Five degrees warmer: 4
No hard frost

There are four things to learn, and the program uses each of them.

The first answer in this program is -1. A function that returned -1 for "nothing found" could not have told you so: the caller would not know whether -1 was a temperature or a failure. With std::optional the two cases cannot be mixed up, because "nothing" is not one of the numbers.

Three rules go with it.

• An optional is not the value. frost + 5 does not compile, and neither does int t = frost;. You have to write *frost, and that makes you think about whether there is a value at all.
• Write *frost only where you know there is a value, which in practice means inside if (frost) { ... }. Reading the value of an optional that holds nothing is not defined, like reading outside a vector with []. The compiler does not stop you.
• if (frost) asks whether there is a value. It is still true when the value is 0, and when the value is false.

The type in the angle brackets can be any type, as for a vector. This project uses std::optional<Mark> for "the mark that has won, or nothing" and std::optional<int> for "the cell at this point, or nothing".

Winning lines as data

A player wins by holding all three cells of a line. There are eight lines: three rows, three columns and two diagonals.

One way to look for a winner is eight if statements, each naming three cells. That is twenty-four positions typed into conditions, and one wrong digit among them makes a game that misses one win. Nobody would see it by reading.

The other way is to notice that the eight tests are the same test with different numbers. Then the numbers can be data, and the test can be written once. The eight lines fit in a grid of positions, as in module 11: eight rows, and each row holds the three positions of one line.

#include <iostream>
#include <vector>

const std::vector<std::vector<int>> win_lines = {
    {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
    {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
    {0, 4, 8}, {2, 4, 6}
};

// Needs: position is from 0 to 8.
// Returns: how many of the eight lines pass through that cell.
int lines_through(int position) {
    int total = 0;
    for (const std::vector<int>& line : win_lines) {
        for (int p : line) {
            if (p == position) {
                ++total;
            }
        }
    }
    return total;
}

int main() {
    std::cout << "Lines: " << win_lines.size() << "\n";
    std::cout << "Through the centre: " << lines_through(4) << "\n";
    std::cout << "Through a corner: " << lines_through(0) << "\n";
    std::cout << "Through an edge: " << lines_through(1) << "\n";
}

Lines: 8
Through the centre: 4
Through a corner: 3
Through an edge: 2

win_lines is declared outside every function, so it is a global variable. Module 6 said that those are avoided, and gave the reason: any line anywhere in the program may be the one that changed it. That reason does not apply here. The variable is const, so no line can change it. A const table that several functions read is the ordinary way to keep a program's fixed data.

Read the table against the numbered board. The first row of the table is the three rows of the board, the second is the three columns, and the third is the two diagonals. A table like this can be checked by eye in a few seconds, which eight conditions cannot.

for (const std::vector<int>& line : win_lines) visits the eight lines in turn. Each line is a vector of three positions, so line[0], line[1] and line[2] are the positions of its cells. lines_through uses them to answer a question about the board's shape. The centre lies on four lines, a corner on three and an edge on two, which is why players like the centre.

A function that looks for a winner has the same outer loop. For each line it asks about the three cells of the board at those three positions: board.cells[line[0]] and its two neighbours. You will write that function in the lab. One warning now: on an empty board, the three cells of every line are equal to each other.

How does the game stand?

Many programs have to say how far along something is: running, finished well, finished badly. The possibilities are a short fixed list, so an enum class holds them. The function that works out the answer asks a few questions about the state, and the order of the questions matters.

A quiz has five questions, and three right answers pass it.

#include <iostream>
#include <string>

struct Quiz {
    int asked = 0;
    int right = 0;
};

enum class Progress { Running, Passed, Failed };

Progress progress_of(const Quiz& quiz) {
    if (quiz.right >= 3) {
        return Progress::Passed;
    }
    if (quiz.asked == 5) {
        return Progress::Failed;
    }
    return Progress::Running;
}

std::string progress_name(Progress progress) {
    switch (progress) {
        case Progress::Running:
            return "running";
        case Progress::Passed:
            return "passed";
        case Progress::Failed:
            return "failed";
    }
    return "unknown";
}

int main() {
    std::cout << progress_name(progress_of(Quiz{2, 1})) << "\n";
    std::cout << progress_name(progress_of(Quiz{4, 3})) << "\n";
    std::cout << progress_name(progress_of(Quiz{5, 2})) << "\n";
    std::cout << progress_name(progress_of(Quiz{5, 3})) << "\n";
}

running
passed
failed
passed

Look at the last quiz: five questions asked, three right. Both if conditions are true for it. The quiz is over, and it is passed. The function gives the right answer because it asks about passing first. With the two if statements exchanged, a learner whose third right answer came on the last question would be told they had failed.

The rule is general. When two conditions can be true together, decide which one wins, and test that one first. return then leaves the function, and the later questions are asked only when the earlier answers were no.

Tic-Tac-Toe has the same trap. A game is drawn when the board is full and nobody has won. But the ninth mark can be the one that completes a line, and then the board is full and there is a winner. So the function that reports the status of a game asks its questions in this order: is there a winner? If not, is there an empty cell? If not, it is a draw.

Notice also that Progress is not stored in the Quiz. It is worked out from the two numbers whenever somebody asks. A stored copy could disagree with the numbers after one forgotten update. A value that is worked out cannot.

A function the lab calls

Every function so far ran because your program called it. A program that reacts to clicks needs the opposite: the program cannot know when a click will come, so the lab has to call a function of yours when it does.

on_click arranges that. You give it the name of a function, and the lab calls that function for every click on the picture, with the x and y of the click.

#include "scimigo.h"
#include <string>
using namespace scimigo;

int clicks = 0;

void number_the_click(int x, int y) {
    ++clicks;
    circle(x, y, 16, "gold");
    text(x - 6, y + 7, std::to_string(clicks), 20);
}

int main() {
    canvas(600, 400);
    rectangle(0, 0, 600, 400, "skyblue");
    text(20, 30, "Click anywhere", 20);
    on_click(number_the_click);
}

Run this in the lab and click the picture a few times. Each click gets a gold disc with a number: 1, 2, 3.

number_the_click is a click handler: a function that is written to be called when a click happens. It must have this shape: it returns nothing, and it takes two ints. The lab fills them in with the position of the click, in the coordinates of module 1. You choose the name.

on_click(number_the_click); hands the function to the lab. Notice that there are no parentheses after number_the_click. With parentheses it would be a call. Without them it is only the function's name, and on_click remembers it. Nothing in this program calls number_the_click. The lab does.

Here is what happens, in order.

1. main runs to its end: the background, the line of text, and on_click.
2. The program waits.
3. You click. The lab calls number_the_click with the position of the click.
4. The program waits again.

The handler needs to know how many clicks came before, and it has nowhere to get that from. Its parameters are fixed: an x and a y, and the lab supplies both. Its local variables are made new on every call, as module 6 showed, so a local counter would be 1 every time. The count has to live in a variable that outlasts the call, and that is a variable declared outside the functions: int clicks = 0;.

This is the one place in this course where a global variable that changes is the right tool. The handler cannot be given the state as a parameter, because you are not the one who calls it. Keep the habit of module 6 everywhere else. In this project there will be exactly one such variable, and only the handler will name it. Every other function gets what it needs through its parameters.

One detail about the lab, in case you look closely. It does not keep your program running between clicks. On every click it runs the program again from the start, and then calls the handler once for each click so far, in order. The result is the same as if the program had been waiting: after the third click, the handler has been called three times and clicks is 3. You can write your program as if steps 1 to 4 above were the whole story. It does mean that anything main prints is printed again on each click.

State first, picture second

The last program drew straight from the handler. That only works for a picture that never has to change. In a game, a click may have to change something that is already on the screen, or be refused, or end the game. The handler cannot decide any of that by looking at the picture. It can only decide it from the state.

So a program that reacts to events is arranged in two halves that are kept apart.

1. An event changes the state, and nothing else.
2. The picture is drawn again, all of it, from the state.

#include "scimigo.h"
#include <string>
#include <vector>
using namespace scimigo;

void draw(const std::vector<int>& taps) {
    canvas(600, 400);
    int total = 0;
    int n = taps.size();
    for (int i = 0; i < n; ++i) {
        rectangle(100 + i * 100, 150, 96, 96, "gold");
        text(135 + i * 100, 212, std::to_string(taps[i]), 36);
        total += taps[i];
    }
    text(100, 300, "Total: " + std::to_string(total), 24);
}

std::vector<int> counters = {0, 0, 0, 0};

void handle_click(int x, int y) {
    if (x >= 100 && x < 500 && y >= 150 && y < 250) {
        int box = (x - 100) / 100;
        ++counters[box];
    }
    draw(counters);
}

int main() {
    draw(counters);
    on_click(handle_click);
}

Four boxes each show a number, and a click on a box adds one to its number. A line below shows the total.

The state is counters, four ints. handle_click does the first half. It works out which box was clicked and adds one to that element. It draws nothing itself. Then it calls draw.

draw does the second half. It starts with canvas(600, 400). Calling canvas again clears the picture, so every call of draw starts from an empty picture and draws the four boxes, the four numbers and the total from the vector it was given. It does not know that a click happened, or which box changed.

This arrangement has three consequences.

• The picture cannot disagree with the state. There is no old number to erase and no way to forget to update the total. Whatever the vector holds is what is shown.
• The state can answer questions. The total is worked out from the vector. A program that only drew numbers on the screen would have nothing to add up. In the game, "is this cell taken?" and "has somebody won?" are questions of this kind.
• draw can be tested without clicking. It takes the state as a parameter, so it can be called with any vector. Only handle_click names the global variable.

The handler also shows how a click becomes a position in the state. The boxes start at x 100 and each is 100 wide, so (x - 100) / 100 is 0 for the first box, 1 for the second, and so on. The if before it matters. A click at x 40 is to the left of every box, and (40 - 100) / 100 is -60 / 100, which is 0 in int division. Without the if, that click would count for the first box.

Trying a move on a copy

A computer opponent has to think ahead by one move: if I put my mark here, have I won? To answer, it must put the mark there and look. But it must not put it on the real board, because it is only asking.

The answer is a copy. Module 6 said that a parameter passed by value is a copy that the function may change freely, and module 10 said to pass vectors by const reference to avoid that copy. Here the copy is the point.

#include <algorithm>
#include <iostream>
#include <vector>

// Needs: scores has at least two elements.
// Returns: the total of the best three scores if extra were added.
int best_three_with(std::vector<int> scores, int extra) {
    scores.push_back(extra);
    std::sort(scores.begin(), scores.end());
    int n = scores.size();
    return scores[n - 1] + scores[n - 2] + scores[n - 3];
}

int main() {
    std::vector<int> scores = {55, 80, 62, 71};
    std::cout << "With a 90: " << best_three_with(scores, 90) << "\n";
    std::cout << "With a 40: " << best_three_with(scores, 40) << "\n";
    std::cout << scores.size() << " scores, and the first is still " << scores[0] << "\n";
}

With a 90: 241
With a 40: 213
4 scores, and the first is still 55

best_three_with answers a "what if" question. It adds the extra score, sorts, and adds up the last three. All of that happens to its own copy, because the parameter is std::vector<int> scores with no &. The last line of output shows that the caller's vector still has four elements, in their old order. Each call starts from a fresh copy, so the 90 of the first call is not there during the second.

A struct is copied in the same way, with every member, including a vector inside it. A function with the parameter Board board can place a mark on its board and ask who has won, and the game's real board never changes.

When a copy is needed in the middle of a function, an ordinary declaration makes one.

std::vector<int> trial = scores;   // a copy; changing trial leaves scores alone
trial.push_back(90);

The two ways do the same thing. Choose the parameter when the whole function is one "what if". Choose the declaration when a loop needs a fresh copy on each turn.

That is the last piece. The computer opponent in the lab looks at each empty cell, asks on a copy whether a mark there would win, and takes the first cell where the answer is yes.