Tic Tac Toe Game Over Detection Algorithm: From Fixed Tables to General Solutions

Problem Background and Challenges

In Tic Tac Toe game development, determining game over is a core problem. Traditional approaches typically use predefined win pattern tables to check game state, which is acceptable for small 3×3 boards but becomes infeasible as board size increases to n×n (e.g., 16×16, 25×25) with win conditions requiring x consecutive placements (x=4,5,...). The number of win patterns grows exponentially with board size, causing storage and computational costs to skyrocket.

Algorithm Optimization Approach

The key insight is that a winning move can only occur after a player makes their most recent move. Therefore, we only need to check the row, column, and possibly relevant diagonals containing that move, rather than the entire board. This approach limits the search space from the entire n×n board to specific linear paths, significantly improving efficiency.

Core Algorithm Implementation

The following Java code demonstrates the win detection algorithm for general n×n boards:

public class TicTacToe {
    
    enum State { BLANK, X, O };
    
    int n = 3; // Board size
    State[][] board = new State[n][n];
    int moveCount = 0;
    
    void makeMove(int x, int y, State player) {
        if (board[x][y] == State.BLANK) {
            board[x][y] = player;
            moveCount++;
            
            // Check win conditions
            if (checkWin(x, y, player)) {
                System.out.println("Player " + player + " wins!");
                return;
            }
            
            // Check draw
            if (moveCount == n * n) {
                System.out.println("Game draw!");
            }
        }
    }
    
    boolean checkWin(int x, int y, State player) {
        // Check column
        for (int i = 0; i < n; i++) {
            if (board[x][i] != player) break;
            if (i == n - 1) return true;
        }
        
        // Check row
        for (int i = 0; i < n; i++) {
            if (board[i][y] != player) break;
            if (i == n - 1) return true;
        }
        
        // Check main diagonal
        if (x == y) {
            for (int i = 0; i < n; i++) {
                if (board[i][i] != player) break;
                if (i == n - 1) return true;
            }
        }
        
        // Check anti-diagonal
        if (x + y == n - 1) {
            for (int i = 0; i < n; i++) {
                if (board[i][n - 1 - i] != player) break;
                if (i == n - 1) return true;
            }
        }
        
        return false;
    }
}

Algorithm Complexity Analysis

Traditional fixed-table methods require checking all possible win patterns, with the number of win patterns being O(n²) on an n×n board. The optimized algorithm checks only 4 paths (row, column, two diagonals), each with at most n elements, resulting in O(n) time complexity. Space complexity is O(n²) for storing board state, but the checking process requires only constant additional space.

Scalability and Generality

This algorithm naturally supports arbitrary board size n and win condition x (x consecutive pieces). Simply modify the win check logic by changing the condition from i == n-1 to consecutive count == x. For example, for a 5×5 board requiring 4 consecutive pieces to win:

boolean checkWin(int x, int y, State player, int winLength) {
    // Check for consecutive winLength pieces in four directions
    // Implementation details similar but require maintaining consecutive count
}

Comparison with Other Methods

The magic square method (Answer 2) quickly detects wins through mathematical properties but is limited to standard 3×3 boards, lacking generality. The single-loop counting method (Answer 3) simplifies implementation but may misjudge non-consecutive arrangements. The recent-move-based algorithm presented in this paper achieves the best balance between generality, accuracy, and efficiency.

Practical Implementation Recommendations

When implementing, encapsulate the win check logic as a separate method for easier testing and maintenance. For very large boards (n>100), consider further optimizations such as bit manipulation or incremental win state updates. The move count mechanism ensures accurate draw detection without unnecessary full-board scans.