I had to modify the "perft estimation" functionality of KnockOut to be able to deal correctly with arbitrary positions, initially there were some hard-coded hacks suitable for the starting position only. I also made some other improvements, one of them being fully legal move generation, currently used exclusively for perft-like processing. Other speedups were minor.sje wrote:Here's another piece of perft(13):
(diagram) rnbqkbnr/1ppppppp/p7/8/8/2NP4/PPP1PPPP/R1BQKBNR b KQkq - 0 2
The perft(10) for the above is 165,358,518,306,919. How well does your estimator algorithm do with this?
Now I get these results for the position above, still with the method as defined by Uri Blass:
Code: Select all
Your move: uperft 6
u[ 1] = 19
u[ 2] = 28
u[ 3] = 30
u[ 4] = 36
u[ 5] = 46
u[ 6] = 50
time = 0:00:39.25
Your move: uperftr 10 1000000
u[ 1] = 19
u[ 2] = 28
u[ 3] = 30
u[ 4] = 36
u[ 5] = 46
u[ 6] = 50
u[ 7] = 52
u[ 8] = 56
u[ 9] = 54
u[10] = 59
time = 0:00:44.25
Your move: setu 19 28 30 36 46 50 52 56 54 59
Your move: randgame 10 1000000
estimated perft(10) after 1000000 random games (13539 legal) = 165991922206516
time = 0:00:20.92
Your move: randgame 10 2000000
estimated perft(10) after 2000000 random games (27192 legal) = 166690758129832
time = 0:00:42.47
Your move: randgame 10 4000000
estimated perft(10) after 4000000 random games (54272 legal) = 166347470307852
time = 0:01:24.18
Your move: randgame 10 8000000
estimated perft(10) after 8000000 random games (108471 legal) = 166235595258725
time = 0:02:46.91
Your move: randgame 10 16000000
estimated perft(10) after 16000000 random games (215804 legal) = 165363582889500
time = 0:05:34.83
Your move: randgame 10 32000000
estimated perft(10) after 32000000 random games (432648 legal) = 165762041968583
time = 0:11:09.29
Your move: randgame 10 64000000
estimated perft(10) after 64000000 random games (864346 legal) = 165580053446887
time = 0:22:32.01
Code: Select all
165,991,922,206,516 1,000,000 0.383%
166,690,758,129,832 2,000,000 0.806%
166,347,470,307,852 4,000,000 0.598%
166,235,595,258,725 8,000,000 0.530%
165,363,582,889,500 16,000,000 0.003%
165,762,041,968,583 32,000,000 0.244%
165,580,053,446,887 64,000,000 0.134%
"uperft" calculates the exact perft(1) upper bounds for K plies.
"uperftr" estimates these by finding lower bounds for them, playing random games.
"randgame" uses the (calculated or estimated) perft(1) upper bounds to estimate perft(N) with the formula "(nLegalGames / nTotalGames) * u(1) * u(2) * ... * u(N)", also by playing random games.
It seems this method has been heavily improved by Peter Österlund and others but I think it is still interesting to see how other methods perform against the current "leader".
EDIT: Just a note, I did not take the time to repeat these measurements several times and calculate the variance. The numbers given above are just a "snapshot". But at least some kind of "closeness" to the real value can be seen there.
Sven