Algorithm for Determining Tic Tac Toe Game Over (Java)

Question

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 ... }?

Answer 1

you can use a magic square http://mathworld.wolfram.com/MagicSquare.html if any row, column, or diag adds up to 15 then a player has won.

Answer 2

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.

edit: this code is for an n by n board with n in a row to win (3x3 board requries 3 in a row, etc)

edit: added code to check anti diag, I couldn't figure out a non loop way to determine if the point was on the anti diag so thats why that step is missing

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)
     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 == (n^2 - 1)){
      //report draw
     }
    }
}

Answer 3

How about this pseudocode:

After a player puts down a piece at position (x,y):

col=row=diag=rdiag=0
winner=false
for i=1 to n
  if cell[x,i]=player then col++
  if cell[i,y]=player then row++
  if cell[i,i]=player then diag++
  if cell[i,n-i+1]=player then rdiag++
if row=n or col=n or diag=n or rdiag=n then winner=true

I'd use an array of char [n,n], with O,X and space for empty.

1. simple.
2. One loop.
3. Five simple variables: 4 integers and one boolean.
4. Scales to any size of n.
5. Only checks current piece.
6. No magic. :)

Answer 4

I developed an algorithm for this as part of a science project once.

You basically recursively divide the board into a bunch of overlapping 2x2 rects, testing the different possible combinations for winning on a 2x2 square.

It is slow, but it has the advantage of working on any sized board, with fairly linear memory requirements.

I wish I could find my implementation

Answer 5

This is similar to Osama ALASSIRY's answer, but it trades constant-space and linear-time for linear-space and constant-time. That is, there's no looping after initialization.

Initialize a pair (0,0) for each row, each column, and the two diagonals (diagonal & anti-diagonal). These pairs represent the accumulated (sum,sum) of the pieces in the corresponding row, column, or diagonal, where

A piece from player A has value (1,0)
A piece from player B has value (0,1)

When a player places a piece, update the corresponding row pair, column pair, and diagonal pairs (if on the diagonals). If any newly updated row, column, or diagonal pair equals either (n,0) or (0,n) then either A or B won, respectively.

Asymptotic analysis:

O(1) time (per move)
O(n) space (overall)

For the memory use, you use 4*(n+1) integers.

two_elements*n_rows + two_elements*n_columns +
two_elements*two_diagonals = 4*n + 4 integers = 4(n+1) integers

Exercise: Can you see how to test for a draw in O(1) time per-move? If so, you can end the game early on a draw.