Avalanche Chess Engine... Part 1

Introduction

After successfully building a 5x5 shogi engine in C#, I thought I would make my own chess engine, totally from scratch. This would enhance my skills with low-level instructions, and give me something to constantly improve and challenge myself.

In this series of posts, I will talk about steps to create a chess engine as well as my progress in making one.

The source code of Avalanche Chess Engine will be here: github.com/SnowballSH/Avalanche. Feel free to follow along!

Choice of Programming Language

I was originally going to use Rust. However, when making a chess-playing program, you don't need safety -- or rather you don't want safety -- you only care about speed and all the safety checks should be done at debug time. Sure, you can disable checks in Rust, but the code would be bloated by unsafe keywords.

I choose Zig because it's an interesting C alternative. GCC works badly on my machine, so C wouldn't work. Zig uses LLVM to compile code that optimizes for different machines and is able to cross-compile to different platforms. So, here is my first Zig project.

Phases of developing a chess (or any other board game) engine

Board representation

For any game, you will need a state to represent the current position of the game. This is usually a struct containing board(s), turn, move count, and other information.

A chessboard has 8x8 = 64 squares, which is exactly the number of bits in a 64-bit unsigned integer! We can use the bitboard board representation for chess. There's 12 kinds of pieces in chess (6 for each color), so we only need 12 u64 to represent the entire board. each set bit (1) at index k of board p means there is p at the kth square on the board. We can also store the combination of pieces of each color to 2 separate u64s -- so we don't need to OR 6 numbers everytime we need the full occupancy.

Example of bitboard:

This will be position.bitboards.white_pawns after the move 1. e4. This bitboard can be represented as 0x1000ef00 as a single number -- or 0b10000000000001110111100000000. Credits to Tearth's great bitboard debugger.

This is the layout of squares in my engine (and most engines). This is convenient, because >> 1 moves right, << 1 moves left, >> 8 moves down, << 8 moves up, very intuitive.

Btw, Bit twiddling

To check if a square is set, we can do @truncate(u1, bb >> sq) in Zig.

To toggle a square, we can do bb ^= 1 << sq.

To set a square, we can do bb |= 1 << sq.

To clear a square, we can do bb &= ~(1 << sq), which means parts of bb that does not intersect with 1 << sq.

We also need a turn (0 for white and 1 for black), En Passant square (null or 0-63), Castling rights (4-bit bitflag, WhiteKing = 1, WhiteQueen = 2, BlackKing = 4, BlackQueen = 8, we can AND and OR them to get different combinations).

Move generation & attacks

You don't just play with a board. The program needs knowledge about which moves are legal.

With bitboards, it is easy to pre-compute attack tables for leapers (Pawn, King, Knight). With Zig, it is even easier to generate code at compile-time:

pub const KingDelta: [8][2]i8 = .{
    .{ -1, -1 },
    .{ -1, 0 },
    .{ -1, 1 },
    .{ 0, -1 },
    .{ 0, 1 },
    .{ 1, -1 },
    .{ 1, 0 },
    .{ 1, 1 },
};

pub const KingPatterns: [64]u64 align(64) = init: {
    @setEvalBranchQuota(64 * 8 * 3); // force compiler to compute this
    var patterns: [64]u64 align(64) = undefined;
    for (patterns) |*pt, idx| {
        const r: i8 = BB.rank_of(idx);
        const f: i8 = BB.file_of(idx);
        var bb: u64 = 0;
        for (KingDelta) |delta| {
            bb |= rank_file_to_bb(r + delta[0], f + delta[1]);
        }
        pt.* = bb;
    }
    break :init patterns;
};

And... Done! We just finished the move generator for Kings.
KingPatterns[sq] will be a bitboard containing all legal moves of the king.

Let's say sq is 20. (Refer to the image above for location)

This is KingPatterns[20], in which we can use bitscan to find the first square that is set and send it to the search function. bitscan can also be replaced with a single CPU instruction on most modern machines - ctz, or least-significant bit, or "count trailing zeroes". This makes sure bitboard is faster than representing the board with 2-dimensional arrays.

Ending

I will talk about some different techniques to generate slider (bishop, rook, queen) moves in the next post, since I barely figured out how to use Magic Bitboards myself. Normal algorithms would definitely work (which is what Avalanche has now) -- but Magic Bitboard signifies the true magic of bitboards -- computing all attacks with a single multiplication!

Avalanche can now complete basic perft positions (perft stands for Performance Test, testing the speed and accuracy of move generation) and is correct 99.9% of the time. There's some small bugs I'll fix while it is playing games and some performance issues (currently 2x slower than a C# Magic-bitboard generator).

Thank you for reading, and I'll see you in the next post.
github.com/SnowballSH/Avalanche