I tried this time splitting perft values into the initial twenty moves again, but now using Lagrange polynomials:Ajedrecista wrote:Hi everybody:
Just for curiosity I tried the method of Adam Hair of adjusting odd BF's with polynomials:
http://talkchess.com/forum/viewtopic.ph ... 16&t=39678
In my case I adjusted with quartic functions (A·x^4 + B·x³ + C·x² + D·x + E) because I splitted in twenty different polynomials, one for each initial move. Firstly I did the calculations with Excel and the sum was around 1.98316e+18 (a little high from my point of view).
I suspected than roundings of Excel 'hurted' a little the estimations, so I adjusted again the twenty polynomials with the help of Derive 6, for getting more digits. I had reason this time, but the final sum is still 'high' in comparison with other computational methods that I have read here. Here are the numbers I got (hoping no errors when doing all the math):
Although the number is a little high IMO, I also think that the relative percentages of this estimate (for each move) are fairly good in view of the trend that each move follows when n grows (I calculated it in two Excel files on July). I wonder what would be the final sum when splitting in the initial moves, using for example Peter1 method with fw = 4 (which seems a star method), and compare the final sum and the counts of each move (also the relative percentages). I encourage everybody to run this, if possible (I do not know if Peter1 method allows splitting in initial moves; I hope yes because all the methods here seem very complete). Good luck.Code: Select all
Move Estimate a3 54,531,136,234,162,156 a4 79,063,508,502,158,903 b3 72,639,688,816,621,455 b4 73,709,067,003,701,511 c3 86,056,827,153,858,571 c4 97,970,589,000,615,670 d3 141,383,458,087,446,826 d4 213,018,757,033,778,459 e3 240,725,195,611,700,379 e4 246,589,794,037,145,382 f3 43,493,804,033,203,347 f4 61,162,666,611,330,980 g3 76,232,972,134,254,158 g4 65,814,044,230,043,052 h3 54,049,205,191,901,014 h4 80,829,651,636,234,054 Na3 63,795,543,395,998,863 Nc3 84,531,400,071,549,975 Nf3 82,344,973,694,923,533 Nh3 64,898,200,828,736,569 ------------------------------- SUM = 1,982,840,483,309,364,857
Regards from Spain.
Ajedrecista.
http://en.wikipedia.org/wiki/Lagrange_interpolation
I studied Lagrange polynomials before but I did not realise of use them. Taking into account branching factors in this way: BF(move_i, n) = [Perft(move_i, n)]/[Perft(move_i, n-1)] where n = 3, 5, 7, 9, 11. Then, for n = 13 I have:
[BF(move_i, n = 13)]* = BF(move_i, n = 3) - 5·BF(move_i, n = 5) + 10·BF(move_i, n = 7) - 10·BF(move_i, n = 9) + 5·BF(move_i, n = 11)
Where I extend move_i to all first posible twenty moves. And finally:
[Perft(move_i, n = 13)]* = [Perft(move_i, n = 12)] · [BF(move_i, n = 13)]*
I quote myself because the results are incredibly similar to the ones I got before, using twenty different quartic functions, one for estimating each BF. Note that here there is an only equation that estimates all BF's. Here are the numbers, hoping no typos:
Code: Select all
Move Estimate
a3 54,531,136,245,433,857
a4 79,063,508,508,444,871
b3 72,639,688,830,427,074
b4 73,709,067,010,541,664
c3 86,056,827,162,078,542
c4 97,970,589,005,764,498
d3 141,383,458,092,703,225
d4 213,018,757,047,938,236
e3 240,725,195,616,730,295
e4 246,589,794,029,993,095
f3 43,493,804,037,847,797
f4 61,162,666,623,173,938
g3 76,232,972,139,647,889
g4 65,814,044,240,929,760
h3 54,049,205,206,297,538
h4 80,829,651,642,814,500
Na3 63,795,543,402,742,775
Nc3 84,531,400,076,854,934
Nf3 82,344,973,704,170,665
Nh3 64,898,200,838,916,087
-------------------------------
SUM = 1,982,840,483,463,451,240
The estimates for each move_i are slightly greater when using Lagrange interpolation, except on 1.- e4, here is the only move that its estimate is slightly greater when using quartic functions. I do not know why. I still prefer my original estimate of (1.9804681 ± 0.0002024)e+18 with my own original (and imaginative) method (if it could be named in this way), and these two last estimates by mine should be understood as attempts, and not serious estimates. Remember that all my estimates were not computational ones, searching in the game tree, pruning moves or whatever else. I 'play' with numbers, trends... nothing scientifical, of course!
I have seen that the topic is a little dead these days... maybe people is on holiday? Or there are not new ideas? Maybe all that should be said is said? It is a pity because the topic was so good and instructive. Anyway, thanks for all people contributing here. I hope this thread will not be dead anymore.
Regards from Spain.
Ajedrecista.