Following a request in the general subforum, I am now creating a thread concerning the development of Loki. The reasons for creating it are two fold: 1) To - perhaps somewhat sporadically - document the development of Loki, and 2) To have a place where I can gather my thoughts and ideas during development which can hopefully become useful for others.
As a starting point, I have collected some information about the engine below.
A quick introduction to Loki: Loki is a UCI-compatible chess engine written in C++17. It is the second engine I have written, the first one being Copper. Copper was a mess and had a lot of features either (too) heavily influenced or taken directly from Vice (author: BluefeverSoft on Youtube). It was written because I needed a project to work on in order to learn C++. Secondly, chess is an interest of mine, and I had for a long time been wondering how on earth chess engines worked (started out with the classical: "Don't they just look ahead? That sounds pretty easy... Wonder why it took a supercomputer, IBM Deep Blue, to surpass human chess knowledge").
After getting stuck with the development of Copper (primarily due to many severe bugs), wanting a multi-threaded engine, and wanting to create an engine that I could actually call my own, I started working on Loki. It is a work in progress, and will probably not become a top tier chess engine. But that is fine because making a 3400+ rated engine wasn't my goal to start with. Although it would be lovely to one day make it strong enough to beat Magnus Carlsen
Features and their implementations: Loki uses bitboards and a piece list as its board representation.
Move generation:
- Magic Bitboards, as implemented by maksimKorzh, for generation of sliding piece attacks. This gives a perft (no bulk-counting) speed at depth 5 from the initial position of 282 ms
- MVV/LVA as an initial sorting of captures and then SEE when they get fetched from the list of moves
- Killer moves
- Countermoves are implemented, but due to an elo loss and crash bug they are disabled ATM.
- History heuristic.
Search:
- Minimax with alpha beta pruning in a negamax framework (fail-hard).
- Lazy SMP supporting up to 8 threads.
- A two-bucket transposition table from 1MB to 1000MB. It is configured such that the first bucket has a depth- and age-preferred replacement scheme, and the second is always replace.
- Iterative deepening.
- Mate distance pruning.
- Adaptive null move pruning.
- Enhanced futility pruning.
- Reverse futility pruning.
- Razoring.
- Quiescence search. Here, moves with SEE < 0 are pruned.
- Material and (simple) material imbalances.
- Piece-square tables
- Pawn structure and passed pawns.
- Space in the middlegame.
- Safe mobility evaluation of pieces.
- King safety evaluation.
- Evaluation of pieces. This is disabled since all tests of it has shown a decrease in elo, but I will hopefully make it work some day.
- Tapered eval.
Future improvements:
This list is not very exhaustive, and a good deal of features and optimizations will probably be added on the way, but the main improvements I want are the following:
- Staged move generation, which I am working on right now.
- Late move reductions.
- Late move pruning.
- Better time management. At the moment, Loki divides the remaining time by 30, if not told otherwise, which is the number of moves, that is assumed to be left of the game. This makes Loki use way too much time in the opening, and then suffer from time trouble in the late middlegame and endgame.
- A working piece activity evaluation.
- If Loki gets to a descent strength, I will look into some machine learning for the evaluation. This is probably pretty far out in the future, but seeing the success Stockfish has with NNUE, it seems like something to try out. However, I do not want to use Stockfish's implementation directly since I think it will be way too much external code considering the enormous role evaluation plays in deciding the engine's strength and style.
Link to the github repository: https://github.com/BimmerBass/Loki/tree/master
I remember reading a post on the forum when I just started work on Copper. There someone warned about how addictive chess programming is. I didn't really think too much of it back then, but to the surprise of probably no one here, he was right. And look at me now: An "nps-junkie" always anxiously looking to get more node-count reductions