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

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?

• Rotational symmetry here. Notice that X in the top left is the same as X in any corner (at this stage) – Alec Teal Aug 27 '15 at 8:51
• okay.. i get it. – techno Aug 27 '15 at 8:52
• why question is downvoted. – techno Aug 27 '15 at 8:54
• it may be because of the low picture quality. I don't know, I think the question is fine as is. – 5xum Aug 27 '15 at 8:55
• Because you've shown no effort at understanding it yourself, and it's really simple. You can see that there are 9 places X can go, yet 3 are shown and didn't see the pattern. – Alec Teal Aug 27 '15 at 8:55

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$.

• What's with the downvote? – 5xum Aug 27 '15 at 8:53
• i only upvoted.. my question is also downvoted. – techno Aug 27 '15 at 8:54
• @techno I am not accusing you, but I would like the downvoter to explain how my answer is bad and needs a downvote. – 5xum Aug 27 '15 at 8:55
• yeah .. i know.. just sayin my part :) – techno Aug 27 '15 at 8:55

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.

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.

• okay.. thanks.. – techno Aug 27 '15 at 9:16