Insanely buggy move generator, please help

[vittyvirus]

But but, here's what Cheng (another strong engine) has to say:

Code: Select all

perft 6
119060324 nodes
took 2537 ms

For reference, here's what I get on my 2.0 GHz Intel Core 2 Duo Late 2007 MacBook:

Code: Select all

ProcyonLeo: ~/Documents/Chess/Kirby] ./perft_new 
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
Depth = 6
Leaf nodes = 119060324
Time taken = 5425 ms

For which engine? Cheng? Or Yours?
And I've 4x 2.4 Ghz Intel i5 2nd gen @2.40 Ghz

[zullil]

But but, here's what Cheng (another strong engine) has to say:

Code: Select all

perft 6
119060324 nodes
took 2537 ms

For reference, here's what I get on my 2.0 GHz Intel Core 2 Duo Late 2007 MacBook:

Code: Select all

ProcyonLeo: ~/Documents/Chess/Kirby] ./perft_new 
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
Depth = 6
Leaf nodes = 119060324
Time taken = 5425 ms

For which engine? Cheng? Or Yours?
And I've 4x 2.4 Ghz Intel i5 2nd gen @2.40 Ghz

Above is for my move generator on the old MacBook. My earlier post was my move generator on an Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz.

[vittyvirus]

zullil, if you remembered you had once challenged me to write a correct move gen. i haven't still done that, but just to remind you

[zullil]

zullil, if you remembered you had once challenged me to write a correct move gen. i haven't still done that, but just to remind you

But you're working at it, and you haven't given up, so good! My "challenge" was designed to encourage you to start writing code, which is what you've done. Keep at it, and good luck.

[zullil]

This is my move generator code for black. Its insanely buggy, please help me find those bugs.

One day I might use bitboards, and maybe even understand "magic" bitboards. For now, I use an array of 130 (thought of as 13 x 10) ints for my board representation. (It's a 12 x 10 scheme, with an extra "rank" that holds state information and king locations.) After two weeks of writing and debugging (twice finding = where I intended to have ==), I seem to have a working (legal) move generator:

Code: Select all

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
Depth = 6
Leaf nodes = 119060324
Time taken = 2353 ms

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Depth = 5
Leaf nodes = 193690690
Time taken = 2199 ms

Good luck getting yours working. I'm sure it will be faster than mine once you've killed all the bugs.

If your move generator does perft 6 in under 3 seconds, it is fairly difficult to beat.

But not for a world-class engine like the one you want to create!

Code: Select all

Stockfish 270714 64 SSE4.2 by Tord Romstad, Marco Costalba and Joona Kiiski
position startpos
perft 6

Position: 1/1

Perft 6 leaf nodes: 119060324

===========================
Total time (ms) : 758
Nodes searched  : 119060324
Nodes/second    : 157071667

You have a faster system:

Code: Select all

Stockfish 5 64 SSE4.2 by Tord Romstad, Marco Costalba and Joona Kiiski
perft 6

Position: 1/1

Perft 6 leaf nodes: 119060324

===========================
Total time (ms) : 939
Nodes searched  : 119060324
Nodes/second    : 126794807

But but, here's what Cheng (another strong engine) has to say:

Code: Select all

]
perft 6
119060324 nodes
took 2537 ms

Here's what Cheng gives on my Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz:

Code: Select all

louis@LZsT5610:~/Documents/Chess/cheng4$ ./cheng4_linux_x64 
perft 6
119060324 nodes
took 1918 ms

My generator takes about 25% longer.

[vittyvirus]

This is my move generator code for black. Its insanely buggy, please help me find those bugs.

One day I might use bitboards, and maybe even understand "magic" bitboards. For now, I use an array of 130 (thought of as 13 x 10) ints for my board representation. (It's a 12 x 10 scheme, with an extra "rank" that holds state information and king locations.) After two weeks of writing and debugging (twice finding = where I intended to have ==), I seem to have a working (legal) move generator:

Code: Select all

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -
Depth = 6
Leaf nodes = 119060324
Time taken = 2353 ms

louis@LZsT5610:~/Documents/Chess/Kirby$ ./perft_new 
FEN string = r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
Depth = 5
Leaf nodes = 193690690
Time taken = 2199 ms

Good luck getting yours working. I'm sure it will be faster than mine once you've killed all the bugs.

If your move generator does perft 6 in under 3 seconds, it is fairly difficult to beat.

But not for a world-class engine like the one you want to create!

Code: Select all

Stockfish 270714 64 SSE4.2 by Tord Romstad, Marco Costalba and Joona Kiiski
position startpos
perft 6

Position: 1/1

Perft 6 leaf nodes: 119060324

===========================
Total time (ms) : 758
Nodes searched  : 119060324
Nodes/second    : 157071667

You have a faster system:

Code: Select all

Stockfish 5 64 SSE4.2 by Tord Romstad, Marco Costalba and Joona Kiiski
perft 6

Position: 1/1

Perft 6 leaf nodes: 119060324

===========================
Total time (ms) : 939
Nodes searched  : 119060324
Nodes/second    : 126794807

But but, here's what Cheng (another strong engine) has to say:

Code: Select all

]
perft 6
119060324 nodes
took 2537 ms

Here's what Cheng gives on my Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz:

Code: Select all

louis@LZsT5610:~/Documents/Chess/cheng4$ ./cheng4_linux_x64 
perft 6
119060324 nodes
took 1918 ms

My generator takes about 25% longer.

So you've a fairly good move generator. What about my code?

[hgm]

My 7-year-old qperft still doesn't do too bad, even as a non-PGO 32-bit compile with gcc 3.4.4 -O4 (it uses a 0x88 mailbox board). On my 2.2GHz i3 laptop:

Code: Select all

C:\cygwin\home\perft>qperft 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: 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.015 sec)
perft( 5)=      4865609 ( 0.031 sec)
perft( 6)=    119060324 ( 1.079 sec)

It does seem high time to design something faster, though.

[ZirconiumX]

Such fast move generators. I adapted Sunfish's move generator to become a perft counter, just to get an idea of the relative speed of the various Python interpreters/compilers.

CPython (interpreter)

Code: Select all

[matthew@localhost sunfish]$ python perft.py
Perft(1) = 20 (0.004 sec)
Perft(2) = 400 (0.149 sec)
Perft(3) = 8902 (2.226 sec)
Perft(4) = 197281 (50.984 sec)

PyPy (JIT compiler)

Code: Select all

[matthew@localhost sunfish]$ pypy perft.py
Perft(1) = 20 (0.019 sec)
Perft(2) = 400 (0.274 sec)
Perft(3) = 8902 (1.280 sec)
Perft(4) = 197281 (6.568 sec)
Perft(5) = 4865609 (91.719 sec)

Nuitka GCC backend (AOT compiler)

Code: Select all

[matthew@localhost sunfish]$ ./perft.exe
Perft(1) = 20 (0.004 sec)
Perft(2) = 400 (0.082 sec)
Perft(3) = 8902 (2.091 sec)
Perft(4) = 197281 (52.200 sec)

Nuitka Clang backend (AOT compiler)

Code: Select all

[matthew@localhost sunfish]$ ./perft.exe
Perft(1) = 20 (0.004 sec)
Perft(2) = 400 (0.126 sec)
Perft(3) = 8902 (2.581 sec)
Perft(4) = 197281 (62.011 sec)

Python is probably not the language to use if you want a fast program.

Matthew:out

[hgm]

Python is probably not the language to use if you want a fast program.

Perhaps not, but the numbers you show here are truly dismal. 4000 moves per second. My old 1Mz 6502 assembly program would probably do better, and on a modern PC with a 6502 emulator it would certainly do better. And many of the compiled versions are just as poor, or hardly better.

So something must seriously suck in the algorithm too.

[Sven]

This is my move generator code for black. Its insanely buggy, please help me find those bugs. I've fixed parts of white move generator code, but Black's movegen code is still buggy. So just not to confuse you guys, I've only posted White movegen code.

If your move generator works for one color but not for the other then why don't you store both functions GenWhiteMoves() and GenBlackMoves() in separate temporary files and use a graphical "diff" tool to compare them and watch out for unwanted differences? Look at each single difference and answer the question: is this the correct way of generating black moves instead of white moves?

As to your code: a lot has already been said about it, I suggest to follow those advices of course. I would especially follow the advice to do isolated tests before testing all at once. Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1. Get move generation for kings (without castling) and knights perfect, then move on to rooks, bishops, queens, then trivial pawn moves (single push + capture), then special pawn moves (double push, promotion, ep), finally castling. Always use test positions that are appropriate for the current phase of testing by not including piece types or move types that are not supported yet. While testing this way, comment out (#if 0 - #endif) the move generation code that has not been tested before AND is not needed in the current test step, and uncomment step by step.

Now watch out for legality issues as well. You can have a 100% perfect pseudo-legal move generator but your perft(1) tests can already fail miserably - why?

1) When in check, only certain check evasions are legal.
2) When not in check, only those moves are legal that do not put the own king into check (king moves, moves of pinned pieces, ep capture are candidates for illegal moves).

So your own perft() function must somehow take this into account, by counting legal move paths only. I'd assume you have done this already.

But just in case you haven't done so yet: a typical approach is to write a legal move generation function on top of the pseudo-legal move generator, and only use the legal generator inside perft() which would become a very simple function of only few lines. The first, dumb implementation of the legal move generator would be very slow and ineffective, by making/unmaking each pseudo-legal move on the board and testing inbetween whether it leaves the own king in check. A better implementation would restrict this make/unmake test to only few types of moves (see above): check evasions, king moves, moves of pinned pieces, and ep captures, while all other pseudo-legal moves are intrinsically legal. I'd suggest to start with the slow way to catch all bugs, and optimize it later (testing again).

Just a note: an efficient legal move generator may be useful for tree search as well, not only for perft, so the effort for writing it now might pay off later. There are certainly different opinions about that, some prefer a pseudo-legal move generator for tree search and some don't.