Last call for perft 13 estimates!
Moderators: hgm, Harvey Williamson, bob
Last call for perft 13 estimates!
The computation ended about an hour ago, but I'll wait a couple of days
to give folks a chance to post their estimates... or for someone to extract
them from the rather lengthy betting pool thread. :)
Total run time was about 5 days to compute the 85,375,278,064 different
positions at depth 10 and how often each occurs  this essentially
precomputing the transpositions. Plus 17 days and change to compute
the perft itself (perhaps 6 hours of work was lost due to two power
failures  both in the last 24 hours).
The work was done on a 6core Phenom 1090T with 8 GB of memory
(unfortunately the machine proved not quite stable with 16 GB).
I do plan to repeat the computation later this month with an updated
version of the code. Hopefully the numbers will match, which should
greatly reduce the possibility of machine error if not the possibility of
programmer stupidity. :)
paul
to give folks a chance to post their estimates... or for someone to extract
them from the rather lengthy betting pool thread. :)
Total run time was about 5 days to compute the 85,375,278,064 different
positions at depth 10 and how often each occurs  this essentially
precomputing the transpositions. Plus 17 days and change to compute
the perft itself (perhaps 6 hours of work was lost due to two power
failures  both in the last 24 hours).
The work was done on a 6core Phenom 1090T with 8 GB of memory
(unfortunately the machine proved not quite stable with 16 GB).
I do plan to repeat the computation later this month with an updated
version of the code. Hopefully the numbers will match, which should
greatly reduce the possibility of machine error if not the possibility of
programmer stupidity. :)
paul

 Posts: 672
 Joined: Tue May 22, 2007 9:13 am
Re: Last call for perft 13 estimates!
Is there a pseudocode example for the Monte Carlo type of perft simulation? The topic "Perft betting pool" takes 58 pages by now and it's hard to find a concrete implementation. I'm curious as to what algorithm has converged from that thread.ibid wrote:The computation ended about an hour ago, but I'll wait a couple of days
to give folks a chance to post their estimates... or for someone to extract
them from the rather lengthy betting pool thread.
Total run time was about 5 days to compute the 85,375,278,064 different
positions at depth 10 and how often each occurs  this essentially
precomputing the transpositions. Plus 17 days and change to compute
the perft itself (perhaps 6 hours of work was lost due to two power
failures  both in the last 24 hours).
The work was done on a 6core Phenom 1090T with 8 GB of memory
(unfortunately the machine proved not quite stable with 16 GB).
I do plan to repeat the computation later this month with an updated
version of the code. Hopefully the numbers will match, which should
greatly reduce the possibility of machine error if not the possibility of
programmer stupidity.
paul
Rein
 Ajedrecista
 Posts: 1361
 Joined: Wed Jul 13, 2011 7:04 pm
 Location: Madrid, Spain.
 Contact:
Re: Last call for perft 13 estimates!
Hello Paul!
I hope these results match with yours (I post them for verification purposes).
Now, giving my estimate I posted somewhere in this forum some months ago:
1,980,265,717,471,381,929 < [my Perft(13) estimate] < 1,980,670,474,119,967,566
I recall that my estimate is not based in computational algorithms (MonteCarlo, UCT or others), but is based in a polynomial adjust of my invention (nothing serious, of course). I know that giving all the numbers is painful for the eyes, so sorry.
Thank you very much for this great effort, also thanks to Steven (he will bring a whole verification) and the rest that had brought excellent ideas for estimating this number.
Regards from Spain.
Ajedrecista.
Those are great news! Congratulations. I was running Perft(11) of 1. f3, f6 position using JetChess and the result will be given ASAP (I hope in November or December...); but why 1. f3, f6 position? Because I think this one has the smallest number of nodes of all 400 possible positions with two plies played from the starting position (is it right, Paul?). As a little verification, I give the results of all Perft(10) I have calculated until today (it is impossible to me running the whole Perft(11) and I will sum all the 19 Perft(10) results of 1. f3, f6; 2. ...):ibid wrote:The computation ended about an hour ago, but I'll wait a couple of days
to give folks a chance to post their estimates... or for someone to extract
them from the rather lengthy betting pool thread.
Total run time was about 5 days to compute the 85,375,278,064 different
positions at depth 10 and how often each occurs  this essentially
precomputing the transpositions. Plus 17 days and change to compute
the perft itself (perhaps 6 hours of work was lost due to two power
failures  both in the last 24 hours).
The work was done on a 6core Phenom 1090T with 8 GB of memory
(unfortunately the machine proved not quite stable with 16 GB).
I do plan to repeat the computation later this month with an updated
version of the code. Hopefully the numbers will match, which should
greatly reduce the possibility of machine error if not the possibility of
programmer stupidity.
paul
Code: Select all
Perft(10) of 1. f3, f6; 2. ...
2. Na3 > 41,794,156,721,456
2. Nc3 > 55,573,541,056,355
2. Nh3 > 54,797,454,951,987
2. a3 > 35,534,716,982,746
2. a4 > 50,028,388,474,083
2. b3 > 47,346,825,745,074
2. b4 > 48,072,714,223,110
2. c3 > 55,581,388,282,559
2. c4 > 63,072,589,712,461
Now, giving my estimate I posted somewhere in this forum some months ago:
1,980,265,717,471,381,929 < [my Perft(13) estimate] < 1,980,670,474,119,967,566
I recall that my estimate is not based in computational algorithms (MonteCarlo, UCT or others), but is based in a polynomial adjust of my invention (nothing serious, of course). I know that giving all the numbers is painful for the eyes, so sorry.
Thank you very much for this great effort, also thanks to Steven (he will bring a whole verification) and the rest that had brought excellent ideas for estimating this number.
Regards from Spain.
Ajedrecista.
Re: Last call for perft 13 estimates!
Some engines implement a Monte Carlo perft. For example the latest version GNU Chess implements Peter Osterlund's algorithm.Is there a pseudocode example for the Monte Carlo type of perft simulation? The topic "Perft betting pool" takes 58 pages by now and it's hard to find a concrete implementation. I'm curious as to what algorithm has converged from that thread.
Note that is on a netbook so it is very slow.perftmc 13
m=1.983768e+18 sd=4.501236e+15 ci(99%)=[1.972173e+18,1.995363e+18] n=3568492 sdn=8.503039e+18 t=73.20s
m=1.983181e+18 sd=2.664379e+15 ci(99%)=[1.976317e+18,1.990044e+18] n=5352792 sdn=6.164335e+18 t=109.60s
Interrupted!
Re: Last call for perft 13 estimates!
In order to compute these large perft's as quickly as I do, I make a ratherAjedrecista wrote:Hello Paul!
Those are great news! Congratulations. I was running Perft(11) of 1. f3, f6 position using JetChess and the result will be given ASAP (I hope in November or December...); but why 1. f3, f6 position? Because I think this one has the smallest number of nodes of all 400 possible positions with two plies played from the starting position (is it right, Paul?). As a little verification, I give the results of all Perft(10) I have calculated until today (it is impossible to me running the whole Perft(11) and I will sum all the 19 Perft(10) results of 1. f3, f6; 2. ...):
I hope these results match with yours (I post them for verification purposes).Code: Select all
Perft(10) of 1. f3, f6; 2. ... 2. Na3 > 41,794,156,721,456 2. Nc3 > 55,573,541,056,355 2. Nh3 > 54,797,454,951,987 2. a3 > 35,534,716,982,746 2. a4 > 50,028,388,474,083 2. b3 > 47,346,825,745,074 2. b4 > 48,072,714,223,110 2. c3 > 55,581,388,282,559 2. c4 > 63,072,589,712,461
Ajedrecista.
large tradeoff: I compute the perft itself and nothing else. That is, the
program does not produce any breakdown by initial move(s). In this
sense Steven Edward's program is rather more useful as he will get a
complete breakdown up to 5 moves into the game. The only real
verification my result will get (I hope) is when Steven's program finishes
and we can compare the final perft. (OK, actually I computed perft 11 and
12 at the same time as perft 13 as a quick sanity check, but the fact that
these match known results doesn't really mean much.)
I can of course compute partial perft's directly like the previous depth 12
1. a3 result, but this becomes quite inefficient. That said, should Steven's
result not match mine, I will work through them this way to figure out
where the variance is.
paul
 Ajedrecista
 Posts: 1361
 Joined: Wed Jul 13, 2011 7:04 pm
 Location: Madrid, Spain.
 Contact:
Re: Last call for perft 13 estimates!
Hello Paul:
It is true! I forgot it, sorry. I compare my tiny results with Steven and not with you. In fact, when my (slow) Perft(11) count for 1. f3, f6 position will finish, it should be around 1.1e+15 or 1.2e+15 (more less), so it is less than 0.1% (almost insignificant) of whole Perft(13) result, which should be around 1.98e+18 or 1.981e+18 (according with several fine estimates).
Thank you very much for your great achievement. I suppose that Perft(14) (which I estimated it around 6.1861e+19 on August 4th, 2011) will wait some years.
Regards from Spain.
Ajedrecista.
It is true! I forgot it, sorry. I compare my tiny results with Steven and not with you. In fact, when my (slow) Perft(11) count for 1. f3, f6 position will finish, it should be around 1.1e+15 or 1.2e+15 (more less), so it is less than 0.1% (almost insignificant) of whole Perft(13) result, which should be around 1.98e+18 or 1.981e+18 (according with several fine estimates).
Thank you very much for your great achievement. I suppose that Perft(14) (which I estimated it around 6.1861e+19 on August 4th, 2011) will wait some years.
Regards from Spain.
Ajedrecista.
Re: Last call for perft 13 estimates!
Well actually... :) Computing it directly from the unique positions at 10 plyAjedrecista wrote:Thank you very much for your great achievement. I suppose that Perft(14) (which I estimated it around 6.1861e+19 on August 4th, 2011) will wait some years.
would take about a year and a half, which is a bit much at this point.
Going to the uniq positions at 11 ply would reduce the perft time by a
factor of 3 or so, but computing those 11 ply positions would currently
require many additional months of hard drive abusing work. The current
rewrite is to add some threading and disk caching to the uniq program.
The computation will still have to be done in about 15 parts (even with
compression, a 1 TB drive only holds so much), but the current time
estimate is about 8 months for perft 14 once the code is done.
Realistically it will no doubt take a good bit longer since I have other uses
for the machine, but it will be a good program to run when the machine is
otherwise idle.
paul
Re: Last call for perft 13 estimates!
I stick with my initial estimate:
http://talkchess.com/forum/viewtopic.ph ... 43&t=39678
1981075670675789312
http://talkchess.com/forum/viewtopic.ph ... 43&t=39678
1981075670675789312
Re: Last call for perft 13 estimates!
Turns out this is a very good estimate. :)petero2 wrote:I stick with my initial estimate:
http://talkchess.com/forum/viewtopic.ph ... 43&t=39678
1981075670675789312
1,981,066,775,000,396,239
So you are within 0.0005%...
paul
 Ajedrecista
 Posts: 1361
 Joined: Wed Jul 13, 2011 7:04 pm
 Location: Madrid, Spain.
 Contact:
Re: Last call for perft 13 estimates!
Hello:
Regards from Spain.
Ajedrecista.
Thank you very much for the final result! Peter's estimate is truly outstanding... no words come to my mind. Congratulations.ibid wrote:Turns out this is a very good estimate.petero2 wrote:I stick with my initial estimate:
http://talkchess.com/forum/viewtopic.ph ... 43&t=39678
1981075670675789312
1,981,066,775,000,396,239
So you are within 0.0005%...
paul
Regards from Spain.
Ajedrecista.