

Notes on TicTacToe (Noughts and Crosses)   Fred Curtis 
[Normal 3 x 3 TicTacToe] [2D Configuration counts] [3D 3 x 3 x 3 TicTacToe] [Symmetries] [Source Code] [Chronology] [References] 
So, the questions arose:



Depth  No. of Configurations  1.5GHz Pentium4 RH Linux 7.2  

Estimated  Actual Total  NonTerminal  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 p_{1} pieces of player 1 and p_{2} pieces of player 2 in a board with n slots is: (number of ways of placing p_{1} pieces in n slots) * (number of ways of placing p_{2} pieces in remaining slots) = [n choose p_{1}]*[(np_{1}) choose p_{2}) = [n!/(p_{1}!*(np_{1})!)]*[(np_{1})!/(p_{2}!*(np_{1}p_{2})!)] = n!/(p_{1}!*p_{2}!*(np_{1}p_{2})!). If we assume that almost none of these configurations has any selfsymmetry (see Symmetries below), then we can divide by a factor of d!*2^{d} where d is the number of dimensions. For a 3x3x3 board, the estimate for a given p_{1} and p_{2} is: 27!/(48*p_{1}!*p_{2}!*(np_{1}p_{2})!).
A ddimensional cube has d!*2^{d} distancepreserving symmetries. Imagine one corner of the cube placed at the origin in dspace, with d axes radiating from the origin. Now imagine the origin translated to one of the 2^{d} 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!*2^{2} = 2*4 = 8 
3  3!*2^{3} = 6*8 = 48 
4  4!*2^{4} = 24*16 = 384 


