pychessengine is a pure-python chess engine and learning tool. It supports:
A board is represented as a state object which stores a list of piece bitboards, as well as occupancy bitboards for each piece type and color. The occupancy bitboards are redundant, but are available for efficient evaluation. A board state is updated, but never copied. A state can be updated to apply or revert a move allowing for forward and backward traversal through a game tree. Since pieces are stored as bitboards, updating is efficient through the use of bitwise operations. A rolling hash is also implemented using Zobrist Hashing, which means a state's hash does not need to be recomputed after every move, allowing for fast board caching (see evaluation).
A bitboard is a 64 bit integer where each bit corresponds to a square on the board. Bitboards are powerful because they can be manipulated using bitwise operations to perform computations that would otherwise only be possible through iterating through squares on the board.
Each piece bitboard contains a single on bit indicating the square the piece is on. There are 32 pieces at the start of a chess game, so a board state can be stored and maintained with just 32 integers: 256 bytes. Piece bitboards are never removed from a board state. Following a move (which is also represented as a bitboard), piece bitboards are updated using bitwise operations. If the move is a capture, the captured piece becomes an empty bitboard. This way, scanning through individual bits in a bitboard can be avoided. Checking if a bitboard is empty is efficient because it can be done with a simple equality check, since an an empty bitboard will be equal to 0.
A positive score indicates white is winning, while a negative score means black is winning. A score is determined for each property, which then is multiplied by a weight. Weights are currently hardcoded in, but I plan to use some type of regression or neural net to optimize them. The evaluation function is a Linear Combinations of evaluation features. There are 3 types of evaluation modes (lazy, normal, eager), which allows for certain positions to be evaluated more fully (evaluation heuristics). Every time a position is evaluated, the evaluation is cached using the board's Zobrist hash. This way, a position only needs to be evaluated once, which is necessary since game trees will often contain many recurring positions.
Evaluation Features
Searching for the optimal move in a game tree. Moves are edges, board states are nodes. A soft maximum search depth is used in order to overcome Evaluation Discontinuity.
Minimax is a depth first search algorithm that maximizes the worst possible outcome. The upper bound time complexity is O(b^d), where b is the number of legal moves and d is the maximum search depth. On it's own, minimax is an inefficient algorithm, but is optimized with alpha-beta pruning.
Alpha-Beta Pruning eliminates branches that are mathematically garunteed to be sub-optimal. If a player's optimal worst position is worse than the opponents optimal worst outcome, a cutoff occurs. This is possible because chess is a zero sum game. The efficiency of alpha-beta pruning is directly correlated with the strength of the move ordering algorithm, since more alpha-beta cutoffs will occur when better moves are searched first.
Moves are represented as bitboards. Move generation is done in 2 steps. Attack generation and legal move generation. Moves are generated by performing bitwise operations on precomputed move caches. Magic bitboards are used for for sliding piece move generation. Move Ordering needs some work but currently, moves are ordered using MVV-LVA and through sorting based on a lazy evaluation.
A lot of pregame setup is involved, so pregame gets its own package. During pregame setup, data files are stored to memory. These data files consists of move caches (include the magic bitboard cache), board masks, and data used for evaluation. These files are either json or pickle files. Pickle files are used when the data includes dictionaries with integer keys, since json only permits string keys. Isolating the pregame setup and storing its results to files allows for much cleaner code in the files that are prevalent to the actual game. If the data files don't exist, the engine will automatically generate them, so no manual setup is required.
- Quiescence Search/Iterative Deepening
- Principle Variation Search
- Killer Move Heuristic
- PGN Parsing
- Tapered Evaluation
- Pawn Structure Evaluation
- King Safety Evaluation
- pin detection
- opening book
- transposition tables
- perft testing
- multi processing
- Futility Pruning