Perft(14) estimates thread

[sje]

Perft(14) estimates thread

66,000,000,000,000,000,000

[Ajedrecista]

Hello Steven:

I copy a link from other similar thread:

Perft(14) estimates

Those are old estimates that I collected in the past:

Code: Select all

61,803,489,628,662,504,195 by Joshua Haglund.

6.187e+19 by François Labelle.

6.18847822079403e+19 by Peter Österlund.

61,886,459,822,115,294,738 by myself.

6.188925e+19 by H.G.Muller.

6.19009592e+19 by Reinhard Scharnagl.

It is too soon for say something, but it looks like 6.188e+19 < Perft(14) < 6.189e+19. Let us wait and see.

Regards from Spain.

Ajedrecista.

[sje]

Thank you for the link.

I'm doing a few selections of perft(14). One present calculation is for perft(10) of
[d]rnbqkbnr/ppp2ppp/8/3pp3/3PP3/8/PPP2PPP/RNBQKBNR w KQkq - 0 3[/d]
The above was chosen as a guess of the largest draft(10) sub-result (of all 72,078 ply 4 unique positions) in the perft(14) calculation. I will post the result and a few others with the hope they will be independently verified.

All of Symbolic's transposition work uses 120 bit position signatures. For deep perft calculations, any hash codes with about 80 bits or less are too scary for me.

[ZirconiumX]

My Wild Ass Guess technique:

Perft(1) = 20
Perft(2) = 400 (x20)
Perft(3) = 8902 (x22.25)
Perft(4) = 197281 (x22.16) (down by .09)
Perft(5) = 4865609 (x24.66)
Perft(6) = 119060324 (x24.46) (down by .2)
Perft(7) = 3195901860 (x26.84)
Perft(8) = 84998978956 (x26.59) (down by .25)
Perft(9) = 2439530234167 (x28.70)
Perft(10) = 69352859712417 (x28.42) (down by .28)
Perft(11) = 2097651003696806 (x30.24)
Perft(12) = 62854969236701747 (x29.96) (down by .28)
Perft(13) = 1981066775000396239 (x31.51)

Perft(14) = 1981066775000396239 x (31.51-.28) =
61,868,715,383,262,374,543

At least according to GNU bc.

Matthew:out

[Ajedrecista]

Hello Matthew:

My Wild Ass Guess technique:

Perft(1) = 20
Perft(2) = 400 (x20)
Perft(3) = 8902 (x22.25)
Perft(4) = 197281 (x22.16) (down by .09)
Perft(5) = 4865609 (x24.66)
Perft(6) = 119060324 (x24.46) (down by .2)
Perft(7) = 3195901860 (x26.84)
Perft(8) = 84998978956 (x26.59) (down by .25)
Perft(9) = 2439530234167 (x28.70)
Perft(10) = 69352859712417 (x28.42) (down by .28)
Perft(11) = 2097651003696806 (x30.24)
Perft(12) = 62854969236701747 (x29.96) (down by .28)
Perft(13) = 1981066775000396239 (x31.51)

Perft(14) = 1981066775000396239 x (31.51-.28) =
61,868,715,383,262,374,543

At least according to GNU bc.

Matthew:out

It is good to see that more people do their estimates!

Estimating branching factors (BFs) of consecutive plies give more wrong results than if you estimate BFs of only odd plies or only even plies (in this case only even plies) if I am not wrong: it is due to something called odd-even effect IIRC.

I use a complicated polinomial fitting and more things to do my perft estimates (I was wrong in Perft(13) in around 0.03%). I expect to be wrong in less than 0.01% this time. It is too soon but I think that Peter's estimate is the best one, followed by my own estimate. You will be probably wrong in around 0.025% more less. Indeed I think that 31.236 < [Perft(14)]/[Perft(13)] < 31.24 being in the safe side. Let us wait and see.

It would be nice if Peter could provide updates of the current computation for estimating an approximated date of finish of the count.

Regards from Spain.

Ajedrecista.

[ZirconiumX]

Attempting to use even plies and 5 decimal places I get an answer that is waay off.

4,949,919,967,095,655,793

Using those Perft(14)/Perft(13) I get between 61,880,601,783,912,376,921 and 61,888,526,051,012,378,506.

Matthew:out

[ZirconiumX]

OK - EBFs of consecutive plies to 5 decimal places.

Perft(1) = 20
Perft(2) = 400 (x20)
Perft(3) = 8902 (x22.25500)
Perft(4) = 197281 (x22.16142) (down by .09358)
Perft(5) = 4865609 (x24.66334)
Perft(6) = 119060324 (x24.46977) (down by .19357)
Perft(7) = 3195901860 (x26.84271)
Perft(8) = 84998978956 (x26.59624) (down by .24647)
Perft(9) = 2439530234167 (x28.70070)
Perft(10) = 69352859712417 (x28.42878) (down by .27192)
Perft(11) = 2097651003696806 (x30.24606)
Perft(12) = 62854969236701747 (x29.96446) (down by .2816)
Perft(13) = 1981066775000396239 (x31.51806)

Perft(14) = 1981066775000396239 x (31.51-.2816) =
61,865,545,676,422,373,910

Again, using GNU bc. I may try to work out a line of best fit if I have the time.

Matthew:out

[Ajedrecista]

Hello again:

My method is far more complicated than only estimating BFs. I do lots of things (the good estimate starts at 'Own estimation:'). I did it in December, 2011 and I have just translated it quickly (it was written in Spanish):

Code: Select all

Perft(14) estimate:
-------------------

{Perft(0) = 1}

 Perft(1)	20
 Perft(2)	400
 Perft(3)	8,902
 Perft(4)	197,281
 Perft(5)	4,865,609
 Perft(6)	119,060,324
 Perft(7)	3,195,901,860
 Perft(8)	84,998,978,956
 Perft(9)	2,439,530,234,167
Perft(10)	69,352,859,712,417
Perft(11)	2,097,651,003,696,806
Perft(12)	62,854,969,236,701,747
Perft(13)	1,981,066,775,000,396,239

=========================================


	Estimate with Branching Factors:


I only use Branching Factors of even plies for avoiding the 'odd-even effect'.

BF(n) = [Perft(n)]/[Perft(n-1)]

Using Lagrange polinomials for interpolation:

[BF(14)]* = -BF(2) + 6·[BF(4) + BF(12)] - 15·[BF(6) + BF(10)] + 20·BF(8)

[BF(14)]* ~ 31.20194592760110701903111328617

[Perft(14)]* = [Perft(13)]·[BF(14)]* ~ 61813138392529471996.474237957537


			[Perft(14)]* ~ 61,813,138,392,529,471,996


=========================================


	Own estimation:


I define two provisional bounds [Perft'(n)] y [Perft"(n)]:


(n-2)·log[Perft'(n)]   (n-3)·log[Perft(n-1)]
____________________ = _____________________
 n·log[Perft(n-2)]     (n-1)·log[Perft(n-3)]


(n-3)·log[Perft"(n)]   (n-4)·log[Perft(n-1)]
____________________ = _____________________
 n·log[Perft(n-3)]     (n-1)·log[Perft(n-4)]


n = 6, 8, 10, 12 and 14.

I introduce a couple of parameters ß y ß' to be defined as follows:

	     [True Perft(n)] - (lower bound)
ß(n) = _________________________________
       (Geometric mean) - (lower bound)

	      [True Perft(n)] - (lower bound)
ß'(n) = _________________________________
	     (Arithmetic mean) - (lower bound)


Logically |ß(n)| > |ß'(n)|.

----------------------------------------

n = 6:

Perft'(6) ~ 117195628.69126660435006809820962
Perft"(6) ~ 131812282.31006907917506129585269

(Geometric mean) ~ 124289272.64474301871252199740585
(Arithmetic mean) ~ 124503955.5006678417625646970311

ß(6) ~ 0.26286846661081092703699139473544
ß'(6) ~ 0.25514667821568969151958679754055

----------------------------------------

n = 8:

Perft'(8) ~ 85448071072.696527647366788601596
Perft"(8) ~ 94286554952.913420579106782235894

(Geometric mean) ~ 89758588718.942393849420014645874
(Arithmetic mean) ~ 89867313012.80497411323678541874

ß(8) ~ -0.10418519387982387798752495688939
ß'(8) ~ -0.10162198014565074994859453052581

----------------------------------------

n = 10:

Perft'(10) ~ 70566039639018.724439241219749495
Perft"(10) ~ 76687869715314.067199418757683525

(Geometric mean) ~ 73563301000993.39648097445973928
(Arithmetic mean) ~ 73626954677166.395819329988716505

ß(10) ~ -0.40476280847341609135325416685804
ß'(10) ~ -0.39634550828169558329350700279514

----------------------------------------

n = 12:

Perft'(12) ~ 64357853234363528.789463136158867
Perft"(12) ~ 69071112659627391.736068618132372

(Geometric mean) ~ 66672847031475177.679584224329504
(Arithmetic mean) ~ 66714482946995460.262765877145615

ß(12) ~ -0.64919569095039774359150530679473
ß'(12) ~ -0.63772598198438680726618342308215

----------------------------------------

n = 14:

Perft'(14) ~ 63540359095620017443.137430353155
Perft"(14) ~ 67503078579525222377.754522031655

(Geometric mean) ~ 65491754084028687211.646630105519
(Arithmetic mean) ~ 65521718837572619910.4459761924

----------------------------------------

[ß(14)]* and [ß'(14)]* are estimated with two Lagrange polinomials:

[ß(14)]* = -ß(6) + 4·[ß(8) + ß(12)] - 6·ß(10)
[ß'(14)]* = -ß'(6) + 4·[ß'(8) + ß'(12)] - 6·ß'(10)

[ß(14)]* ~ -0.847815155091200865233587448319
[ß'(14)]* ~ -0.834465477045666420617656595198

----------------------------------------

I reach the following:

{Perft(14), [ß(14)]*}* = (lower bound) + {[ß(14)]*}·[(geometric mean) - (lower bound)]
{Perft(14), [ß'(14)]*}* = (lower bound) + {[ß'(14)]*}·[(arithmetic mean) - (lower bound)]

{Perft(14), [ß(14)]*}* ~ 61885936850878128968.649632013785
{Perft(14), [ß'(14)]*}* ~ 61886982793352460506.492528666782


		{Perft(14), [ß(14)]*}* ~ 61,885,936,850,878,128,969
		{Perft(14), [ß'(14)]*}* ~ 61,886,982,793,352,460,506


(Arithmetic mean of the last two estimates) ~ 61886459822115294737.571080340281
&#40;Arithmetic mean of the last two estimates&#41; = <P_14> ~ 61,886,459,822,115,294,738

&#40;Half-amplitude of the interval&#41; ~ 522971237165768.92144832650095139
&#40;Half-amplitude of the interval&#41; = |a| ~ 522,971,237,165,769

|a|/<P_14> ~ 8.450495288775327999269466739614e-6 ~ 0.0008450495288775327999269466739614%

I only used Windows calculator... I hope no typos. ß and ß' are parameters for correcting estimates and getting them more accurate.

I look it and I do not know how I came up with this mess!

Regards from Spain.

Ajedrecista.

[petero2]

It would be nice if Peter could provide updates of the current computation for estimating an approximated date of finish of the count.

My first estimate was this:

The perft 14 computation has now been running for about 18 hours and is 1.9% complete. If the current speed is representative for the whole computation, perft 14 will require about 40 days to complete.

Currently the computation has been running for 4.9 days and 12.7% of all perft(3) results have been computed. Extrapolation gives 38.5 days for the whole computation. The completion time can be delayed by at least three things though:

1. I may not be able to run 24/7 on all computers.

2. If there is a power outage (which is rare where I live, but it does happen occasionally), it will likely cause about 2 days of delay.

3. At the end of the computation it may not be possible to keep all three computers busy, which might cause a delay of 1-2 days.

Based on the above my current estimate is that the computation will be finished 2013-04-05.

[sje]

For the ply 4 position:
[d]rnbqkbnr/ppp2ppp/8/3pp3/3PP3/8/PPP2PPP/RNBQKBNR w KQkq - 0 3[/d]
The perft(10) is: 5,029,284,456,467,481

My suggestion here is that this is the largest perft(10) sub-result in the perft(14) calculation.

The raw output:

Code: Select all

[] df
rnbqkbnr/ppp2ppp/8/3pp3/3PP3/8/PPP2PPP/RNBQKBNR w KQkq - 0 3
[] emptran 10
Bb5+ 17,314,348,805,538
Bd2 139,611,278,955,576
Bc4 171,717,598,567,349
Ba6 138,815,134,645,006
Bd3 139,787,861,250,292
Be3 147,110,759,013,232
Be2 118,250,962,669,378
Bf4 167,146,121,596,558
Bg5 140,303,429,278,672
Ke2 83,100,201,274,885
Kd2 83,898,201,734,421
Bh6 134,323,072,429,890
Na3 128,060,580,632,892
Nd2 85,939,693,066,604
Ne2 78,044,880,771,139
Nc3 157,581,787,803,007
Nf3 122,974,270,899,116
Nh3 128,633,327,951,232
Qe2 124,647,347,044,033
Qd3 184,544,753,938,429
Qd2 132,009,205,132,385
Qf3 200,513,885,331,720
a3 126,330,747,530,766
Qg4 173,308,815,937,802
Qh5 164,447,753,692,978
a4 154,680,160,403,395
b3 137,188,459,581,242
b4 125,973,346,118,533
c3 141,605,375,087,568
f3 88,758,051,711,177
c4 143,360,866,458,867
exd5 149,197,709,622,931
dxe5 156,667,916,125,830
g3 140,383,170,798,272
f4 115,302,855,962,552
g4 108,079,800,048,565
h3 125,107,255,994,390
h4 154,563,468,601,259
Depth: 10   Count: 5,029,284,456,467,481   Elapsed: 349758  (1.43793e+10 Hz / 6.95442e-11 s)