Introduction
An interesting problem I came across while creating a Connect 4 game in Java was detecting when one of the players was in a winning state. If you’re not already familiar with connect 4 it’s a game played between 2 players on a 6×7 grid. The grid starts off empty and each player picks 1 of the 7 columns to drop in a counter. Counters are affected by gravity so each grid spaces can only be filled once all the grid spaced below are also filled. The first player to get 4 of their counters in a row is the winner or if this condition isn’t met and the board is full, it’s a draw. A row can be vertical, horizontal or either of the 2 diagonals.
This is a demo of the connect 4 game in action. A link to the original repository can be found here.
The easiest way to detect a winning state is to iterate through a hard-coded list of all possible winning positions for each player. This is made possible by the fact that there are only 69 possible ways for each player to get 4 in a row. A breakdown of my calculation for each possible direction is shown below:
| Horizontal = 4 * 6 = 24 | Vertical = 3 * 7 = 21 | Diagonal = (1 + 2 + 3 + 3 + 2 + 1) * 2 = 24 |
While this method would work in practice, what if we wanted to try playing on a bigger board? Or change the winning requirement to 5 in a row? To achieve this, we need to be able to iterate through all row positions dynamically and check if each position contains a winning state.
Checking a single row position
I broke this problem down by first writing a function that checks a single row position on the board. I defined a row as having a starting (x, y) location and a direction given by a pair of 0 and 1s. For example, to check diagonally from the bottom-left corner of the board we start at (0, 0) and look in the direction of (1, 1). The full code for this function can be found here. This function takes as input the current state of board along with these row parameters.
private static boolean isFourIn(char[][] board, int startX, int startY,
int directionX, int directionY)
Assuming that the starting location of the row lies within the game board – the first task this function performs is checking whether the counter on the opposite end of the row also lies within the game board. Provided these conditions are met, we know we have a valid row position.
An example of 2 possible row positions. The S denotes the starting position of each row. Yellow is a valid row and the horizontal red row is invalid. The counters are floating here to simplify the picture.
The code below effectively takes the starting position, jumps 3 spaces along the row, and then checks if the resulting (x,y) position is outside the size of the board. If it is, we return false indicating no winning row position.
if (((startX + (NUMBER_IN_ROW - 1)*directionX) >= board.length) ||
((startX + (NUMBER_IN_ROW - 1)*directionX) < 0) ||
((startY + (NUMBER_IN_ROW - 1)*directionY) >= board[0].length) ||
((startY + (NUMBER_IN_ROW - 1)*directionY) < 0)) {
return false;
}
The final check this function makes is to test that the state of the start position (blank, red, yellow) equals the state of the other 3 positions in the row. Or in other words, the row is all of the same colour. This is implmentated in the code below. If we get past these two checks we return true indicating four in a row!
char start = board[startX][startY];
for (int i = 1; i < NUMBER_IN_ROW; i++) {
int x = startX + (i * directionX);
int y = startY + (i * directionY);
if (board[x][y] != start) {
return false;
}
}
Iterating all possible rows
Now we have a method for checking a single row position, we still need to work out how to iterate through all possible rows. The most straight forward way to do this is to loop through all positions on the board and look in all 8 possible directions. However, it turns out we only need to check 4 directions for each starting position otherwise we end up checking the same rows twice. For example, (0, 0) (1, 1) and (3, 3) (-1, -1) correspond to the same row. The 4 directions I check in my code are (1, 0), (0, 1), (1, 1), (–1, 1) corresponding to horizontal, vertical, upper-right and bottom-right. The defintion of my function is given below. It takes as input the current state of the game board and outputs the x, y coordinates of the winning row position (so they can flash once a player has won). The full code for this function can be found here.
public static int[][] isFourInRow(char[][] board) {
// For each space in the board...
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
// If a space has red or yellow in it...
if (board[i][j] != BLANK) {
// Check in 4 directions for a row
for (int[] DIRECTION : DIRECTIONS) {
if (isFourIn(board, i, j, DIRECTION[0], DIRECTION[1])) {
// Return the winning position
}
}
}
}
}
// Return no winning position
}
Reflection
As of writing, I wrote this code 3 years ago in my spare time during university and have only revisted this code again to write this post. I was able to work out the algorithm I had originally implemented and the code was easy for me to understand even after this time.
Where I think I fell short is in the algorithm itself. Reading back through the code I can now think of quite a few ways it could be simplified.
- We could iterate through only the valid board positions and avoid individually checking each one in the isFourIn method.
- The task of checking the starting position for a yellow or red counter should be given to the isFourIn method to provide better seperation of concerns.
- Why do we check the entire board after each player’s move? Any new winning position will always overlap the move of the last player. This means we only need to check at most 16 row positions after each turn.
I welcome anyone to fork this code and try making some of these improvements or come up with your own!