Last call for perft 13 estimates!

[ibid]

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]

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

[Ajedrecista]

Hello Paul!

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]

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]

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

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

[Ajedrecista]

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]

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]

I stick with my initial estimate:

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

1981075670675789312

[ibid]

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

[Ajedrecista]

Hello:

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.