Move generation

NagaSkaki has a unique method of generating moves. Instead of using rotated bitboards (like most programs do), it uses shifted bitboards. Before I go into detail about how this works, let me first explain how NagaSkaki represents the chess board.

NagaSkaki represents the chessboard as a combination of 64bit integers, called bitboards. The chessboard structure looks something like this (remember we'll call the 64bit integers bitboards - this is standard in chess literature):

struct chessboard
{
bitboard white_pawns;
bitboard black_pawns;
bitboard white_knights;
bitboard black_knights;
bitboard white_bishops;
bitboard black_bishops;
bitboard white_rooks;
bitboard black_rooks;
bitboard white_queens;
bitboard black_queens;
bitboard white_king;
bitboard black_king;
}

We let each bit of the bitboard map to a square on the chess board, e.g. bit 0 maps to square A1, bit1 maps to square B1 ..... bit 63 maps to square H8. Here is a representation of the mapping of all 64 bits of a bitboard to the squares on a chessboard:

If there is a piece on a square, the corresponding bit of the bitboard will be set to one. For example, when starting a game of chess the white king will be on square E1. E1 corresponds to bit 4 of the white_king bitboard, thus white_king = 0x10 (see the tutorial on boolean algebra if this doesn't make sense.) The full list of chess bitboards at the beginnig of a game are:

white_pawns = 0x000000000000ff00
black_pawns = 0x00ff000000000000
white_knights = 0x000000000000042
black_knights = 0x4200000000000000
white_bishops =0x000000000000024
black_bishops = 0x2400000000000000
white_rooks = 0x000000000000018
black_rooks = 0x1800000000000000
white_queens = 0x0000000000000008
black_queens = 0x0800000000000000
white_king = 0x0000000000000010
black_king = 0x1000000000000000

We will also have other useful bitboards, namely:

Move generation

King moves

To generate the king's moves is very easy. First we precalculate a bitboard for each square with only the bits the king can move to set, lets call it: king_xray[64]. Now if the king is on square A1, it can only move to squares: B1,A2 and B2, thus:
king_xray[0] = 0x302. To generate the kings moves on any square, we AND the king_xray for that particular square with the enemy_and_empty_squares bitboard. Now all the bits where the king can move to will be set.

To generate only captures, AND the king_xray with the enemy_squares bitboard. To generate only non-captures, AND the king_xray with the empty_squares bitboard.

Knight moves

For the knight we do exactly the same thing as for the king, thus:

knight_moves = knight_xray[square] AND enemy_and_empty_bitboard

Pawn moves

For pawn moves we do the following:

Rook moves

Things get a bit more difficult with the sliding pieces (rook, bishop and queen), because their moves will be stopped by the first piece on a file, rank or diagonal.

First, precalculate the following bitboards:

To calculate the squares to the right where the rook can move to, we do the following:

right_moves = right_board[sq] AND occupiedboard

We do this because the first piece will stop the rook moving to the right. Right_moves will now look as follows:

Because the first piece will stop the rook, we need to fill in all the squares to the right of the piece (<< 1 means shift left one, << 2 means shift left 2, etc):

right_moves = (right_moves<<1) OR (right_moves<<2) OR (right_moves<<3) OR (right_moves<<4) OR (right_moves<<5) OR (right_moves<<6)

We now have the following bitboard (this might look funny because we shift left but the squares to the right gets set, but remember the mapping of the squares to the bits we used and you will see that this is what happens - you could always change your mapping if it makes things easier for you!):

To get rid of the bits that overflowed to the next row, we AND the result with right_board:

right_moves = right_moves AND right_board

Right_moves bitboard now looks like this:

This is all the squares to the right where the rook can't move to. To get the squares where the rook can move to, we exlusive OR the board with right_board:

right_moves = right_moves XOR right_board

This is what right_moves looks like now:

You will notice that this is all the squares to the right of the rook where it can move to. But what if the pawn on F3 was a black pawn? Then we can't capture it, thus we need one last operation:

right_moves = right moves AND enemy_and_empty_squares

For the board in our example nothing would change, but if the piece on F3 was a friendly piece, this last operation would delete it from the right_moves bitboard.

We would do the same thing for moves to the left, up and below the rook. Here is all the formulas for rook moves:

right_moves = right_board[sq] AND occupiedboard
right_moves = (right_moves<<1) OR (right_moves<<2) OR (right_moves<<3) OR (right_moves<<4) OR (right_moves<<5) OR (right_moves<<6)
right_moves = right_moves AND right_board
right_moves = (right_moves XOR right_board) AND enemy_and_empty_squares

up_moves = up_board[sq] AND occupiedboard
up_moves = (up_moves<<8) OR (up_moves<<16) OR (up_moves<<24) OR (up_moves<<32) OR (up_moves<<40) OR (up_moves<<48)
up_moves = up_moves AND up_board
up_moves = (up_moves XOR up_board) AND enemy_and_empty_squares

down_moves = down_board[sq] AND occupiedboard
down_moves = (down_moves>>8) OR (down_moves>>16) OR (down_moves>>24) OR (down_moves>>32) OR (down_moves>>40) OR (down_moves>>48)
down_moves = down_moves AND down_board
down_moves = (down_moves XOR down_board) AND enemy_and_empty_squares

rook_moves = right_moves OR left_moves OR up_moves OR down_moves

For a bishop we use the same process as we used for a rook, here are the formulas:

225deg_moves = 225deg_board[sq] AND occupiedboard
225deg_moves = (225deg_moves>>9) OR (225deg_moves>>18) OR (225deg_moves>>27) OR (225deg_moves>>36) OR (225deg_moves>>45) OR (225deg_moves>>54)
225deg_moves = 225deg_moves AND 225deg_board
225deg_moves = (225deg_moves XOR 225deg_board) AND enemy_and_empty_squares

135deg_moves = 135deg_board[sq] AND occupiedboard
135deg_moves = (135deg_moves<<7) OR (135deg_moves<<14) OR (135deg_moves<<21) OR (135deg_moves<<28) OR (135deg_moves<<35) OR (135deg_moves<<42)
135deg_moves = 135deg_moves AND 135deg_board
135deg_moves = (135deg_moves XOR 135deg_board) AND enemy_and_empty_squares

315deg_moves = 315deg_board[sq] AND occupiedboard
315deg_moves = (315deg_moves>>7) OR (315deg_moves>>14) OR (315deg_moves>>21) OR (315deg_moves>>28) OR (315deg_moves>>35) OR (315deg_moves>>42)
315deg_moves = 315deg_moves AND 315deg_board
315deg_moves = (315deg_moves XOR 315deg_board) AND enemy_and_empty_squares

bishop_moves = 45deg_moves OR 225deg_moves OR 135deg_moves OR 315deg_moves
bishop_captures = bishop_moves AND enemy_board
bishop_non_captures = bishop_moves AND empty_board

Queen Moves

The queen is just a combination of rook and bishop moves, thus:

queen_moves = rook_moves OR bishop_moves

Other moves

Of course there is also moves like castling and en passant. For NagaSkaki these moves are coded with If statements (IF king_hasn't_moved AND not_in_check ...)

If you want to see how all this works in action, you can download this file (please note: this file doesn't generate all possible pawn moves - it's just an example of the basic moves)