Valkyrie - A C++ Chess Engine

While learning the rules of chess are simple, coding them is a much more difficult task. Not only do you need to implement moving each type of piece in a specific way, but you also need to look at conditional moves such as castling, promoting a pawn, en passant, and check, among others.

To calculate the best move, the engine strategically traverses a tree of all possible game combinations, analyzing only those with a realistic probability of being played (i.e., assumes the opponent will not give away his queen).

After testing a typical mid-game position, Valkyrie searched to a depth of 6 in about 0.33 seconds. Out of the ~240 billion possible combinations, the engine analyses only 0.00037% of them to determine the best move. Yet to achieve this speed, it must test 2.6 million positions per second.

One important decision was how to encode piece movements efficiently. My move system needed to be memory efficient to maximize the amount of information I could store with limited memory. I choose a more complex system with both a 16-bit BaseMove and a 24-bit Move. The memory breakdown is as follows:

Basemove:
    6 bits ==> start position
    6 bits ==> end position
    4 bits ==> flags to indicate special moves including 
               castling, en passant, and captures

Move:
    16 bits ==> Basemove
    3 bits ==> type of piece moving
    3 bits ==> type of piece captured
    2 bits ==> spare

The next difficult task was establishing a sense of strategy for the engine, including the ability to quantify how favorable a given position is. This quantification is where an understanding of chess theory was helpful. To quantify which side is winning and by what amount, the engine considers the following:

• Material base value
• Decreasing knight value with a lesser number of pawns
• Increasing rook value with a lesser number of pawns
• Bonus for having two bishops
• Penalty for having no pawns
• Penalty for having doubled pawns
• Penalty for having isolated pawns
• Reduced value of a and h file pawns
• Bonus for advancing pawn (bonus increases with game duration)
• Bonus for knights in the center of the board
• Small penalty for queens and bishops in corners
• Penalty for advancing king early in the game

While I am currently satisfied with evaluation performance, I believe it could be improved by considering passed pawns and king safety. Additionally, it would greatly help to create some kind of parameter tuning method to better quantify exactly what effect each of these evaluation methods should have.

The last step was making my engine efficient to the point where it could run fast enough on a modern-day laptop to be competitive. I used Intel's VTune profiler extensively to find slow or memory-consuming functionality in my code. VTune helped me discover one surprising bottleneck: the time required to allocate and de-allocate memory. To deal with this, I allocated all the memory I needed on startup and would overwrite memory as required.

Upon completion, Valkyrie could evaluate about 2.6 million positions per second and run on 18 MB of memory. Ultimately, the engine was a resounding success as I met my primary goal: creating a program that could consistently beat me at chess. The source code and compiled versions can be found on my Github page.