3

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?

2
  • If you haven't already done it, I'd consider posting this question on this forum: talkchess.com/forum3/viewforum.php?f=7
    – emdio
    Commented Nov 25, 2022 at 9:34
  • 3
    I am not a chess engine expert but you might gain some information if you use a code performance analyzer thing which shows which part of the code takes most of the time. I don't know if there is something like that for Rust but I remember using something like that on Visual Studio with C++. It shows which functions or which loops take how much CPU/GPU and how much time.
    – Minot
    Commented Nov 25, 2022 at 15:25

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.