Reducing TIC-TAC TOE State Space by using Symmetry in Artificial Intelligence

Question

Im learning Heuristics in AI.I see that for brute force search there are 9! states.But the textbook says that first 3 levels are reduced by symmetry.How does that work?

Answer 1

The position

x |  | 
__|__|__
  |  |
__|__|__
  |  |
  |  |

Is equivalent to

  |  | x 
__|__|__
  |  |
__|__|__
  |  |
  |  |

and

  |  | 
__|__|__
  |  |
__|__|__
  |  |
x |  |

and

  |  | 
__|__|__
  |  |
__|__|__
  |  |
  |  | x

So you don't have to look at each individual position, thus reducing the number of positions to analyse by a factor of $4$.

Answer 2

You can rotate or flip the board from any other configuration to match one of those three.

For example, if you moved in bottom center, flip the board from top to bottom to get the third configuration on the second row.

Or if you moved in the bottom right, you could rotate the board 180 degrees to get the first configuration in the second row.

Answer 3

There is another reduction in the third row, where there are two x's and one o. It is not important in which order the x's appear, so one can reduce by a factor of 2.