magnuskahr

writing code

Bitboards in Swift

This post will demonstrate the use of bitboards in Swift using chess as an example, so I warn of chess terminology.

What is so special about the hexadecimal number 0xffffffffffffffff? Well in binary, it represents 64 bits of one's, and 64 is the total number of squares on a chessboard. If we agree that a square can either be filled or not, making it a boolean (or a bit) value, we can represent a whole chessboard with a number, why the number before represents a filled board.

Representing a game board with a binary number is called bitboard, where each bit represents the state of one square. For this article, we will let binary numbers be Big Endian and then let the least significant bit (LSB) represent A1 on the chessboard, followed by B1, C1, D1, E1, F1, G1, H1, A2, B2 ... and all the way up to the most significant bit (MSB) representing the H8.

Why use bitboards?

Bitboards are more complicated since we represent the board as raw data and not in some object-oriented way, but it has some major benefits.

Low Memory Usage

Having only to store a number to represent the state of a board, means that it has a crazy small memory footprint, in fact as mentioned only 64 bits. Well, that is for each bitboard.

In chess we will need a bitboard to represent each color of each type of piece, that means we will need 12 bitboards: one for all white pawns, one for all black pawns, one for all white bishops, and so on... even though we need 12 bitboards, it is still a very small footprint of 12 * 64 bit = 768 bits.

Fast bitwise operations

When we need to generate a new state of a bitboard like if white moved a pawn in chess, we need to manipulate its raw data. Being that it is binary numbers we will manipulate, we can simply shift the value or use any other bitwise operation like AND, XOR, NOT etc. all of which are operations provided directly by the CPU, why it is really fast, compared to manipulating a bunch of objects.

Swift implementation

One could just go ahead and use a raw UInt64 as a bitboard, but by wrapping it we can provide some great functionality.

struct Bitboard: Equatable {
    private(set) var rawValue: UInt64 = 0
    init(rawValue: UInt64) {
        self.rawValue = rawValue
    }
    init() { }
}

With this basic struct, we can create empty boards, specific boards from a number, and compare boards, but this is just the beginning.

Advanced boards

What if we wanna create boards in a more advanced way, like in a way that is more focused on the data instead of the type? Later we wanna do this with masks and see how they can be used for different operations and having them in an easily manageable way.

Initialization with Literals

Using Swift we can create instances of our types simply stating our values, which we will utilize with the ExpressibleByIntegerLiteral-protocol by implementing the following initializer:

extension Bitboard: ExpressibleByIntegerLiteral {
    public init(integerLiteral value: UInt64) {
        self.init(rawValue: value)
    }
}

What this enables is pure sugar, but very good sugar, because it now enables us to create boards easily, like with the following masks:

extension Bitboard {
    struct Masks {
        static let full: Bitboard = 0xffffffffffffffff
        static let fileA: Bitboard = 0x101010101010101
        static let fileB: Bitboard = 0x202020202020202
        static let fileC: Bitboard = 0x404040404040404
        static let fileD: Bitboard = 0x808080808080808
        static let fileE: Bitboard = 0x1010101010101010
        static let fileF: Bitboard = 0x2020202020202020
        static let fileG: Bitboard = 0x4040404040404040
        static let fileH: Bitboard = 0x8080808080808080
    }
}

Initialization with a position

It would be suitable to also being able to initialize a bitboard in a more readable way, like having a specific position marked, so let us say we have the following enums: File and Rank, and the struct: Position.

enum File: Int {
    case A, B, C, D, E, F, G, H
}

enum Rank: Int {
    case one, two, three, four, five, six, seven, eight
}

struct Position {
    let file: File
    let rank: Rank
}

Then we can also provide the following initializer:

extension Bitboard {
    init(marked position: Position) {
        let file = position.file.rawValue
        let rank = position.rank.rawValue
        let exponent = rank * 8 + file
        self.rawValue = 1 << exponent
    }
}

The initializer calculates what is called an exponent from a Position. The exponent tells how many times we have to bitwise shift the position A1 to the given position, ending up with a bitboard that has been marked only at that square:

let position = Position(file: .B, rank: .two)
let bitboard = Bitboard(marked: position)

Challenge: Can you create an initializer which takes several positions and marks them all on a single bitboard? Well probably come back to this later, you will need the OR operation.

Manipulating bitboards

Creating the bitboards is one thing, but how about when we wanna manipulate them? To do that, we will have to implement some bitwise operations to the bitboards, enabling us to XOR, AND, OR, shift, and comparing.

Challenge: Can you create them? Or else they will be listed next:

extension Bitboard {
    static func << (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
        let shifted = lhs.rawValue << rhs.rawValue
        return Bitboard(rawValue: shifted)
    }
    
    static func >> (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
        let shifted = lhs.rawValue >> rhs.rawValue
        return Bitboard(rawValue: shifted)
    }
    
    static func & (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
        let ANDed = lhs.rawValue & rhs.rawValue
        return Bitboard(rawValue: ANDed)
    }
    
    static func | (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
        let ORed = lhs.rawValue | rhs.rawValue
        return Bitboard(rawValue: ORed)
    }
    
    static func ^ (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
        let XORed = lhs.rawValue ^ rhs.rawValue
        return Bitboard(rawValue: XORed)
    }
    
    static func > (lhs: Bitboard, rhs: Bitboard) -> Bool {
        lhs.rawValue > rhs.rawValue
    }
    
    static func < (lhs: Bitboard, rhs: Bitboard) -> Bool {
        lhs.rawValue < rhs.rawValue
    }
}

As we see, all the work are done with bitwise operations on the rawValue itself, making it super fast to calculate. But these are trivial, and what they enable is the more interesting part.

Marking and clearing positions

With these functions, we have now enabled some powerful ways to manipulate the bitboards, and now we will use them to mark a position on a board:

extension Bitboard {
    @discardableResult
    mutating func mark(_ position: Position) -> Bool {
        let markedPosition = Bitboard(marked: position)
        let newData = self ^ markedPosition
        guard newData > self else {
            return false
        }
        self = newData
        return true
    }
}

We see that the mark(_ position:) -> Bool function uses much of our other code, like the bitwise operations and the initialization of single marked bitboards. The logic behind the method is as following:

  1. Create a single marked bitboard from the given position
  2. XOR the new bitboard with self
  3. If the XOR´ed bitboard has a higher value than self we know that a position was marked since it contains an extra '1', so we set the XOR´ed data as self and return true, else we return false.

It is pretty simple and should make sense. We could just go ahead and save the XOR´ed state, but making the check to return if it was successful allows us to know it in other situations - and by marking the function with @discardableResult, allows to use the return value when we like.

Challenge: Can you create the clear(_ position:) -> Bool function? If not it will be listed next.

extension Bitboard {
    @discardableResult
    mutating func clear(_ position: Position) -> Bool {
        let markedPosition = Bitboard(marked: position)
        let newData = self ^ markedPosition
        guard newData < self else {
            return false
        }
        self = newData
        return true
    }
}

Creating attacks

Lastly, we will have a look at how to use bitboards to generate valid attacks or movements. In chess, there are two types of pieces: sliding pieces and nonsliding pieces. If we look at the Rook, which is a sliding piece, it can move to any square vertically and horizontal from its position; but it can also be blocked, and it can help to mate by x-raying the King and so on: Sliding pieces are very hard to work with, why we will take a look at nonsliding pieces instead. For information on calculating sliding pieces, please see chessprogramming.org.

The pawn is a special piece, it is nonsliding, but its movement and attacking capability are different and it can only be pushed forward relative to the corresponding color.

Let's say we have a white Pawn at B2, it can then attack A3 and C3. If we look at square B2 in our binary representation of our board; the bits of the attacking squares are located 7 and 9 placed further to the left, why we can use our shifting methods created earlier:

func attacksUp(on board: Bitboard) -> Bitboard {
    let rightAttack = board << 9
    let leftAttack = board << 7
    return leftAttack | rightAttack
}

We can see from earlier, that even though the << operator takes two bitboards and we use a bitboard and a number, it utilizes the ExpressibleByIntegerLiteral implemented in the bitboard to autowrap the number as a bitboard. We create both a right attack and a left attack, and we return the combined result where we OR them together. The result is a bitboard containing both attacks for a Pawn, and if there multiple Pawns on the given board, it will calculate the attacks for all of them with these simple and fast lines code.

Using masks to filter

There is one problem left though, and to solve it we will come back the masks mentioned earlier. Because if we use the above method, to calculate the attack for A1, we will see that it will return a bitboard where H1 and B2 are marked, and this is wrong. If we think a bit we can say the following about the white Pawn attack:

  • Attacking left can never attack the H file
  • Attacking right can never attack the A file

So when calculating the left attack, we will filter out any markings on the H file, and for the right attack: the A file. To do this, we have two masks:

static let fileA: Bitboard = 0x101010101010101
static let fileH: Bitboard = 0x8080808080808080

These two hex-numbers each contain a bitboard where the corresponding file is the only thing marked, and if we negate them we will then have two boards marked with the allowed positions of the attacks. We will do this, and AND it with the calculated attacks, to have only valid moves:

func attacksUp(on board: Bitboard) -> Bitboard {
    let rightAttack = board << 9 & ~Bitboard.Masks.fileA
    let leftAttack = board << 7 & ~Bitboard.Masks.fileH
        
    return leftAttack | rightAttack
}

Challenge: Can you create the attacksDown(on board: Bitboard) -> Bitboard function?

Conclusion

We have now seen how we can have a simple value, and use the power of Swift to easily and safely manipulate it, and you should now have a clear understanding of using bitboards. It is a huge topic and has such great potential, and to fully use it, a lot still needs to be implemented. You should though be equipped to generate lots of different move patterns now and manipulate the bitboards for your needs.

There is a lot of great reading on using bitboards and programming chess on the internet, but not much is written in Swift. Whenever I have time, I try to work on my own chess-engine-kit-thing called SkakKit, which I hope will be finished someday (Skak is danish for chess).