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
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.
source to share
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.
source to share
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.
source to share