As the final project of a 6 month C/Unix coding bootcamp, I worked on the implementation of a chess AI, that is able to compete online using the UCI protocol.

I. Chess Game engine

implementation of the rules of the game of chess. Chessboard representation, pieces, allowed moves, state, etc.

This is the engine used locally to test our AI. It is critical that it is

1. functional. So that our AI plays proper chess.

2. efficient. Our AI involves a lot of chessboard replication to test all possibilities. All the operations related to the chessboard need to be as light as possible on our CPU and memory.

The bitboard representation is a very efficient way to represent a chessboard. Each piece family (type + color) is modeled as a single uint64. As a result we only need 12 integers to represent our board (instead of the 64 we would have with the naive representation of a chess board)

II. Chess AI

implementation of a decision AI that searches for the best move given a board state

The baseline AI evaluates a board state, and searches for the best move it.

To evaluate, we define a heuristic function. This heuristic is critical to the good behaviour of our AI, and tries to answer the question "given this board situation, am I in a good position ?". Our heuristic computes the sum of the value of our pieces remaining, as well as their position. For instance, a pawn that is 1 tile away from being upgraded to a queen, should be worth more than a pawn that is somewhere on the middle of the board. This heuristic is subject to change though, and remains a major route to improve the AI.

The AI performs a lot of chessboard duplication: when searching for my best move, I have to project what chessboard would emerge from performing such move. Then, I have to see what is my opponent's best move on the resulting chessboard. And so and so on. We are limited by the memory of our computer in this case, and have to introduce a "depth" parameter, that indicates how many steps we can predict in advance. Ultimately, the performance of our AI will wildly depend on the depth we allow it to use.