Avalanche Chess Engine... Part 1
Tags: chess, zig
Published: 2022-01-27 03:11:22

## Introduction
After successfully building [a 5x5 shogi engine](https://github.com/SnowballSH/GoneuraOu) 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](https://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 `k`th square on the board. We can also store the combination of pieces of each color to 2 separate `u64`s -- so we don't need to `OR` 6 numbers everytime we need the full occupancy.

Example of bitboard:
![Bitboard Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yfzkhfb4mwo45xzibe7o.png)
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](https://tearth.dev/bitboard-viewer/).

![Layout](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5z7dgmkkjnlqft94ms28.png)
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](https://en.wikipedia.org/wiki/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:

```zig
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)
![KingPatterns 20](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sz2br69faua30g43dpqk.png)
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](https://github.com/SnowballSH/Avalanche)