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.