Insanely buggy move generator, please help

[Sven]

Also have a look at blackDoublePush(), the shift direction looks wrong ...

[Sven]

Castling code needs to be looked at as well. If your square numbering is A1=0, ..., H1=7 (I suggest to use such constants to improve readability of all your castling related code) then your masks to test whether all squares between king and rook are empty do not look correct to me. If you use A1=7, ..., H1=0 then other parts of your castling code would be wrong.

[vittyvirus]

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.

Thanks! I've lately been able to do correct perft 1. perft 2? 730+ moves

[zullil]

Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1.

Thanks! I've lately been able to do correct perft 1. perft 2? 730+ moves

Are your perft 1 results correct for all legal positions, or just for the start position?

What do you get for this position, for example?
[D]k7/8/8/KPp4r/8/8/8/8 w - c6

[vittyvirus]

Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1.

Thanks! I've lately been able to do correct perft 1. perft 2? 730+ moves

Are your perft 1 results correct for all legal positions, or just for the start position?

What do you get for this position, for example?
[D]k7/8/8/KPp4r/8/8/8/8 w - c6

Here's what it generates for white:

Code: Select all

m_move=27558
Piece 6 From 38 To 46 Capt 0
1. g7
m_move=6055
Piece 1 From 39 To 30 Capt 0
2. Kg5
m_move=595943
Piece 1 From 39 To 31 Capt 9
3. Kxh5
m_move=6183
Piece 1 From 39 To 32 Capt 0
4. Ka5
m_move=7079
Piece 1 From 39 To 46 Capt 0
5. Kg7
m_move=7143
Piece 1 From 39 To 47 Capt 0
6. Kh7
m_move=1052804
Piece 1 From 4 To 2 Capt 0
7. O-O-O

I told you its insanely buggy.

[zullil]

Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1.

Thanks! I've lately been able to do correct perft 1. perft 2? 730+ moves

Are your perft 1 results correct for all legal positions, or just for the start position?

What do you get for this position, for example?
[D]k7/8/8/KPp4r/8/8/8/8 w - c6

Here's what it generates for white:

Code: Select all

m_move=27558
Piece 6 From 38 To 46 Capt 0
1. g7
m_move=6055
Piece 1 From 39 To 30 Capt 0
2. Kg5
m_move=595943
Piece 1 From 39 To 31 Capt 9
3. Kxh5
m_move=6183
Piece 1 From 39 To 32 Capt 0
4. Ka5
m_move=7079
Piece 1 From 39 To 46 Capt 0
5. Kg7
m_move=7143
Piece 1 From 39 To 47 Capt 0
6. Kh7
m_move=1052804
Piece 1 From 4 To 2 Capt 0
7. O-O-O

I told you its insanely buggy.

OK. So forget about perft(2) and follow Sven's advice: "Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1."

[Rein Halbersma]

OK. So forget about perft(2) and follow Sven's advice: "Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1."

Pro tip: keep a set of such perft(1) unit tests that are automatically run after every build. Takes 0.01 seconds but will catch move generation bugs early.

[vittyvirus]

OK. So forget about perft(2) and follow Sven's advice: "Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1."

Pro tip: keep a set of such perft(1) unit tests that are automatically run after every build. Takes 0.01 seconds but will catch move generation bugs early.

I'd surely try.
Any way, I think I'll end up in rewriting my movegen. This code looks (to me) very simple and bug free...

[mar]

This code looks (to me) very simple and bug free...

Well... if it produces wrong results then it's buggy, it's as simple as this
Someone recently said that his perft gives "almost correct" results. Almost is not enough...

[JVMerlino]

This code looks (to me) very simple and bug free...

Well... if it produces wrong results then it's buggy, it's as simple as this
Someone recently said that his perft gives "almost correct" results. Almost is not enough...

Indeed. When you can do ALL of these correctly, then you can pretty safely say that your movegen is accurate:

r3k2r/8/8/8/3pPp2/8/8/R3K1RR b KQkq e3 0 1 // perft(6) = 485,647,607
r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1 // perft(6) = 706,045,033
8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28 // perft(6) = 38,633,283
8/3K4/2p5/p2b2r1/5k2/8/8/1q6 b - - 1 67 // perft(7) = 493,407,574
rnbqkb1r/ppppp1pp/7n/4Pp2/8/8/PPPP1PPP/RNBQKBNR w KQkq f6 0 3 // perft(6) = 244,063,299
r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - // perft(5) = 193,690,690
8/p7/8/1P6/K1k3p1/6P1/7P/8 w - - // perft(8) = 8,103,790
n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - - // perft(6) = 71,179,139
r3k2r/p6p/8/B7/1pp1p3/3b4/P6P/R3K2R w KQkq - // perft(6) = 77,054,993
8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - // perft(7) = 178,633,661
8/5p2/8/2k3P1/p3K3/8/1P6/8 b - - // perft(8) = 64,451,405
r3k2r/pb3p2/5npp/n2p4/1p1PPB2/6P1/P2N1PBP/R3K2R w KQkq - // perft(5) = 29,179,893