In parts 6 and 7 we will write a tic-tac-toe console program that plays itself.
The goal is to learn how to understand and solve problems.
We know how to write functions now, but we've glossed over the other fundamental aspect of programming; the data.
A good way to start writing code is to think of the data, and how that data changes in distinct steps.
So what data do we need for tic-tac-toe?
- A board, containing a 3x3 grid of cells where players can enter X's and O's.
Ok, we'll start programming there.
The grid will be represented with an array, which we learned is just a list of values.
Items in an array are accessed by their position in the array.
In C, and most modern languages, the first item in the array is considered to be at position 0, and the next item is at position 1.
Accessing items in an array by position is called indexing, and the position of an item in the array is also called the index.
Let's number the cells in our 3x3 tic-tac-toe grid so we can refer to them in our example data.
|1|2|3|
|4|5|6|
|7|8|9|
There are 2 fundamental ways to represent a grid with arrays.
-
A single array containing every row value consecutively.
int grid[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };Each three items is a row.
To access cell x,y:
int x = 2; int y = 1; int width = 3; int value = grid[y * width + x]; printf("%d\n", value); // prints 6
This technique requires you know the width of a row.
You use basic math to get to the start of the y-th row (y * width) then offset from there by the cell number in that row (x).
-
An array whose values point to other arrays, of row values.
int grid[3][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };Each item in the outer array points to the array of row values.
To access cell x,y:
int x = 2; int y = 1; int value = grid[y][x]; printf("%d\n", value); // prints 6
But, notice how I wrote
grid[y][x]instead ofgrid[x][y].If you think of the inner secondary arrays containing row values, then it is obvious they should be indexed by x, which represents the left-to-right position of a cell.
Another way to see it is that the values in the outer array point to the y-th row.
Row 0 is y 0: { 1, 2, 3 } Row 1 is y 1: { 4, 5, 6 } Row 2 is y 2: { 7, 8, 9 }
In addition, each of these techniques has a variation which flips the x and y.
The variations, described the same way, are:
-
b. A single array containing every column value consecutively.
int grid[9] = { 1, 4, 7, 2, 5, 8, 3, 6, 9 };Each three items is a column.
To access cell x,y:
int x = 2; int y = 1; int height = 3; int value = grid[x * height + y]; printf("%d\n", value); // prints 6
NOTE: Another name for the width/height value in both variations is 'stride'.
-
b. An array whose values point to other arrays, of column values.
int grid[3][3] = { { 1, 4, 7 }, { 2, 5, 8 }, { 3, 6, 9 } };Each item in the outer array points to the array of column values.
To access cell x,y:
int x = 2; int y = 1; int value = grid[x][y]; printf("%d\n", value); // prints 6
The way you layout the grid in memory and iterate over it with for loops can matter for performance.
But, you may also want a particular layout just to match your encoded understanding of whatever you're doing.
That's what we're going to do in our code, since it's a 3x3 grid and we want a layout that matches the real tic-tac-toe board as well as the one in our head.
We want to be able to write and think of it visually like technique 2, with an array pointing to other arrays.
char grid[3][3] = {
{'1', '2', '3'},
{'4', '5', '6'},
{'7', '8', '9'},
};This means we will have to access cells with grid[y][x], since that's how we've decided to layout the values.
You'll also notice I changed int to char, which means I changed the type of value from integer to character. So, I need to use character literals ('1', '2', '3') instead of integer literals (1, 2, 3) when defining the values.
Although, I could technically still use integer literals to represent the chars, but it would be annoying because the integer literals for the character '1' is actually 49, as defined by the ascii encoding standard.
Ok, so we've defined the board. The next obvious thing I can think is that we will need to see it.
So, write a show_board function which prints the board, and change the character literals in the global grid value to spaces, which will designate open cells.
char grid[3][3] = {
{' ', ' ', ' '},
{' ', ' ', ' '},
{' ', ' ', ' '},
};
void show_board() {
printf("\n");
printf("|%c|%c|%c|\n", grid[0][0], grid[0][1], grid[0][2]);
printf("|%c|%c|%c|\n", grid[1][0], grid[1][1], grid[1][2]);
printf("|%c|%c|%c|\n", grid[2][0], grid[2][1], grid[2][2]);
}
void main() {
show_board();
}The printf statement takes a variable number of parameters, which it uses to fill in the 'format string' passed as the first parameter.
In addition, the string literals have "\n" in them, which represent newline characters, according to the definition of string literals.
Check some documentation for 'printf' and 'string literal escape sequences' if you want to know more.
Now let's do the next obvious thing, take a turn.
So, we'll write a function which takes the position of the turn, and a character variable c that tells what player made the turn, X or O.
Then call the new function from main and show_board again.
void take_turn(int x, int y, char c) {
grid[y][x] = c;
}
void main() {
show_board();
take_turn(1, 1, 'X');
show_board();
}When you run, the output should show you the blank board, then the board after the first turn.
| | | |
| | | |
| | | |
| | | |
| |X| |
| | | |
So what happens next is, of course, the players take turns filling in cells.
In static code a full game would look like this:
void main() {
show_board();
take_turn(1, 1, 'X');
show_board();
take_turn(0, 0, 'O');
show_board();
take_turn(0, 2, 'X');
show_board();
take_turn(2, 0, 'O');
show_board();
take_turn(1, 0, 'X');
show_board();
take_turn(1, 2, 'O');
show_board();
take_turn(2, 1, 'X');
show_board();
take_turn(0, 1, 'O');
show_board();
take_turn(2, 2, 'X');
show_board();
}
We want to make it take turns dynamically, so we don't have to tell it where to take a turn.
So we will introduce a take_turn_auto function, with this signature:
void take_turn_auto(char c)We removed the x and y parameters that were in take_turn because we will calculate them in the function.
First, change the take_turn calls in main to take_turn_auto.
void main() {
show_board();
take_turn_auto('X');
show_board();
take_turn_auto('O');
show_board();
take_turn_auto('X');
show_board();
take_turn_auto('O');
show_board();
take_turn_auto('X');
show_board();
take_turn_auto('O');
show_board();
take_turn_auto('X');
show_board();
take_turn_auto('O');
show_board();
take_turn_auto('X');
show_board();
}Then define take_turn_auto.
For now let's just take the turn in the dumbest way possible, by iterating the grid and looking for a free spot to take a turn in.
void take_turn_auto(char c) {
// take first available turn we find
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
char this_char = grid[y][x];
if (this_char == ' ') {
take_turn(x, y, c);
return;
}
}
}
}The return statement causes the execution to exit the function when it is encountered. The for loops are abandoned when it is encountered and control goes back to the caller of the function. The function has 'returned' or exited.
Now we have something that takes turns automatically, and will always end up in a draw like this:
|X|O|X|
|O|X|O|
|X|O|X|
But if you look at the board after the fifth turn, you can see X can easily win.
|X|O|X|
|O|X| |
| | | |
We want to make X win here.
Which means we want to modify take_turn_auto so it looks for a winning position to take, but still defaults to the old turn logic if it can't find a win.
So, how about when we iterate the grid we try to calculate if that cell is a winning position.
void take_turn_auto(char c) {
// take first available turn we find
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
char this_char = grid[y][x];
// TODO: check for winning position to take here...
}
}
}We'll do that with another function:
int is_winning_position(int x, int y, char c)So we'll have code that looks like this:
void take_turn_auto(char c) {
// look for winning turn
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
char this_char = grid[y][x];
if (this_char == ' ') {
if (is_winning_position(x, y, c)) {
take_turn(x, y, c);
return;
}
}
}
}
}But, if no winning position is found, the function will not take a turn.
So, after those for loops we will still need to do the old turn logic as well.
void take_turn_auto(char c) {
// first, look for winning turn
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
char this_char = grid[y][x];
if (this_char == ' ') {
if (is_winning_position(x, y, c)) {
take_turn(x, y, c);
return;
}
}
}
}
// no winning turn found, take dumb turn
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
char this_char = grid[y][x];
if (this_char == ' ') {
take_turn(x, y, c);
return;
}
}
}
}So now it will try to find any winning position on the board, and if none is found it will otherwise find the first turn available, like it did before.
But, we still need to write is_winning_position for this to work.
For now, let's define it like this, so we can compile and test that everything is working right.
int is_winning_position(int x, int y, char c) {
return 0;
}This just says no winning position found, every time it is called. This should compile and run, and should behave the same as before, except now it is primed for our most sophisticated feature.
In part 7 we will define is_winning_position, but you should start thinking about how you would automate that. Think about how you would define generic logic to determine whether a position would be a winning position.
Think about how we do it in real life. We look for a row with two of our own characters, and an open space to take our turn in.
We do the same thing for columns, and for the two diagonals across the grid.
You should think about how you would detect these conditions with if statements.