Insanely buggy move generator, please help
Moderators: hgm, Rebel, chrisw
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Insanely buggy move generator, please help
Also have a look at blackDoublePush(), the shift direction looks wrong ...
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Insanely buggy move generator, please help
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.
-
- Posts: 646
- Joined: Wed Jun 18, 2014 2:30 pm
- Full name: Fahad Syed
Re: Insanely buggy move generator, please help
Thanks! I've lately been able to do correct perft 1. perft 2? 730+ movesSven Schüle wrote: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?vittyvirus wrote: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.
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.
-
- Posts: 6442
- Joined: Tue Jan 09, 2007 12:31 am
- Location: PA USA
- Full name: Louis Zulli
Re: Insanely buggy move generator, please help
Are your perft 1 results correct for all legal positions, or just for the start position?vittyvirus wrote:Thanks! I've lately been able to do correct perft 1. perft 2? 730+ movesSven Schüle wrote:
Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1.
What do you get for this position, for example?
[D]k7/8/8/KPp4r/8/8/8/8 w - c6
-
- Posts: 646
- Joined: Wed Jun 18, 2014 2:30 pm
- Full name: Fahad Syed
Re: Insanely buggy move generator, please help
Here's what it generates for white:zullil wrote:Are your perft 1 results correct for all legal positions, or just for the start position?vittyvirus wrote:Thanks! I've lately been able to do correct perft 1. perft 2? 730+ movesSven Schüle wrote:
Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1.
What do you get for this position, for example?
[D]k7/8/8/KPp4r/8/8/8/8 w - c6
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
-
- Posts: 6442
- Joined: Tue Jan 09, 2007 12:31 am
- Location: PA USA
- Full name: Louis Zulli
Re: Insanely buggy move generator, please help
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."vittyvirus wrote:Here's what it generates for white:zullil wrote:Are your perft 1 results correct for all legal positions, or just for the start position?vittyvirus wrote:Thanks! I've lately been able to do correct perft 1. perft 2? 730+ movesSven Schüle wrote:
Get perft(1) working perfectly for a couple of test positions before moving on to perft(N) for N>1.
What do you get for this position, for example?
[D]k7/8/8/KPp4r/8/8/8/8 w - c6I told you its insanely buggy.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
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: Insanely buggy move generator, please help
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.zullil wrote: 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."
-
- Posts: 646
- Joined: Wed Jun 18, 2014 2:30 pm
- Full name: Fahad Syed
Re: Insanely buggy move generator, please help
I'd surely try.Rein Halbersma wrote: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.zullil wrote: 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."
Any way, I think I'll end up in rewriting my movegen. This code looks (to me) very simple and bug free...
-
- Posts: 2559
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: Insanely buggy move generator, please help
Well... if it produces wrong results then it's buggy, it's as simple as thisThis code looks (to me) very simple and bug free...
Someone recently said that his perft gives "almost correct" results. Almost is not enough...
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Insanely buggy move generator, please help
Indeed. When you can do ALL of these correctly, then you can pretty safely say that your movegen is accurate:mar wrote:Well... if it produces wrong results then it's buggy, it's as simple as thisThis code looks (to me) very simple and bug free...
Someone recently said that his perft gives "almost correct" results. Almost is not enough...
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
Last edited by JVMerlino on Mon Aug 04, 2014 8:38 pm, edited 1 time in total.