Perishing Perft !

[GeoffW]

Hi Allesandro

I was wondering how your Core Duo CPU compared to my Prescott P4

Kiwi results on my PC

perft 7
perft: depth=7, FEN=r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - - -
depth=1, nodes=14
depth=2, nodes=192
depth=3, nodes=3466
depth=4, nodes=60120
depth=5, nodes=1223784
depth=6, nodes=24161970
depth=7, nodes=528388659
perft complete: total=553838205 nodes in 59.250 seconds (9347 KNps)

That surprised me, as I was expecting your Core Duo to perform better.
I guess it is explained by the fact 1.6 is quite a low clock speed and it is not the latest Core 2 Duo design.

So taking the CPU difference into account that means that your worst algorithm is more than twice as fast as my best !!

I guess I need to have a rethink !

Thanks for the feedback

Regards Geoff

[Alessandro Scotti]

Another datapoint:

Code: Select all

Hamsters 0.3 by Alessandro Scotti
s r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - - - 
p 7
1 = 14
2 = 192
3 = 3466
4 = 60120
5 = 1223784
6 = 24161970
7 = 528388659

N = 553838205, T = 16257 ms (34067 KNps)

It seems your machine is about twice as fast as mine (assuming single core).

[smrf]

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.

[smrf]

SMIRF agrees with that final sum.

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 |:::   :::   :::   :::   | (with TT caching +256.0 MB / 4-fold)
4 |   :::   :::   :::   :::| TT Access Success +69.0%
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; +30.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.031
6       24161970       281348      2      1651267        97     0     0   0.312
7      528388659      7551900     54     40457103      9714     0     0   2.594
8    11297385161    198312821   2463    864164302    196741     0     0   18.41
9   260049637216   5128640760  63348  21138095393  10017457  7472     0   128.9
-------------------------------------------------------------------------------

Reinhard.

[Ross Boyd]

raw:14 end:14 secs:0.00
raw:206 end:192 secs:0.00
raw:3672 end:3466 secs:0.00
raw:63792 end:60120 secs:0.02 nps:3987000
raw:1287576 end:1223784 secs:0.33 nps:3925537
raw:25449546 end:24161970 secs:6.78 nps:3753067
raw:553838205 end:528388659 secs:141.59 nps:3911452

I also improved the time to perft 7 quite a bit, but it still looks very poor against some others quoted. (P4 @3.4 GHz)

I am not really interested in doing any specialist tricks for perft as I was using it to just prove the correctness of my code. My perft is simply, generate moves -> make move -> undo move

I would be interested to compare some more perft 7 times, for engines that use a similar non-specific perft loop. If you do post some more times, please quote CPU speed to make it more meaningful.

Regards Geoff

Hi Geoff,
No special tricks... no hashing.
The make/unmake are updating all the hashkeys, material, etc

On an AMD Athlon 4000...
Regards,
Ross

Code: Select all

=================================
TRACE 2.00 - May 18 2007 18:49:12
=================================
WinBoard and UCI compatible chess
 engine by Ross Boyd,  Australia

   May be distributed freely
 No warranties given or implied
---------------------------------
setboard r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1
perft 7

Ply       Nodes  Total Nodes         Secs       NPS
===================================================
  1          14           14        0.000
  2         192          206        0.000
  3        3466         3672        0.000
  4       60120        63792        0.000
  5     1223784      1287576        0.109  11812624
  6    24161970     25449546        2.297  11079471
  7   528388659    553838205       48.859  11335439
===================================================

with hashing enabled it gets this....

Code: Select all

hperft 7
Hash Size : 256Mb (16777216 entries)

Ply       Nodes  Total Nodes         Secs       NPS
===================================================
  1          14           14        0.000
  2         192          206        0.000
  3        3466         3672        0.000
  4       60120        63792        0.000
  5     1223784      1287576        0.016  80473500
  6    24161970     25449546        0.234 108758744
  7   528388659    553838205        1.828 302974948
===================================================

This is old TRACE (same move gen as 1.37a) so you can compare hardware... (no tricks etc)

Code: Select all

TRACE 1.38 CCT9 - May 19 2007
setboard r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1
perft 7

Ply       Nodes  Total Nodes         Secs      NPS
==================================================
  1          14           14        0.000
  2         192          206        0.000
  3        3466         3672        0.000
  4       60120        63792        0.016  3987000
  5     1223784      1287576        0.125 10300608
  6    24161970     25449546        2.594  9810928
  7   528388659    553838205       56.390  9821568
==================================================

[Allard Siemelink]

Hi Allard
Could you explain in more detail where and when you are making and unmaking moves. There is possibly a simple optimisation that hasn't occurred to me yet ?

Regards Geoff

Hi Geoff,

The perft is coded like this:

Code: Select all

uint Board::perft(int depth, Move last) {
    Move moves[256];
    Move *m2 = genAllMoves(moves, last);
    uint n=0;
    State state = save();
    for &#40;Move *m=moves; m<m2; m++) &#123;
        if (!&#40;last=move&#40;*m&#41;)) continue;
        if &#40;depth>1&#41; n += perft&#40;depth-1, last&#41;;
        else n++;
        undo&#40;*m, state&#41;;
    &#125;
    return n;
&#125;

Things to note:
-genAllMoves() generates pseudo legal moves.
-move() will check if the move is legal (0 is returned for illegal moves)
-move() will set the check flag in the returned Move if the move was check;
genAllMoves() will generate just check evasions if this check flag is set.

To quickly detect checks, move() looks at the piece type of the moving piece and its new location. For sliders, the old 0x88 trick is used to avoid
scanning the board if a slider cannot possibly deliver checks regardless of blocking pieces. Discoverd checks are handled the same way, but by looking at the location that was vacated by the piece.

Hope this helps.

[tvrzsky]

Hi, let me show my humble bunch of numbers ...
All tests have been done without use of hashing (which I have not implemented in perft), however with hash keys as well as all other unnecessary data structures updated in make/unmake functions (they are the same as in the regular search). Only move evaluation in generator is switched off, therefore there is no call of SEE (what would otherwise slow down the whole thing a lot).

Code: Select all

CPU Type:  Intel(R) Core(TM)2 CPU         T5500  @ 1.66GHz
CPU Frequency: 1662.5 MHz

1. fastest possible case = not making/unmaking last ply, no check detection in last ply (thanks legal move generator, of course)

Code: Select all

perft(7):           SubtreePerft        SubtreeInnerNodes
----------------------------------------------------------------------------------
01/14    Ra1-b1     50,081,018          2,291,566               1.02 s   2241.49 kN/s
02/14    Ra1-c1     47,457,788          2,191,590               2.00 s   2238.51 kN/s
03/14    Ra1-d1     33,831,669          1,605,787               2.72 s   2247.99 kN/s
04/14    Rh1-f1     36,304,708          1,651,084               3.45 s   2237.62 kN/s
05/14    Rh1-g1     51,302,720          2,277,740               4.48 s   2215.29 kN/s
06/14     a2-a3     23,941,522          1,284,348               5.04 s   2319.04 kN/s
07/14     a2-a4     26,931,187          1,411,249               5.65 s   2289.24 kN/s
08/14     h2-h3     24,346,577          1,295,833               6.21 s   2322.20 kN/s
09/14     h2-h4     27,793,666          1,432,291               6.84 s   2292.21 kN/s
10/14    Ke1-d1     21,704,666          1,164,297               7.34 s   2334.56 kN/s
11/14    Ke1-d2     52,542,952          2,478,059               8.44 s   2253.03 kN/s
12/14    Ke1-e2     59,615,160          2,776,871               9.68 s   2227.64 kN/s
13/14    Ke1-f1     20,933,844          1,142,686              10.17 s   2335.73 kN/s
14/14    Ke1-f2     51,601,182          2,446,145              11.26 s   2248.66 kN/s
----------------------------------------------------------------------------------
Total:   PERFT(7) = 528,388,659         25,449,546             11.26 s   2260.19 kN/s
FOUND: PERFT(7)=528388659
OK!

2. with make/unmake of last ply but still without check detection in leaves

Code: Select all

perft(7):           SubtreePerft        SubtreeInnerNodes
----------------------------------------------------------------------------------
01/14    Ra1-b1     50,081,018          2,291,566               2.88 s    794.44 kN/s
02/14    Ra1-c1     47,457,788          2,191,590               5.70 s    778.01 kN/s
03/14    Ra1-d1     33,831,669          1,605,787               7.68 s    813.74 kN/s
04/14    Rh1-f1     36,304,708          1,651,084               9.78 s    783.95 kN/s
05/14    Rh1-g1     51,302,720          2,277,740              12.74 s    770.55 kN/s
06/14     a2-a3     23,941,522          1,284,348              14.19 s    885.88 kN/s
07/14     a2-a4     26,931,187          1,411,249              15.81 s    871.99 kN/s
08/14     h2-h3     24,346,577          1,295,833              17.28 s    881.72 kN/s
09/14     h2-h4     27,793,666          1,432,291              18.94 s    863.39 kN/s
10/14    Ke1-d1     21,704,666          1,164,297              20.27 s    870.31 kN/s
11/14    Ke1-d2     52,542,952          2,478,059              23.34 s    807.64 kN/s
12/14    Ke1-e2     59,615,160          2,776,871              26.76 s    811.44 kN/s
13/14    Ke1-f1     20,933,844          1,142,686              28.04 s    894.73 kN/s
14/14    Ke1-f2     51,601,182          2,446,145              31.01 s    823.15 kN/s
----------------------------------------------------------------------------------
Total:   PERFT(7) = 528,388,659         25,449,546             31.01 s    820.59 kN/s

3. with make/unmake of last ply and check detection in leaves

Code: Select all

perft(7):           SubtreePerft        SubtreeInnerNodes
----------------------------------------------------------------------------------
01/14    Ra1-b1     50,081,018          2,291,566               3.38 s    677.50 kN/s
02/14    Ra1-c1     47,457,788          2,191,590               6.67 s    666.26 kN/s
03/14    Ra1-d1     33,831,669          1,605,787               8.99 s    693.44 kN/s
04/14    Rh1-f1     36,304,708          1,651,084              11.45 s    671.22 kN/s
05/14    Rh1-g1     51,302,720          2,277,740              14.89 s    660.96 kN/s
06/14     a2-a3     23,941,522          1,284,348              16.58 s    762.77 kN/s
07/14     a2-a4     26,931,187          1,411,249              18.45 s    754.37 kN/s
08/14     h2-h3     24,346,577          1,295,833              20.15 s    761.95 kN/s
09/14     h2-h4     27,793,666          1,432,291              22.06 s    751.30 kN/s
10/14    Ke1-d1     21,704,666          1,164,297              23.60 s    753.30 kN/s
11/14    Ke1-d2     52,542,952          2,478,059              27.18 s    693.23 kN/s
12/14    Ke1-e2     59,615,160          2,776,871              31.20 s    689.96 kN/s
13/14    Ke1-f1     20,933,844          1,142,686              32.67 s    779.91 kN/s
14/14    Ke1-f2     51,601,182          2,446,145              36.13 s    706.55 kN/s
----------------------------------------------------------------------------------
Total:   PERFT(7) = 528,388,659         25,449,546             36.13 s    704.39 kN/s

4. like previous case but also updating attack bitboards in leaves

Code: Select all

perft(7):           SubtreePerft        SubtreeInnerNodes
----------------------------------------------------------------------------------
01/14    Ra1-b1     50,081,018          2,291,566              14.31 s    160.08 kN/s
02/14    Ra1-c1     47,457,788          2,191,590              28.01 s    160.01 kN/s
03/14    Ra1-d1     33,831,669          1,605,787              37.62 s    167.18 kN/s
04/14    Rh1-f1     36,304,708          1,651,084              47.88 s    160.94 kN/s
05/14    Rh1-g1     51,302,720          2,277,740              62.50 s    155.75 kN/s
06/14     a2-a3     23,941,522          1,284,348              69.42 s    185.66 kN/s
07/14     a2-a4     26,931,187          1,411,249              77.20 s    181.45 kN/s
08/14     h2-h3     24,346,577          1,295,833              84.28 s    182.88 kN/s
09/14     h2-h4     27,793,666          1,432,291              92.29 s    178.80 kN/s
10/14    Ke1-d1     21,704,666          1,164,297              98.58 s    185.14 kN/s
11/14    Ke1-d2     52,542,952          2,478,059             113.71 s    163.78 kN/s
12/14    Ke1-e2     59,615,160          2,776,871             130.90 s    161.61 kN/s
13/14    Ke1-f1     20,933,844          1,142,686             136.99 s    187.51 kN/s
14/14    Ke1-f2     51,601,182          2,446,145             151.90 s    164.10 kN/s
----------------------------------------------------------------------------------
Total:   PERFT(7) = 528,388,659         25,449,546            151.90 s    167.55 kN/s

5. previous case with additional move generation in leaves (de facto perft(8), only without counting and calling perft() function in last ply)

Code: Select all

perft(7):           SubtreePerft        SubtreeInnerNodes
----------------------------------------------------------------------------------
01/14    Ra1-b1     50,081,018          2,291,566              23.32 s     98.25 kN/s
02/14    Ra1-c1     47,457,788          2,191,590              45.65 s     98.17 kN/s
03/14    Ra1-d1     33,831,669          1,605,787              61.53 s    101.13 kN/s
04/14    Rh1-f1     36,304,708          1,651,084              78.25 s     98.73 kN/s
05/14    Rh1-g1     51,302,720          2,277,740             101.98 s     95.97 kN/s
06/14     a2-a3     23,941,522          1,284,348             113.16 s    114.91 kN/s
07/14     a2-a4     26,931,187          1,411,249             125.73 s    112.30 kN/s
08/14     h2-h3     24,346,577          1,295,833             137.10 s    113.96 kN/s
09/14     h2-h4     27,793,666          1,432,291             150.13 s    109.95 kN/s
10/14    Ke1-d1     21,704,666          1,164,297             160.23 s    115.24 kN/s
11/14    Ke1-d2     52,542,952          2,478,059             184.61 s    101.63 kN/s
12/14    Ke1-e2     59,615,160          2,776,871             212.57 s     99.32 kN/s
13/14    Ke1-f1     20,933,844          1,142,686             222.35 s    116.86 kN/s
14/14    Ke1-f2     51,601,182          2,446,145             246.23 s    102.45 kN/s
----------------------------------------------------------------------------------
Total:   PERFT(7) = 528,388,659         25,449,546            246.23 s    103.36 kN/s

6. circle is closing: real perft(8) with same conditions as in 1.

Code: Select all

perft(8):           SubtreePerft        SubtreeInnerNodes
----------------------------------------------------------------------------------
01/14    Ra1-b1     1,062,390,196       52,372,584             23.53 s   2226.17 kN/s
02/14    Ra1-c1     994,961,141         49,649,378             45.89 s   2220.36 kN/s
03/14    Ra1-d1     699,902,214         35,437,456             61.61 s   2254.24 kN/s
04/14    Rh1-f1     749,864,388         37,955,792             78.51 s   2246.09 kN/s
05/14    Rh1-g1     1,078,224,310       53,580,460            102.57 s   2226.71 kN/s
06/14     a2-a3     521,883,593         25,225,870            113.92 s   2223.07 kN/s
07/14     a2-a4     584,490,738         28,342,436            126.63 s   2229.25 kN/s
08/14     h2-h3     530,959,096         25,642,410            138.09 s   2237.70 kN/s
09/14     h2-h4     602,822,744         29,225,957            151.19 s   2231.24 kN/s
10/14    Ke1-d1     471,895,061         22,868,963            161.47 s   2225.16 kN/s
11/14    Ke1-d2     1,138,087,181       55,021,011            186.01 s   2241.76 kN/s
12/14    Ke1-e2     1,299,305,185       62,392,031            214.01 s   2228.49 kN/s
13/14    Ke1-f1     452,781,746         22,076,530            223.81 s   2251.11 kN/s
14/14    Ke1-f2     1,109,817,568       54,047,327            247.82 s   2251.37 kN/s
----------------------------------------------------------------------------------
Total:   PERFT(8) = 11,297,385,161      553,838,205           247.82 s   2234.83 kN/s

So, updating of attack bitboards costs me the most, even little bit more than the move generation ...

[smrf]

... Discoverd checks are handled the same way, but by looking at the location that was vacated by the piece. ...

With special treatment of e.p. capture moves and castlings?!

Reinhard.

[Allard Siemelink]

... Discoverd checks are handled the same way, but by looking at the location that was vacated by the piece. ...

With special treatment of e.p. capture moves and castlings?!

Reinhard.

Yes, these are detected as special cases, for which flags get set during move generation.

[hgm]

I had missed a line of code to either add or subtract 0x10 to move 1 rank.

If you want to do this in a color-independent way without any ifs, you can XOR the rank with 0x10. With normal 0x88 numbering this maps 4th rank into 3rd (and vice versa), as well as 5th rank into 6th.

Quick Perft (7) takes only 8.9 sec on my new Core 2 Duo machine (E6600, 2.4GHz)!