What is the best known speed of move generation?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
kcc

What is the best known speed of move generation?

Post by kcc » Fri Oct 12, 2007 4:51 pm

Dear computer chess experts,

I am wondering, what is the best known speed of move generation (one thread, no transposition table, etc)?
E.g. simply measured by perft().

On my c2d@2.4GHz, crafty (I've downloaded the most recent 64-bit binary for linux) gives ~19M nodes per second.

Code: Select all

White(1): perft 6
total moves=119060324  time= 6.29
White(1): perft 7
total moves=3195901860  time=167.37
(can't measure for 8 plies, there seem to be an overflow)

With my own engine I get 24M nps on the same machine (the algorithm is similar to the http://www.cis.uab.edu/hyatt/bitmaps.html, section 2)

Code: Select all

d=1     n=20    t=0     ratio=inf
d=2     n=400   t=0     ratio=inf
d=3     n=8902  t=0     ratio=inf
d=4     n=197281        t=0     ratio=inf
d=5     n=4865609       t=0.2   ratio=2.4328e+07
d=6     n=119060324     t=4.92  ratio=2.41993e+07
d=7     n=3195901860    t=131   ratio= 2.43962e+07
d=8     n=84998978956   t=3501.88       ratio=2.42724e+07
d=9     n=2439530234167 t=100312        ratio=2.43193e+07
But I am very curious if any engine is able to generate moves *significantly* faster.

Thanks,

--kcc

Vempele

Re: What is the best known speed of move generation?

Post by Vempele » Fri Oct 12, 2007 5:31 pm

Reinhard Scharnagl wrote:Here is some result including statistics and also mating analysis by SMIRF (thus a little bit slow):

Code: Select all

FEN: r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis.Studio C++ 32-Bit-Vers. 13.10
8 |[r]:::   :::[k]:::   [r]| (Compilation: May 19 2007)
7 |[p]   :::   :::   :::[p]|
6 |   :::   :::   :::   :::| Perft Testseries
5 |:::   :::   :::   :::   |
4 |   :::   :::   :::   :::| (without caching)
3 |:::   :::   :::   :::   |
2 |<P>&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   <P>| Smirf Test No.&#58;  0
1 |<R>   &#58;&#58;&#58;   <K>   &#58;&#58;&#58;<R>|
=>+-a--b--c--d--e--f--g--h-+ Break Time&#58; +20.00 Sec.

Ply       Nodes    all &#40;x&#41;   &#40;ep&#41;     all (+)     (#)   Prom.   Cstl.      Sec.
-------------------------------------------------------------------------------
1            14          0      0           0       0       0       0         0
2           192          0      0           4       0       0       0         0
3          3466          5      0         168       0       0       0         0
4         60120        311      0        3108       0       0       0         0
5       1223784       9773      0       82992       4       0       0     0.062
6      24161970     281348      2     1651267      97       0       0     1.484
7     528388659    7551900     54    40457103    9714       0       0     29.08
-------------------------------------------------------------------------------


FEN&#58; r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis.Studio C++ 32-Bit-Vers. 13.10
8 |&#91;r&#93;&#58;&#58;&#58;   &#58;&#58;&#58;&#91;k&#93;&#58;&#58;&#58;   &#91;r&#93;| &#40;Compilation&#58; May 19 2007&#41;
7 |&#91;p&#93;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;&#91;p&#93;|
6 |   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;| Perft Testseries
5 |&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   | &#40;with TT caching +256.0 MB / 4-fold&#41;
4 |   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;| TT Access Success +71.0%
3 |&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   |
2 |<P>&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   <P>| Smirf Test No.&#58;  0
1 |<R>   &#58;&#58;&#58;   <K>   &#58;&#58;&#58;<R>|
=>+-a--b--c--d--e--f--g--h-+ Break Time&#58; +10.00 Sec.

Ply        Nodes     all &#40;x&#41;   &#40;ep&#41;     all (+)      (#)  Prom.  Cstl.     Sec.
-------------------------------------------------------------------------------
1             14           0      0           0        0      0      0        0
2            192           0      0           4        0      0      0        0
3           3466           5      0         168        0      0      0        0
4          60120         311      0        3108        0      0      0        0
5        1223784        9773      0       82992        4      0      0    0.032
6       24161970      281348      2     1651267       97      0      0    0.313
7      528388659     7551900     54    40457103     9714      0      0    2.594
8    11297385161   198312821   2463   864164302   196741      0      0    18.33
-------------------------------------------------------------------------------
(AMD Athlon 64 X2 3800+ in single threaded 32 Bit mode)

Reinhard.
That'd be a little over 600 Mnps for perft 8. See this topic.

Jacob

Re: What is the best known speed of move generation?

Post by Jacob » Fri Oct 12, 2007 6:49 pm

Smirf's results are without a make/undo in the leaf nodes, right?

Alex Brunetti

Re: What is the best known speed of move generation?

Post by Alex Brunetti » Fri Oct 12, 2007 7:11 pm

kcc wrote:

Code: Select all

&#91;code&#93;d=1     n=20    t=0     ratio=inf
d=2     n=400   t=0     ratio=inf
d=3     n=8902  t=0     ratio=inf
d=4     n=197281        t=0     ratio=inf
d=5     n=4865609       t=0.2   ratio=2.4328e+07
d=6     n=119060324     t=4.92  ratio=2.41993e+07
d=7     n=3195901860    t=131   ratio= 2.43962e+07
d=8     n=84998978956   t=3501.88       ratio=2.42724e+07
d=9     n=2439530234167 t=100312        ratio=2.43193e+07&#91;/code&#93;
[/quote]
I wonder how fast is mine on your CPU. Perft 6 is completed in 8.5 secs on my very slow PC, but Crafty's (20.14) in 36 seconds.  May you test it? You can download 0.5.4a form my site.

[quote]

But I am very curious if any engine is able to generate moves *significantly* faster.
[/quote]

Delfi is faster than mine, but 5.2 seems to have not the perft command anymore. You should test 5.1 or even 5.0.


Alex

kcc

Re: What is the best known speed of move generation?

Post by kcc » Fri Oct 12, 2007 9:20 pm

Vempele wrote: That'd be a little over 600 Mnps for perft 8. See this topic.
Emm, that does not count, as the caching was enabled.
For this position I have 20M nps:

Code: Select all

d&#58; 1    n&#58; 14   t&#58; 0    nps&#58; inf
d&#58; 2    n&#58; 192  t&#58; 0    nps&#58; inf
d&#58; 3    n&#58; 3466 t&#58; 0    nps&#58; inf
d&#58; 4    n&#58; 60120        t&#58; 0    nps&#58; inf
d&#58; 5    n&#58; 1223784      t&#58; 0.06 nps&#58; 2.03964e+07
d&#58; 6    n&#58; 24161970     t&#58; 1.19 nps&#58; 2.03042e+07
d&#58; 7    n&#58; 528388659    t&#58; 25.65        nps&#58; 2.05999e+07
SMIRF w/o caching has 18M nps (but the machine is different)

Code: Select all

7     528388659    7551900     54    40457103    9714       0       0     29.08 

kcc

Re: What is the best known speed of move generation?

Post by kcc » Fri Oct 12, 2007 9:24 pm

Alex Brunetti wrote:
I wonder how fast is mine on your CPU. Perft 6 is completed in 8.5 secs on my very slow PC, but Crafty's (20.14) in 36 seconds. May you test it? You can download 0.5.4a form my site.
That may not be apples-to-apples comparison.
Are you running crafty as 64-bit?
Do you have linux version of your engine?

User avatar
hgm
Posts: 24731
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: What is the best known speed of move generation?

Post by hgm » Fri Oct 12, 2007 9:44 pm

kcc wrote:On my c2d@2.4GHz, crafty (I've downloaded the most recent 64-bit binary for linux) gives ~19M nodes per second.

Code: Select all

White&#40;1&#41;&#58; perft 6
total moves=119060324  time= 6.29
White&#40;1&#41;&#58; perft 7
total moves=3195901860  time=167.37
(can't measure for 8 plies, there seem to be an overflow)

With my own engine I get 24M nps on the same machine
This does not seem very fast for a 2.4GHz C2D. Qperft reaches about that speed on a 1GHz Athlon XP...

Code: Select all

$ perft 6
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - 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&#58; No hashing, bulk counting in horizon nodes

perft&#40;1&#41;=20 ( 0.000 sec&#41;

perft&#40;2&#41;=400 ( 0.000 sec&#41;

perft&#40;3&#41;=8902 ( 0.000 sec&#41;

perft&#40;4&#41;=197281 ( 0.010 sec&#41;

perft&#40;5&#41;=4865609 ( 0.210 sec&#41;

perft&#40;6&#41;=119060324 ( 5.498 sec&#41;


kcc

Re: What is the best known speed of move generation?

Post by kcc » Fri Oct 12, 2007 10:09 pm

hgm wrote: perft(6)=119060324 ( 5.498 sec)
Impressive!
On my c2d I get this out of Qperft:

Code: Select all

perft&#40;6&#41;=119060324 ( 1.750 sec&#41;
perft&#40;7&#41;=3195901860 &#40;47.210 sec&#41;
that is about 67M nps... I am stunned. :)
can someone do better?

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: What is the best known speed of move generation?

Post by Michael Sherwin » Fri Oct 12, 2007 10:22 pm

kcc wrote:
hgm wrote: perft(6)=119060324 ( 5.498 sec)
Impressive!
On my c2d I get this out of Qperft:

Code: Select all

perft&#40;6&#41;=119060324 ( 1.750 sec&#41;
perft&#40;7&#41;=3195901860 &#40;47.210 sec&#41;
that is about 67M nps... I am stunned. :)
can someone do better?
On an 80486 processor my code runs faster. :lol:

Harm's code is hard (next to impossible) to beat on modern processors.

If someone beats it, it would only be by a very small amount.

I may give it a try using my new vector-magnitude code that I have not implemented yet.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Alex Brunetti

Re: What is the best known speed of move generation?

Post by Alex Brunetti » Fri Oct 12, 2007 10:35 pm

kcc wrote:That may not be apples-to-apples comparison.
Are you running crafty as 64-bit?
No, I just have a 32 bit processor. It may not be apples-to-apples if they run on a 64 bit machine, since my engine is designed for 32 bit :)
kcc wrote:Do you have linux version of your engine?
No, I'm sorry.

Alex

Post Reply