In part 6, we left the definition of is_winning_position as follows:
int is_winning_position(int x, int y, char c) {
return 0;
}We need to provide a real implementation for this stub.
The implementation should return true, ie. 1, if the position at x,y would result in a win for the player representing character c.
We should check the row we are in and the column we are in.
We should also check the two diagonal possibilities that cross the grid, but only if the x,y position is in the diagonal.
The most straightforward way to do this is with if statements.
If you haven't thought about how you might do this, take a break and think about it before continuing. Break out a piece of paper and pen if you have to. This kind of problem solving is what programming is about at the lowest levels.
The function takes x, y, and c. The x and y are the position on the grid we are checking. The c is the character we are checking for a win with, X or O.
We'll start with row checking first, since it should be the easiest.
When the function is called, the y parameter tells us what row we are checking.
To check the row for a win we would just check the other cells in that row, and if they are both our character, then this position is a win.
However, now is a good time to remember that we only call this function for cells where a turn can actually be taken, where the cell value is a space, ' ', because that's what we've decided represents an open cell.
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
...
}We can check for a row win by checking 3 cells:
grid[y][0]
grid[y][1]
grid[y][2]
One of those, the one at grid[y][x], is the winning position you are checking for, as specified by the function parameters.
We also know that cell will be blank when this function is called. That's not an ideal precondition, but it's fine for this example.
With that in mind, you should understand that if the other two cells are our character, then we have found a winning position.
You can do this logic with some hard-coded if statements.
if (x == 0) {
if (grid[y][1] == c && grid[y][2] == c) {
return 1;
}
} else if (x == 1) {
if (grid[y][0] == c && grid[y][2] == c) {
return 1;
}
} else if (x == 2) {
if (grid[y][0] == c && grid[y][1] == c) {
return 1;
}
}I think it's good to be able to break down things you don't understand into a static form before considering a dynamic form.
If we had a grid larger than 3x3 we might want to do this dynamically, and we could achieve that with a for loop.
int leftright_matches = 0;
for (int ix = 0; ix < 3; ix++) {
char this_char = grid[y][ix];
if (ix == x) {
// this is the cell where we are checking for a win, it is blank when this function is called
leftright_matches++;
} else {
if (this_char == c) {
// this is one of the other cells, and the value matches our character
leftright_matches++;
}
}
}
if (leftright_matches == 3) {
// all 3 cells we checked are what we expect for a winning position, so this is a winning position
return 1;
}That would useful if our board was arbitrarily large, but for now I think the if statements are more straightforward.
So let's implement that:
int is_winning_position(int x, int y, char c) {
// check for win in this row
if (x == 0) {
if (grid[y][1] == c && grid[y][2] == c) {
return 1;
}
} else if (x == 1) {
if (grid[y][0] == c && grid[y][2] == c) {
return 1;
}
} else if (x == 2) {
if (grid[y][0] == c && grid[y][1] == c) {
return 1;
}
}
return 0;
}We keep returning 0 at the end as a catch-all in case we don't return from the other cases.
If you run the code now you'll see we didn't really achieve anything yet because there are no row wins.
It's good enough that the code runs and we understand the idea.
Now let's quickly implement the check for column win, and test it.
int is_winning_position(int x, int y, char c) {
// check for win in this row
if (x == 0) {
if (grid[y][1] == c && grid[y][2] == c) {
return 1;
}
} else if (x == 1) {
if (grid[y][0] == c && grid[y][2] == c) {
return 1;
}
} else if (x == 2) {
if (grid[y][0] == c && grid[y][1] == c) {
return 1;
}
}
// check for win in this column
if (y == 0) {
if (grid[1][x] == c && grid[2][x] == c) {
return 1;
}
} else if (y == 1) {
if (grid[0][x] == c && grid[2][x] == c) {
return 1;
}
} else if (y == 2) {
if (grid[0][x] == c && grid[1][x] == c) {
return 1;
}
}
return 0;
}Now we can detect wins in rows and columns, but our turns are too dumb for present any winning conditions.
In order to test our new logic, we can temporarily change our code with data we know will present winning conditions for the code we wrote.
// i moved the old main() to main_old()
void main_test() {
// check auto row win
show_board();
take_turn(0, 1, 'X');
take_turn(2, 1, 'X');
show_board();
take_turn_auto('X');
show_board();
// reset board
printf("\nresetting...\n");
grid[1][0] = ' ';
grid[1][1] = ' ';
grid[1][2] = ' ';
show_board();
// check auto column win
take_turn(1, 0, 'O');
take_turn(1, 1, 'O');
show_board();
take_turn_auto('O');
show_board();
}
void main() {
main_test();
}If you run this it will show the row and column win checking is working.
We can switch main back to calling main_old now.
void main() {
main_old();
}And then we'll implement checking for wins on the two diagonals on the board.
We'll call the first diagonal the one that goes from top-left to bottom-right.
|1| | |
| |5| |
| | |9|
Before we check though, we need to make sure we are checking a position that is in the diagonal.
This function might be called for positions that are not in the diagonal. All positions are in rows and columns, but not all positions are in the diagonals.
So our first if statement will make sure we are in the diagonal.
if (x == 0 && y == 0) {
...
}And then we will write if statements to check the other cells in that diagonal position, like we did for rows and columns.
// position 1
if (x == 0 && y == 0) {
if (grid[1][1] == c && grid[2][2] == c) { // position 5 & 9
return 1;
}
}
// position 5
if (x == 1 && y == 1) {
if (grid[0][0] == c && grid[2][2] == c) { // position 1 & 9
return 1;
}
}
// position 9
if (x == 2 && y == 2) {
if (grid[0][0] == c && grid[1][1] == c) { // position 1 & 5
return 1;
}
}And we'll do the same for the other diagonal, by copying that code and changing the index values.
Diagonal two is:
| | |3|
| |5| |
|7| | |
So the code will be slightly more awkward. Remember the first index in the grid is y, so position 3 is grid[0][2]
// position 7
if (x == 0 && y == 2) {
if (grid[1][1] == c && grid[0][2] == c) { // position 5 & 3
return 1;
}
}
// position 5
if (x == 1 && y == 1) {
if (grid[2][0] == c && grid[0][2] == c) { // position 7 & 3
return 1;
}
}
// position 3
if (x == 2 && y == 0) {
if (grid[2][0] == c && grid[1][1] == c) { // position 7 & 5
return 1;
}
}That should be good, now let's test it.
Make sure your main is calling main_old.
void main_old() {
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();
}
void main() {
main_old();
}And add a print statement to the if block where we call is_winning_position.
...
if (is_winning_position(x, y, c)) {
printf("win found!\n");
take_turn(x, y, c);
return;
}
...Compile and run, and you should see that X finds a win before turns 7 and 9.
|X|O|X|
|O|X|O|
| | | |
win found!
&
|X|O|X|
|O|X|O|
|X|O| |
win found!
That's great, but you can see that before O takes turn 6, X is already going to win.
|X|O|X|
|O|X| |
| | | |
Using is_winning_position we can actually help O here, by detecting the X win, and blocking it.
So, it's O's turn and we want to block the X win with O's turn.
We can do that in take_turn_auto by checking for an opponent win.
Right now take_turn_auto checks for our own win, or takes a dumb turn.
We still want to check for our own win, and we will still want to do that even if there is a win blocking move.
So that means we want our win blocking code to go after checking for our own game-ending win.
Otherwise we might be blocking an opponent win when we actually have our own win available to end the game.
So copy the win checking for loop and paste it in between the two for loops already in the function.
...
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)) {
printf("win found!\n");
take_turn(x, y, c);
return;
}
}
}
}
...Now what? It's still checking for our own win.
Well, now we will check for the opponent win character instead.
But first we have to calculate the opponent character so we can pass it to a second is_winning_position call.
char opponent_char;
if (c == 'O') {
opponent_char = 'X';
} else {
opponent_char = 'O';
}Then modify our win blocking code to use the opponent_char in the is_winning_position check, and change the print as well.
// look for winblock position
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, opponent_char)) {
printf("winblock found!\n");
take_turn(x, y, c);
return;
}
}
}
} Compile and run, and you will see things getting smarter.
|X|O|X|
|O|X| |
| | | |
winblock found!
|X|O|X|
|O|X| |
|O| | |
win found!
|X|O|X|
|O|X| |
|O| |X|
winblock found!
|X|O|X|
|O|X|O|
|O| |X|
O blocks X's win at position 7, then X sees its own win at position 9 and takes it.
Then, since we aren't detecting the end of the game, it continues with O finding another win block at position 6.
And finishes with X taking the final turn at position 8.
|X|O|X|
|O|X|O|
|O|X|X|
Obviously, what we want to do now is detect the end of the game.
I won't be walking through this code, but you can read it and try to understand.
This function will tell us if there is a winner, and who it is.
// return board winner, or null
char get_board_winner() {
// leftright
for (int y = 0; y < 3; y++) {
char c = grid[y][0]; // first char in row y
if (c != ' ' && c == grid[y][1] && c == grid[y][2]) {
return c;
}
}
// updown
for (int x = 0; x < 3; x++) {
char c = grid[0][x]; // first char in column x
if (c != ' ' && c == grid[1][x] && c == grid[2][x]) {
return c;
}
}
// diagonal1
char d1_char = grid[0][0];
if (d1_char != ' ' && d1_char == grid[1][1] && d1_char == grid[2][2]) {
return d1_char;
}
// diagonal2
char d2_char = grid[2][0];
if (d2_char != ' ' && d2_char == grid[1][1] && d2_char == grid[0][2]) {
return d2_char;
}
return '\0';
}And this new main function will run the game automatically, stopping if someone wins, and printing the winner.
void main_auto() {
// take up to 9 turns
char current_char = 'X';
char winner = '\0';
for (int i = 0; i < 9; i++) {
// each loop is a turn
take_turn_auto(current_char);
show_board();
char c = get_board_winner();
if (c == 'O' || c == 'X') {
winner = c;
break; // exit the for loop because a winner was found
}
// switch to other char at end of turn
if (current_char == 'X') {
current_char = 'O';
} else {
current_char = 'X';
}
}
if (winner != '\0') {
printf("WINNER! %c\n", winner);
} else {
printf("DRAW!\n");
}
}
void main() {
main_auto();
}But, every game will be the same now, because the catch-all turn logic just picks the first available position.
|X|O|X|
|O|X| |
| | | |
winblock found!
|X|O|X|
|O|X| |
|O| | |
win found!
|X|O|X|
|O|X| |
|O| |X|
WINNER! X
I've added randomization to that old default turn logic to force the games to play out differently.
First, I seed the randomization function, so it generates a different randomized sequence dependent on the current time in seconds.
That actually means that if you run the program twice in the same second it will produce the same results.
Similarly, if you don't seed, the seed is assumed to be 1, so the randomized results will be the same every time.
The rand function produces the same sequence of 'random' values when it has the same seed.
So, at the top of main_auto I add:
// seed randomizer to current time in seconds, so it plays different each run
// without this, the seed is considered to be 1 on every run
time_t t;
srand((unsigned) time(&t));
printf("seed: %d\n", (unsigned) t);Then I comment the 'dumb turn' logic at the end of take_turn_auto.
// 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;
// }
// }
// }And after it I add this code, which takes the ideal first two turns when possible, and a random turn otherwise.
// count remaining moves, so we can do other logic
int blank_count = 0;
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
char this_char = grid[y][x];
if (this_char == ' ') {
blank_count++;
}
}
}
// ideal first turn: place in corner
if (blank_count == 9) {
take_turn(0, 0, c);
return;
}
// if second turn: place in middle
if (blank_count == 8) {
take_turn(1, 1, c);
return;
}
// randomly select one of the remaining options, as if they were in a list
int random = rand() % blank_count;
// % is the modulo operator, it returns the remainder of an integer division
// since rand() returns a value from 0 to 32768, the modulo operator converts that to between 0 and blank_count
// iterate to find the random-th remaining move, since they aren't in their own consecutive list (they could be, though..)
int blank_index = 0;
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
char this_char = grid[y][x];
if (this_char == ' ') {
if (random == blank_index) {
take_turn(x, y, c);
return;
} else {
blank_index++;
}
}
}
} But, I also need to add two includes at the top of the file.
#include <stdlib.h>
#include <time.h>The rand and srand functions come from stdlib, and the time_t type comes from stdlib.
Compile and run and you will see the game plays out differently each time depending on the seed.
seed: 1679857743
|X| | |
| | | |
| | | |
|X| | |
| |O| |
| | | |
|X| | |
| |O| |
| | |X|
|X| |O|
| |O| |
| | |X|
winblock found!
|X| |O|
| |O| |
|X| |X|
winblock found!
|X| |O|
|O|O| |
|X| |X|
win found!
|X| |O|
|O|O| |
|X|X|X|
WINNER! X
If we wanted to improve this further, and make winning impossible, we would be able to by changing the random turn logic into more and more articulate moves depending on the board state.
But, I think this is fine for now.
I think the most important thing to understand in this lesson is what kind of thinking and level of detail fundamentally defines programming. I think a lot of the time beginners are looking for function calls and libraries to do all the work for them instead of exploring their own solutions through harder work.
Here'a video of a rube-goldberg-like machine that moves marbles through a system to play music. I consider this video a good visualization of what low-level programming is like. The machine he made is like the program, and he uses it in this video: https://www.youtube.com/watch?v=IvUU8joBb1Q