A perft() benchmark

[sje]

Symbolic running perft(n) (n = 0 to 9) with a single thread on a 3.4 GHz Intel Core i7-2600 with a transposition table having 2^24 elements and using 128 bit hash keys:

Code: Select all

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

CountStTran(0): 1   Time: 0   Frequency: inf   Period: 0
CountStTran(1): 20   Time: 1e-06   Frequency: 2e+07   Period: 5e-08
CountStTran(2): 400   Time: 1.9e-05   Frequency: 2.10526e+07   Period: 4.75e-08
CountStTran(3): 8902   Time: 0.000162   Frequency: 5.49506e+07   Period: 1.81982e-08
CountStTran(4): 197281   Time: 0.002834   Frequency: 6.96122e+07   Period: 1.43653e-08
CountStTran(5): 4865609   Time: 0.0391   Frequency: 1.2444e+08   Period: 8.03599e-09
CountStTran(6): 119060324   Time: 0.599397   Frequency: 1.98634e+08   Period: 5.0344e-09
CountStTran(7): 3195901860   Time: 7.11643   Frequency: 4.49088e+08   Period: 2.22673e-09
CountStTran(8): 84998978956   Time: 93.4384   Frequency: 9.0968e+08   Period: 1.09929e-09
CountStTran(9): 2439530234167   Time: 1505.83   Frequency: 1.62005e+09   Period: 6.17263e-10

All times in seconds; all frequencies in hertz. Time needed to reset the transposition table is not included.

[sje]

Similar to the above, which also uses bulk counting at penultimate nodes, but this one has no transposition table assistance:

Code: Select all

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

CountStBulk(0): 1   Time: 2e-06   Frequency: 500000   Period: 2e-06
CountStBulk(1): 20   Time: 1e-06   Frequency: 2e+07   Period: 5e-08
CountStBulk(2): 400   Time: 1.1e-05   Frequency: 3.63636e+07   Period: 2.75e-08
CountStBulk(3): 8902   Time: 0.00015   Frequency: 5.93467e+07   Period: 1.68501e-08
CountStBulk(4): 197281   Time: 0.002833   Frequency: 6.96368e+07   Period: 1.43602e-08
CountStBulk(5): 4865609   Time: 0.061997   Frequency: 7.84814e+07   Period: 1.27419e-08
CountStBulk(6): 119060324   Time: 1.52874   Frequency: 7.78813e+07   Period: 1.28401e-08
CountStBulk(7): 3195901860   Time: 38.7014   Frequency: 8.25785e+07   Period: 1.21097e-08
CountStBulk(8): 84998978956   Time: 1058.88   Frequency: 8.02723e+07   Period: 1.24576e-08

No depth = 9 in the above; that would take half a day or so to calculate.

About 80 MHz, a reasonable rate.

[sje]

This time with no transposition assistance, and no bulk counting:

Code: Select all

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

CountStFull(0): 1   Time: 1e-06   Frequency: 1e+06   Period: 1e-06
CountStFull(1): 20   Time: 8e-06   Frequency: 2.5e+06   Period: 4e-07
CountStFull(2): 400   Time: 6.6e-05   Frequency: 6.06061e+06   Period: 1.65e-07
CountStFull(3): 8902   Time: 0.001322   Frequency: 6.73374e+06   Period: 1.48506e-07
CountStFull(4): 197281   Time: 0.027721   Frequency: 7.11666e+06   Period: 1.40515e-07
CountStFull(5): 4865609   Time: 0.704355   Frequency: 6.90789e+06   Period: 1.44762e-07
CountStFull(6): 119060324   Time: 17.8372   Frequency: 6.67484e+06   Period: 1.49816e-07
CountStFull(7): 3195901860   Time: 482.409   Frequency: 6.62488e+06   Period: 1.50946e-07

About 6.6 MHz and so about 26 MHz if all four cores were running; maybe 10%-20% more if hyperthreading (8 virtual cores) was in play.

[ibid]

gperft under about the same conditions but on a Phenom 1090T @ 3.6 GHZ, first with hashing (1-9 ply):
0.000 0.000 0.000 0.001 0.010 0.144 1.781 22.511 352.277
and without (1-8 ply):
0.000 0.000 0.000 0.001 0.015 0.349 8.919 239.553
bulk counting is not optional. :) The times are not cumulative, not sure how other people report that.

Of course this is hardly an apples-to-apples comparison: gperft is not a real chess program -- anything not needed for perft has been stripped out and there are some tweaks which would make little sense in a full chess engine.

-paul

[sje]

If those gperft numbers are for a single thread implementation, then they are fairly impressive.

Symbolic does a lot of incremental updating with each move execute/retract. This includes the full 64 element attack bitboard array and its transpose, plus various other bitboards, arrays, and lists.

Symbolic uses a 16 byte hash instead of an eight byte hash. This eats some time, but it nearly obliterates the need for any concern of false positives.

This Symbolic is a migration/re-write and does not yet have thread management. I expect the new multithreaded perft to be very fast.

This time around, perft activity is shoved into its own PathCounter class which has six methods for counting based upon single/multiple threads and full, bulk, and transposition modes. PathCounter gets two helper classes: a transposition table class and a transposition item class. The purpose of the subsystem is not to do a general perft for its own sake; rather, it is for helping to verify all the other code used for generate, execute, and retract.

[Ajedrecista]

Hello:

I did a similar experiment with JetChess (single core, 32-bit) in an Intel i5-760 (2.8 GHz) back in January, 2012. The results can be found here:

http://talkchess.com/forum/viewtopic.php?p=486603

I modified the size of hash tables depending on the ply of perft.

@Steven: if you prefer a table with frequencies and periods (approximated numbers):

Code: Select all

              Hash (MB)     Freq. (Hz)        Period (sec.)

Perft(04)         64       1.972810e+08       5.068912e-09
Perft(05)         64       2.115482e+08       4.727055e-09
Perft(06)         64       3.720635e+08       2.687713e-09
Perft(07)         64       8.270968e+08       1.209048e-09
Perft(08)        256       1.510824e+09       6.618903e-10
Perft(09)       1024       3.191891e+09       3.132939e-10
Perft(10)       1024       6.537895e+09       1.529544e-10

I did the math with the Windows calculator... I hope no typos.

@Paul: I reported times in a not accumulative way.

JetChess is a perft counter so, as gperft, is not a real chess engine.

Regards from Spain.

Ajedrecista.

[sje]

Code: Select all

k7/8/8/8/8/8/8/7K w - - 0 1

CountStTran(0): 1   Time: 0   Frequency: inf   Period: 0
CountStTran(1): 3   Time: 1e-06   Frequency: 3e+06   Period: 3.33333e-07
CountStTran(2): 9   Time: 1.3e-05   Frequency: 692308   Period: 1.44444e-06
CountStTran(3): 54   Time: 1.3e-05   Frequency: 4.15385e+06   Period: 2.40741e-07
CountStTran(4): 324   Time: 2.6e-05   Frequency: 1.24615e+07   Period: 8.02469e-08
CountStTran(5): 1890   Time: 7.1e-05   Frequency: 2.66197e+07   Period: 3.75661e-08
CountStTran(6): 11024   Time: 0.000195   Frequency: 5.65333e+07   Period: 1.76887e-08
CountStTran(7): 71758   Time: 0.00042   Frequency: 1.70852e+08   Period: 5.85301e-09
CountStTran(8): 466210   Time: 0.00084   Frequency: 5.55012e+08   Period: 1.80176e-09
CountStTran(9): 3083208   Time: 0.00093   Frequency: 3.31528e+09   Period: 3.01634e-10
CountStTran(10): 20296614   Time: 0.002489   Frequency: 8.15453e+09   Period: 1.22631e-10
CountStTran(11): 137688284   Time: 0.003799   Frequency: 3.62433e+10   Period: 2.75913e-11
CountStTran(12): 928817526   Time: 0.003323   Frequency: 2.79512e+11   Period: 3.57767e-12
CountStTran(13): 6338164714   Time: 0.008175   Frequency: 7.75311e+11   Period: 1.28981e-12
CountStTran(14): 43010471992   Time: 0.011692   Frequency: 3.67862e+12   Period: 2.71841e-13
CountStTran(15): 294704424538   Time: 0.015787   Frequency: 1.86675e+13   Period: 5.35689e-14
CountStTran(16): 2009892516456   Time: 0.022335   Frequency: 8.99885e+13   Period: 1.11125e-14
CountStTran(17): 13775845493902   Time: 0.028479   Frequency: 4.83719e+14   Period: 2.06731e-15
CountStTran(18): 94070961872736   Time: 0.021861   Frequency: 4.30314e+15   Period: 2.32388e-16
CountStTran(19): 644662402680014   Time: 0.040686   Frequency: 1.58448e+16   Period: 6.31121e-17
CountStTran(20): 4405504652323456   Time: 0.046736   Frequency: 9.42636e+16   Period: 1.06085e-17

[sje]

Code: Select all

k7/8/8/8/8/8/8/2B1K1N1 w - - 0 1

CountStTran(0): 1   Time: 0   Frequency: inf   Period: 0
CountStTran(1): 15   Time: 1e-06   Frequency: 1.5e+07   Period: 6.66667e-08
CountStTran(2): 43   Time: 1.4e-05   Frequency: 3.07143e+06   Period: 3.25581e-07
CountStTran(3): 686   Time: 2.2e-05   Frequency: 3.11818e+07   Period: 3.207e-08
CountStTran(4): 3959   Time: 0.00014   Frequency: 2.82786e+07   Period: 3.53625e-08
CountStTran(5): 67777   Time: 0.000476   Frequency: 1.42389e+08   Period: 7.02303e-09
CountStTran(6): 364461   Time: 0.00386   Frequency: 9.44199e+07   Period: 1.0591e-08
CountStTran(7): 6510273   Time: 0.008486   Frequency: 7.67178e+08   Period: 1.30348e-09
CountStTran(8): 38575135   Time: 0.036088   Frequency: 1.06892e+09   Period: 9.35525e-10
CountStTran(9): 711141935   Time: 0.07165   Frequency: 9.92522e+09   Period: 1.00753e-10
CountStTran(10): 4148146032   Time: 0.234932   Frequency: 1.76568e+10   Period: 5.66354e-11
CountStTran(11): 78116433114   Time: 0.413928   Frequency: 1.8872e+11   Period: 5.29886e-12
CountStTran(12): 462062560569   Time: 1.10935   Frequency: 4.16517e+11   Period: 2.40086e-12
CountStTran(13): 8832667622969   Time: 1.73083   Frequency: 5.10315e+12   Period: 1.95957e-13
CountStTran(14): 51785270159946   Time: 3.86253   Frequency: 1.34071e+13   Period: 7.45874e-14
CountStTran(15): 1000229602330778   Time: 5.63325   Frequency: 1.77558e+14   Period: 5.63196e-15
CountStTran(16): 5853744114170218   Time: 11.1698   Frequency: 5.24068e+14   Period: 1.90815e-15
CountStTran(17): 113901628056467536   Time: 15.6861   Frequency: 7.2613e+15   Period: 1.37716e-16
CountStTran(18): 662434866772928150   Time: 27.2098   Frequency: 2.43455e+16   Period: 4.10754e-17
CountStTran(19): 12957043766236616874   Time: 43.7439   Frequency: 2.96202e+17   Period: 3.37607e-18

Spills 64 bits at perft(20).

[ankan]

Perft benchmark at start position for my programs. Only for perft - not part of real chess engine (yet)

perft_cpu (64 bit/core 2 @ 3 GHz):

With bulk counting:

Code: Select all

Perft 1: 20,   Time taken: 2.28693e-005 seconds, nps: 874533

Perft 2: 400,   Time taken: 3.72054e-005 seconds, nps: 10751141

Perft 3: 8902,   Time taken: 0.000109227 seconds, nps: 81500202

Perft 4: 197281,   Time taken: 0.00182306 seconds, nps: 108214076

Perft 5: 4865609,   Time taken: 0.0399756 seconds, nps: 121714424

Perft 6: 119060324,   Time taken: 0.982133 seconds, nps: 121226328

Perft 7: 3195901860,   Time taken: 24.0978 seconds, nps: 132622234

Perft 8: 84998978956,   Time taken: 647.14 seconds, nps: 131345674

Without bulk counting:

Code: Select all

Perft 1: 20,   Time taken: 2.9696e-005 seconds, nps: 673491

Perft 2: 400,   Time taken: 2.28693e-005 seconds, nps: 17490662

Perft 3: 8902,   Time taken: 0.000153259 seconds, nps: 58084776

Perft 4: 197281,   Time taken: 0.00339149 seconds, nps: 58169422

Perft 5: 4865609,   Time taken: 0.0804291 seconds, nps: 60495631

Perft 6: 119060324,   Time taken: 1.96872 seconds, nps: 60476126

Perft 7: 3195901860,   Time taken: 51.9904 seconds, nps: 61471021

perft_gpu (GTX 780)

with bulk counting:

Code: Select all

GPU Perft 1: 20,   Time taken: 2.1536e-005 seconds, nps: 928677

GPU Perft 2: 400,   Time taken: 0.000123392 seconds, nps: 3241701

GPU Perft 3: 8902,   Time taken: 0.00021344 seconds, nps: 41707271

GPU Perft 4: 197281,   Time taken: 0.000591424 seconds, nps: 333569493

GPU Perft 5: 4865609,   Time taken: 0.00120736 seconds, nps: 4029956998

GPU Perft 6: 119060324,   Time taken: 0.0104103 seconds, nps: 11436742219

GPU Perft 7: 3195901860,   Time taken: 0.249936 seconds, nps: 12786865811

GPU Perft 8: 84998978956,   Time taken: 6.91274 seconds, nps: 12295997840

GPU Perft 9: 2439530234167,   Time taken: 190.924 seconds, nps: 12777524166

GPU Perft 10: 69352859712417,   Time taken: 5924 seconds, nps: 11707099883

All results without transposition tables (I still need to get transposition table working...)

[Ajedrecista]

Hi Steven:

Code: Select all

k7/8/8/8/8/8/8/2B1K1N1 w - - 0 1

[...]

Spills 64 bits at perft(20).

I have combined JetChess and MonteCarlo perft estimates to bring the hopefully correct result of perft(20) of the position you suggested:

[d]k7/8/8/8/8/8/8/2B1K1N1 w - - 0 1

I ran JetChess and it reported the following result: 1,285,783,583,762,534,722 which is obviously wrong... the true, huge number overflowed the 64-bit counter. JetChess also outputs a wrong number for perft(19), but the good thing is that the correct number is:

Code: Select all

[Correct perft(n) value] = [wrong reported perft(n) value] + k*[2^(64)]

Where k is a positive integer. In the case of perft(19), k = 1 (one overflow). But how estimate k? Here is where MonteCarlo perft estimates shine. I used Nebiyu 1.42 w32 for estimate perft(20) of the KBNk position:

Code: Select all

Mean:               7.506067e+019
Standard deviation: 2.046972e+016

k is easily calculated:

Code: Select all

k ~ {(Mean) - [wrong reported perft(20) value]}*[2^(-64)] = (7.506067e+019 - 1,285,783,583,762,534,722)*[2^(-64)] ~ 3.9993

Obviously: k = 4 (there was an overflow four times). Then:

Code: Select all

perft(20) = 1,285,783,583,762,534,722 + 4*[2^(-64)] = 75,072,759,878,600,741,186

Regarding spent times: JetChess took 766.982 seconds (0:12:46.982) to output a wrong (but valuable) value of perft(20) in my Intel Pentium D930 (at 3 GHz); the whole MonteCarlo perft estimate was done in around half an hour, but the first seconds were enough for conclude that k = 4. I let Nebiyu to finish the entire MC estimate for seeing the accuracy of it. Just calculating the z-value:

Code: Select all

z = [(Mean) - perft(20)]/(standard deviation) ~ -0.5906

It looks quite reasonable for me!

Regards from Spain.

Ajedrecista.