What I've Got So Far
June 26, 2026
Building a chess bot is an interesting endeavor, and having recently learnt Rust, I had the perfect excuse to build one. This started as a private hobby project, but then I decided to build in the open!
So far, I have:
- Implemented the movements for each chess piece.
- Built a bot that looks one step ahead and picks a move based on material advantage and piece activity.
- Created a basic terminal UI to play against the robot.
This video is a demo of a game I played against the robot. Although I didn’t reach checkmate, the bot has no understanding of checks, so i captured its king on the next round.
I’ll be sharing updates I make to the bot and new games to show how it’s improving!
A Recursive Algorithm for Evaluating Moves
June 17, 2026
Arguably the thing that makes computers so good at playing chess is their ability to look many moves into the future and pick the best positions, taking advantage of computational strength to mimic having a plan to reach checkmate; hence, I must implement that into my bot!
This is achieved through a recursive algorithm, which takes in a depth and a current position as input. All proceeding possible positions are generated. For each of those, the next positions are generated recursively for the aforementioned depth. This generates a tree of possible proceeding positions, with the root of each as a possible next move the bot could immediately play, and each node as a possible proceeding position from its parent.
The leaves are evaluated based on a weighted equation. The evaluations are bubbled up the tree until the root. This determines how good the move is. The bot chooses the move with the highest evaluation to play next.
The evaluation of each non-leaf node is negative the maximum of its children’s evaluations. This is because from White’s perspective, the evaluation of a position is as bad as the best-case scenario for Black on his next move.
This algorithm worked! The bot plays smarter now, though very slowly. For depth=2 (which is very low), it takes more than a minute for the bot to play its first move. The next step would be to find a way to make the algorithm faster somehow.
Parallelism
June 29, 2026
Last time, I was able to make the bot go smarter by implementing recursive search through possible future positions, but the algorithm was too slow even at depth=2. So right after, I started working on making the bot faster!
I landed on pararellism as a solution. I was going through the Tokio docs in preparation to download it when I met a line that said something like “If your application is CPU bound, consider using Rayon.”
And I was thankful for having started reading about CPU virtualisation.
What this is trying to say is that Tokio is best used for when you have an application that does a lot of waiting on I/O, like a server or a GUI. These are called I/O bound applications. They are limited by how fast they can get their I/O requests fulfilled. Other types programs which do more computations but need minimal I/O are called CPU bound. These applications will run faster if they have longer access to the CPU. A perfect example of this is my chess bot.
In the case of CPU bound programs, the docs are directing us to use Rayon, another rust crate.
After installing Rayon, I used their very simple parallel iterators to run searches through multiple positions in parallel.
Now my bot responds within 2 secs for depth=2!
The bot is still slow for depth=3 though, so I still ll have a lot of optimisation to do. And I have a plan for doing that should work though I’m not certain…
A Troublesome Tree
July 9, 2026
Last time, i said I had an Idea for how i would make the bot faster. That idea was caching! i wanted to cache the results of generating the moves recursively.
If i wanted to look 5 moves into the future:
- i would generate the 5 layers for my first move
- On my next turn, the top 2 layers of the tree are thrown away (the move I originally played and the move my opponent played next), so i need to only generate 2 additionally layers of the tree to look 5 moves ahead.
- The above scenario repeats for the rest of the game.
To actually cache the tree, I have to actually generate it first. The original algorithm didn’t actually build a tree data structure in memory… rather the tree was implied; moves were explored through pushing frames onto the callstack and disposing of them immediately. In other words, the algorithm was stateless, so I had nothing to cache.
Because of that, i rewrote the algorithm. Now, I have a PoistionTree data structure with methods for move geenration and position evaluation. I implemented the data structure myself; Rust doesn’t have a built in tree data structure to the best of my knowledge. Lastly the code looked fantastic! using the interface provided by the PositionTree struct made everything much cleaner.
However the bot became significantly slower. This is odd, as, at the end of the day, bothi versions of the algorithm execute a similar work load.
I decided to work on speeding up the current version of the algorithm before properly implementing caching, and I should be sharing that chsapter of this journey soon enough!
Fat Pointers
July 12, 2026
Last time, I explained how my cacheable implementation of the algorithm was, unfortunately, quite slow. So I tried to fix that.
Flame graphs would be a perfect tool for identifying the slowdown; however, the multithreaded nature of the program made using them quite hard. I looked into profiling and benchmarking via crates like Rust Tracing, but that would require large changes to the codebase, so before doing that, I wanted to try general performance improvements.
What first came to mind was vector reallocations. I rewrote the algorithm so it reserves all the required space before expanding the tree. Additionally, I took advantage of the fact that the tree is generated breadth-first: all children are written to memory next to each other, so I could use a fat pointer to represent the children of a node instead of the vector of indices I was using.
I did this among other performance improvements, but to no avail. I asked an LLM with the full context of the repo to compare both old and new implementations of the algorithm, and it came up with a list of reasons why it was slower, but they mostly weren’t actionable. Furthermore, I looked into alpha-beta pruning—a well-known method to speed up chess engines—and that required the tree to be built depth-first, not breadth-first, so my code and all optimizations I just built had to be scrapped.
And I had to start over, from square one, before implementing the cacheable data structure.
Memoization & Minimax
July 17, 2026
I’ve been doing research, and I found out that the algorithm I invented in Issue 2 is actually a well-known algorithm called Minimax. It is really rewarding to see that my scribblings at a dining table are actually a THING in computer science and is used by many AI systems to play games.
I also got a vague impression of Alpha-Beta Pruning (as I said in my last entry in this series, it’s a technique that allows Minimax algorithms to run significantly faster) and that I needed to rewrite my code to search and evaluate moves depth-first rather than breadth-first. Besides enabling ABP, depth-first search means I only have to walk the tree of all possible positions once for both generation and evaluation, not once to generate and another to evaluate, which is possibly another performance speedup.
The depth-first search rewrite is done, thankfully; it’s almost exactly what I had about a few weeks ago before the cacheable tree fiasco.
In this version of the algorithm, “memoisation” - not “caching” - better describes how I intend to save work. The function to evaluate a position takes a mutable reference to a tree of positions. Before generating new positions from the current one, it checks if the current position saved within the tree already has children. If so, it uses those. If not, it generates the positions and writes them in the tree. This is all still a plan; I haven’t fully implemented that quite yet.
One last tidbit. During my experimentation, I found out that checking whether each position was checkmate or stalemate and skipping generating child moves if either was true was significantly less efficient than generating the moves either way and having the robot discover “Oops! No legal moves after this position.” That might’ve been the reason behind the older algorithm I just replaced being so slow.
So after all that, what were the results? The bot is now noticeably faster while playing exactly the same (sometimes better, since I fixed a bug along the way). I am quite satisfied with the outcome of this work, and hope to tell you next time how my bot plays with memoisation enabled!