Factors that contribute to slow move generation in building chess engine

Question

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.
• For make_move
  • 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_move check 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 count as 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?

Answer 1

8 seconds for perft(6) is alright - and move generation is not particularly important in the grand scheme of things. There are 3000+ chess engines with perft speed around the same speed as yours. Move generation usually only takes around 10% of the time. Evaluation, pruning and move ordering are all significantly more important factors.

However, one of the best things you can do to improve perft speed is to get rid of branched code. This does two things: First, branching is inherently slow, and the reason is somewhat complex but you can read about it here. In addition, Rust's compiler automatically "vectorizes" code, i.e. takes sequential code and "parallelizes" it. Again, a complicated topic, but you can read about it here. This results in a huge speed boost sometimes (and is partially the reason why the linter recommends iterating over a list by value, as it is able to very easily autovectorize it). However, branched code makes it significantly harder for the compiler to identify potential places to autovectorize.

So, instead of using

if to_move == 0 {
    2
} else if to_move == 1 {
    5
} else {
    panic!("Invalid color!")
}

use

const FOO: [u8; 2] = [2, 5];
FOO[to_move as usize]

Finally, use a profiler! find out what parts of your code are slow and speed them up