Winboard Forum

I'm writing a chess engine,I'm working on move generation and I have the following dillema:
when generating moves how do I make sure that the move I make won't let my king in check.Of course I could check this for every move I make but that would be very inefficient.

I read about precomputing some bitboards so I could do a simple look-up and applying bitwise operations to tell if my move is valid:
"The common approach is to apply a pre-calculated 64 times 64 array for every from- or to-square. Containing bitboards with in-between or obstructed sets for distant squares sharing the same line. If the intersection with occupied squares is empty, the move is considered valid. This is implicitly true for squares in king- and knight distance as well since they already contain zero."

My question is what should the bitboards contain,can you explain me what this line is about "Containing bitboards with in-between or obstructed sets for distant squares sharing the same line".

Thanks you.

In Joker I first check for own pieces pinned on the King, by running through the enemy slider list. I trat such pieces special, they do not participate in the normal move generation, and I only generate moves along the pin line for them.

Then the only moves that could put my King in check are King moves and e.p. captures. Those I check after the move,which is an expensive test, but not performed too often.

vlad_tudose wrote:I'm writing a chess engine,I'm working on move generation and I have the following dillema:
when generating moves how do I make sure that the move I make won't let my king in check.Of course I could check this for every move I make but that would be very inefficient.

I read about precomputing some bitboards so I could do a simple look-up and applying bitwise operations to tell if my move is valid:
"The common approach is to apply a pre-calculated 64 times 64 array for every from- or to-square. Containing bitboards with in-between or obstructed sets for distant squares sharing the same line. If the intersection with occupied squares is empty, the move is considered valid. This is implicitly true for squares in king- and knight distance as well since they already contain zero."

My question is what should the bitboards contain,can you explain me what this line is about "Containing bitboards with in-between or obstructed sets for distant squares sharing the same line".

Thanks you.

There are many aspects of checking the validity of moves.

- If you are testing your own move the move generator should produce pseudo legal moves.
The only validity test missing is the test whether your king is in check after the move.
Don't do this test inside the move generator. Do it when you are actually doing the move on
the board and immediately skip it as invalid and try the next move. This saves time since
very often previous moves will trigger a cutoff and the untested move is never made.

You should know before move generating if your king is in check before your moves.
If so you could even use another different move generator.

- If you want to test the legality of moves from suspicious sources like the opponent user moves
or hash table moves or killer moves there are more things to test. A very slow method
is to generate all valid moves and then look for the move in the list. Faster methods are
like small move driven move generators. Test the from and to squares and the pieces on it
and test the squares between these squares for slider moves.

- Beware of all special cases. If your king moves the test may be different than the test for
other moving pieces. If a king is in check only king moves or capture the attacker
moves or moves blocking sliders in the direction from the king to the from square and
to the to square may be valid.

- An array move_directions[64][64] may help to find the direction between two squares and
most entries just tell you there is no connection between squares.

- With bitboards there may be arrays for all pieces and all squares that tell you all attacked
squares (bits) by the piece on an empty board. Or you could look in a bitboard if a queen
on your king's square could attack the from/to square of the last move. With this information
decide if and what you should test (own king in check).

- May be the in_between[64][64] bitboards of your question are used to test these moves
with questionable validity. If you intersect it with an occupied bitboard, that is a
bitboard containig 1-bits for all pieces on the board, and the result ist not zero
(in_between[from][to] & occ) != 0,
than that move is really invalid if the moving piece is a slider.
In_between in this case does not include the from- and to-square.

I think I may have confused you enough now. Please refine your question.

Harald

Thank you for the answer Harald,my question refers to how do you pick valid moves when generating all moves in an efficent way.I understand what in-between array does,but I can't figure out how it should look like,if you could give me an example it would be great.

Assume you are using a bitboard with the mapping A1=0, H1=7, A8=56, H8=63.

Code: Select all

Bitboard in_between[64][64];
in_between[0][3] = 0x0000000000000006;
// 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 1 0 0 0 0 0
// and if there is a knight on B1 a rook can not go from A1 to D1,
// because in_between[0][3] & occ is 0x0000000000000002 and not 0.

in_between[0][63] = 0x0040201008040200;
// 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 1 0 0 0
// 0 0 0 1 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
// and if the A1-H8 diagonal is empty a bishop can move from A1 to A8
// because in_between[0][63] & occ is 0x0000000000000000.

I dont use these in_between bitboards and I am not an expert with them.

Harald