1

I'm new to writing chess engines but just recently finished my first program. It ran slowly however so I switched over to bitboards, and now to magic bitboards. I used the chess programming wiki a lot.

I'm now trying a test position and a perft function to see how many nodes per second the program can calculate (including bulk-counting). Right now my perft function is set to calculate only pseudo legal moves and I have set the make_move function to not switch the turn. Therefore I can analyze the position R7/8/8/8/8/8/8/8 w - - with perft.

My problem however is that without magic bitboards, I get 6.22 million nodes per second, and with I only get 6.29. It seems that my magic bitboards are not working properly. It feels intuitively that the speed up of magic bitboards should be much greater. Also, 95% of the computing time is spent in my pseudo legal move generator.

As I mentioned, I'm new to chess engines, and especially magic bitboards. I didn't know how to finish the look up table properly and right now I have a table (for rooks) of 64*8192 entries. I initialize this table at the start of the program by calculating all different combinations of blockers for each square. Then my index is given by (occ >> (64-13))+8192 * square, to not get overlaps in the table entries. (From https://www.chessprogramming.org/Magic_Bitboards).

Is the reason for my slow magic bitboards my gigantic table size? Is there another way to do this more effectively?

Edit: After further inspection it is totally possible that the reason the speed up is so small is because the time is not spend generating moves, but rather iterating over the bits in the different bitboards. Is there a way to speed up this process? It seems (with some googling) that my functions

int ls1b(u64 bitboard) {
    if (bitboard) {
        return count((bitboard & -bitboard) - 1);
    }
    return -1;
}

and

int count(u64 bitboard) {
    int count = 0;
    while(bitboard) {
        count++;
        bitboard &= bitboard - 1;
    }
    return count;
}

are as fast as they can be. How does stockfish (or other c++ engines) do this iterating?

1
  • 3
    Your popcount implementation is only good for sparse bitboards. There are much faster methods involving clever bitshifts for dense bitboards. Also your forward bitscan (lsb) function is really slow too. Look up De Bruijn magics if you want a faster method. Note: I doubt this will speed up your chess engine by a substantial amount. It is true that the move generation speed is slow (my engine gives 100m nps), but improving the nps is only possible if we see the entire code, which is impractical. If you shorten your question to only ask the content in the edit then I can answer it if you'd like. Oct 14 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.