TalkChess.com

Steven Edwards · 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

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

H.G.Muller · Joined: 10 Mar 2006 Posts: 12777 Location: Amsterdam

An improved estimate is:

Daniel Shawul · Joined: 14 Mar 2006 Posts: 2187 Location: Ethiopia

what did you do you ? Smile

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

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

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

Paul Byrne · Joined: 13 Jun 2011 Posts: 44

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)

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

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.