Python Chess: Efficient Move Generation Using Bitwise Operations (Ep.2)

Building My Second Chess Engine Using Python

This article is also available to read on Medium

You can find part 1. here

This is part 2 in a series of articles documenting my process of building a chess engine. I hope to share insights from my previous experience, and explain some of the concepts and techniques I’ll be using. If you haven’t already read part 1, I’d strongly recommend taking a look before reading part 2. You can check it out at the link above.

Time to pick up where we left of…

In the previous article, we built a data structure to represent the chessboard. We used a collection of bitboards (64-bit binary numbers) and 1-hot encoding to represent the different types of pieces and their locations. We then defined a set of tools to allow us to access, modify and display this data structure.

Python

# example usage

B = new_board()

print_board(B)

print_bitboard(B[Brook])

print_bitboard(B[Wpawn])

Python

# whole board            # black rooks            # white pawns

    A B C D E F G H          A B C D E F G H          A B C D E F G H 
  __________________       __________________       __________________ 
8 | r n b q k b n r      8 | 1 · · · · · · 1      8 | · · · · · · · ·
7 | p p p p p p p p      7 | · · · · · · · ·      7 | · · · · · · · ·
6 |                      6 | · · · · · · · ·      6 | · · · · · · · ·
5 |                      5 | · · · · · · · ·      5 | · · · · · · · ·
4 |                      4 | · · · · · · · ·      4 | · · · · · · · ·
3 |                      3 | · · · · · · · ·      3 | · · · · · · · ·
2 | P P P P P P P P      2 | · · · · · · · ·      2 | 1 1 1 1 1 1 1 1
1 | R N B Q K B N R      1 | · · · · · · · ·      1 | · · · · · · · ·

We also have the tools:

Python

# set a bit of a bitboard to a 1
set_bit(bitboard, square) -> bitboard

# set a bit of a bitboard to a 0
remove_bit(bitboard, square) -> bitboard

# get the value of a bit of a bitboard
get_bit_(bitboard, square) -> bool

# count trailing zeros / find least significant bit
ctz(bitboard) -> int

Before we move on, let’s define one more tool that allows us to get the inverse of a bitboard:

Python

# invert, or perform a bitflip on, a bitboard
def invert(b):
    return b ^ (1<<64)-1

Move Generation

Our first task is to calculate what moves can be made in a given position. When we come to writing the search algorithm to identify the best move, we will need to repeatedly generate a list of possible moves, then try each of them, in order to explore different game outcomes. Hence, making the move generation algorithm as efficient as possible is really important.

A simple approach to move generation could look something like this:

For a given piece type, colour and location,
Calculate which squares it could move to
For each of those squares, check if there’s a piece in it: if there’s an allied piece it can’t move to that square, but if there’s an enemy piece, it may be able to take it. (Unless it’s a pawn as they can’t take pieces in the same file).
Depending on the piece type, there may be some special moves that we need to check for such as double pawn moves, en-passant, and castling

After this process has finished, we need to remove any illegal moves. These are moves that would put yourself in check, and moves such as castling out of or through a check.

To make this process as efficient as possible, we’re going to rely on fast lookups instead of calculations to find possible moves.

Knight

The knight is perhaps the simplest piece to calculate moves for as it’s move set is virtually the same regardless of its location on the board. It can move in an ‘L’ shape, that is, 2 squares in one direction, and 1 square to the side.

We can generate a list of movement masks for every square of the board. These identify the squares that the piece can move to. When we need a list of moves, we can just look-up the required mask for the given square. Below are the movement masks for a knight. We’ll see how this can be generated a little later on.

Python

knight_move_masks = [132096, 329728, 659712, 1319424, 2638848, 5277696, 10489856, 4202496, 33816580, 84410376, 168886289, 337772578, 675545156,
1351090312, 2685403152, 1075839008, 8657044482, 21609056261, 43234889994, 86469779988, 172939559976, 345879119952, 687463207072,
275414786112, 2216203387392, 5531918402816, 11068131838464, 22136263676928, 44272527353856, 88545054707712, 175990581010432,
70506185244672, 567348067172352, 1416171111120896, 2833441750646784, 5666883501293568, 11333767002587136, 22667534005174272,
45053588738670592, 18049583422636032, 145241105196122112, 362539804446949376, 725361088165576704, 1450722176331153408,
2901444352662306816, 5802888705324613632, 11533718717099671552, 4620693356194824192, 288234782788157440, 576469569871282176,
1224997833292120064, 2449995666584240128, 4899991333168480256, 9799982666336960512, 1152939783987658752, 2305878468463689728,
1128098930098176, 2257297371824128, 4796069720358912, 9592139440717824, 19184278881435648, 38368557762871296, 9077567998918656]


### TESTING

B = new_board()

# move: Nc6
B[Bknight] = remove_bit(B[Bknight], b8)
B[Bknight] = set_bit(B[Bknight], c6)
update_bitboards(B)


print_board(B)

# all possible knight moves for this square
print_bitboard(knight_move_masks[c6])

# knight moves restricted by nearby pieces
print_bitboard(  knight_move_masks[c6] & invert(B[black])  )

Python

# board                 # all possible moves     # moves restricted by pieces

     A B C D E F G H          A B C D E F G H          A B C D E F G H 
   __________________       __________________       __________________ 
 8 | r   b q k b n r      8 | · 1 · 1 · · · ·      8 | · 1 · · · · · ·
 7 | p p p p p p p p      7 | 1 · · · 1 · · ·      7 | · · · · · · · ·
 6 |     n                6 | · · · · · · · ·      6 | · · · · · · · ·
 5 |                      5 | 1 · · · 1 · · ·      5 | 1 · · · 1 · · ·
 4 |                      4 | · 1 · 1 · · · ·      4 | · 1 · 1 · · · ·
 3 |                      3 | · · · · · · · ·      3 | · · · · · · · ·
 2 | P P P P P P P P      2 | · · · · · · · ·      2 | · · · · · · · ·
 1 | R N B Q K B N R      1 | · · · · · · · ·      1 | · · · · · · · ·

This is the same principle we are going to use for the other pieces too: calculate a movement mask (bitboard), find the locations of allied pieces (also a bitboard), then use a bitwise AND to remove the occupied squares.

Sliding Vs Non-Sliding Pieces

A knight is the simplest example because it has no ‘special moves’ and it is a non-sliding piece. Unlike a bishop, rook or queen (sliding pieces), a knight’s movement range is fixed; it can move to only a set number of squares around it.

A sliding piece can move any number of squares in a given direction. Its movement path is cut short by the presence of enemy and allied pieces. It can move up to and including the square an enemy piece is on, but it can only move up to (not including) an allied piece. To simplify this problem, we’ll assume all pieces on the board are enemy pieces. Then our sliding piece is able to capture all of them. After producing our movement mask, we can then remove from it the squares occupied by allied pieces.

Python

# Consider a rook on square a1. Let the rest of the board be empty except
# two pieces located on a7 and e1. (shown in left bitboard)

# if those two pieces are enemy pieces, the rook can move up to and including
# those squares. (shown in middle bitboard)

# if those two pieces are enemy pieces, the rook can only move up to those 
# squares (shown in right bitboard)

     A B C D E F G H          A B C D E F G H          A B C D E F G H 
   __________________       __________________       __________________ 
 8 | · · · · · · · ·      8 | · · · · · · · ·      8 | · · · · · · · ·
 7 | 1 · · · · · · ·      7 | 1 · · · · · · ·      7 | · · · · · · · ·
 6 | · · · · · · · ·      6 | 1 · · · · · · ·      6 | 1 · · · · · · ·
 5 | · · · · · · · ·      5 | 1 · · · · · · ··     5 | 1 · · · · · · ·
 4 | · · · · · · · ·      4 | 1 · · · · · · ·      4 | 1 · · · · · · ·
 3 | · · · · · · · ·      3 | 1 · · · · · · ·      3 | 1 · · · · · · ·
 2 | · · · · · · · ·      2 | 1 · · · · · · ·      2 | 1 · · · · · · ·
 1 | 1 · · · 1 · · ·      1 | · 1 1 1 1 · · ·      1 | · 1 1 1 · · · ·

# Hence, the set of moves determined by the presence of allied pieces is a
# subset of the moves determined by enemy pieces.

# Therefore, we assume all pieces are enemy pieces, then remove from that
# movement mask, the squares occupied by allied pieces.

# moves = moves & invert( B[allied_pieces] )

Generating Sliding Piece Movement Masks

Consider a rook on a1. It can access squares a2through a8and b1through h1(14 squares). However, this will be affected by the presence of other pieces on those squares. As discussed above, we assume all pieces on the board are enemy pieces.

Given this simplification, we only need to consider the squares a2to a7and b1to g1, as these are the only squares that affect the movement of the rook on a1. (If there is an enemy piece on a8, we will be able to move there only if we can move to a7(so a8does not determine movement options. If there is an allied piece on a8, this square will be removed when we subtract squares containing allied pieces afterwards).

Hence there are 12 squares (known as occupancy bits) that affect the movement of a rook on a1, and there are 14 possible squares that the rook can move to. These numbers will differ depending on which square the rook is on.

Consider only a2-a7. The number of squares the rook can move in this direction is determined by the position of the first bit in this sequence. A bit on a2means the rook can only move 1 square. A bit on a7means the rook can move 6 squares. No bits at all means the rook can move 7 squares. The same is true for b1-g1. Therefore there are 7 * 7 = 49 combinations of possible movement masks.

These two bitboards:

Python

# Bitboards showing the location of enemy pieces on the board
# The rook is on a1

     A B C D E F G H         A B C D E F G H 
   __________________     __________________
 8 | 1 · · · · · · ·     8 | · · · · · · · · 
 7 | · · · · · · · ·     7 | 1 · · · · · · · 
 6 | · · · · · · · ·     6 | · · · · · · · · 
 5 | · · · · · · · ·     5 | · · · · · · · · 
 4 | 1 · · · · · · ·     4 | · · · · · · · · 
 3 | 1 · · · · · · ·     3 | 1 · · · · · · · 
 2 | · · · · · · · ·     2 | · · · · · · · · 
 1 | · · · · · 1 · ·     1 | · · · · · 1 1 ·

Will result in the same possible moves, since the rook can move up to a4and up to f1in both cases. Even though there’s only 49 outcomes, there are 2¹² = 4096 combinations of occupancy bits that map to them.

Procedure:

We start by working out which bits are the occupancy bits for each square. These bits are stored in a mask. This mask can be applied to another bitboard to retrieve the state of those bits on that particular board.
Next we will compute all possible combinations of occupancy bits (for every square).
Finally, for each combination of bits, we calculate the possible moves that it corresponds to. We can store this information in a dictionary for fast lookup.

Implementation

Let’s start by building a set of masks to identify the occupancy bits for each square.

Python

# count up to and inlcuding:
    # count up to next multiple of 8 -2
    # count down to next multiple of 8 + 1
    # count multiples of 8 down until <=15
    # count multiples of 8 up until >= 48

rook_occupancy_masks = []

for square in range(64):
    bitboard = 0

    # count right until you reach file 7
    temp = square
    while temp%8 < 6: 
        temp += 1
        bitboard = set_bit(bitboard, temp)

    # count left until you reach file 2
    temp = square
    while temp%8 > 1:
        temp -= 1
        bitboard = set_bit(bitboard, temp)

    # count up until you reach rank 2
    temp = square
    while temp > 15:
        temp -=8
        bitboard = set_bit(bitboard, temp)

    # count down until you reach rank 7
    temp = square
    while temp < 48:
        temp +=8
        bitboard = set_bit(bitboard, temp)

    rook_occupancy_masks.append(bitboard)

Python

print_bitboard(rook_occupancy_masks[f6])

# rook occupancy mask for a rook on f6 - these are the bits we need to check
# in order to identify where the rook can move

      A B C D E F G H 
    __________________ 
  8 | · · · · · · · ·
  7 | · · · · · 1 · ·
  6 | · 1 1 1 1 · 1 ·
  5 | · · · · · 1 · ·
  4 | · · · · · 1 · ·
  3 | · · · · · 1 · ·
  2 | · · · · · 1 · ·
  1 | · · · · · · · ·

With our masks identified, we can now calculate every possible combination of bits in the shape of each of those masks. If there are n bits in a mask, there will be 2^n combinations of those occupancy bits. These can be represented by the binary values 0, …, (2^n)-1. We take each of those binary values in turn, and insert them into a blank bitboard in the pattern described by the occupancy mask.

Python

# set of combinations of occupancy bits
rook_combinations = [[]]*64

for square in range(64):
    rook_combinations[square] = []
    
    # total number of bits in occupancy mask
    n = int.bit_count(rook_occupancy_masks[square]) 

    for i in range(2**n):
        bit_string = bin(i)[2:].zfill(n)
        
        occupancy_bits = 0
        occupancy_mask = rook_occupancy_masks[square]

        # scan bit_string
        for j in bit_string:
            
            # find and remove least significant bit from occupancy mask
            sq = ctz(occupancy_mask)
            occupancy_mask = remove_bit(occupancy_mask, sq)

            # copy bit string into occupancy mask locations
            if j == "1":
                occupancy_bits = set_bit(occupancy_bits, sq)

        rook_combinations[square].append(occupancy_bits)

Python

print_bitboard( rook_combinations[d3][583] )

# Left: rook occupancy mask for d3
# Right: one combination of those occupancy bits (there are 1024 
# combinations total for this square)

     A B C D E F G H         A B C D E F G H 
   __________________     __________________
 8 | · · · · · · · ·     8 | · · · · · · · · 
 7 | · · · 1 · · · ·     7 | · · · 1 · · · · 
 6 | · · · 1 · · · ·     6 | · · · · · · · · 
 5 | · · · 1 · · · ·     5 | · · · · · · · · 
 4 | · · · 1 · · · ·     4 | · · · 1 · · · · 
 3 | · 1 1 · 1 1 1 ·     3 | · · · · · 1 1 · 
 2 | · · · 1 · · · ·     2 | · · · 1 · · · · 
 1 | · · · · · · · ·     1 | · · · · · · · ·

Now we have every combination of occupancy bits worked out for every square on the board, we just need to identify a mapping from occupancy bits to movement masks. We create a series of hash tables (python dictionaries are implemented using a hash table) to store this. This code will look similar to before when we calculated the occupancy masks.

Python

rook_move_masks = [{}]*64

for square in range(64):
    rook_moves[square] = {}
    
    combinations = rook_combinations[square]
    for i in combinations:
        moves = 0
        
        # scan right
        temp = square
        while temp%8 < 7: 
            temp += 1
            moves = set_bit(moves, temp)
            if get_bit(i, temp) == 1:
                break
    
        # scan left
        temp = square
        while temp%8 > 0:
            temp -= 1
            moves = set_bit(moves, temp)
            if get_bit(i, temp) == 1:
                break
    
        # scan up
        temp = square
        while temp > 7:
            temp -=8
            moves = set_bit(moves, temp)
            if get_bit(i, temp) == 1:
                break
    
        # scan down
        temp = square
        while temp < 56:
            temp +=8
            moves = set_bit(moves, temp)
            if get_bit(i, temp) == 1:
                break

        # add to dictionary
        rook_move_masks[square][i] = moves

Now we can bring everything together.

Python

# TESTING

# bitboard representing locations of all pieces
# (again, we assume all pieces are enemy pieces)
b1 = 0
b1 = set_bit(b1, a7)
b1 = set_bit(b1, e1)
b1 = set_bit(b1, g1)
b1 = set_bit(b1, h4)
b1 = set_bit(b1, d6)

# bitboard representing locations of allied pieces (same colour as rook)
b2 = 0
b2 = set_bit(b2, e1)

print_bitboard(b1)
print_bitboard(b2)

# rook on a1
square = a1

# work out which squares in the occupancy mask have pieces on them
occupancy_bits = rook_occupancy_masks[square] & b1
print_bitboard(occupancy_bits)

# lookup the movement masks for the given square and occupancy bits
moves = rook_move_masks[square][occupancy_bits]
print_bitboard(moves)

# identify moves when we include the positions of allied pieces
moves = moves & invert(b2)
print_bitboard(moves)

Python

# masks for a rook on a1 (for a given random board setup shown at top) 

 # all pieces           # allied pieces 
  
    A B C D E F G H          A B C D E F G H
    __________________     __________________
  8 | · · · · · · · ·    8 | · · · · · · · ·
  7 | 1 · · · · · · ·    7 | · · · · · · · ·
  6 | · · · 1 · · · ·    6 | · · · · · · · ·
  5 | · · · · · · · ·    5 | · · · · · · · ·
  4 | · · · · · · · 1    4 | · · · · · · · ·
  3 | · · · · · · · ·    3 | · · · · · · · ·
  2 | · · · · · · · ·    2 | · · · · · · · ·
  1 | · · · · 1 · 1 ·    1 | · · · · 1 · · ·


  # occupancy bits       # movement mask        # movement mask (allied 
  # from board                                  # pieces removed)

      A B C D E F G H        A B C D E F G H        A B C D E F G H
    __________________    __________________    __________________
  8 | · · · · · · · ·    8 | · · · · · · · ·    8 | · · · · · · · ·
  7 | 1 · · · · · · ·    7 | 1 · · · · · · ·    7 | 1 · · · · · · ·
  6 | · · · · · · · ·    6 | 1 · · · · · · ·    6 | 1 · · · · · · ·
  5 | · · · · · · · ·    5 | 1 · · · · · · ·    5 | 1 · · · · · · ·
  4 | · · · · · · · ·    4 | 1 · · · · · · ·    4 | 1 · · · · · · ·
  3 | · · · · · · · ·    3 | 1 · · · · · · ·    3 | 1 · · · · · · ·
  2 | · · · · · · · ·    2 | 1 · · · · · · ·    2 | 1 · · · · · · ·
  1 | · · · · 1 · 1 ·    1 | · 1 1 1 1 · · ·    1 | · 1 1 1 · · · ·

Moves For Other Pieces

Now that we’ve completed the code for rook move generation, it’s fairly straightforward to adapt this to work with bishops. The movement mask for a queen is calculated by first looking up the movement as it were a rook, doing the same as if it were a bishop, then performing a bitwise OR on these two movement masks to take their union.

As we saw earlier, with the knights, the movement masks for non-sliding pieces is simpler to compute and is only determined by the square that the piece is on. A similar piece of code to that of the rook (as shown above) can be used to generate movement masks for the knight, king and pawn.

The only complication with the pawns, is that we need different movement masks depending on the colour, and we need to create a mask to identify on which squares the pawn can capture another piece. The movement masks also need to include double moves if the pawn is on the 2nd or 7th rank (if they haven’t moved yet). But these masks can still be generated in a similar way to before.

Special Moves

The last step is to allow for special moves. These are en-passant, castling, and pawn capture. Pawn promotion will be handled later on when we come to applying a chess move to a given board.

En-passant is where a pawn captures another pawn that moved two spaces, but as if it had only moved one space. The square that a pawn skips when it performs a double move will be stored in a bitboard called enpassant.

We now modify our original board data structure to include some extra information about the state of the board. We use an array to store a series of bitboards (integers) as well as integers to store the additional data. This array is indexed via the following constants.

Python

# enumerate array indices for easier board access
# this also gives us constants for white and black that can be used elsewhere
Wpawn, Bpawn, Wrook, Brook, Wknight, Bknight, Wbishop, Bbishop, Wqueen, Bqueen, Wking, Bking, white, black, all,\
enpassant, WLcastle, WScastle, BLcastle, BScastle, nextToMove = range(21)

def new_board():
    
    # initial starting position
    B = [ 71776119061217280, 65280,    # pawns (white, black)
       9295429630892703744, 129,       # rooks
       4755801206503243776, 66,        # knights
       2594073385365405696, 36,        # bishops
       576460752303423488, 8,          # queens
       1152921504606846976, 16,        # kings
       18446462598732840960, 65535,    # colour
       18446462598732840960 | 65535,   # all board pieces
       0,                              # en-passant squares
       1, 1, 1, 1,                     # castling rights (wlong, wshort, blong, bshort)
       0                               # player to move (0=w, 1=b)          
       ]

    return B

To handle en-passant, we set the enpassant bitboard to contain the square that was skipped by the double pawn move. This is the square that the capturing pawn would move to. We treat this square as an extension of the enemy pieces. Hence, for pawn move generation, we have the following function.

Python

def pawn_move(B, square, pieceColour):

    if pieceColour == white:

        # standard moves (including double moves)
        # remove all squares occupied by another piece - pawns cannot
        # capture enemy pieces moving along the same file so all pieces are blockers
        moves = wpawn_move_masks[square] & invert(B[all])

        # capture moves (take diagonally)
        # add capture moves if there is an enemy piece (or the enpassant
        # square) in the capture mask
        moves |= ( wpawn_capture_masks[square] & (B[black] | B[enpassant] ) )
    
    
    else: # black pieces
        moves = bpawn_move_masks[square] & invert(B[all])
        moves |= ( bpawn_capture_masks[square] & (B[white] | B[enpeassant] ) )
    
    return moves

Python

### TESTING

B = new_board()
B[Bpawn] = set_bit(B[Bpawn], d3)
B[Bpawn] = remove_bit(B[Bpawn], d7)
update_bitboards(B)
print_board(B)
print_bitboard(pawn_move(B, c2, white))

-------------------------------------------------------------------

# board setup            # possible pawn moves for pawn on c2
     A B C D E F G H         A B C D E F G H 
   __________________     __________________
 8 | r n b q k b n r     8 | · · · · · · · · 
 7 | p p p   p p p p     7 | · · · · · · · · 
 6 | · · · · · · · ·     6 | · · · · · · · · 
 5 | · · · · · · · ·     5 | · · · · · · · · 
 4 | · · · · · · · ·     4 | · · 1 · · · · · 
 3 | · · · p · · · ·     3 | · · 1 1 · · · · 
 2 | P P P P P P P P     2 | · · · · · · · · 
 1 | R N B Q K B N R     1 | · · · · · · · ·

Similarly, for a king, we have the special move of castling. In order for this to be allowed, the king and the corresponding rook cannot have moved so far in the game. This is known as a right to castle, and will be represented by a Boolean value in our board data structure (see above). There must also be empty squares between the king and the rook. We will not enforce that a player cannot castle through, into or out of a check yet; we will consider that later when we come to applying a chess move to a board. For king move generation, we have the following function.

Python

def king_move(B, square, pieceColour):   
    alliedPieces = B[white] if pieceColour == white else B[black]
    
    moves = king_move_masks[square] & -(alliedPieces+1)

    # check for possible castling moves
    # check right to castle conditions, and for empty squares  
    Long, Short = (WLcastle, WScastle) if pieceColour == white else (BLcastle, BScastle)
  
    if ( Long and not get_bit(B[all], square-1 ) and not get_bit( B[all], square-2 ) and not get_bit( B[all], square-3 ) ):
        moves |= 1<<square-2 # add a additional move

    if ( Short and (not get_bit( B[all], square+1) ) and (not get_bit( B[all], square+2 ) ) ):
        moves |= 1<<square+2 # add a additional move

    return  moves

Python

### TESTING

B = new_board()
B[Wbishop] = remove_bit(B[Wbishop], f1)
B[Wknight] = remove_bit(B[Wknight], g1)
B[Wpawn] = remove_bit(B[Wpawn], e2)
B[Wpawn] = remove_bit(B[Wpawn], f2)
update_bitboards(B)
print_board(B)
print_bitboard(king_move(B, e1, white))

-------------------------------------------------------------------

# board setup            # possible king moves (king on e1),
                         # allowed to castle short
     A B C D E F G H         A B C D E F G H 
   __________________     __________________
 8 | r n b q k b n r     8 | · · · · · · · · 
 7 | p p p p p p p p     7 | · · · · · · · · 
 6 | · · · · · · · ·     6 | · · · · · · · · 
 5 | · · · · · · · ·     5 | · · · · · · · · 
 4 | · · · · · · · ·     4 | · · · · · · · · 
 3 | · · · · · · · ·     3 | · · · · · · · · 
 2 | P P P P · · P P     2 | · · · · 1 1 · · 
 1 | R N B Q K · · R     1 | · · · · · 1 1 ·

We now have move generation working for every type of piece. It’s difficult to effectively check the move generation code since there are so many scenarios to consider, but it’s worth checking a few different scenarios with different combinations of pieces to make sure everything’s working correctly.

We’ve also managed to implement this code with very few computations, instead relying mainly on lookups of pre-computed masks to identify where a piece can move.

In the next article in this series, we will tackle applying a move to a board, allowing us to start simulating a game of chess.

This is part 2 in a series of walkthroughs documenting my journey in developing a chess engine. If you’ve found this useful, insightful, or even vaguely interesting, please consider following to be notified of future updates. Thanks for reading 🙂