I'm building a toy chess engine. I have a correct but slow move generation. Doing perft on starting position to depth 6 with my engine takes 8 seconds and but takes stockfish 0.5 seconds on my computer. So that's an order of magnitude difference.
I'd like to exposit the algorithms I've used so far to see if anyone can spot any obvious problems. How I've implemented move generation so far:
- Rust as programming language, so there should be little/no language overhead
- Bitboard representation with u64 for each piece type, white occupancy, black occupancy, board occupancy
- Non-sliding pieces uses look-up table to find attack mask
- Sliding pieces uses look-up tables generated through magic bitboards
- Moves are generated by piece type
- pseudo-legal style -- I check for king-check during the make-move stage
- For each piece type, loop through the LSBs (
x & -x) of the bitboard
- Obtain the attack mask and generate a move structure (32-bits in size)
- Do this for all the piece types
- Generate move for enpassant if applicable
- Generate the moves for castling if applicable
- To elaborate, e.g. for the start position, the pawn bitboard has 8 bits set and I iterate through them to generate the 16 pawn moves.
- The move structure distinguishes between castling, enpassant, promotion, normal move so make_move is more efficient, no hunting through bitboards to see what type of move it is
- Do the bit operations needed to update the bitboards
- After doing
make_movecheck if king is in check, and dispose move if it is
- There is little/no dynamic memory allocation during the movegen/makemove process because I implement these using iterators, which incurs very little overhead in Rust. Almost all operations are on the stack.
- I've also tried zobrist hash generation, which also works properly according to Perft numbers. For the caching, I use a hash map with
(hash, depth)as the key and
countas the value, so the same position at the same depth is not calculated twice. This does not seem to make much difference in the performance.
I can see that data structure improvements might make it a bit faster, or optimize for hardware instructions, but to observe more than an order of magnitude difference in speed, I must be using inferior algorithms. But none of my reading points to the answer.
I'm happy to elaborate on anything else I've missed. Is there anything obvious in these algorithms that I can be doing instead?