Optimal algorithm for finding out who won the game with tick-tock

I have a ready-made tic tac toe game board. It's 3 x 3. I'm not really asking for the code (although it helps), but what algorithms would be the best to see who won? Another way of expressing this would be what algorithms should I research, what would be helpful to see who won?

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


source to share

5 answers

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

There are eight possible winning sequences (rows, columns, and diagonals) on a 3x3 board. This gives you 24 comparisons to check if the same marker has the same marker across all cells. 24 comparisons take no time even on a very slow computer.



Here is the best , smart and optimal algorithm: (This is a well-known trick, so I'm not bragging, only praising the algorithm)

Definitions . The cells are named as follows:

A31  A32  A33
A21  A22  A23
A11  A12  A13


Pieces of W (hite) or B (flaw). 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 the mapping from cells to a set of winning combinations:

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


and etc.

Thus, each cell A points to those combinations that contain A.

Keep a set of possible winning combinations for both players. At 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 cell A, remove the corresponding winning combinations from B. For example, when White plays A12, remove C1, C5 from the list of possible winning combinations.

After the end of the game, the player with non-empty possible winning combinations wins. If both Poss_W and Poss_B are empty, the game is a draw.



Just use the card diagonal -> number of checks in that diagonal


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



If you need to check after each step if the game is over, you can cache the temporary results.

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



It is impossible to determine the winner without checking the entire board condition. If you want to check at the end of each move, traverse each row, column, and both diagonals, checking for equality (eg: board[0][0] == board[1][0] == board[2][0]

etc.). If you want to keep track of the state of the board while playing with ticks, you can use dynamic programming although this is a lot of overkill. A dynamic approach would be helpful if you are using abnormally large boards that would otherwise require a huge number of steps to find a winner. It is also worth noting that the standard tic-tac-toe is small enough that an efficient algorithm does not affect performance in the least.



All Articles