In your implementation you are not taking advantage of the power of bitboards. That is the main reason for getting a slow move generator, and probably slow engine code in general.Henk wrote:Skipper uses 19% percent of it's time for collecting captures.jdart wrote:Most programs do not spend most of their time in movegen. Usually it is sub 10% of the total search time. You can profile and see if this is the case for you.
I am not clear if you are using bitboards or not. Finding attacked pieces with bitboards and magic move generation is pretty fast and can be done with no looping at all.
--Jon
Other bottleneck is collecting remaining moves after killers. And that's another 10-20%.
Besides that, I would strongly recommend that you write a small utility function that calculates the MVV/LVA score for given piece types of moving piece, captured piece, and possibly also promotion piece. This will greatly simplify your code (it will remove a lot of inner switch blocks) without slowing it down; I would even expect it to become slightly faster due to the much more compact code. Also don't bother with the special case of "king capture" in the move generator. By checking each single move whether it captures the king (which is not the case for the majority of moves) you are in fact slower than simply assigning a sufficiently high score to moves capturing the king and letting your move ordering do the rest.
Regarding the use of bitboards, let's take a look at generating knight moves for instance (actually you do the same for kings at least). What you do is the following:
a) you get all possible knight move target squares for the given source square at once (good);
b) now you loop over 8 possible (knight) directions and extract all moves (target squares) for that direction from the previously obtained set of target squares (why do you do that?);
c) finally you loop over all moves in that direction (which must be either 0 or 1 moves since there are never two knight moves going into the same direction), for each one you look up the board to see whether there is an enemy piece present, and if so, you add a capture move to the move list.
This can be done faster. Ignore the intermediate step through the direction. Simply get a bitboard from your board representation that shows all squares occupied by an enemy piece, and do an AND with the set of target squares obtained in step a). The resulting bitboard shows all target squares where the given knight can capture an enemy piece. Then loop over these bits only to fill your move list.
Do the same for kings.
For pawns I see two possible improvements.
- First one: move the whole EP move generation to one central place. Don't test for each single pawn whether it can capture en passant, since there is at most one EP target square for the whole position and therefore there are at most two possible EP moves (if you have two pawns left and right to the enemy pawn that has just made a double step). EP is a very rare move and should be handled like that.
- Second one: generate *all* pawn captures at once using one shift operation, in two steps: one for all captures to the left side and one to the right. To get that done make sure your board representation is able to return a bitboard for all squares occupied by pawns of a given color (I assume you have that already). Figure out how to exclude pawns on a-file for captures to the left, and h-file for captures to the right. I am sure you'll find out the remaining stuff on your own. For this purpose you would also exclude all pawns from your "main loop" that loops over all pieces of the active color.
Sliding move generation is a separate issue. Here you currently do the same stuff with directions as described above, which is really slow. Probably you can get the biggest performance boost by improving this part of your move generator but here you would need a different technology. Most authors of a bitboard program use magic bitboards, rotated bitboards or something like that for an efficient implementation of sliding moves/sliding attacks generation. Maybe you have new ideas in that area. However, if you haven't then it is really hard to get that working without using anything that has been published by others. I suggest you take a look at the bitboards section in the chessprogramming wiki, if you haven't done so yet.
The key point is, e.g. for a given bishop you want to get all attacks to all directions "at once", i.e. with as few operations as possible, and this shall cover all attacks to empty squares as well as attacks (resp. defenses) to enemy or friendly pieces. For capture generation you can use this attack bitboard by simply AND-ing with the bitboard of all enemy pieces, as mentioned above for knights, and there you are. You save one inner loop compared to your current code, provided the code to obtain the attack bitboard is fast (for magic bitboards it is, definitely).
Similar things can be done for generating non-captures, of course, and for in-check detection and legality checking as well.