Building an Ardiuno Chess Engine using only 2K of RAM

I've always loved writing chess engines. When I need to learn a new programming language or re-familiarize myself with one I always find that writing a chess engine in the language gives me a full deep dive into its capabilities and grammar.

Before this project I had already written chess engines in Java (JavaChess), Modern C++ (CPlusPlusChess), and Javascript (JavaScriptChess).

Last year in the r/Arduino subreddit I help moderate we had a wave of microcontroller based chess projects for a time. All of the projects seemed to be related to the user-interface side of things such as moving the physical pieces on the board, or lighting up a grid of colors representing the current game.

But none of the programs actually implemented the real chess engine itself. And that makes sense since on the basic Uno or Nano you only have a total of 2K of RAM to work with. But I wondered if it could be done and ended up writing a fully working MicroChess chess engine that:

• Runs using less than 2K of memory.
• Can look up to 6 plies ahead.
• Implements the full minimax algorithm including alpha-beta pruning for faster and deeper move searches.
• Supports quiescent searches
• Recursive to a configurable ply depth or by using an optional "stack surfing" technique whereby the recursive look-ahead depth is determined by the current available stack space. 😎
• Fully random seed or replay specific games by seed.
• Full support for move time limits.
• Implemented support to drive an optional 8x8 Color LED board using a WS2812b LED strip.
• Every possible move is generated using only two highly optimized and short functions.
• Implemented using a recursive Visitor pattern where each possible board state is recursively visited by each legal move replacing lower scoring moves as it goes.
• Much much more!

The full source code is available at the project's repository at https://github.com/ripred/MicroChess.

A full series of articles describing the creation of the engine and the theory of operation can be found here:

• So You Want to Build a Chess Engine?
• So, You Want To Build A Chess Engine? Part 2
• MicroChess - Move Evaluation Function
• MicroChess Update: Money for Nothing..
• Writing an Embedded Chess Engine - Part 5
• MicroChess updated for Uno R4 Minima Compatibility