TalkChess.com
Hosted by Your Move Chess & Games

 Perft(13) betting pool Goto page 1, 2, 3 ... 56, 57, 58  Next
Author Message
Steven Edwards

Joined: 13 Mar 2006
Posts: 3075
Location: Mud, Bugs, and Taxes, NH, USA

 Posted: Sun Jul 10, 2011 3:29 pm    Post subject: Perft(13) betting pool Place your estimate of perft(13) here so that it'll be easy to compare it with those of others when the actual value becomes known, probably sometime in early 2012. I'll stick with my 2*10^18 figure as I'm too lazy to improve it.
H.G.Muller

Joined: 10 Mar 2006
Posts: 12777
Location: Amsterdam

Posted: Sun Jul 10, 2011 4:36 pm    Post subject: Re: Perft(13) betting pool

OK, I am also lazy, so my guess is this:

 Code: hgm@hgm-laptop:~/qperft\$ ./fakeperft 13  - - - - - - - - - - - -  - - - - - - - - - - - -  - - r n b q k b n r - -  - - p p p p p p p p - -  - - . . . . . . . . - -  - - . . . . . . . . - -  - - . . . . . . . . - -  - - . . . . . . . . - -  - - P P P P P P P P - -  - - R N B Q K B N R - -  - - - - - - - - - - - -  - - - - - - - - - - - - Quick Perft by H.G. Muller Perft mode: No hashing, bulk counting in horizon nodes perft( 1)=                      20 ( 0.000 sec) perft( 2)=                     400 ( 0.000 sec) perft( 3)=                    8902 ( 0.000 sec) perft( 4)=                  197281 ( 0.010 sec) perft( 5)=                 4865609 ( 0.300 sec) perft( 6)= ca.           118935680 ( 0.750 sec) perft( 7)= ca.          3191629568 ( 1.510 sec) perft( 8)= ca.         84735868928 ( 2.760 sec) perft( 9)= ca.       2445589086208 ( 5.000 sec) perft(10)= ca.      69392470638592 ( 8.980 sec) perft(11)= ca.    2095210624450560 (16.570 sec) perft(12)= ca.   62829565818437632 (30.500 sec) perft(13)= ca. 1972589998431535104 (57.270 sec)
H.G.Muller

Joined: 10 Mar 2006
Posts: 12777
Location: Amsterdam

Posted: Sun Jul 10, 2011 5:33 pm    Post subject: Re: Perft(13) betting pool

An improved estimate is:

 Code: perft(13)= ca. 1978347153520590848 (912.710 sec)

But I guess for the official contest I will stick to the sub-minute value.
Daniel Shawul

Joined: 14 Mar 2006
Posts: 2187
Location: Ethiopia

 Posted: Sun Jul 10, 2011 6:32 pm    Post subject: Re: Perft(13) betting pool what did you do you ? My guess is you filled up the pst table with average number of moves from the perfts you _can_ calculate. I will try my luck with that if you didn't already use that.
H.G.Muller

Joined: 10 Mar 2006
Posts: 12777
Location: Amsterdam

 Posted: Sun Jul 10, 2011 6:48 pm    Post subject: Re: Perft(13) betting pool Just a Monte-Carlo sampling of the perft tree. After a certain ply (but not in horizon nodes) I only accept moves with the probability 1/N (i.e. I prune them with probability 1-1/N), and then multiply the total count by N for each ply where I do that. The results her use N=16. (In the supposedly more accurate one I started the pruning one level later.) This required me to only slip one extra if statement into qperft (for the pruning), and fiddle a bit with the final printing of the count.
Daniel Shawul

Joined: 14 Mar 2006
Posts: 2187
Location: Ethiopia

 Posted: Sun Jul 10, 2011 6:58 pm    Post subject: Re: Perft(13) betting pool I see. So you did an artifical reduction of the branching factor first and then correct the result (similar to progressive widening i think). I will try with estimating the branching factor on a per move basis. The problem with the opening position is that the branching factor increases rapidly so I am not sure it will be a good estimate..
H.G.Muller

Joined: 10 Mar 2006
Posts: 12777
Location: Amsterdam

Posted: Sun Jul 10, 2011 8:56 pm    Post subject: Re: Perft(13) betting pool

 Code: perft( 1)=    2.000000e+01 ( 0.000 sec)       -nan perft( 2)=    4.000000e+02 ( 0.000 sec)   0.000000 perft( 3)=    8.902000e+03 ( 0.000 sec)   0.000000 perft( 4)=    1.972810e+05 ( 0.010 sec)   0.000000 perft( 5)=    4.865609e+06 ( 0.300 sec)   0.000000 perft( 6)= ca.1.191103e+08 ( 0.910 sec)  14.981951 perft( 7)= ca.3.193653e+09 ( 1.900 sec)  15.016684 perft( 8)= ca.8.500709e+10 ( 3.590 sec)  15.006076 perft( 9)= ca.2.439202e+12 ( 6.440 sec)  14.990016 perft(10)= ca.6.939898e+13 (11.690 sec)  14.993228 perft(11)= ca.2.097027e+15 (21.220 sec)  15.010978 perft(12)= ca.6.284901e+16 (39.290 sec)  14.996416 perft(13)= ca.1.979269e+18 (74.120 sec)  14.995501

I correct the values a little bit to increase the accuracy, by counting at each level how many moves are accepted, and how many are pruned. As this is randomly decided on a per-move basis, it is never exactly 1/16 of the moves that is searched. So now I multiply the final count by the actual number, rather than 16. This shouldproduce a significant reduction of the standard deviation (at the expenseof a 25% slowdown).

So my bet is now on 1.979269e+18 .
Paul Byrne

Joined: 13 Jun 2011
Posts: 44

 Posted: Mon Jul 11, 2011 6:46 am    Post subject: Re: Perft(13) betting pool Hmmm. Lemme think about this for a month or so and I'll have an "estimate" for you. :) Seriously though, an update on the other perft 13 project... I have finished computing the unique positions at 10 ply: 85,375,278,064 matching François Labelle's result at http://wismuth.com/chess/statistics-positions.html -- we also agree on the number of uniquely realizable positions. For those keeping score, the most frequent position at 10 ply is just the position after 1. e4 e5, which is reached in 1,126,591 different 10 ply lines. I have just finished recomputing perft 12 as a sanity check, and obtained the correct result in 85326 seconds -- just short of a day. I have another project I'd like to run on the machine over the next couple of days before I give it over to perft 13, but once it gets started it should finish in about a month. -paul
Julien MARCEL

Joined: 05 May 2008
Posts: 2270
Location: Nantes (France)

 Posted: Mon Jul 11, 2011 7:57 am    Post subject: Re: Perft(13) betting pool My bet: 1,953,532,443,876,690,000_________________ Author of Prédateur chess engine: http://predateur-chess.blogspot.fr
Daniel Shawul

Joined: 14 Mar 2006
Posts: 2187
Location: Ethiopia

 Posted: Mon Jul 11, 2011 12:41 pm    Post subject: Re: Perft(13) betting pool Well EBF method sucks as expected. EBF10 = 24.1139 EBF11 = 24.6177 +0.5038 EBF12 = 25.0257 +0.408 EBF13 = 25.3379 +0.3122 Assuming same amount of reduction So perft(13) = 2*10^18 Probably an upper bound though? .... I will improve in the coming month.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMTGoto page 1, 2, 3 ... 56, 57, 58  Next Page 1 of 58

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum