Menu
I'm trying to build a tic tac toe game to demonstrate and experiment with machine learning algorithms, and i've found an interesting problem.
eg: a tic tac toe board can be mirrored, but for a machine learning purposes both these states are equivilent
x _ o o _ x
o o x = x o o
_ _ _ _ _ _
like-wise rotations
x _ o _ _ x _ _ _ o _ _
_ _ _ = _ _ _ = _ _ _ = _ _ _
_ _ _ _ _ o o _ x x _ _
finally, juxtapositions
x _ o o _ x
_ x _ = _ o _
_ _ x _ _ o
what is the best way to identify/count the unique states for tic tac toe?
is there a field of study or mathematics that I should look into ?
464
Minimax Algorithm is a decision rule formulated for 2 player zero-sum games (Tic-Tac-Toe, Chess, Go, etc.). This algorithm sees a few steps ahead and puts itself in the shoes of its opponent.
The key to the Minimax algorithm is a back and forth between the two players, where the player whose "turn it is" desires to pick the move with the maximum score. In turn, the scores for each of the available moves are determined by the opposing player deciding which of its available moves has the minimum score.
There are 362,880 possible move sequences.
When a player places a piece, update the corresponding row pair, column pair, and diagonal pairs (if on the diagonals). If any newly updated row, column, or diagonal pair equals either (n,0) or (0,n) then either A or B won, respectively.
The trick is to use Polyas enumeration theorem:
http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem
Ignoring the duplicates, there are 9 squares of 3 states (x, o and -), so there are 3^9 = 19683 configurations. You need to define the group which provides actions on the board. For your problem the Dihedral Group D4 seems to work for everything but the juxtapositions. But the juxtapositions are easy since there are 2 whenever it is not a board full of don't cares (all -, the initial configuration).
While the math lets us count the configurations, it doesn't help identify them. The perhaps simplest solution is to define a board as a tuple: {p1, p2, p3, ..., p9} where each pn is either {0,1,2}. It requires 2 bits per square and there are 9 of them for a total of 18 bits. A board hence can be represented by a 32bit integer or less.
Indexing into boards is easily done by a hash table. There are only the 19000 configurations, so it isn't going to kill us.
Running through all board configurations is best done on radix-3 arithmetic on the 9-tuple above: {0,0,9,...,0}, {0,0,0,..., 1}, {0,0,0,...,1,0} and so on. It is just addition with carry. This generates all boards. Notice how the group action and juxtaposition will transform such a number. There is a limited amount of possibilities (juxta shifts x to o and vice versa, the others moves around positions on the board according to the D4 group. There are 8 such transformations.) You can use Polya to make sure your algorithm got them all.
As suggested, picking the smallest guy from the set is a unique representant of the configuration modulo the actions.
129
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
