Perft(13) betting pool
Moderators: hgm, Rebel, chrisw
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
Re: Perft(13) & (14)
P.S.: I have corrected that first estimation in posting: http://www.talkchess.com/forum/viewtopi ... 49&t=39678
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Perft(13) & (14)
Hi Reinhard,smrf wrote:Hi Sven,Well, this is not a constant. It is the best value available for this level. This has been taken to be repeated for to interpolate/extrapolate results for higher plies.Sven Schüle wrote:... just curious: how did you come to the conclusion that the value "-2587,643803" for n=12 in the rightmost column of your second table (for even levels) could be seen as "constant" so that you could assume it as a base for all remaining calculations with n>12 ?
Despite of the different base value levels for even and odd plies both interpolations describe the same function, for which I presume the properties will converge. Therefore I "freely" took the last calculated inverse factor, not having anything better.
Nevertheless slightly changing that value at this outmost level will not have that big impact to the finally interpolated Perft13 or Perft14 result as you might expect.
actually it seems that the perft(13) estimate in your table is "almost independent" from that number "-2587,643803". Nearly always I get a result of approximately 1,98E+18 regardless whether I change that "-2587,..." number into -1000, +1000000000, or to -33333. The differences seem to affect the less significant digits beyond "1,98" only. I can't explain why, maybe you have an explanation?
Sven
-
- Posts: 173
- Joined: Sun May 11, 2008 7:43 am
Re: Perft(13) & (14)
I used the same methods as Julien Marcel (See page 2), but I took it a little further with a couple more calculations. Reversing the process arrived at the new data points.Ajedrecista wrote:Hello Joshua:
Your estimates are in the range of others I have seen here, so congratulations. Of all of these numbers, I only understand the number of plies (13 and 14), the estimates (1.9801...e+18 and 6.1803...e+19) and the branching factors (31.5031... and 31.2118...). What are the other numbers?jhaglund wrote:Since everyone is doing it. Here's perft 13 && 14:
[/size]Code: Select all
---- 13: 1,980,129,047,919,513,981 31.503142423993004168978123191565 1.257078852929608946962414133095 0.0036557068606018934960828966085374 0.001270444072415891627173672353 1.53868736167378627291822506431 0.28828426113381666238302199236626 0.976284002591335606776647463467 14: 61,803,489,628,662,504,195 31.211849396178658401366246283531 1.247394333859440505306348156281 0.003735340796412668778854450991
You can see an image here:
http://www.mediafire.com/?d420quf32c0r4mj
Joshua D. Haglund
Almost a month ago, Reinhard Scharnagl did estimates using inverse interpolation and the output of the results is similar to yours. I guess you have done one kind of interpolation or extrapolation, but could you confirm this, please? Thanks in advance.
Regards from Spain.
Ajedrecista.
The other numbers are differences and percentages of increases and decreases.
Bottom_line, I manually crunched numbers for 6 hours, on my "NASA" calculator. I guess I lost track of time or maybe time lost track of me? Both? I crunched so many numbers I might have time traveled.
Joshua D. Haglund
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Perft(13) & (14)
Hello Joshua:
I see, thanks for replying; until this momment, my estimates were usually the lowest of all here... but it has changed! It is very hard to find a serious estimate not starting by 1.980...e+18 or 1.981...e+18. If true Perft(13) value is among this range, then estimates will be a total success.
Regards from Spain.
Ajedrecista.
I see, thanks for replying; until this momment, my estimates were usually the lowest of all here... but it has changed! It is very hard to find a serious estimate not starting by 1.980...e+18 or 1.981...e+18. If true Perft(13) value is among this range, then estimates will be a total success.
Regards from Spain.
Ajedrecista.
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Perft(13) betting poll
Hello again:
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:
This means that the absolute error on whole Perft(13) estimates using quartic functions and Lagrange interpolation (when dividing into the first twenty moves and estimating BF's) is only 154,086,383 ~ 1.54e+8, which is ridiculous! I did not expected such a small absolute error between them, so if somebody knows why it happens, it will be very appreciated.
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.
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.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Perft(13) betting pool
The first draft 12 results should appear in mid October. The first of these will likely be for the opening moves 1 a3 and 1 Na3.
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
Re: Perft(13) & (14)
Hi Sven,
Regards, Reinhard.
well, here you are inside of an inverse interpolation. Thus, the bigger (abs value) an expression is, the smaller its impact to the left will be here.Sven Schüle wrote:... actually it seems that the perft(13) estimate in your table is "almost independent" from that number "-2587,643803". Nearly always I get a result of approximately 1,98E+18 regardless whether I change that "-2587,..." number into -1000, +1000000000, or to -33333. The differences seem to affect the less significant digits beyond "1,98" only. I can't explain why, maybe you have an explanation?
Regards, Reinhard.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Perft(13) betting poll
Well I am not sure if Daniel would agree but it seems that for chess perftI have seen that the topic is a little dead these days... maybe people is on holiday? Or there are not new ideas?
trees the longer you make the cycles the better you can make the
sd*sqrt(moveGen) metric.
This is already seen by the fact that fw=6 is better than fw=5 which itself is
better than fw=4.
You can interpolate somewhat smoothly between different fw's by doing
more than one Monte Carlo search at the tips of the fw tree.
So it seems that optimizing the sd*sqrt(moveGen) metric is not well defined.
It depends on how long you want to make the cycles (and also on how
much memory you can use). So in fact we are comparing apples and
oranges (as Daniel was saying in the beginning).
For me Peter1 remains the best compromise between simplicity of
implementation and results.
I am sure though that for artificial trees the adaptive
methods that have been discussed will have a decisive advantage
(Peter was saying for example that Peter1 performs very badly on heavily
LMR'ed trees).
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Perft(13) betting poll
Well I agree to some extent. My second addition i.e a MC layer with more than one move becomes closer to full width when more moves are considered. But doing one more full width ply is not a solution because it takes really long to generate enough samples. Imagine how much full width depth-7 takes compared to a 6-ply full width + 2-move MC perft. I would definitely choose the later.Michel wrote:Well I am not sure if Daniel would agree but it seems that for chess perftI have seen that the topic is a little dead these days... maybe people is on holiday? Or there are not new ideas?
trees the longer you make the cycles the better you can make the
sd*sqrt(moveGen) metric.
This is already seen by the fact that fw=6 is better than fw=5 which itself is
better than fw=4.
You can interpolate somewhat smoothly between different fw's by doing
more than one Monte Carlo search at the tips of the fw tree.
So it seems that optimizing the sd*sqrt(moveGen) metric is not well defined.
It depends on how long you want to make the cycles (and also on how
much memory you can use). So in fact we are comparing apples and
oranges (as Daniel was saying in the beginning).
Well obviously Peter1 looses in an apple-to-apple comparison if I just store the first 5 plies in memory and guide the search. My second improvement 2-move MC maybe debatable but is still a win when you don't have time to do the next full width ply.For me Peter1 remains the best compromise between simplicity of
implementation and results.
I don't remember Peter saying that but I have repeatedly said LMR and other _real_ (not artificial) trees are a problem to the Peter1 method. It was just a lucky combination that resulted in a better performance (almost uniform tree + inherent tree guiding with sub-tree node counts), which even escaped us until I did Peter vs HG Monte carlo tests. But even if we take out the tree part(supposedly the "hard" part) , Peter1 still gets beaten by the additional selective layer which btw HG's method failed to achieve even though it does something similar in essence. Also except for the tree growth full-width + selective_ply + MC are all in one function I used to have for the MC only. So mine is really simple too! If you are really in to simplicity, at least for the current competition a pure MC with one move, is a good candidate. The tree is very uniform so it matches the MC distribution. But if that was really the goal, then we shouldn't have started those discussions on improvements. Beauty is in the eye of the beholderI am sure though that for artificial trees the adaptive
methods that have been discussed will have a decisive advantage
(Peter was saying for example that Peter1 performs very badly on heavily
LMR'ed trees).
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Perft(13) betting poll
Hello:
To Steven: thanks for replying your estimates of when the first draft 12 result will appear. In view of some draft 11 results, I guess that the four first draft 12 will be a3, b3, Na3 and Nc3 (but not necessarily in this order). All chess community appreciate so much your effort running Perft(13) count. It would be nice that Paul Byrne also runs this for comparing results (according to him, once the count starts, it should end in a month or so):
http://talkchess.com/forum/viewtopic.ph ... 53&t=39678
To Michel: I suppose that increasing moveGen gives better result (less error). I also think that, regarding fw: 'the more the merrier' (altough I imagine that increasing fw has a cost in time, RAM, ... that few people can assume). For what I understood reading this topic, reduce sdn = sd·sqrt(moveGen) is preferable because, given an ammount of moveGen, less sdn means less sd (which is good) and less sd means less variance, and a 'measure' of efficiency you noted (variance · time) would be improved. But it seems difficult of optimize and here I can only say: 'good luck'.
Peter1 still resembles a star method in view of the comments of everybody, so congrats to Peter for bringing such a good idea. Sorry to read that Peter1 performs bad on heavily LMR's trees: I only know that LMR means 'Late Move Reductions' and they could be useful; despite this issue, Peter1 is still a great method. I have no clue about what could be artificial trees. I also do not know what are you referring about when you say adaptive methods. Maybe that do not chose moves uniformly? If I am right (near zero probability) I agree with you, just take a look on BF's: Perft(13)/Perft(12) will be slightly over 31.5, but not all the initial moves have this value of BF. I calculated the trend of percentages of each initial move and they evolve quite differently. According with my estimates, BF(e4) will be around 34 while BF(f3) will be near 28 (the rest of BF's should be between 28 and 34). So, chosing moves with probability = 1/32 works quite well but it could be improved a little (but I guess it is complex).
As you see, I have almost no clue about what you wrote, but I try to be useful as much as possible (i.e. 0.01%), here with BF's. Thanks for replying.
To everybody: I forgot to say that in my quartic functions: n = 2x + 5. But I have to be careful because different values of x gives different estimates (although not very different). It is not the same picking n = 2x + 5, or n = 2x + 1 (for example), or x = n, or x = ln(n), or for example n = ln(10x + 7)... adjusting with polynomials works fine but keeping in mind this 'scale issue' (for giving it a name) of the independent variable. Simply I have to chose reasonable values for x. And what are reasonable values? ... The ones I write before should be valid, they are countless.
Lagrange interpolation seems easier to me. Maybe the results were so close between them because the Lagrange polynomial I got has degree 4, the same as the quartic functions.
Regards from Spain.
Ajedrecista.
To Steven: thanks for replying your estimates of when the first draft 12 result will appear. In view of some draft 11 results, I guess that the four first draft 12 will be a3, b3, Na3 and Nc3 (but not necessarily in this order). All chess community appreciate so much your effort running Perft(13) count. It would be nice that Paul Byrne also runs this for comparing results (according to him, once the count starts, it should end in a month or so):
http://talkchess.com/forum/viewtopic.ph ... 53&t=39678
To Michel: I suppose that increasing moveGen gives better result (less error). I also think that, regarding fw: 'the more the merrier' (altough I imagine that increasing fw has a cost in time, RAM, ... that few people can assume). For what I understood reading this topic, reduce sdn = sd·sqrt(moveGen) is preferable because, given an ammount of moveGen, less sdn means less sd (which is good) and less sd means less variance, and a 'measure' of efficiency you noted (variance · time) would be improved. But it seems difficult of optimize and here I can only say: 'good luck'.
Peter1 still resembles a star method in view of the comments of everybody, so congrats to Peter for bringing such a good idea. Sorry to read that Peter1 performs bad on heavily LMR's trees: I only know that LMR means 'Late Move Reductions' and they could be useful; despite this issue, Peter1 is still a great method. I have no clue about what could be artificial trees. I also do not know what are you referring about when you say adaptive methods. Maybe that do not chose moves uniformly? If I am right (near zero probability) I agree with you, just take a look on BF's: Perft(13)/Perft(12) will be slightly over 31.5, but not all the initial moves have this value of BF. I calculated the trend of percentages of each initial move and they evolve quite differently. According with my estimates, BF(e4) will be around 34 while BF(f3) will be near 28 (the rest of BF's should be between 28 and 34). So, chosing moves with probability = 1/32 works quite well but it could be improved a little (but I guess it is complex).
As you see, I have almost no clue about what you wrote, but I try to be useful as much as possible (i.e. 0.01%), here with BF's. Thanks for replying.
To everybody: I forgot to say that in my quartic functions: n = 2x + 5. But I have to be careful because different values of x gives different estimates (although not very different). It is not the same picking n = 2x + 5, or n = 2x + 1 (for example), or x = n, or x = ln(n), or for example n = ln(10x + 7)... adjusting with polynomials works fine but keeping in mind this 'scale issue' (for giving it a name) of the independent variable. Simply I have to chose reasonable values for x. And what are reasonable values? ... The ones I write before should be valid, they are countless.
Lagrange interpolation seems easier to me. Maybe the results were so close between them because the Lagrange polynomial I got has degree 4, the same as the quartic functions.
Regards from Spain.
Ajedrecista.