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 .
. . . . . . . . . . . . . . X
51 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 .
. . . . . . . . . . . . . . X
15 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 . . O
19 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 = 215
513 = 135
519 = 195
521 = 125
524 = 245
528 = 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 = 251
192 = 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, Forced
123 S
124 F
125 F
126
127 F
128
129 F
132
134 F
135 F
136
137 F
138
139 F
152
153 S
156
159 S*
162
163
164
165
167 S
168
169
192 F
193 F
195 S
196
213
214 S
215 F
216
217
218 F
219 D
241 F
243 F
245 F
246
247
248 F
249
251 D
254 S
257
258 S
271 F
273 F
274
275 F
276
278 F
279 S
281 F
284
285 S
287
512 D
513 D
516 F
519 D
521 D
524 D
527 F
528 D

No comments: