Connect 4, check for winner algorithm

Mastering Connect 4: A Comprehensive Guide to Winner Detection Algorithms

Dive deep into the logic behind detecting a winner in the classic game of Connect 4. This article explores various algorithmic approaches, from basic checks to optimized solutions, complete with Java code examples and visual explanations.

Connect 4 is a two-player connection game where players take turns dropping colored discs into a seven-column, six-row vertically suspended grid. The objective is to be the first to form a horizontal, vertical, or diagonal line of four of one's own discs. Implementing the winner detection logic is a core component of any Connect 4 game, and it presents an interesting algorithmic challenge. This article will guide you through the process of designing and implementing an efficient winner-checking algorithm in Java.

Understanding the Game Board and Win Conditions

Before we can check for a winner, we need a clear representation of the game board. A 2D array (or matrix) is the most common and intuitive way to model the Connect 4 grid. For a standard 6x7 board, board[row][col] can store the state of each cell, typically using integers (e.g., 0 for empty, 1 for Player 1, 2 for Player 2) or enums.

The win conditions are straightforward: four consecutive discs of the same player in any of the following orientations:

• Horizontal: (row, col), (row, col+1), (row, col+2), (row, col+3)
• Vertical: (row, col), (row+1, col), (row+2, col), (row+3, col)
• Diagonal (Up-Right): (row, col), (row+1, col+1), (row+2, col+2), (row+3, col+3)
• Diagonal (Down-Right): (row, col), (row-1, col+1), (row-2, col+2), (row-3, col+3)

It's important to note that after a disc is dropped, we only need to check for a win around the last placed disc. This significantly optimizes the checking process, as we don't need to scan the entire board every turn.

flowchart TD
    A[Player Drops Disc] --> B{Is Board Full?}
    B -->|Yes| C[Draw]
    B -->|No| D[Check for Win]
    D --> E{Check Horizontal}
    D --> F{Check Vertical}
    D --> G{Check Diagonal /}
    D --> H{Check Diagonal \}
    E --> I{Win Found?}
    F --> I
    G --> I
    H --> I
    I -->|Yes| J[Declare Winner]
    I -->|No| K[Next Player's Turn]

Connect 4 Game Flow with Winner Check

Implementing the Winner Check Algorithm in Java

The most efficient way to check for a winner is to focus on the cell where the last disc was placed. From this (row, col) position, we can extend outwards in all four directions (horizontal, vertical, and both diagonals) to see if a line of four has been formed. Each direction check will involve iterating up to three steps away from the (row, col) position in both positive and negative directions, ensuring we stay within board boundaries.

public class Connect4 {
    private static final int ROWS = 6;
    private static final int COLS = 7;
    private int[][] board;

    public Connect4() {
        board = new int[ROWS][COLS]; // 0 for empty, 1 for Player 1, 2 for Player 2
    }

    /**
     * Checks if the last placed disc at (row, col) results in a win.
     * @param row The row of the last placed disc.
     * @param col The column of the last placed disc.
     * @param player The player who just made the move (1 or 2).
     * @return true if the player wins, false otherwise.
     */
    public boolean checkWinner(int row, int col, int player) {
        // Check horizontal
        if (checkDirection(row, col, player, 0, 1) + checkDirection(row, col, player, 0, -1) >= 3) return true;
        // Check vertical
        if (checkDirection(row, col, player, 1, 0) + checkDirection(row, col, player, -1, 0) >= 3) return true;
        // Check diagonal (up-right / down-left)
        if (checkDirection(row, col, player, 1, 1) + checkDirection(row, col, player, -1, -1) >= 3) return true;
        // Check diagonal (up-left / down-right)
        if (checkDirection(row, col, player, 1, -1) + checkDirection(row, col, player, -1, 1) >= 3) return true;

        return false;
    }

    /**
     * Counts consecutive discs of the same player in a given direction from (row, col).
     * @param r Starting row.
     * @param c Starting column.
     * @param player The player to check for.
     * @param dr Row increment for direction.
     * @param dc Column increment for direction.
     * @return Number of consecutive discs in that direction (excluding the starting disc).
     */
    private int checkDirection(int r, int c, int player, int dr, int dc) {
        int count = 0;
        for (int i = 1; i < 4; i++) {
            int newR = r + dr * i;
            int newC = c + dc * i;

            if (newR >= 0 && newR < ROWS && newC >= 0 && newC < COLS && board[newR][newC] == player) {
                count++;
            } else {
                break;
            }
        }
        return count;
    }

    // Example method to simulate dropping a disc (simplified)
    public boolean dropDisc(int col, int player) {
        for (int row = ROWS - 1; row >= 0; row--) {
            if (board[row][col] == 0) {
                board[row][col] = player;
                // After dropping, check for winner
                if (checkWinner(row, col, player)) {
                    System.out.println("Player " + player + " wins!");
                    return true;
                }
                return false; // No win yet, continue game
            }
        }
        return false; // Column is full
    }

    // Main method for a simple test
    public static void main(String[] args) {
        Connect4 game = new Connect4();
        // Simulate some moves
        game.dropDisc(0, 1); // P1
        game.dropDisc(1, 2); // P2
        game.dropDisc(0, 1); // P1
        game.dropDisc(1, 2); // P2
        game.dropDisc(0, 1); // P1
        game.dropDisc(1, 2); // P2
        game.dropDisc(0, 1); // P1 wins vertically
    }
}

Java implementation of the Connect 4 winner detection logic.

Optimizations and Edge Cases

While the provided algorithm is efficient for most cases, consider these points for further optimization or robustness:

• Board Full Check: Before checking for a winner, always check if the board is full. If it is, and no winner is found, the game is a draw.
• Boundary Conditions: The checkDirection method already handles boundary conditions (newR >= 0 && newR < ROWS && newC >= 0 && newC < COLS). Ensure these are correctly implemented to prevent ArrayIndexOutOfBoundsException.
• Performance for Larger Boards: For significantly larger boards (though not typical for Connect 4), more advanced algorithms like iterative deepening or alpha-beta pruning (often used in AI for game playing) might be considered, but for a standard 6x7 grid, the direct check is perfectly adequate and fast.
• Last Move Only: Emphasize that checking only around the last move is the primary optimization. A full board scan every turn would be O(ROWS * COLS * 8 * 3) which is much slower than O(8 * 3) for checking around a single point.

graph TD
    A[Last Placed Disc (R, C)]
    A --> B{Check Horizontal}
    B --> B1["Count (R, C+1), (R, C+2), (R, C+3)"]
    B --> B2["Count (R, C-1), (R, C-2), (R, C-3)"]
    A --> C{Check Vertical}
    C --> C1["Count (R+1, C), (R+2, C), (R+3, C)"]
    C --> C2["Count (R-1, C), (R-2, C), (R-3, C)"]
    A --> D{Check Diagonal /}
    D --> D1["Count (R+1, C+1), (R+2, C+2), (R+3, C+3)"]
    D --> D2["Count (R-1, C-1), (R-2, C-2), (R-3, C-3)"]
    A --> E{Check Diagonal \}
    E --> E1["Count (R+1, C-1), (R+2, C-2), (R+3, C-3)"]
    E --> E2["Count (R-1, C+1), (R-2, C+2), (R-3, C+3)"]
    B1 & B2 --> F{Sum >= 3?}
    C1 & C2 --> F
    D1 & D2 --> F
    E1 & E2 --> F
    F -->|Yes| G[Winner Found!]
    F -->|No| H[No Winner Yet]

Detailed breakdown of the winner check logic from the last placed disc.

By understanding the game mechanics and applying a focused algorithmic approach, implementing a robust Connect 4 winner detection system becomes a manageable task. The provided Java code offers a solid foundation that can be integrated into a larger game application, ensuring accurate and efficient win condition checks.