algorithmstatetic-tac-toe

Algorithm for Determining Tic Tac Toe Game Over


I've written a game of tic-tac-toe in Java, and my current method of determining the end of the game accounts for the following possible scenarios for the game being over:

  1. The board is full, and no winner has yet been declared: Game is a draw.
  2. Cross has won.
  3. Circle has won.

Unfortunately, to do so, it reads through a predefined set of these scenarios from a table. This isn't necessarily bad considering that there are only 9 spaces on a board, and thus the table is somewhat small, but is there a better algorithmic way of determining if the game is over? The determination of whether someone has won or not is the meat of the problem, since checking if 9 spaces are full is trivial.

The table method might be the solution, but if not, what is? Also, what if the board were not size n=9? What if it were a much larger board, say n=16, n=25, and so on, causing the number of consecutively placed items to win to be x=4, x=5, etc? A general algorithm to use for all n = { 9, 16, 25, 36 ... }?


Solution

  • You know a winning move can only happen after X or O has made their most recent move, so you can only search row/column with optional diag that are contained in that move to limit your search space when trying to determine a winning board. Also since there are a fixed number of moves in a draw tic-tac-toe game once the last move is made if it wasn't a winning move it's by default a draw game.

    This code is for an n by n board with n in a row to win (3x3 board requires 3 in a row, etc)

    public class TripleT {
        
        enum State{Blank, X, O};
        
        int n = 3;
        State[][] board = new State[n][n];
        int moveCount;
        
        void Move(int x, int y, State s){
            if(board[x][y] == State.Blank){
                board[x][y] = s;
            }
            moveCount++;
            
            //check end conditions
            
            //check col
            for(int i = 0; i < n; i++){
                if(board[x][i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
            
            //check row
            for(int i = 0; i < n; i++){
                if(board[i][y] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
            
            //check diag
            if(x == y){
                //we're on a diagonal
                for(int i = 0; i < n; i++){
                    if(board[i][i] != s)
                        break;
                    if(i == n-1){
                        //report win for s
                    }
                }
            }
                
            //check anti diag (thanks rampion)
            if(x + y == n - 1){
                for(int i = 0; i < n; i++){
                    if(board[i][(n-1)-i] != s)
                        break;
                    if(i == n-1){
                        //report win for s
                    }
                }
            }
    
            //check draw
            if(moveCount == (Math.pow(n, 2) - 1)){
                //report draw
            }
        }
    }