What is the best known speed of move generation?

tvrzsky · Post by **tvrzsky** » Sat Oct 13, 2007 12:36 am

Yes, I do ... with Muller's QPerft

This is the output of the binary compiled by myself (with MSVC 2005 Express Edition) running on Intel E2140 which is overclocked just on 2.4 GHz:

Code: Select all

     CPU Type&#58;        Genuine Intel&#40;R&#41; CPU            2140  @ 1.60GHz
     CPU Frequency&#58;   2405.4 MHz

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.016 sec&#41;

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

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

perft&#40;7&#41;=          3195901860 &#40;31.406 sec&#41;

And this is my own engine:

Code: Select all

perft&#40;7&#41;&#58;           SubtreePerft        SubtreeInnerNodes
----------------------------------------------------------------------------------
01/20    Nb1-a3     120,142,144         5,064,713               1.68 s   3020.10 kN/s
02/20    Nb1-c3     148,527,161         5,952,936               3.63 s   3054.77 kN/s
03/20    Ng1-f3     147,678,554         5,967,223               5.58 s   3058.57 kN/s
04/20    Ng1-h3     120,669,525         5,085,038               7.23 s   3078.60 kN/s
05/20     a2-a4     137,077,337         5,591,157               9.05 s   3065.83 kN/s
06/20     b2-b4     134,087,476         5,519,474              10.87 s   3047.66 kN/s
07/20     c2-c4     157,756,443         6,116,954              12.90 s   3009.91 kN/s
08/20     d2-d4     269,605,599         9,254,372              16.11 s   2886.99 kN/s
09/20     e2-e4     309,478,263         10,190,798             19.69 s   2845.11 kN/s
10/20     f2-f4     119,614,841         5,098,253              21.35 s   3061.75 kN/s
11/20     g2-g4     130,293,018         5,463,693              23.13 s   3070.83 kN/s
12/20     h2-h4     138,495,290         5,614,153              24.97 s   3063.26 kN/s
13/20     a2-a3     106,743,106         4,653,171              26.47 s   3099.80 kN/s
14/20     b2-b3     133,233,975         5,535,399              28.28 s   3060.50 kN/s
15/20     c2-c3     144,074,944         5,650,214              30.15 s   3017.82 kN/s
16/20     d2-d3     227,598,692         8,414,112              32.99 s   2963.75 kN/s
17/20     e2-e3     306,138,410         10,142,760             36.52 s   2876.44 kN/s
18/20     f2-f3     102,021,008         4,591,888              37.99 s   3113.14 kN/s
19/20     g2-g3     135,987,651         5,573,256              39.82 s   3052.11 kN/s
20/20     h2-h3     106,678,423         4,652,972              41.32 s   3111.59 kN/s
----------------------------------------------------------------------------------
Total&#58;   PERFT&#40;7&#41; = 3,195,901,860       124,132,536            41.32 s   3004.42 kN/s

kcc · Post by **kcc** » Sat Oct 13, 2007 12:43 am

Still, Protej seems to beet crafty (and me) significantly

On my 32-bit box (something @2Ghz) it gives

Code: Select all

Depth&#58;   1  Nodes&#58;            20  Time&#58;       0.00  NPS&#58;    OO
Depth&#58;   2  Nodes&#58;           400  Time&#58;       0.00  NPS&#58;    OO
Depth&#58;   3  Nodes&#58;         8,902  Time&#58;       0.00  NPS&#58;    OO
Depth&#58;   4  Nodes&#58;       197,281  Time&#58;       0.02  NPS&#58; 12.3M
Depth&#58;   5  Nodes&#58;     4,865,609  Time&#58;       0.22  NPS&#58; 22.3M
Depth&#58;   6  Nodes&#58;   119,060,324  Time&#58;       3.59  NPS&#58; 33.1M

wow!

Jacob · Post by **Jacob** » Sat Oct 13, 2007 2:41 am

Still, Protej seems to beet crafty (and me) significantly Smile

I'm not sure about significantly : ). Looking at your results, it seems you're making/undoing each move at the leaf nodes. Legal move generators can skip the last make/unmake by simply counting the number of moves they generated at depth == 1, which gives much faster results.

Intel(R) Core(TM)2 CPU 6700 @ 2.66GHz (over-clocked to 3.4GHz)

Code: Select all

&#40;with last make/unmake&#41;
 1.             20    0.00s    1.00 mnps
 2.            400    0.00s    1.00 mnps
 3.           8902    0.00s    1.00 mnps
 4.         197281    0.01s    1.00 mnps
 5.        4865609    0.17s   28.62 mnps
 6.      119060324    4.19s   28.42 mnps

&#40;without last make/unmake&#41;
 1.             20    0.00s    1.00 mnps
 2.            400    0.00s    1.00 mnps
 3.           8902    0.00s    1.00 mnps
 4.         197281    0.00s    1.00 mnps
 5.        4865609    0.04s    1.00 mnps
 6.      119060324    0.89s  133.78 mnps

My perft code looks like this (for BitboardPerft, which doesn't do any material/zobrist updates. Etude is much slower):

Code: Select all

U64 Perft&#40;int depth&#41;
&#123;
    U64 nodes = 0;
    U32 moves&#91;256&#93;;
    int n_moves, i;

    // Last make/unmake
    //if &#40;depth == 0&#41; &#123; return 1; &#125; 

    if &#40;Attacked&#40;king&#91;side&#93;, xside&#41;) &#123;
        n_moves = &#40;int&#41;&#40;GenEvasions&#40;moves&#41; - moves&#41;;
    &#125;
    else &#123;
        U32* p_moves = GenCaptures&#40;moves&#41;;
        n_moves = &#40;int&#41;&#40;GenNonCaptures&#40;p_moves&#41; - moves&#41;;
    &#125;

    // No last make/unmake
    if &#40;depth == 1&#41; &#123; return n_moves; &#125;    

    for &#40;i = 0; i < n_moves; i++) &#123;
        Move&#40;moves&#91;i&#93;);
        nodes += Perft&#40;depth - 1&#41;;
        Undo&#40;moves&#91;i&#93;);
    &#125;

    return nodes;
&#125;

kcc · Post by **kcc** » Sat Oct 13, 2007 2:50 am

Legal move generators can skip the last make/unmake by simply counting the number of moves they generated at depth == 1, which gives much faster results.

Yep, I do make_move for leaf nodes; since I generate pseudo moves, I have to

(I don't have unmake though since I copy the state)

I see that the generators that generate legal moves are more efficient in perft.
Is that so for the real chess?

Jacob · Post by **Jacob** » Sat Oct 13, 2007 3:00 am

Nope : ), in the search you have to make the leaf moves for Evaluate() to work. It's only a perft trick.

edit: actually, some would argue that legal move generators are better for other reasons, such as cleaner code, decision making based on available moves, etc. But pseudo move generators might be faster, depending on the implementation. I'll let someone who's more experienced elaborate,...

kcc · Post by **kcc** » Sat Oct 13, 2007 3:05 am

Jacob wrote:Nope : ), in the search you have to make the leaf moves for Evaluate() to work. It's only a perft trick.

Yea...
So, let me rephrase my initial question a bit:
what is the best known speed of move generation if you have to actually generate all leaf nodes (not just count)?

Dann Corbit · Post by **Dann Corbit** » Sat Oct 13, 2007 4:55 am

Movei 449 on 2.2 GHz does perft 6 in 4.673 seconds and perft 7 under two minutes.

Code: Select all

new
perft 5
perft&#40;5&#41; = 4865609,time=203
perft 6
perft&#40;6&#41; = 119060324,time=4673
perft 7
perft&#40;7&#41; = 3195901860,time=117708

Uri uses hashing with perft.

Dann Corbit · Post by **Dann Corbit** » Sat Oct 13, 2007 5:19 am

Using your program on AMD 2.2 GHz with profile guided optimization, I get:

Code: Select all

C&#58;\pgn\WINBOA~1\perft\Release>perft 7 H22
Hash-table size = 3fffff, Starts at 450020
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - 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; Hash-table size = 64MB, 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.015 sec&#41;

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

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

perft&#40;7&#41;=3195901860 ( 9.094 sec&#41;

Dann Corbit · Post by **Dann Corbit** » Sat Oct 13, 2007 5:20 am

Dann Corbit wrote:Using your program on AMD 2.2 GHz with profile guided optimization, I get:

Code: Select all

C&#58;\pgn\WINBOA~1\perft\Release>perft 7 H22
Hash-table size = 3fffff, Starts at 450020
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - 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; Hash-table size = 64MB, 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.015 sec&#41;

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

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

perft&#40;7&#41;=3195901860 ( 9.094 sec&#41;

Using bigger hash helps with level 7:

Code: Select all

C&#58;\pgn\WINBOA~1\perft\Release>perft 7 H25
Hash-table size = 1ffffff, Starts at 450020
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - 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; Hash-table size = 512MB, 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.000 sec&#41;

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

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

perft&#40;7&#41;=3195901860 ( 8.454 sec&#41;

Dann Corbit · Post by **Dann Corbit** » Sat Oct 13, 2007 5:23 am

Wow! Perft 8 in under 2 minutes.

Code: Select all

C&#58;\pgn\WINBOA~1\perft\Release>perft 8 H25
Hash-table size = 1ffffff, Starts at 450020
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - 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; Hash-table size = 512MB, 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.000 sec&#41;

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

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

perft&#40;7&#41;=3195901860 ( 8.469 sec&#41;

perft&#40;8&#41;=84998978956 &#40;113.348 sec&#41;

What is the best known speed of move generation?

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

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

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

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

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

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

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

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

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

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