Craig Engine

Introduction

One of my friends and I thought it would be fun to both make chess engines, and have them play against each other. At the start of working on this project I had no idea how satisfying it would be to write and test a chess engine.

Features

• Implements the UCI interface
• Bitboard representation
• Magic Bitboard Move generation
• Move pruning and Sorting
• Evaluation function
• Search Pruning
• Position Hashing
• Transposition
• Static Exchange Evaluator

Board Representation

S, J. H. [illustrator]; Barnicott & Pearce [printer]; S, J. H. [author], Public domain, via Wikimedia Commons

The first thing I had to do when writing the engine was pick a representation, while the first thing you may thing of is a char-array of length 64 for each piece and square this has generally fallen out of popularity, especially with the move to 64-bit processors which allow us to represent pieces on the board as a 64 bit integer called bitboard representation. For this to work though you have to manage multiple boards and make sure you keep them in sync. As you have a bitboard for each type of piece and color, along with additional bitboards that hold information like which squares are under attack. This allows us to greatly reduces the number of cycles needed for move generation and analysis while introducing a bit of complexity.

Move Generation

Once I had my board representation next I had to generate all the legal moves in a position, this is done for the King, Pawn, and Knight by of mapping each square to legal moves from that square and then when using it comparing it with open and unattacked squares. The sliding pieces, such as the Queen, Bishop and Rook provide their own challenge which I solved by using a hashing technique known as magic bitboards. Once I had move generation I spent a lot of time on debugging using a perft function I had written.

Evaluation

For positional evaluation I originally just used a pure material solution which gave each piece type a value and judged who was winning based on material advantages. I upgraded the evaluation function to a method that has two stages, mid-game and end-game, that takes into account positional advantages and is able to understand different values for pieces based on the stage of the game. Implementing this saw a huge increase in the skill level of the engine, and I expect if I eventually implement NNUE in the future I will see another large jump in skill.

Search

Bryce Chess
Zeno333, CC BY-SA 3.0, via Wikimedia Commons

The search algorithm used in the craig engine is an alpha-beta search. The speedup in this type of algorithm is that we can use move ordering to guess which move will be the best in any position, and then see if that move is refuted. Since both sides want to pick the best move this allows us to prune a lot of moves as they would either give the opponent too good of a move or just lose the current player evaluation points. Every time a position is searched the resulting found best move hashed based on the position and stored in a hash table. This allows us to do a process of iterative deepening where we use our previous found best moves to predict which part of the search tree to explore first.

The search also implements a few more pruning methods:

• Zero Window Search
• Null Move Pruning
• Futility Pruning
• Delta Pruning
• Late Move Reductions
• Razoring

Once a best move is found, a quiescence search is done to make sure that move can't be refuted at a slightly deeper depth with a simple recapture.

Future Considerations

Infinite chess board Sven Hermann, CC BY-SA 4.0, via Wikimedia Commons

In the future with this project there are many things that I would like to add and change. Some of the things on the top of my mind are:

• NNUE The new popular way to evaluate positions in chess are with a neural networks that you can feed in the bitboards to get some sort of evaluation from. I have not looked too far into this as it adds a huge layer of complexity and would be a whole separate project, but eventually I would like to write a NNUE for the engine.

• Opening and Endgame book support This would a relatively simple thing to add. It would allow for the engine to avoid drawing and losing hard technical endgames, and allow it to compete in tournaments against other engines which use opening books at the start of games to ensure a unique match.

• Improved Multithreading As of right now the engine when in multithreaded mode will launch completely unique search threads that share and make atomic operations on the common hash table. The way the threading is currently implemented leaves a lot of room for improvement.

Acknowledgements

Shout out to the Chess Programming WIKI

And to Luke for making the rival engine.