The Development Process of the Linear Chess Engine

Linear Chess is a chess engine and interactive chess GUI. It comes with custom games, variable difficulty, and the ability to import games in the form of a FEN. Linear Chess was developed over the course of 5 weeks, going through 4 distinct iterations.

Iteration One:

The first iteration of Linear Chess was primarily a learning exercise. I decided to try and make the engine without the use of any online resources and it went as well as can be expected. The game was lacking castling, en peasant, and frequently miscalculated the status of check. The major mistakes I made creating this first iteration were: not spending time researching chess, failing to ensure the stability of systems before adding to them, and poorly planning how new features like en peasant would interact with the engine. The engine for the first iteration ran on the minimax algorithm using alpha-beta pruning. It was exceptionally basic in the evaluation function as well, only having material value and piece-square tables. It used a proprietary board representation where each piece was a class inheriting from a parent piece class. Each piece was stored in a two dimensional array which represented the 8 by 8 board. Needless to say, the move generation was very slow. After seeing how impractical this project would be if I chose to continue with this board representation system, I decided to create a second iteration.

Iteration Two:

Iteration two was a naïve attempt to fix the problems with the first engine. Primarily, I changed the board representation completely. I still hardly spent any time researching how to make the most efficient board, however, and so I thought that a FEN representation would be ideal. All the movement logic was generated based on a FEN string and so for each piece, at some point in its move generation, it would have to iterate over the FEN string. This is also very slow, and while much faster than my previous move generation, still nowhere near acceptable. Not to mention it was never fully completed as the move generation became so convoluted that debugging became very difficult. I decided that the chess engine problem was more complex than I originally anticipated and so I decided to take it more seriously with iteration three.

Iteration Three:

This iteration ended up being far better then either of its predecessors. It was at this point I discovered the chess programming wiki and it changed the whole game. I still used my own ideas for board representation and move generation. This time, I went with a char[64] to represent the board. Each piece was represented by its respective FEN character and empty spaces were represented by ‘-’. This time the move generation was at least respectable, though far from perfect, and I could start really working on the guts of the engine. I added many upgrades to this engine including, move ordering (history heuristic and static exchange evaluation), transposition tables, a custom opening book creation program, iterative deepening, and Principle Variation Search. The evaluation function also got a shiny new coat of paint and heuristics for center control and pawn structure. This engine was able to reach a depth of 5 in around 10 seconds. Still not great, but it was at least the strongest yet. However, the code I wrote for this engine was not well written and quickly became confusing and bloated. Move generation problems plagued the system and evaluation errors caused horrendous blunders at times. While the engine could play decently and win some games against weak engines on chess.com (the site I used to test my engines), it still was not where I wanted it. Iteration four cleaned up all these problems though.

Iteration Four:

The final iteration of Linear Chess was written in one and half weeks. I used the ever efficient bitboard board representation. The technical aspects of the techniques used are discussed in detail in a separate document. I made a point to write code as cleanly as possible as the complexity of the move generation system was a core problem in previous iterations. I quickly completed the move generation in two days (along with the GUI and player interaction), and I started work on the engine itself. I knew this would be the last iteration, so I wanted to ensure it stayed stable. Instead of cramming the engine with feature after feature I selected carefully. I ended up using the Negamax algorithm (to simplify the engine code to one Negamax function instead of a Mini and a Maxi function) and eventually upgraded it to Negascout. The move ordering system and evaluation were similar to the previous iteration, only far more optimized for fast run times. There are few features implemented in the version one release of Linear Chess for the search function because stability was most important and 5 weeks is far longer than a standard project. After much testing and refinement the engine can reliably beat 1800 rated opponents on chess.com, being able to search 2 million possible game states in only 20 odd seconds. Currently the greatest problems with the engine are end game tactics and opening repetition. Since there is not an endgame table base or an opening book implemented yet, the openings are not always maximally ideal and the engine often misses possible forced mates due to the rather shallow 6 depth search. To help with the endgame problem, I implemented iterative deepening for end game states only (I had strange problems with iterative deepening blunders when in early game states). There are still many optimizations to be made, but for now the Linear Chess engine is more than competent.