Friday, August 27, 2010

Tic Tac Toe Algorithm

If you are given a Tic Tac Toe board. How do you find if a specific player is a winner.

The straight forward algorithm is going to start from the first row and the first column. the algorithm will start by checking if this square is an X or if it is an O.
assume we are trying to find if X is the winner.

If this square is an X, then we will increment the number of X's found in row 1 and the number of X's found in column 1 and the number of X's found in the 270 degrees diagonal.

Because this first row and first column square is a member of all these three possibilities. in order to support this algorithm then we need a storage that will hold the number of X's found in Row 1, the number of X's found in row 2, the number of X's found in row 3, the number of X's found in column 1. the number of X's found in column 2. the number of X's found in column 3. the number of X's found in the 270 degrees diagonal and finally the number of X's found in 45 degrees diagonal.

We can create a class called Tic Tac Toe as follows.

class TicTacToe
{
private readonly int[] _rows; //array to store the number of X's found in each row
private readonly int[] _cols; //array to store the number of X's found in each column
private int _270Diagonal; //one variable to store the number of X's found in the 270 degrees diagonal
private int _45Diagonal;//one variable to store the number of X's found in the 45 degrees diagonal

private readonly int _boardSize; //Caching the board size
private readonly int _boardSizeMinusOne; //cashing the board size minus one in order to perform the subtraction only once

public TicTacToe(int boardSize) // constructor will set the rows and columns array sizes, cash the board size and calculate the boardsize - 1
{
_rows = new int[boardSize];
_cols = new int[boardSize];
_boardSize = boardSize;
_boardSizeMinusOne = _boardSize - 1;
}

//Function to add a Square taken by player X and return true if X won due to this addition
public bool AddSquare(int row, int col)
{
if (_rows[row] == _boardSizeMinusOne) return true; //Since X exist in this row, check if there were two more (or board -1). if so, adding this X will make X take all the squares in this row and hence win
_rows[row] += 1; //otherwise increase the number of X's in this row

if (_cols[col] == _boardSizeMinusOne) return true;
_cols[col] += 1;


if (row == col) //this is the 270 degrees diagonal
{
if (_270Diagonal == _boardSizeMinusOne) return true;
_270Diagonal += 1;
}

if (((row + col) == _boardSizeMinusOne)) //this is the 45 degrees diagonal
{
if (_45Diagonal == _boardSizeMinusOne) return true;
_45Diagonal += 1;
}
return false; //No winner yet
}
}





This class contains the AddSquare function which will add a square taken by X and will let us know if X has won due to this addition.

This algorithm will visit every single square only in the worst case scenario and at this time the Big O will be n to the power of 2.

in order to test this class we would create a sample board and use the class as follows

static void Main(string[] args)
{
var board = new int[3,3];
board[0, 0] = 0;
board[0, 1] = 0;
board[0, 2] = 1;

board[1, 0] = 0;
board[1, 1] = 0;
board[1, 2] = 1;

board[2, 0] = 1;
board[2, 1] = 0;
board[2, 2] = 1;

var ticTacToe = new TicTacToe(3);
for(var row = 0; row != 3; row++)
{
for (var col = 0; col != 3; col++)
{
if (board[row,col] == 1)
if (ticTacToe.AddSquare(row, col))
{
Console.WriteLine("Player 1 has won the game.");
Console.ReadKey();
return;
}
}
}

Console.WriteLine("No one won");
Console.ReadKey();
}


a better algorithm could select the squares to examine more carefully and improve the worst case scenario. If we look at the board, we find that the middle square is responsible about 4 different possibilities of winning, and if this square does not contain X, then that means 4 different possibilities are eliminated. secondly the corner squares are responsible for 3 different possibilities and if a corner square does not contain X then 3 possibilities are eliminated. so, if we start with the middle square and then the corner squares the worst case scenario will indeed be improved.

Not only that, but if we can store the importance of every square and how many possibilities it is a member of, then during the examination of the board we will find that some squares will not affect the board and hence we should not check it. here is an illustration.

3

2

3

2

4

2

3

2

3

In the board above, the center square has a weight of 4, and that means it is part of 4 possibilities to win the board. the possibilities are, row 2, column 2, and the diagonals. if we check this square first and it turns out it does not contain an X, then those 4 possibilities are eliminated and the weights of the affected squares can be decreased as per the diagram below

2

1

2

1

-

1

2

1

2

in the board above, the center square is not an X and that means for example for the top left corner square, there is only two possibilities that this square can be part of. the two possibilities are row 1 and column 1, because the 270 degrees diagonal that it was part of has been eliminated.

2

1

2

1

-

1

2

1

2

Now can can go ahead and pick the square which the highest weight, in case there are more than one, we can pick anyone, let's pick the top left corner and check it. let's assume we did not find an X in it. that means row 1 and column 1 has been eliminated as follows

-

0

1

0

-

1

1

1

1


if the top left corner is not an X, then we can go ahead and reduce the weights of all the squares that can make a winning situation jointly with the top left square. in this case we will decrease 1 from the weights of all the squares in row 1, all the squares in column 1 and the 270 degrees diagonal. in this case we will notice that row 1 column 1 now has a weight of zero. and that means the value of this square does not matter, whether it is an X or an O it does not matter, because row 1 can never be a row fully occupied by X, and column 2 can never be fully occupied by X. It does not matter what the value of this square is (row 1, column 2). using this technique we will be able to prune the board and eliminate a number of squares that we do not need to check.

This will affect the Big O calculated for this board since it will not be n square. I still need to calculate how exactly it will be and I should expect to see some log n in the calculation.

I will post the C# program here soon.