局面数の推定
モンテカルロ-黒石ゲームにより算出された「盤面の石が全て繋がっている割合」を
使用し、オセロゲームの概算局面数を算出する。
Transpositionを考慮した場合の計算ノードは
局面数×その局面の着手数(平均10くらい?)になると思われる。
ただしTranspositionを考慮する場合は盤面を記憶する為に使用メモリ量の問題がある。
繋がり数・繋がり割合:「
モンテカルロ-黒石ゲーム」による。
石の分布 :中央4石を除いた(n-4)個の石を60マスに配置するパターン数
(B)=60!/(64-n)!/(n-4)!
白黒の分布 :n個の石の白黒のパターン数 (C)=2^n
推定の局面数 :(A)繋がり割合×(B)石の分布×(C)白黒の分布
石数 |
繋がり数 |
繋がり割合(A) |
石の分布(B) |
白黒の分布(C) |
(A)×(B)×(C) |
04 |
100000000 |
1.00000000 |
1 |
16 |
16 |
05 |
20004603 |
0.20004603 |
60 |
32 |
384.1 |
06 |
6210528 |
0.06210528 |
1770 |
64 |
7035.3 |
07 |
2651252 |
0.02651252 |
34220 |
128 |
116129.1 |
08 |
1373670 |
0.01373670 |
487635 |
256 |
1714814.9 |
09 |
819711 |
0.00819711 |
5461512 |
512 |
22921530.7 |
10 |
550860 |
0.00550860 |
50063860 |
1024 |
282400541.9 |
11 |
409994 |
0.00409994 |
386206920 |
2048 |
3242854809 |
12 |
334110 |
0.00334110 |
2558620845 |
4096 |
35015098799 |
13 |
293219 |
0.00293219 |
14783142660 |
8192 |
3.550985E+11 |
14 |
275577 |
0.00275577 |
75394027566 |
16384 |
3.404081E+12 |
15 |
274856 |
0.00274856 |
3.427001E+11 |
32768 |
3.086522E+13 |
16 |
288436 |
0.00288436 |
1.399359E+12 |
65536 |
2.645200E+14 |
17 |
319226 |
0.00319226 |
5.166863E+12 |
131072 |
2.161898E+15 |
18 |
366211 |
0.00366211 |
1.734590E+13 |
262144 |
1.665207E+16 |
19 |
438863 |
0.00438863 |
5.319409E+13 |
524288 |
1.223946E+17 |
20 |
541043 |
0.00541043 |
1.496084E+14 |
1048576 |
8.487653E+17 |
21 |
685458 |
0.00685458 |
3.872217E+14 |
2097152 |
5.566349E+18 |
22 |
887912 |
0.00887912 |
9.250296E+14 |
4194304 |
3.444970E+19 |
23 |
1172044 |
0.01172044 |
2.044802E+15 |
8388608 |
2.010412E+20 |
24 |
1570317 |
0.01570317 |
4.191845E+15 |
16777216 |
1.104364E+21 |
25 |
2116421 |
0.02116421 |
7.984466E+15 |
33554432 |
5.670193E+21 |
26 |
2872332 |
0.02872332 |
1.415428E+16 |
67108864 |
2.728364E+22 |
27 |
3894667 |
0.03894667 |
2.338533E+16 |
134217728 |
1.222429E+23 |
28 |
5264660 |
0.05264660 |
3.605239E+16 |
268435456 |
5.095001E+23 |
29 |
7050834 |
0.07050834 |
5.191544E+16 |
536870912 |
1.965201E+24 |
30 |
9336923 |
0.09336923 |
6.988617E+16 |
1073741824 |
7.006399E+24 |
31 |
12179195 |
0.12179195 |
8.800480E+16 |
2147483648 |
2.301732E+25 |
32 |
15633886 |
0.15633886 |
1.037199E+17 |
4294967296 |
6.964486E+25 |
33 |
19680715 |
0.19680715 |
1.144496E+17 |
8589934592 |
1.934840E+26 |
34 |
24317934 |
0.24317934 |
1.182646E+17 |
17179869184 |
4.940845E+26 |
35 |
29471336 |
0.29471336 |
1.144496E+17 |
34359738368 |
1.158948E+27 |
36 |
35017182 |
0.35017182 |
1.037199E+17 |
68719476736 |
2.495878E+27 |
37 |
40821327 |
0.40821327 |
8.800480E+16 |
1.37439E+11 |
4.937457E+27 |
38 |
46750848 |
0.46750848 |
6.988617E+16 |
2.74878E+11 |
8.980914E+27 |
39 |
52651937 |
0.52651937 |
5.191544E+16 |
5.49756E+11 |
1.502729E+28 |
40 |
58404984 |
0.58404984 |
3.605239E+16 |
1.09951E+12 |
2.315175E+28 |
41 |
63888325 |
0.63888325 |
2.338533E+16 |
2.19902E+12 |
3.285450E+28 |
42 |
68996804 |
0.68996804 |
1.415428E+16 |
4.39805E+12 |
4.295133E+28 |
43 |
73701036 |
0.73701036 |
7.984466E+15 |
8.79609E+12 |
5.176179E+28 |
44 |
77953716 |
0.77953716 |
4.191845E+15 |
1.75922E+13 |
5.748596E+28 |
45 |
81729772 |
0.81729772 |
2.044802E+15 |
3.51844E+13 |
5.880055E+28 |
46 |
85045279 |
0.85045279 |
9.250296E+14 |
7.03687E+13 |
5.535867E+28 |
47 |
87919676 |
0.87919676 |
3.872217E+14 |
1.40737E+14 |
4.791324E+28 |
48 |
90366672 |
0.90366672 |
1.496084E+14 |
2.81475E+14 |
3.805432E+28 |
49 |
92437727 |
0.92437727 |
5.319409E+13 |
5.6295E+14 |
2.768104E+28 |
50 |
94154061 |
0.94154061 |
1.734590E+13 |
1.1259E+15 |
1.838805E+28 |
51 |
95564790 |
0.95564790 |
5.166863E+12 |
2.2518E+15 |
1.111872E+28 |
52 |
96707124 |
0.96707124 |
1.399359E+12 |
4.5036E+15 |
6.094630E+27 |
53 |
97610648 |
0.97610648 |
3.427001E+11 |
9.0072E+15 |
3.013015E+27 |
54 |
98321752 |
0.98321752 |
75394027566 |
1.80144E+16 |
1.335384E+27 |
55 |
98860597 |
0.98860597 |
14783142660 |
3.60288E+16 |
5.265502E+26 |
56 |
99264703 |
0.99264703 |
2558620845 |
7.20576E+16 |
1.830124E+26 |
57 |
99553725 |
0.99553725 |
386206920 |
1.44115E+17 |
5.540989E+25 |
58 |
99750832 |
0.99750832 |
50063860 |
2.8823E+17 |
1.439397E+25 |
59 |
99878366 |
0.99878366 |
5461512 |
5.76461E+17 |
3.144518E+24 |
60 |
99952473 |
0.99952473 |
487635 |
1.15292E+18 |
5.619377E+23 |
61 |
99988318 |
0.99988318 |
34220 |
2.30584E+18 |
7.889673E+22 |
62 |
100000000 |
1.00000000 |
1770 |
4.61169E+18 |
8.162684E+21 |
63 |
100000000 |
1.00000000 |
60 |
9.22337E+18 |
5.534023E+20 |
64 |
100000000 |
1.00000000 |
1 |
1.84467E+19 |
1.844674E+19 |
|
|
|
|
|
|
|合計| | | | | 5.10136E+29|
@wikiへ
最終更新:2007年12月09日 22:44