Naraku is a chess program that I started way back in 2009 and worked on for about two years as a hobby project to learn C, which at the time I thought would be a useful addition to my skills as a chemical engineer. It was based on various algorithms that at the time appeared to be freeware or publicly available, including, in part, the controversial freeware program Ippolit. Its playing strength is estimated at around 2700–2750 Elo on a modern standard notebook.
I no longer have the program’s source code, but I can summarize its main features here:
- Like the vast majority of chess engines, it uses a Negamax algorithm (a variant of Minimax) with alpha-beta pruning.
- It employs several pruning and search heuristics, including Null Move Pruning, Late Move Reductions, aspiration windows, futility pruning, and history pruning.
- In the later versions, I implemented the use of bitboards, although only partially and probably with a few bugs.
- The earliest versions used a three-stage positional evaluation (opening, middlegame, and endgame), which was later reduced to two stages after I found that the two-phase version was actually stronger.
- The evaluation function included material balance, piece-square tables (PSTs), mobility, king safety, as well as numerous positional terms (bishop pair, passed and protected pawns, rook on the seventh rank, etc.) and integrated tables for some of the most important endgames.
- The program could have its playing strength reduced up to around 1000 Elo by modifying or perturbing the evaluation weights and disabling some of its features.
Highlander, the tuning algorithm
To tune the weights of the evaluation function, I developed my own dedicated tool, which optimized the weights using an evolutionary algorithm that I jokingly called Highlander (“There can be only one”).
Broadly speaking, the algorithm worked as follows: dozens of variants of Naraku were pitted against each other, with their evaluation weights randomly modified using a Monte Carlo approach within a certain range determined by the value of each weight. Weights with larger values were allowed to vary within a wider range. The original “parent” program also took part in the matches.
After a large number of ultra-fast games, the program with the highest score advanced to the next generation. All the others were eliminated, hence the name Highlander. The surviving program then generated dozens of new “childrens” through further random mutations of the evaluation terms, with the mutation range gradually becoming narrower.
The algorithm converged relatively quickly compared with testing each individual term over thousands of games, providing substantial Elo gains in a short amount of time. However, it also had some drawbacks, the most serious being its tendency to converge towards suboptimal local minima. I was able to partially counter this by randomly modifying some of the weights and restarting the testing round.
Today, this approach has been superseded by much more efficient methods, such as Texel’s Tuning Method, for example. Nevertheless, I continued to use it occasionally in my work as a chemical engineer, since it could easily be adapted to other fields. More recently, I have managed to extend it further by adding greater flexibility in the way mutations are introduced between different program versions.
The name of the program Naraku, for those wondering, comes from the main villain of Rumiko Takahashi’s manga Inuyasha, a series I greatly enjoyed in my youth. In the manga, Naraku was known for becoming stronger through continuous recombination and the development of new incarnations of himself. Ironically, this is exactly what happened to the program when I applied the Highlander algorithm to it.
Below is an example game played by Naraku against GNU Chess 6.21, with 20 seconds per move.