Perft(14) estimates thread
Posted: Tue Feb 26, 2013 5:32 am
Perft(14) estimates thread
66,000,000,000,000,000,000
66,000,000,000,000,000,000
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 good to see that more people do their estimates!ZirconiumX wrote: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
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
(Arithmetic mean of the last two estimates) = <P_14> ~ 61,886,459,822,115,294,738
(Half-amplitude of the interval) ~ 522971237165768.92144832650095139
(Half-amplitude of the interval) = |a| ~ 522,971,237,165,769
|a|/<P_14> ~ 8.450495288775327999269466739614e-6 ~ 0.0008450495288775327999269466739614%
My first estimate was this:Ajedrecista wrote:It would be nice if Peter could provide updates of the current computation for estimating an approximated date of finish of the count.
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:petero2 wrote: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.
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)