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