|
|
Notes on Tic-Tac-Toe (Noughts and Crosses) | -- Fred Curtis |
[Normal 3 x 3 Tic-Tac-Toe] [2D Configuration counts] [3D 3 x 3 x 3 Tic-Tac-Toe] [Symmetries] [Source Code] [Chronology] [References] |
So, the questions arose:
|
|
|
Depth | No. of Configurations | 1.5GHz Pentium4 RH Linux 7.2 | |||||
---|---|---|---|---|---|---|---|
Estimated | Actual Total | Non-Terminal | Terminal | Run Time | CPU Time | Storage used | |
0 | 0 | 1 | (empty board) 1 | 0 | |||
1 | 1 | 4 | 4 | 0 | |||
2 | 14 | 31 | 31 | 0 | |||
3 | 183 | 254 | 254 | 0 | |||
4 | 2194 | 2512 | 2512 | 0 | |||
5 | 16819 | 17834 | 17459 | 375 | |||
6 | 123338 | 124162 | 121897 | 2265 | |||
7 | 647522 | 644288 | 600488 | 43800 | |||
8 | 3237609 | 3038859 | 2833234 | 205625 | 4m | 4m | |
9 | 12302916 | 11517172 | 9632913 | 1884259 | 15m | 15m | 0.1Gb |
10 | 44290496 | 37147332 | 31049722 | 6097610 | 1h01m | 57m | 0.5Gb |
11 | 125489739 | 104801129 | 72876736 | 31924393 | 3h15m | 3h03m | 1.2Gb |
12 | 334639305 | 231884196 | 160769332 | 71114864 | 7h24m | 6h53m | 2.3Gb |
13 | 717084225 | 486231284 | 257101228 | 229130056 | 15h22m | 14h19m | 4.0Gb |
14 | 1434168450 | 728803783 | 382334736 | 346469047 | 1d00h30m | 23h13m | 7.0Gb |
15 | 2330523731 | 1103946447 | 405190002 | 698756445 | 2d08h35m | 2d03h38m | 16.4Gb |
16 | 3495785597 | 1090187836 | 393304705 | 696883131 | 1d18h58m | 1d17h22m | 11.7Gb |
17 | 4272626841 | 1128648719 | 263805390 | 864843329 | 1d14h51m | 1d12h14m | 12.1Gb |
18 | 4747363156 | 700867318 | 158449550 | 542417768 | 16h49m | 15h31m | 8.0Gb |
19 | 4272626841 | 457435053 | 62552397 | 394882656 | 9h29m | 9h39m | 3.5Gb |
20 | 3418101473 | 165743273 | 21347314 | 144395959 | 3h01m | 2h53m | 1.6Gb |
21 | 2175155483 | 60903253 | 4409874 | 56493379 | 51m | 49m | 0.4Gb |
22 | 1186448445 | 11368950 | 741017 | 10627933 | 8m | 8m | 0.1Gb |
23 | 494353519 | 1976917 | 64592 | 1912325 | 1m | 1m | |
24 | 164784506 | 150672 | 3881 | 146791 | |||
25 | 38027194 | 8588 | 64 | 384 | |||
26 | 5850338 | 115 | 0 | 115 | |||
27 | 417881 | 0 | 0 | 0 |
Note on estimates - the number ways of arranging p1 pieces of player 1 and p2 pieces of player 2 in a board with n slots is: (number of ways of placing p1 pieces in n slots) * (number of ways of placing p2 pieces in remaining slots) = [n choose p1]*[(n-p1) choose p2) = [n!/(p1!*(n-p1)!)]*[(n-p1)!/(p2!*(n-p1-p2)!)] = n!/(p1!*p2!*(n-p1-p2)!). If we assume that almost none of these configurations has any self-symmetry (see Symmetries below), then we can divide by a factor of d!*2d where d is the number of dimensions. For a 3x3x3 board, the estimate for a given p1 and p2 is: 27!/(48*p1!*p2!*(n-p1-p2)!).
A d-dimensional cube has d!*2d distance-preserving symmetries. Imagine one corner of the cube placed at the origin in d-space, with d axes radiating from the origin. Now imagine the origin translated to one of the 2d corners. The d axes radiating from the new corner can be assigned in d! ways to the edges radiating from the new corner.
d | Number of symmetries |
---|---|
2 | 2!*22 = 2*4 = 8 |
3 | 3!*23 = 6*8 = 48 |
4 | 4!*24 = 24*16 = 384 |
|
|
|