Chess bitboard move generation

Question

I am writing a chess engine, and I'm understanding how chess engines store game positions (in 64-bit bitboards) and how to generate moves from them. When you get your final bitboard of moves, how do you know what piece moves where? For example, take a white knight. You can easily bitshift the white knight bitboard to get the squares the knight/s would move to, and then use other binary operators to make sure that those squares are not occupied by your own pieces and the knight did not move out of bounds. If this is the white knight bitboard:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0

you can figure out that these are the legal moves (assuming there are no friendly pieces on the squares but they are irrelevant for this example)

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0
0 0 * 1 0 0 0 0
1 * 0 0 1 0 0 0
0 1 0 1 0 0 0 0

(*s are used for the knight's positions, just so it's easier to visualize). Now that you know that a knight can move to e2, what does that do? How do you know which white knight. How do you know that both white knights could move to d1? The binary and bitboard operators are used because they are very efficient, but I cannot see how they help getting a final list of legal moves.

Answer 1

When you generate moves you go through each bit in e.g. the knights bitboard. You will then store both the knight bit (start square) and each possible square it can move to (end square) which will get you all legal moves for the piece. I usually store the information either as an object or encode it as a bit number.

During move generation you will also store other information about the move such as if it is a capture move, castling, e.p. etc. Basically any information that is cheap and helpful/needed in later stages of your AI.

I think this is what you are looking for. I also suggest looking at the really nice serie from Code Monkey King about chess programming, if you aren't writing in C you can still get the concepts pretty easily from it. I used it as a guide for both my Python and C# engine.

Answer 2

I do this by storing an array of 64-bit unsigned integers that contains attack maps for knights on each square of the chessboard:

uint64_t knight_attacks[64];

This array can be populated when the program starts. In this array index 0 represents A1 and index 63 represents H8. So:

knight_attacks[0]:   knight_attacks[9]:   knight_attacks[18]
(Knight on A1)       (Knight on B2)       (Knight on C3)
0 0 0 0 0 0 0 0      0 0 0 0 0 0 0 0      0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0      0 0 0 0 0 0 0 0      0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0      0 0 0 0 0 0 0 0      0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0      0 0 0 0 0 0 0 0      0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0      1 0 1 0 0 0 0 0      1 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0      0 0 0 1 0 0 0 0      0 0 * 0 0 0 0 0
0 0 1 0 0 0 0 0      0 * 0 0 0 0 0 0      1 0 0 0 1 0 0 0
* 0 0 0 0 0 0 0      0 0 0 1 0 0 0 0      0 1 0 1 0 0 0 0

And then you have your knight bitboard knight_bb:

0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0  

You will require some sort of pop LSB function, i.e., a function that returns the position of the least significant bit in a bitboard and then zeros the bit.

Square square_of_first_knight = pop_LSB(&knight_bb);

This will return 9 (the index of square B2), now you can get all of the squares attacked by this knight from the look up table:

uint64_t knight_attack_bb = knight_attacks[square_of_first_knight];

Now you can pop all of the bits out of the knight_attack_bb (using pop_LSB and pair them with the knight square to make up your moves:

Squares_idx    Algebraic  
9, 3           B2, D1         1st call: pop_LSB(&atk_bb) returns 3
9, 19          B2, D3         2nd call: pop_LSB(&atk_bb) returns 19
9, 24          B2, A4         3rd call: pop_LSB(&atk_bb) returns 24
9, 26          B2, C4         4th call: pop_LSB(&atk_bb) returns 26

At this point, all of the bits have been popped out of atk_bb so it equals zero. You can use this as a check for when to stop popping bits.

You now repeat this process for the second knight, and you will get a list of (from, to) pairs for all the knight moves.