Last call for perft 13 estimates!

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

ibid
Posts: 88
Joined: Mon Jun 13, 2011 10:09 am

Last call for perft 13 estimates!

Post by ibid » Tue Nov 08, 2011 10:38 pm

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
pre-computing 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 6-core 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 Halbersma
Posts: 672
Joined: Tue May 22, 2007 9:13 am

Re: Last call for perft 13 estimates!

Post by Rein Halbersma » Wed Nov 09, 2011 8:02 am

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
pre-computing 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 6-core 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
Is there a pseudo-code 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.

-Rein

User avatar
Ajedrecista
Posts: 1361
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Last call for perft 13 estimates!

Post by Ajedrecista » Wed Nov 09, 2011 12:00 pm

Hello Paul!
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
pre-computing 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 6-core 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
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.- ...):

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
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.

Michel
Posts: 1960
Joined: Sun Sep 28, 2008 11:50 pm

Re: Last call for perft 13 estimates!

Post by Michel » Wed Nov 09, 2011 12:22 pm

Is there a pseudo-code 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.
Some engines implement a Monte Carlo perft. For example the latest version GNU Chess implements Peter Osterlund's algorithm.
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!
Note that is on a netbook so it is very slow.

ibid
Posts: 88
Joined: Mon Jun 13, 2011 10:09 am

Re: Last call for perft 13 estimates!

Post by ibid » Wed Nov 09, 2011 3:08 pm

Ajedrecista 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.- ...):

Code: Select all

Perft&#40;10&#41; 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
I hope these results match with yours (I post them for verification purposes).

Ajedrecista.
In order to compute these large perft's as quickly as I do, I make a rather
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

User avatar
Ajedrecista
Posts: 1361
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Last call for perft 13 estimates!

Post by Ajedrecista » Wed Nov 09, 2011 3:24 pm

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.

ibid
Posts: 88
Joined: Mon Jun 13, 2011 10:09 am

Re: Last call for perft 13 estimates!

Post by ibid » Wed Nov 09, 2011 3:48 pm

Ajedrecista 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.
Well actually... :) Computing it directly from the unique positions at 10 ply
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

petero2
Posts: 559
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

Re: Last call for perft 13 estimates!

Post by petero2 » Wed Nov 09, 2011 11:25 pm

I stick with my initial estimate:

http://talkchess.com/forum/viewtopic.ph ... 43&t=39678

1981075670675789312

ibid
Posts: 88
Joined: Mon Jun 13, 2011 10:09 am

Re: Last call for perft 13 estimates!

Post by ibid » Thu Nov 10, 2011 11:25 pm

petero2 wrote:I stick with my initial estimate:

http://talkchess.com/forum/viewtopic.ph ... 43&t=39678

1981075670675789312
Turns out this is a very good estimate. :)

1,981,066,775,000,396,239

So you are within 0.0005%...

-paul

User avatar
Ajedrecista
Posts: 1361
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Last call for perft 13 estimates!

Post by Ajedrecista » Fri Nov 11, 2011 10:59 am

Hello:
ibid wrote:
petero2 wrote:I stick with my initial estimate:

http://talkchess.com/forum/viewtopic.ph ... 43&t=39678

1981075670675789312
Turns out this is a very good estimate. :)

1,981,066,775,000,396,239

So you are within 0.0005%...

-paul
Thank you very much for the final result! Peter's estimate is truly outstanding... no words come to my mind. Congratulations.

Regards from Spain.

Ajedrecista.

Post Reply