Roadmap

A chess engine is quite a complex piece of software. It is not possible to "just" write a chess engine off the bat, except if you've got lots of experience in writing chess engines or similar software. (In that case, you're probably reading the wrong book.) Therefore this chapter will describe a roadmap to get your new engine to a playing state.

First, the engine needs to be designed. If necessary, reread the chapters "concept" and "design", where Rustic's overall structure is explained. In the roadmap below, the big parts of this architecture are going to be unpacked into smaller parts which can be implemented one at a time.

The roadmap will describe how to get the engine to play somewhat decent chess. From that point onward, it "just" becomes a matter of adding features to make the engine stronger. If your overal design and implementation is well done, adding newer features on top of the baseline version is much less difficult than getting to the baseline itself.

Don't worry if you encounter terms in the roadmap you don't yet understand. When we get to the design and implementation, these will be explained.

  • Design and write the board representation
    • Represent the board
    • Represent the pieces
    • Read a position from an FEN-string
    • Keep the current state of the game
    • Keep a history of played moves
    • Implement Zobrist hashing
    • Create functions to control the board
    • Create functions to get information from the board
  • Design and write the move generator
    • "Teach" the move generator how the pieces move
    • Create a move format
    • Generate moves for all the pieces when the MG is given a position
    • Take special moves into account (such as castling)
    • Adds generated moves to a move list and returns this when done
    • Can generate captures and silent moves seperately
    • Can determine if a square is attacked
  • Write the search functionality
    • Structs (information) needed by the search
    • Write the iterative deepening function
    • Write the Alpha-Beta function
    • Write the Quiescence search
    • Make fixed search possible (on ply, nodes, or time)
    • Implement time management for non-fixed searches
    • Helper functions such as determining if a position is draw
  • Write the evaluation function
    • Material counting
    • Piece Square tables (PST or PSQT)
  • Order the moves for more speed
    • MVV-LVA (Most Valuable Victim-Least Valuable Attacker)
  • Design a communication interface ("IComm" in Rustic)
    • Write the UCI-protocol
    • Write the XBoard protocol (optional)
    • Make sure the engine understands the commands
    • Make sure the engine reacts correctly

Do not begin to extend the engine with new features until the baseline as outlined above has proven to be bug-free. It should be able to complete a perft suite without errors and it should be able to play thousands and thousands of test games in a row without crashing, making illegal moves or forfeiting on time.

Go back and read the above paragraph again. This is one of the most important things in chess programming. If your baseline engine is not bug-free, any and all features you add next will either not bring you the improvement they should, or they won't work at all. This also means you should only move on to the next feature if the previous feature has proven to be working correctly. Fixing bugs afterwards, in a feature you added weeks or even months ago is difficult in a chess engine; much more so than it is in "normal" software.

After all this is implemented, you should have an engine that is on par with Rustic Alpha 1 with regard to functionality. The engine has no chess knowledge apart from PST's and material values. You can use Rustic Alpha 1 versions to get started. If you do, the only difference between your engine and Rustic Alpha 1 should be speed.

If your engine has no bugs, and you're using Rustic's PST's and material values, you can expect an rating of 1500-1700 Elo after the engine is tested in a list such as the CCRL 2m+1s Blitz list. Rustic Alpha 1 has a rating of 1675 Elo.

In case your baseline engine reaches less than 1500 Elo, it's either slow, buggy, or both. First make sure there are no bugs, then try to optimize for speed. If you are using a slow programming language, there are obviously limits to what you can do with regard to speed.

Should you be in the high 1600's, you could possibly hit 1700 by tinkering a lot with the material values, piece square tables, and time management. It's probably not worth it, as all those functions will either be improved or replaced in later versions, so don't spend too much time on this.

(I believe 1700 on the CCRL Blitz list is the absolute maximum you could reach with the given baseline version that has only material values, PST's, MVV-LVA move sorting, and no special search or move generator optimizations.)

From this point onward, you can add features in any order you want. Mostly, at least. There are features that depend on other features. To implement transposition table move ordering, you obviously first need to have a working transposition table.

Let's move on to the first topic: board representation.