## Thursday, August 6, 2009

### Enumerated theory of tic-tac-toe

This post will just set up the problem I have in mind.

Symmetry plays an important role in tac-tac-toe. For example, there are only 3 first moves: center, corner, and side. (Let's say X plays first). We indicate the move by the square number (1-based indexing, for a change).

 `. . . X . . . X .. X . . . . . . .. . . . . . . . .5 1 2`

Starting from the center, there are 2 second moves, while from the corner or side, there are 5 second moves. That's because 16 = 18 and 12=14 and so on. A total of 12 positions:

 `. . . O . . . O .. X . . X . . X .. . . . . . . . .5 51 52-------------------------------------------X . . X O . X . O X . .. . . . . . . . . . O .. . . . . . . . . . . .1 12 13 15 X . . X . . . . O . . . . . . . . O 16 19-------------------------------------------. X . O X . . X . . X .. . . . . . O . . . O .. . . . . . . . . . . .2 21 24 25 . X . . X . . . . . . . O . . . O . 27 28`

I see that 12 and 21 look identical except that X and O are switched, but I will keep them distinct, to remember the difference in order of play between player 1 and player 2.

For the third move, it is still feasible to enumerate all the moves (although I'll admit it was quite tedious). Those starting positions with left-right (reflection) symmetry (51, 52, 15, 19, 25, 28) or rotational symmetry( ) have 4 additional possibilities. The rest have 7. We generate a total of 6 * 4 + 6 * 7 = 66 boards with 3 plays (but see below).

 `O . . O X . O . X O . . O . .. X . . X . . X . . X X . X .. . . . . . . . . . . . . . X51 512 513 516 519-------------------------------------------------------. O . X O . . O . . O . . O .. X . . X . X X . . X . . X .. . . . . . . . . X . . . X .52 521 524 527 528-------------------------------------------------------X O . X O X X O . X O . X O .. . . . . . X . . . X . . . X . . . . . . . . . . . . . . . 12 123 124 125 126 X O . X O . X O . . . . . . . . . . X . . . X . . . X 127 128 129-------------------------------------------------------X . O X X O X . O X . O X . O. . . . . . X . . . X . . . X . . . . . . . . . . . . . . . 13 132 134 135 136 X . O X . O X . O . . . . . . . . . X . . . X . . . X 137 138 139-------------------------------------------------------X . . X X . X . X X . . X . .. O . . O . . O . . O X . O .. . . . . . . . . . . . . . X15 152 153 156 159-------------------------------------------------------X . . X X . X . X X . . X . .. . O . . O . . O X . O . X O . . . . . . . . . . . . . . . 16 162 163 164 165 X . . X . . X . . . . O . . O . . O X . . . X . . . X 167 168 169-------------------------------------------------------X . . X X . X . X X . . X . .. . . . . . . . . . X . . . X. . O . . O . . O . . O . . O19 192 193 195 196-------------------------------------------------------O X . O X X O X . O X . O X .. . . . . . X . . . X . . . X . . . . . . . . . . . . . . .21 213 214 215 216 O X . O X . O X . . . . . . . . . . X . . . X . . . X 217 218 219-------------------------------------------------------. X . X X . . X X . X . . X .O . . O . . O . . O X . O . X . . . . . . . . . . . . . . .24 241 243 245 246 . X . . X . . X . O . . O . . O . . X . . . X . . . X 247 248 249-------------------------------------------------------. X . X X . . X . . X . . X .. O . . O . X O . . O . . O .. . . . . . . . . X . . . X .25 251 254 257 258-------------------------------------------------------. X . X X . . X X . X . . X .. . . . . . . . . X . . . X .O . . O . . O . . O . . O . .27 271 273 274 275 . X . . X . . X . . . X . . . . . . O . . O X . O . X 276 278 279-------------------------------------------------------. X . X X . . X . . X . . X .. . . . . . X . . . X . . . .. O . . 0 . . 0 . . 0 . X 0 .28 281 284 285 287`

As you probably have noticed, some of these are the same, just reflected or rotated. Just considering the 5.. series, I found six duplicates:

 `512 = 215513 = 135519 = 195521 = 125524 = 245528 = 285`

And notice that the other permutation is not the same, for example:

 `O X . O X . X X .. X . . X . . O .. . . . . . . . .512 215 125`

It only works if we switch X's, the first and third positions. We would have expected 132 = 231, but 231 is not in our list because 23 is the same as 21. I found two more:

 `152 = 251192 = 273`

So it looks like we have 66 - 8 = 58 unique positions.

From this point, there are 6! positions possible for each, neglecting the chance that some of these may be rotational isomers. So there is at most a total of 58 * 720 = 41760 possible positions, which is almost an order of magnitude less than 9! = 362880.

Actually, there are significantly fewer than that, since a number of the 3-mers force the next move by 'O' in order to block the win by 'X'. Also, some have symmetry, allowing only 3 possibilities instead of 6.

From the summary below (D = duplicate, S = symmetric, F = forced), I count 8 duplicates (removed), 23 forced moves (1 each), 9 with symmetry admitting 3 moves, and 1 with special symmetry (159) admitting only 2 moves. That leaves 66 - (8 + 23 + 9 + 1) = 66 - 41 = 25 with 6 possible moves. That's a total of 23 + 9 * 3 + 2 + 25 * 6 = 23 + 27 + 2 + 150 = 202 positions at the 4-mer stage. And some of these may be duplicates.

It's about now that I start begging for a simulation. I'll see what I can do.

 `Duplicate, Symmetric, Forced123 S124 F125 F126127 F128129 F132134 F135 F136137 F138139 F152153 S156159 S*162163164165167 S168169192 F193 F195 S196213214 S215 F216217218 F219 D241 F243 F245 F246247248 F249251 D254 S257258 S271 F273 F274275 F276278 F279 S281 F284285 S287512 D513 D516 F519 D521 D524 D527 F528 D`