magic bitboard perft

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
abulmo2
Posts: 310
Joined: Fri Dec 16, 2016 10:04 am
Contact:

magic bitboard perft

Post by abulmo2 » Sat Apr 11, 2020 10:29 am

I release a new perft program based on magic bitboard:

https://github.com/abulmo/MPerft

I just provide the source code and a makefile. To compile it from a unix like terminal just type 'make pgo' on the command line or 'make pext' if you have a recent intel cpu (unfortunately I just have a ryzen cpu on which this instruction is very slow).

Here is how to use it:

Code: Select all

$ mperft -h
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
mperft [--fen|-f <fen>] [--depth|-d <depth>] [--hash|-H <size>] [--bulk|-b] [--div] [--capture] | [--help|-h] | [--test|-t]
Enumerate moves.
	--help|-h            Print this message.
	--fen|-f <fen>       Test the position indicated in FEN format (default=starting position).
	--depth|-d <depth>   Test up to this depth (default=6).
	--bulk|-b            Do fast bulk counting at the last ply.
	--hash|-H <size>     Use a hashtable with <size> bits entries (default 0, no hashtable).
	--capture|-c         Generate only captures, promotions & check evasions.
	--loop|-l            Loop from depth 1 to <depth>.
	--div|-r             Print a node count for each move.
	--test|-t            Run an internal test to check the move generator.
With magic bitboards, it is about 20% faster than my previous perft program based on hyper-quintessence and about twice faster than qperft by H.G.Muller. To compare the speed of your own move generator, here are some speed example on my Ryzen 1700x at 3.5 Ghz:

Code: Select all

$ mperft -d 7 -l
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: no hashing; no bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
perft  1 :              20 leaves in      0.000 s      8733602 leaves/s
perft  2 :             400 leaves in      0.000 s     25974123 leaves/s
perft  3 :            8902 leaves in      0.000 s     30508455 leaves/s
perft  4 :          197281 leaves in      0.005 s     37698752 leaves/s
perft  5 :         4865609 leaves in      0.122 s     39819131 leaves/s
perft  6 :       119060324 leaves in      2.955 s     40295690 leaves/s
perft  7 :      3195901860 leaves in     79.239 s     40332200 leaves/s
total   :      3320034396 leaves in     82.325 s     40328198 leaves/s
By default, it runs without bulk counting nor hash table, but you can use bulk counting:

Code: Select all

$ mperft -d 8 -b -l
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: no hashing; with bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
perft  1 :              20 leaves in      0.000 s      8163397 leaves/s
perft  2 :             400 leaves in      0.000 s    149253892 leaves/s
perft  3 :            8902 leaves in      0.000 s    223612351 leaves/s
perft  4 :          197281 leaves in      0.001 s    234617005 leaves/s
perft  5 :         4865609 leaves in      0.015 s    332412464 leaves/s
perft  6 :       119060324 leaves in      0.257 s    462975350 leaves/s
perft  7 :      3195901860 leaves in      6.576 s    485993711 leaves/s
perft  8 :     84998978956 leaves in    174.674 s    486615597 leaves/s
total   :     88319013352 leaves in    181.526 s    486536545 leaves/s
Or with an hashtable to get faster numbers:

Code: Select all

$ mperft -d 9 -b -l -H 25
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: hashtable size: 768 Mbytes; with bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
perft  1 :              20 leaves in      0.000 s      5405449 leaves/s
perft  2 :             400 leaves in      0.000 s    168773428 leaves/s
perft  3 :            8902 leaves in      0.000 s    237260014 leaves/s
perft  4 :          197281 leaves in      0.001 s    339820347 leaves/s
perft  5 :         4865609 leaves in      0.008 s    617521609 leaves/s
perft  6 :       119060324 leaves in      0.114 s   1040846615 leaves/s
perft  7 :      3195901860 leaves in      1.389 s   2301513961 leaves/s
perft  8 :     84998978956 leaves in     17.667 s   4811219445 leaves/s
perft  9 :   2439530234167 leaves in    245.597 s   9933051955 leaves/s
total   :   2527849247519 leaves in    264.999 s   9539099229 leaves/s
It comes with an internal test (mperft -t) and should be correct on any position (at least without hashtable):

Code: Select all

$ mperft -t
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Testing the board generator
Test 1. Initial position  rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 passed
Test 2. r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - passed
Test 3. 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - passed
Test 4. r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1 passed
Test 5. rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6 passed
Test 6. r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10 passed
Test 7. 8/5bk1/8/2Pp4/8/1K6/8/8 w - d6 0 1 passed
Test 8. Enpassant capture gives check 8/8/1k6/2b5/2pP4/8/5K2/8 b - d3 0 1 passed
Test 9. Short castling gives check 5k2/8/8/8/8/8/8/4K2R w K - 0 1 passed
Test 10. Long castling gives check 3k4/8/8/8/8/8/8/R3K3 w Q - 0 1 passed
Test 11. Castling r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1 passed
Test 12. Castling prevented r3k2r/8/3Q4/8/8/5q2/8/R3K2R b KQkq - 0 1 passed
Test 13. Promote out of check 2K2r2/4P3/8/8/8/8/8/3k4 w - - 0 1 passed
Test 14. Discovered check 8/8/1P2K3/8/2n5/1q6/8/5k2 b - - 0 1 passed
Test 15. Promotion gives check 4k3/1P6/8/8/8/8/K7/8 w - - 0 1 passed
Test 16. Underpromotion gives check 8/P1k5/K7/8/8/8/8/8 w - - 0 1 passed
Test 17. Self stalemate K1k5/8/P7/8/8/8/8/8 w - - 0 1 passed
Test 18. Stalemate/Checkmate 8/k1P5/8/1K6/8/8/8/8 w - - 0 1 passed
Test 19. Double check 8/8/2k5/5q2/5n2/8/5K2/8 b - - 0 1 passed
Of course you can use a '--div' command to have the detail for each move:

Code: Select all

$ mperft -d 6 --div
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: no hashing; no bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
 a2a3          4463267
 b2b3          5310358
 c2c3          5417640
 d2d3          8073082
 e2e3          9726018
 f2f3          4404141
 g2g3          5346260
 h2h3          4463070
 a2a4          5363555
 b2b4          5293555
 c2c4          5866666
 d2d4          8879566
 e2e4          9771632
 f2f4          4890429
 g2g4          5239875
 h2h4          5385554
 b1a3          4856835
 b1c3          5708064
 g1f3          5723523
 g1h3          4877234
total   :       119060324 leaves in      2.972 s     40061041 leaves/s
It can be also used for qsearch perft.

Code: Select all

$ mperft -f 'r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1' -c -d 6 -l
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: no hashing; no bulk counting; capture only;
  a b c d e f g h
8 r . . . k . . r 8
7 p . p p q p b . 7
6 b n . . p n p . 6
5 . . . P N . . . 5
4 . p . . P . . . 4
3 . . N . . Q . p 3
2 P P P B B P P P 2
1 R . . . K . . R 1
  a b c d e f g h
w, KQkq
perft  1 :               8 leaves in      0.000 s      3603633 leaves/s
perft  2 :              62 leaves in      0.000 s     10064935 leaves/s
perft  3 :             487 leaves in      0.000 s     13710585 leaves/s
perft  4 :            3690 leaves in      0.000 s     12690093 leaves/s
perft  5 :           25347 leaves in      0.002 s     13308124 leaves/s
perft  6 :          182498 leaves in      0.008 s     22135219 leaves/s
total   :          212092 leaves in      0.014 s     15122828 leaves/s
Have fun with it.
Richard Delorme

Rein Halbersma
Posts: 711
Joined: Tue May 22, 2007 9:13 am

Re: magic bitboard perft

Post by Rein Halbersma » Sat Apr 11, 2020 11:09 am

Thanks, this looks very useful as a standard for other programs to conform to. With such a standard in place, I wonder how hard it would be to write a "perft_bisect engine1 engine2" tool that will take the divide output of two perft binaries and zooms in on the first discrepancy or returns silently if there is no discrepancy up to a certain depth.

User avatar
leanchess
Posts: 84
Joined: Sun Dec 08, 2019 7:16 pm
Full name: Dmitry Shechtman
Contact:

Re: magic bitboard perft

Post by leanchess » Sat Apr 11, 2020 11:19 am

Thank you, this looks great. I can confirm that it's about 90% faster than qperft.

I'm wondering if it could be easily updated to dive in deeper than one ply, like qperft does.

User avatar
mvanthoor
Posts: 764
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: magic bitboard perft

Post by mvanthoor » Sat Apr 11, 2020 12:15 pm

Thanks :) I'll have to test this... a claim that it is twice as fast as QPerft (so 50% of time taken) and even 90% faster than QPerft is... dangerous. QPerft has been the benchmark for a LONG time if I remember correctly.

I think I'm going to fork Rustic into a new repository, strip out everything that's not strictly needed for perfting, and then turn it into RPerft, just for giggles and to play with :) Then I can investigate / understand and use some perfting tricks without having to use Rustic for it.
Author of Rustic.
Releases | Code | Docs

User avatar
leanchess
Posts: 84
Joined: Sun Dec 08, 2019 7:16 pm
Full name: Dmitry Shechtman
Contact:

Re: magic bitboard perft

Post by leanchess » Sat Apr 11, 2020 12:25 pm

mvanthoor wrote:
Sat Apr 11, 2020 12:15 pm
Thanks :) I'll have to test this... a claim that it is twice as fast as QPerft (so 50% of time taken) and even 90% faster than QPerft is... dangerous. QPerft has been the benchmark for a LONG time if I remember correctly.
There is an old thread somewhere around here where another implementation is confirmed to be at least x3 faster than qperft.

In any case, this one does perft(7) in about 12 seconds on my machine (with bulk counting, of course).

User avatar
leanchess
Posts: 84
Joined: Sun Dec 08, 2019 7:16 pm
Full name: Dmitry Shechtman
Contact:

Re: magic bitboard perft

Post by leanchess » Sat Apr 11, 2020 1:00 pm

Correction: It's closer to 11 seconds, so it is about 100% faster. I didn't notice the option to "make pgo", so I was getting a slower build.

Now, when trying to "make pext" I'm getting:

Code: Select all

mperft.c: In function ‘magic_index’:
/usr/lib/gcc/x86_64-pc-cygwin/9.3.0/include/bmi2intrin.h:76:1: error: inlining failed in call to always_inline ‘_pext_u64’: target specific option mismatch
   76 | _pext_u64 (unsigned long long __X, unsigned long long __Y)
      | ^~~~~~~~~
mperft.c:446:9: note: called from here
  446 |  return _pext_u64(pieces, attack->mask);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
in both gcc and clang.

User avatar
leanchess
Posts: 84
Joined: Sun Dec 08, 2019 7:16 pm
Full name: Dmitry Shechtman
Contact:

Re: magic bitboard perft

Post by leanchess » Sat Apr 11, 2020 2:03 pm

I noticed that your hash entry size is 24 bytes. May I suggest cutting it by 1.5 by reducing the count size to 56 bits? I just submitted a pull request:

https://github.com/abulmo/MPerft/pull/4

There performance improvement is hardly noticeable (at least for SP), but it just seems like the right thing to do.

Pio
Posts: 264
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: magic bitboard perft

Post by Pio » Sat Apr 11, 2020 3:28 pm

abulmo2 wrote:
Sat Apr 11, 2020 10:29 am
I release a new perft program based on magic bitboard:

https://github.com/abulmo/MPerft

I just provide the source code and a makefile. To compile it from a unix like terminal just type 'make pgo' on the command line or 'make pext' if you have a recent intel cpu (unfortunately I just have a ryzen cpu on which this instruction is very slow).

Here is how to use it:

Code: Select all

$ mperft -h
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
mperft [--fen|-f <fen>] [--depth|-d <depth>] [--hash|-H <size>] [--bulk|-b] [--div] [--capture] | [--help|-h] | [--test|-t]
Enumerate moves.
	--help|-h            Print this message.
	--fen|-f <fen>       Test the position indicated in FEN format (default=starting position).
	--depth|-d <depth>   Test up to this depth (default=6).
	--bulk|-b            Do fast bulk counting at the last ply.
	--hash|-H <size>     Use a hashtable with <size> bits entries (default 0, no hashtable).
	--capture|-c         Generate only captures, promotions & check evasions.
	--loop|-l            Loop from depth 1 to <depth>.
	--div|-r             Print a node count for each move.
	--test|-t            Run an internal test to check the move generator.
With magic bitboards, it is about 20% faster than my previous perft program based on hyper-quintessence and about twice faster than qperft by H.G.Muller. To compare the speed of your own move generator, here are some speed example on my Ryzen 1700x at 3.5 Ghz:

Code: Select all

$ mperft -d 7 -l
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: no hashing; no bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
perft  1 :              20 leaves in      0.000 s      8733602 leaves/s
perft  2 :             400 leaves in      0.000 s     25974123 leaves/s
perft  3 :            8902 leaves in      0.000 s     30508455 leaves/s
perft  4 :          197281 leaves in      0.005 s     37698752 leaves/s
perft  5 :         4865609 leaves in      0.122 s     39819131 leaves/s
perft  6 :       119060324 leaves in      2.955 s     40295690 leaves/s
perft  7 :      3195901860 leaves in     79.239 s     40332200 leaves/s
total   :      3320034396 leaves in     82.325 s     40328198 leaves/s
By default, it runs without bulk counting nor hash table, but you can use bulk counting:

Code: Select all

$ mperft -d 8 -b -l
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: no hashing; with bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
perft  1 :              20 leaves in      0.000 s      8163397 leaves/s
perft  2 :             400 leaves in      0.000 s    149253892 leaves/s
perft  3 :            8902 leaves in      0.000 s    223612351 leaves/s
perft  4 :          197281 leaves in      0.001 s    234617005 leaves/s
perft  5 :         4865609 leaves in      0.015 s    332412464 leaves/s
perft  6 :       119060324 leaves in      0.257 s    462975350 leaves/s
perft  7 :      3195901860 leaves in      6.576 s    485993711 leaves/s
perft  8 :     84998978956 leaves in    174.674 s    486615597 leaves/s
total   :     88319013352 leaves in    181.526 s    486536545 leaves/s
Or with an hashtable to get faster numbers:

Code: Select all

$ mperft -d 9 -b -l -H 25
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: hashtable size: 768 Mbytes; with bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
perft  1 :              20 leaves in      0.000 s      5405449 leaves/s
perft  2 :             400 leaves in      0.000 s    168773428 leaves/s
perft  3 :            8902 leaves in      0.000 s    237260014 leaves/s
perft  4 :          197281 leaves in      0.001 s    339820347 leaves/s
perft  5 :         4865609 leaves in      0.008 s    617521609 leaves/s
perft  6 :       119060324 leaves in      0.114 s   1040846615 leaves/s
perft  7 :      3195901860 leaves in      1.389 s   2301513961 leaves/s
perft  8 :     84998978956 leaves in     17.667 s   4811219445 leaves/s
perft  9 :   2439530234167 leaves in    245.597 s   9933051955 leaves/s
total   :   2527849247519 leaves in    264.999 s   9539099229 leaves/s
It comes with an internal test (mperft -t) and should be correct on any position (at least without hashtable):

Code: Select all

$ mperft -t
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Testing the board generator
Test 1. Initial position  rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 passed
Test 2. r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - passed
Test 3. 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - passed
Test 4. r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1 passed
Test 5. rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6 passed
Test 6. r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10 passed
Test 7. 8/5bk1/8/2Pp4/8/1K6/8/8 w - d6 0 1 passed
Test 8. Enpassant capture gives check 8/8/1k6/2b5/2pP4/8/5K2/8 b - d3 0 1 passed
Test 9. Short castling gives check 5k2/8/8/8/8/8/8/4K2R w K - 0 1 passed
Test 10. Long castling gives check 3k4/8/8/8/8/8/8/R3K3 w Q - 0 1 passed
Test 11. Castling r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1 passed
Test 12. Castling prevented r3k2r/8/3Q4/8/8/5q2/8/R3K2R b KQkq - 0 1 passed
Test 13. Promote out of check 2K2r2/4P3/8/8/8/8/8/3k4 w - - 0 1 passed
Test 14. Discovered check 8/8/1P2K3/8/2n5/1q6/8/5k2 b - - 0 1 passed
Test 15. Promotion gives check 4k3/1P6/8/8/8/8/K7/8 w - - 0 1 passed
Test 16. Underpromotion gives check 8/P1k5/K7/8/8/8/8/8 w - - 0 1 passed
Test 17. Self stalemate K1k5/8/P7/8/8/8/8/8 w - - 0 1 passed
Test 18. Stalemate/Checkmate 8/k1P5/8/1K6/8/8/8/8 w - - 0 1 passed
Test 19. Double check 8/8/2k5/5q2/5n2/8/5K2/8 b - - 0 1 passed
Of course you can use a '--div' command to have the detail for each move:

Code: Select all

$ mperft -d 6 --div
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: no hashing; no bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
 a2a3          4463267
 b2b3          5310358
 c2c3          5417640
 d2d3          8073082
 e2e3          9726018
 f2f3          4404141
 g2g3          5346260
 h2h3          4463070
 a2a4          5363555
 b2b4          5293555
 c2c4          5866666
 d2d4          8879566
 e2e4          9771632
 f2f4          4890429
 g2g4          5239875
 h2h4          5385554
 b1a3          4856835
 b1c3          5708064
 g1f3          5723523
 g1h3          4877234
total   :       119060324 leaves in      2.972 s     40061041 leaves/s
It can be also used for qsearch perft.

Code: Select all

$ mperft -f 'r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1' -c -d 6 -l
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: no hashing; no bulk counting; capture only;
  a b c d e f g h
8 r . . . k . . r 8
7 p . p p q p b . 7
6 b n . . p n p . 6
5 . . . P N . . . 5
4 . p . . P . . . 4
3 . . N . . Q . p 3
2 P P P B B P P P 2
1 R . . . K . . R 1
  a b c d e f g h
w, KQkq
perft  1 :               8 leaves in      0.000 s      3603633 leaves/s
perft  2 :              62 leaves in      0.000 s     10064935 leaves/s
perft  3 :             487 leaves in      0.000 s     13710585 leaves/s
perft  4 :            3690 leaves in      0.000 s     12690093 leaves/s
perft  5 :           25347 leaves in      0.002 s     13308124 leaves/s
perft  6 :          182498 leaves in      0.008 s     22135219 leaves/s
total   :          212092 leaves in      0.014 s     15122828 leaves/s
Have fun with it.
Your code is very fast. I think that doing the board representation colour agnostic could speed up a Perft-program from the initial position a lot. You have two big gains by doing that when hashing. From the start position most of black’s positions have already been searched from white point of view (and the reverse) and the hash-hits will be doubled.

/Pio

User avatar
xr_a_y
Posts: 1464
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: magic bitboard perft

Post by xr_a_y » Sat Apr 11, 2020 6:31 pm

this http://home.hccnet.nl/h.g.muller/perft.c

runs perft 7 in only 14sec on my computer ...

Code: Select all

./perft 7 "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - 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: No hashing, bulk counting in horizon nodes

perft( 1)=           20 ( 0.000 sec)
perft( 2)=          400 ( 0.000 sec)
perft( 3)=         8902 ( 0.000 sec)
perft( 4)=       197281 ( 0.001 sec)
perft( 5)=      4865609 ( 0.022 sec)
perft( 6)=    119060324 ( 0.545 sec)
perft( 7)=   3195901860 (14.363 sec)
And your mperft is taking (bulk counting)

Code: Select all

./mperft -f "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" -d 7 -b
Magic Perft (c) version 1.0 Richard Delorme - 2020
Bitboard move generation based on magic bitboards
Perft setting: no hashing; with bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
perft  7 :      3195901860 leaves in     13.839 s    230936594 leaves/s
both compile with -O3 -march=native -DNDEBUG


Good job

ankan
Posts: 77
Joined: Sun Apr 21, 2013 1:29 pm
Full name: Ankan Banerjee
Contact:

Re: magic bitboard perft

Post by ankan » Sat Apr 11, 2020 7:22 pm

My old perft program also uses magic bitboards. It can be found here: https://github.com/ankan-ban/perft_cpu
On my CPU (i7 4970k) it takes 5.46 seconds for perft(7) of start pos. Single threaded, bulk counting without using transposition tables.

The move-generation code is mostly same that I used in my GPU perft program for computing perft(15).

(sorry for not so great build system - visual studio project should work on windows, and hopefully simple enough to compile all the cpp files in any platform).

Post Reply