CODEWITHSUNDEEP
javaalgorithmtic-tac-toe
user489041
user489041

Reputation: 28312

Optimal algorithm for seeing who won a tick tac toe game

I have a completed tic tac toe game board. It is 3 x 3. Im not really asking for code (although that would help), but what algorithms would be best for seeing who won? Another way to phrase it would be, what algorithms should I research that would be useful to see who won?

The only thing that really comes to mind is brute force. Just test all the possibilities, but I know there has to be a better way.

Upvotes: 4

Views: 2798

Answers (7)

cgn.dev
cgn.dev

Reputation: 1014

Simple problems are best to solve with simple code.

Here is a brute force and straight forward Typescript solution

const tictactoeBoard: ('x' | 'o' | '')[] = [
    'x', 'o', 'x',
    'o', 'x', 'o',
    '',  'o', 'x'
];

const winningCombinations: number[][] = [
    /// horizontal
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8],
    /// vertical
    [0, 3, 6],
    [1, 4, 7],
    [2, 5, 8],
    /// diagonal
    [0, 4, 8],
    [2, 4, 6],
];

const checkForWinner = (): 'x' | 'o' | null => {
    for (const combination of winningCombinations) {
        const fieldsToCheck = combination.map(index => tictactoeBoard[index]);
        /// check if every field holds a truthy value and
        /// is the same value across the array aka won the game
        if (
            fieldsToCheck.every(f => f && f === fieldsToCheck[0])
        ) {
            return fieldsToCheck[0];
        }
    }
    return null;
}

console.log(checkForWinner());

Upvotes: -1

devdanke
devdanke

Reputation: 1620

A slight optimization for tic-tac-toe comes from knowing there can't be a winner until the 5th move. Therefore, if your game keeps a move count, you can reduce the number of times you check the entire board state.

Another optimization is knowing that, if your algorithm finds any row, column, or diagonal containing both an X and an O, then it can never be a winner. You don't need to check it again. You can eject those un-winnables from your search space.

A side effect of the above optimization, is that it may let you detect a draw sooner than waiting for the board to fill up, in cases where the search space becomes empty.

Upvotes: 0

Ali Ferhat
Ali Ferhat

Reputation: 2579

Here is the best, clever and optimal algorithm: (This is a well known trick, so I don't boast, only praise the algorithm)

Definitions: The cells are named as follows:

A31  A32  A33
A21  A22  A23
A11  A12  A13

The pieces are W(hite) or B(lack). There are 8 winning combinations: [A11,A12,A13], [A11,A21,A31], [A13,A22,A31] etc. Give each combination a name: C1..C8.: 

C1 =def= [A11,A12,A13]
C2 =def= [A21,A22,A23]
C3 =def= [A31,A32,A33]
C4 =def= [A11,A21,A31]
C5 =def= [A12,A22,A32]
C6 =def= [A13,A23,A33]
C7 =def= [A11,A22,A33]
C8 =def= [A13,A22,A31]

Define a mapping from cells to a set of winning combinations: 

A11 --> C1,C4,C7
A12 --> C1, C5
A22 --> C2, C5, C7, C8

etc.

So every cell A points to those combinations that has A in it.

Keep a set of possible winning combinations for both players. In the beginning both players have all 8 combinations. 

Poss_W = C1, C2, C3, C4, C5, C6, C7, C8
Poss_B = C1, C2, C3, C4, C5, C6, C7, C8

When W plays in a cell A, delete the corresponding winning combinations from B. For example when white plays A12, delete C1, C5 from Black's possible winning combinations list.

After the game ends, the player with a nonempty possible winning combinations set wins. If both Poss_W and Poss_B is empty, the game is a draw.

Upvotes: 3

Karoly Horvath
Karoly Horvath

Reputation: 96316

If you have to check after each step whether the game ended, you can cache the temporary results.

For each row, column, and diagonal store the number of marks for each player. Increment the appropriate values after each step. If the number is 3, you have a winner.

Upvotes: -1

xikkub
xikkub

Reputation: 1660

There's no way to determine a winner without checking the entire board state. If you want to perform the check at the end of each turn, iterate through each row, column, and both diagonals, checking for equality (ex: board[0][0] == board[1][0] == board[2][0] and so on). If you want to want to keep track of the board state while the tic-tac-toe game is being played, you can use dynamic programming, though it's major overkill. A dynamic approach would be useful if you're using abnormally large boards which would otherwise require a huge number of steps to find a winner. It's also worth noting that standard tic-tac-toe's are small enough that an efficient algorithm doesn't impact performance in the slightest.

Upvotes: -2

Shay
Shay

Reputation: 1000

An important lesson I recently (re-)learned: when the search space is small enough, just use brute force.

On a 3x3 board there are eight possible winning sequences (the rows, columns, and diagonals.) That gives you 24 comparisons to verify if one has the same player marking in all it cells. 24 comparisons take no time at all even on a very slow computer.

Upvotes: 14

akappa
akappa

Reputation: 10490

Just use a map diagonal -> number of checks in that diagonal.

When one of the entries is equal to three, you have a winner.

Upvotes: 2

Related Questions