**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:

56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 |

48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 |

40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |

32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |

24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |

16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |

8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

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:

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

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 | 0 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

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

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 |

1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

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:

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 | 0 | 0 | 0 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

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:

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 | 1 | 0 | 0 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

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 occupiedboardright_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_boardright_moves = (right_moves XOR right_board) XOR enemy_and_empty_squares*

*left_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 occupiedboardup_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_boardup_moves = (up_moves XOR up_board) XOR enemy_and_empty_squares*

*down_moves = down_board[sq] AND occupiedboarddown_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_boarddown_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 occupiedboard225deg_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_board225deg_moves = (225deg_moves XOR 225deg_board) XOR enemy_and_empty_squares*

*135deg_moves = 135deg_board[sq] AND occupiedboard135deg_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_board135deg_moves = (135deg_moves XOR 135deg_board) XOR enemy_and_empty_squares*

*315deg_moves = 315deg_board[sq] AND occupiedboard315deg_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_board315deg_moves = (315deg_moves XOR 315deg_board) XOR enemy_and_empty_squares*

*bishop_moves = 45deg_moves OR 225deg_moves OR 135deg_moves OR 315deg_movesbishop_captures = bishop_moves AND enemy_boardbishop_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 …)