How NagaSkaki plays chess

Chess / By

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.

Board Representation

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 B2 ….. 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:

5657585960616263
4849505152535455
4041424344454647
3233343536373839
2425262728293031
1617181920212223
89101112131415
01234567

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:

  • fullboard
    a bitboard with all bits set (0xffffffffffffffff)
  • occupied_squares
    a bitboard with bits set if any piece occupies a square
    (= white_pawns OR black_pawns OR white_knights …… OR black_king)
  • empty_squares
    a bitboard with bits set if no piece occupies a square
    (= occupied_squares XOR fullboard)
  • enemy_squares
    a bitboard with only the bits set if an enemy piece occupies a square
    (for white = black_pawns OR black_knights …… OR black_king)
  • enemy_and_empty_squares
    a bitboard with the empty bits and the squares with an opponent piece on it set.
    ( = enemy_squares OR empty_squares)

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:

  1. Precalculate a bitboard for all squares with the square in front of the pawn set (move one forward) AND this board with the empty_squares bitboard to generate a one move forward bitboard.
  2. Precalculate a bitboard for all squares with the square two squares in front of the pawn set (if the pawn is on the second row.) AND this board with the empty_squares bitboard ONLY if step 1 above generated a valid move.
  3. Precalculate a bitboard with the squares above left and above right of the pawn set (captures.) AND this bitboard with the enemy_squares bitboard to create a captures bitboard for the pawn


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:

  • right_board[64] – a bitboard for every square with all squares to the right of the square set
  • left_board[64] – a bitboard for every square with all squares to the left of the square set
  • up_board[64] – a bitboard for every square with all squares above the square set
  • down_board[64] – a bitboard for every square with all squares below the square set

To illustrate the move generation process, we’ll use the following position to generate the moves for the rook on C3

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:

00000000
00000000
00000000
00000000
00000000
00000100
00000000
00000000

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!):

00000000
00000000
00000000
00000000
00000000
00000011
11110000
00000000

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:

00000000
00000000
00000000
00000000
00000000
00000011
00000000
00000000

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:

00000000
00000000
00000000
00000000
00000000
00011100
00000000
00000000

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) XOR enemy_and_empty_squaresleft_moves = left_board[sq] AND occupiedboard
left_moves = (left_moves>>1) OR (left_moves>>2) OR (left_moves>>3) OR (left_moves>>4) OR (left_moves>>5) OR (left_moves>>6)
left_moves = left_moves AND left_board

left_moves = (left_moves XOR left_board) XOR 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) XOR enemy_and_empty_squares

down_moves = down_board[sq] AND occupiedboard
down_moves = (down_moves>>1) OR (down_moves>>2) OR (down_moves>>3) OR (down_moves>>4) OR (down_moves>>5) OR (down_moves>>6)
down_moves = down_moves AND down_board
down_moves = (down_moves XOR down_board) XOR enemy_and_empty_squares

rook_moves = right_moves OR left_moves OR up_moves OR down_moves
rook_captures = rook_moves AND enemy_board
rook_non_captures = rook_moves AND empty_board


Bishop moves

For a bishop we use the same process as we used for a rook, here are the formulas:45deg_moves = 45deg_board[sq] AND occupiedboard
45deg_moves = (45deg_moves<<9) OR (45deg_moves<<18) OR (45deg_moves<<27) OR (45deg_moves<<36) OR (45deg_moves<<45) OR (45deg_moves<<54)
45deg_moves = 45deg_moves AND 45deg_board
45deg_moves = (45deg_moves XOR 45deg_board) XOR enemy_and_empty_squares

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) XOR 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) XOR 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) XOR 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 …)