No other news, so I'll talk more about estimating the number of unique legal positions (NULP). In
previous rough estimate I used the number of unique legal positions from 3x4, and the naively computed upper bound in both 3x4 and 4x4, under the assumption that the ratio in 4x4 is the same like in 3x4. Here I'll further refine that estimate.
This time we know the NULP for 2-to-10 pieces in 4x4, so we can use it for computing the overall estimate. First, let's look at 3x4 chess again. We know the NULP for each number of pieces on board (2 to 12). Let's compare it with the respective upper bound values, which is computed for N pieces as UB(N) = 40 * 10^(N-2) * C(10,N-2) (40 is the number of king placements):
Pieces NULP Upper bound Upper bound / NULP
2 20 40 2.0000
3 1,746 4,000 2.2910
4 69,556 180,000 2.5878
5 1,635,355 4,800,000 2.9351
6 25,117,392 84,000,000 3.3443
7 264,331,909 1,008,000,000 3.8134
8 1,936,519,455 8,400,000,000 4.3377
9 9,770,507,866 48,000,000,000 4.9127
10 32,535,116,698 180,000,000,000 5.5325
11 64,617,989,055 400,000,000,000 6.1902
12 58,151,957,864 400,000,000,000 6.8785
Looking at the ratios (UB/NULP) you can quickly see they grow quadratically:
2.0000 2.2910 2.5878 2.9351 3.3443 3.8134 4.3377 4.9127 5.5325 6.1902 6.8785
0.2910 0.2968 0.3473 0.4092 0.4691 0.5243 0.5750 0.6198 0.6577 0.6883
0.0058 0.0505 0.0619 0.0599 0.0552 0.0507 0.0448 0.0379 0.0306
Therefore we can try to see if 4x4 has the same quadratic growth, and if so, use it to predict the NULP in 4x4. We already know the NULP up to 10 pieces:
Pieces NULP
2 21
3 3,378
4 227,863
5 8,800,193
6 226,574,229
7 4,143,017,722
8 56,477,398,248
9 582,113,235,900
10 4,601,321,236,958
Upper bounds in 4x4 can be computed the same simple way: UB(N) = 78 * 10^(N-2) * C(14,N-2) (this time 78 king placements):
Pieces Upper bound
2 78
3 10,920
4 709,800
5 28,392,000
6 780,780,000
7 15,615,600,000
8 234,234,000,000
9 2,676,960,000,000
10 23,423,400,000,000
11 156,156,000,000,000
12 780,780,000,000,000
13 2,839,200,000,000,000
14 7,098,000,000,000,000
15 10,920,000,000,000,000
16 7,800,000,000,000,000
So the known UB/NULP ratios in 4x4 are:
Pieces Upper bound / NULP
2 3.7143
3 3.2327
4 3.1150
5 3.2263
6 3.4460
7 3.7691
8 4.1474
9 4.5987
10 5.0906
3.7143 3.2327 3.1150 3.2263 3.4460 3.7691 4.1474 4.5987 5.0906
-0.4816 -0.1177 0.1113 0.2197 0.3231 0.3783 0.4513 0.4919
0.3639 0.2290 0.1084 0.1034 0.0552 0.0730 0.0406
When using all numbers from 2 to 10 pieces, quadratic curve fits, but not very well, so I chose to skip the first two numbers, and use only 4-to-10 pieces for extrapolation.
First thing that is apparent is that contraty to my previous simple assumption, the UB/NULP ratio is not the same between 3x4 and 4x4. It is consistently larger in 4x4, even if not much, and the gap is widening when larger part of the board is occupied.
Quadratic curve gives quite decent fit (4 to 10 pieces), so I extrapolated to 16 pieces, getting these ratios:
Pieces Upper bound / NULP
11 5.721838
12 6.399510
13 7.152963
14 7.982198
15 8.887213
16 9.868010
Putting these ratios and the upper bounds together, NULP values are estimated as:
Pieces NULP
11 27,291,229,948,942
12 122,006,216,100,920
13 396,926,420,561,661
14 889,228,756,289,934
15 1,228,731,661,995,724
16 790,432,924,166,068
Summing all NULPs from 2 to 16 pieces, we obtain the overall estimated NULP as 3,459,861,499,557,761 = 3.460 peta-positions. Or 3.460 peta-bytes, if uncompressed database is stored with 1 byte for each position. This is smaller than previous estimate of 3.947 peta-positions, and probably close to the true number.
The estimated NULP (number of unique legal positions) in 4x4 chess is 20,680 times larger than the actual NULP in 3x4 chess.
EDIT: 2011-01-31: cleanup.