OmegaZero is a chess engine built from scratch which allows a user to play against an AI. The name "OmegaZero" is an homage to AlphaZero, a program developed by DeepMind that was used to create one of the world's best Chess engines. The Chess Programming Wiki was referenced heavily during development. Credit goes to Bradon Hsu for designing the logo for this project.
The included Makefile is designed to run on GNU/Linux machines. The Boost library
is a requirement, and should be installed locally before compilation.
On Ubuntu systems, users may use the apt-get package manager to
install Boost like so:
sudo apt-get install libboost-all-dev
To build the software, simply type make in the root directory of the project.
This will take several minutes as the magics.cc file takes quite
a while to build. To completely clean a build, make purge will remove the
entire build directory. To remove all object files except for the one generated
by magics.cc, you may make clean. Doing so will result in much faster
rebuild times.
To begin a game, a user invokes the program as follows:
OmegaZero -p [SIDE] -t [TIME]
where [SIDE] is the side the user would like to player. This may be w for
White, b for Black, or r for a random selection. [TIME] is the amount of time (in seconds) to give the engine during play. This defaults to 5s.
The format used to denote entered moves is based around FIDE standard algebraic
notation. The only exception to FIDE notation is that e.p. must immediately
follow an en passant move without a space (in FIDE rules, this is optional). Further specification is only needed
to avoid ambiguity in a movement command. Some valid example moves are
- Move pawn to e4:
e4 - Move queen to e4:
Qe4 - Move pawn to d8 and promote to queen:
d8Q - Pawn takes piece on d6:
exd6 - Night takes piece on e4:
Nxe4 - Rook on rank 1 moves to a3:
R1a3 - Rook on d file moves to f8:
Rdf8 - Pawn takes a piece on d8 and promotes to queen:
exd8Q - Queen from h4 moves to e1:
Qh4e1 - Queen from h4 takes piece on e1:
Qh4xe1 - Pawn from e file takes pawn on d5 in en passant:
exd6e.p. - Queenside castle:
0-0-0 - Kingside castle:
0-0
To resign, a user must enter q on their turn.
To print out the Perft results for engine, invoke the program as follows:
OmegaZero -i [POSITION] -d [DEPTH]
[POSITION] is a FEN formatted string denoting the intial position to
start counting nodes from in the search tree; not providing this will cause the
program to default to the standard initial position in a chess game.
[DEPTH] is a positive integer denoting the number of levels to generate in
the search tree.
After doing this, users have the choice of entering either a move formatted as
previously outlined to walk the search tree, or q to exit the program.
The positions on this page were used to confirm the correctness of the move generator.
The engine uses both Bitboards and an 8x8 Board to represent board. states. Squares are indexed in the Little Endian Rank File (LERF) format.
For non-sliding pieces, arrays of bitboards representing all possible places
a piece can move to on an empty board for every square are computed
by generate_masks.py. For sliding pieces, move generation is implemented
through the magic bitboard technique.
The move generation function Engine::GenerateMoves() is implemented as a
pseudo-legal generator. A full legality check is made in Board::MakeMove()
to ensure that a move does not put the moving player in check; illegal moves are
unmade if they are found to do this.
A custom hash table was used to implement the Transposition Table. The Zobrist Hashing algorithm was used to hash board states. This technique an expected collision rate of one in 2^32 ≈ 4.29 billion. Relatively little can be done to mitigate this risk, and as such is a known and unavoidable bug with this implementation. The Transposition Table is two-tiered, using the "Always Replace" and "Depth-Preferred" replacement schemes in parallel.
The MTD(f) search algorithm is used within an Iterative Deepening framework. This routine calls an implementation of the Negamax algorithm with alpha-beta pruning, Null Move Pruning, and Late Move Reduction. A depth reduction value R of 3 is used when depth is greater than 6, and 2 otherwise in Null Move Pruning. For Late Move Reductions are computed using the formula
int(sqrt(double(depth-1)) + sqrt(double(move_idx-1)))
taken from Fruit. Reduction is only done on non-PV (Principle Variation) nodes. A Transposition Table is used to cache seen positions, allowing the engine to store each node's type is and prevent costly re-evaluation of a node. This is especially important for storing the Principle Variation during Iterative Deepening.
After search to a specified depth, all captures are searched during the Quiescence Search to limit the Horizon Effect. Delta Pruning is used to limit the number of nodes explored during Quiescence Search.
To reduce the number of nodes needed to be searched, OmegaZero takes advantage
of a set of heuristics to perform move ordering in Engine::OrderMoves() in
order to increase the number of Beta-Cutoffs during alpha-beta pruning.
Moves are put in the following order:
- Hash Move
- Captures, ordered using the MVV-LVA heuristic
- Two Killer Moves
- All other moves, unordered
In the beginning of the game, the engine randomly picks an opening from an
opening book. This list of openings are provided from the text file,
p3ECO.txt written by Paul Onstad (with contributions by Franz Hemmer and
J.E.H.Shaw). Slight modifications have been made to the file to aid in parsing.
Following in the footsteps of Fruit, OmegaZero follows a minimalist evaluation philosophy, with a "light" evaluation, which scores a board position based on the following factors:
-
Raw material
-
Piece position, using the Piece Square Tables defined in
piece_sq_tables.cc -
Pawn structure. The engine is aware of backward pawns, isolated pawns, passed pawns, phalanxes, and defended pawns. It also adds penalties for holes in the king's pawn shield when castled.
-
Misc. bonuses/penalties for the following features: connnected rooks, loss of castling rights, bishop pair, and rook behind passed pawn.
We use a Tapered Eval scheme when scoring the position of the king, using the formula found here.
The move generator is capable of producing up to ~7 million moves/sec.
OmegaZero consistently wins against Stockfish through level four, and is competitive with Stockfish level five. From this, we can approximate an ELO score of ~2000 for the engine.