Doumi Chess

« Back

Doumi in Arena

Doumi is an open-source chess engine written in C++. Its ELO should be around 1700. It contains about 4000 lines of code, which you can find in GitHub. Doumi implements basic version of Universal Chess Interface (UCI) Protocol, which enables users to play against it with a GUI or test it against other engines.

Algorithm

The goal of a chess engine is to provide a "best" move for a given board. To provide such information, Doumi has three parts: move generation, board evaluation and recursion.

Move generation algorithm is simply finding the list of possible moves from a given board.

Board evaluation algorithm is assessing the board to see which side is winning, and by how much. Normally the unit of advantage is centipawns (1 pawn = 100 centipawn). Doumi uses a simple heuristic for evaluation, only considering the pieces' strengths and the location of the piece. For example, a rook is worth more than a pawn, and a knight in the center is better than a knight in a corner square.

Recursion is needed for chess engines since it needs to look far ahead to win. If there is a mate in 5 possible by sacrificing a queen, the engine should be able to foresee the mate and be willing to sacrifice. Hence, it is important to have as much depth as possible. Some of the best chess engines go over 40 plies deep in a search. Negamax is a variant of minimax, which is a standard search method for two-player games. Doumi also uses Alpha-beta pruning for efficient search. Alpha-beta pruning is a pruning algorithm that significantly cuts down the number of boards the engine needs to evaluate.

Future Improvements

The two ways to siginificantly improve the engine are to use a better pruning algorithm or to evaluate the board faster. Currently, I am trying to improve the pruning algorithm by Principal Variation ordering, an algorithm that first checks a variation (sequence of moves) that yields a good position to prune more branches.

Versions

1.1.0 - Added basic support for UCI Protocol
1.0.0 - Initial release

You can read more about the changes here.