Suggestion on Tic Tac Toe

Question

I am designing my implementation strategy for Tic-Tac-Toe game. Since this is my 1st game implementation, I am a bit confused and need some general pointers.

Now, the total number of winning combinations in a Tic-Tac-Toe are 8. Currently, I plan to store these winning combinations in an array. Once the end user has made at least 3 moves, I would start checking if the Player has won the game by comparing the current positions used by a Player against this array. However, I am sure this is not an efficient way to check if the player has a winning combination.

Can anyone please suggest me on how to go about with design the logic for the game?

Answer 1

Don't worry about efficiency. I wrote a backtracking solution and there are only 549,945 possible game states. It takes less than 0.25 seconds to run through these on my laptop. Here was my logic to see if the game was over - clearly not very efficient, but it doesn't matter:

private boolean isWinningMove(int row, int col) {
    int piece = board[row][col];

    // check current row
    boolean w = true;
    for (int x = 0; x < 3; x++) { w = w && (board[row][x] == piece); }
    if (w) { return true; }

    // check current column
    w = true;
    for (int x = 0; x < 3; x++) { w = w && (board[x][col] == piece); }
    if (w) { return true; }

    // check 0,0 diagonal
    w = true;
    for (int x = 0; x < 3; x++) { w = w && (board[x][x] == piece); }
    if (w) { return true; }

    // check 0,2 diagonal
    w = true;
    for (int x = 0; x < 3; x++) { w = w && (board[x][2 - x] == piece); }
    return w;
}

Here were my results, which match data on the Wikipedia page for tic-tac-toe:

Moves Simulated: 549945
Draws=46080   Player1-Wins=131184   Player2-Wins=77904
Perfect Strategy Implies: Always a tie.

Games won in 0 moves? 0
Games won in 1 moves? 0
Games won in 2 moves? 0
Games won in 3 moves? 0
Games won in 4 moves? 0
Games won in 5 moves? 1440
Games won in 6 moves? 5328
Games won in 7 moves? 47952
Games won in 8 moves? 72576
Games won in 9 moves? 81792

Answer 2

Since the state space for tic-tac-toe is so small, you could store all the possible end game positions, and use rotations, but I think you're overthinking it a little.

Instead of storing a 3x3 array for the game board, use a 7x7 array, with the inner-most 3x3 for the game board. You should have at least three values that each square can represent -- something like PLAYER_1, PLAYER_2 and NONE. Initially, all values should be set to NONE. Then, after every player's move, check all around the square that was chosen for for 3-in-a-row; 2 above, 2 below, 2 left, 2 right, 2 upper left, 2 lower right, 2 upper right, 2 lower left.

Why the 7x7 array? With a 7x7 array, you can safely search in all directions from any square in the 3x3 area without requiring if statements to see if you're walking off the edge of the array. The board will look like this:

  0 1 2 3 4 5 6
0 * * * * * * *

1 * * * * * * *

2 * * * * * * *

3 * * * * * * *

4 * * * * * * *

5 * * * * * * *

6 * * * * * * *

For example, if the first player moves to, 0,0 on the tic-tac-toe board, that is the same as moving to 2,2 on the 7x7 board. When the move is made, you run a check all around the 2,2 square to see if there are three squares in a row that have the same value

• above: 2,0 and 2,1 and 2,2
• below: 2,2 and 2,3 and 2,4
• left: 0,2 and 1,2 and 2,2
• right: 2,2, and 2,3 and 2,4
• upper-left: 0,0 and 1,1 and 2,2
• upper-right: 2,2 and 3,1 and 4,0
• lower-left: 0,4 and 1,3 and 2,2
• lower-right: 2,2 and 3,3 and 4,4

Since the band of squares around the 3x3 board will always have the value NONE, they can never trigger a winning condition.

If any of those all match the same player value (e.g. PLAYER_1 for the first player), then the game is over with a win. Else, if all squares are taken, the game is a draw.

I've used this for other similar games in the past and it works quite well.