Avalanche

Avalanche is the first chess engine (computer chess player and analyzer) written in the Zig programming language, proving Zig’s ability to succeed in real-world, competitive applications. It is an open-source, standalone, and cross-platform software. As an Universal Chess Interface (UCI) program, Avalanche interacts with the user with text, but it is compatible with most popular chess software. Version 3.0.0 holds an official CCRL rating of 3350, far beyond the strongest human grandmasters, and Avalanche was among the top 32 chess engines to qualify for TCEC Swiss 6 and competed for the title of world champion in the most prestigious computer chess competition in the world.

The newly released version 4.0.0 brings a major breakthrough in neural network training and optimization, measuring roughly 200 elo stronger in testing — including an 88 elo win over Stockfish 11 — and performing on par with engines around 3600 on the CCRL Blitz list. It is currently being rated by CCRL, so version 3.0.0 remains the recommended download for now.

Using UCI, the user or GUI can inform Avalanche the current board and clock situation, and it will search for the best move and decide when to stop thinking on its own.

Features

• Avalanche uses the NNUE (Efficiently Updatable Neural Network) technology for its evaluation, with a redesigned network architecture in 4.0.0 and the Jihan (极寒) network family introduced in 3.0.0.
• The training data is purely generated from self-play games, accumulated over hundreds of millions of self-play positions.
• Syzygy endgame tablebase support for perfect play in late endgames.

Technical Details

I represent the chess board using a unique Bitboard-Mailbox hybrid data structure. There are 8x8=64 squares on a chess board, which happens to be the same as the number of bits in a 64-bit integer. By representing each piece+color with a single integer, where a bit is 1 if the piece exists on that square, my data structure allows efficient move generations thousands of times faster than naive algorithms.

Two modules influence Avalanche’s thinking: Search and Evaluation.

I use an extremely optimized version of Minimax. While on average 30 legal moves exist per position, Avalanche only has a branching factor of about 4, discarding most options quickly using many smart algorithms like Futility Pruning and Static Exchange Evaluation. This is because in chess, many moves are obviously worse than others, even considering tactical possibilities.

I evaluate leaf nodes with an Efficiently Updatable Neural Network (NNUE), and I am one of the pioneers of applying it to chess. Because each chess move changes the position by at most four squares, Avalanche only needs to recalculate its evaluation for four input neurons instead of the whole board. With Reinforcement Learning, it predicts the future much more accurately than traditional hand-crafted methods with human knowledge.

For testing, I let the new version play games against the old version from random openings until the Sequential Probability Ratio Test (SPRT) tells me there is a 95% probability the new version is stronger.

Results

I have released 18 versions of Avalanche, each time making many improvements. Although most of the improvements consist of modified algorithms, some unfortunately introduced new bugs. For example, in version 1.3.0, I introduced a new feature called “Countermove Heuristics,” which I concluded to be 66 elo stronger than the previous version after 28 blitz games. However, when testers at CCRL tested it, they saw a decrease in strength. After consulting a statistician, I learned that 28 was way too small of a sample size for a meaningful conclusion. Furthermore, I found a critical bug in my implementation of Countermove Heuristics, where I forgot to reset a section of the memory to zero, causing Countermove Heuristics to essentially add random noises. The chess engine community taught me how to perform the Sequential Probability Ratio Test, which requires thousands of games but gives a statistically significant result. Since then, I have been using this rigorous means of regression testing and carefully zeroing important arrays at the start of the program, never making this mistake again. Through this project, I learned the importance of collaboration and humbly consulting experts in specific areas for advice on things I am weak in. Next time, I would design and build a rigorous development and testing workflow before starting to code to minimize the chance of committing code that contains mistakes.