131 lines
4.8 KiB
Markdown
131 lines
4.8 KiB
Markdown
# BitChess Engine
|
|
## A Pure Algorithmic Chess Engine
|
|
|
|
### Chess Engine Overview
|
|
|
|
BitChess is a high-performance chess engine developed as a hobby project to explore low-level optimization techniques and algorithmic game theory. The engine uses traditional, non-AI approaches to chess programming, focusing on efficient data structures, multithreaded search, and careful optimization of critical paths.
|
|
|
|
This project demonstrates how far a pure algorithmic approach to chess can go without relying on neural networks or machine learning techniques that dominate modern engines like Stockfish, Leela Chess Zero, or AlphaZero.
|
|
|
|
### Motivation
|
|
|
|
The primary goals of this project are:
|
|
- Deepen understanding of bitboard representations and bit manipulation
|
|
- Master low-level optimization techniques in C
|
|
- Explore multithreaded search algorithms
|
|
- Build an efficient, pure algorithmic chess engine from scratch
|
|
- Benchmark algorithmic approaches against more modern techniques
|
|
|
|
### Key Features
|
|
- Bitboard-based representation for maximum performance
|
|
- Alpha-beta pruning with move ordering for efficient search
|
|
- Multithreaded search to utilize multi-core processors
|
|
- Position evaluation using piece-square tables and material value
|
|
- Clean terminal interface that updates in real-time
|
|
- Standard Algebraic Notation (SAN) support for move representation
|
|
|
|
### Technical Approach
|
|
|
|
#### Board Representation
|
|
|
|
The engine uses bitboards (64-bit unsigned integers) to represent the chess position, where each bit corresponds to a square on the board. This approach allows for extremely fast position updates and move generation using bitwise operations.
|
|
|
|
Bitboard for White Pawns (P): `0x000000000000FF00`
|
|
|
|
----------------
|
|
8 | . . . . . . . . |
|
|
7 | . . . . . . . . |
|
|
6 | . . . . . . . . |
|
|
5 | . . . . . . . . |
|
|
4 | . . . . . . . . |
|
|
3 | . . . . . . . . |
|
|
2 | P P P P P P P P |
|
|
1 | . . . . . . . . |
|
|
----------------
|
|
a b c d e f g h
|
|
|
|
#### Search Algorithm
|
|
|
|
BitChess employs a classic Minimax algorithm with Alpha-Beta pruning to search the game tree efficiently. The engine implements:
|
|
- Move ordering to maximize alpha-beta cutoffs
|
|
- Multithreaded search at the root node to parallelize evaluation
|
|
- Iterative deepening to find good moves quickly
|
|
- MVV-LVA (Most Valuable Victim - Least Valuable Aggressor) for capture ordering
|
|
|
|
#### Evaluation Function
|
|
|
|
The evaluation combines several components:
|
|
- **Material balance** - basic piece values (pawn=100, knight=320, etc.)
|
|
- **Piece-square tables** - bonuses/penalties for piece positioning
|
|
- **Mobility** - counting legal moves as a proxy for piece activity
|
|
- **King safety** - evaluating the king's defensive structure
|
|
|
|
#### Move Generation
|
|
|
|
The engine generates moves using precomputed attack tables:
|
|
- **Sliding pieces** (bishops, rooks, queens) - using ray attacks
|
|
- **Knights and kings** - using precomputed attack patterns
|
|
- **Pawns** - handling special moves like promotions, en passant, and double pushes
|
|
|
|
### Implementation Details
|
|
|
|
BitChess is written in C and designed with modularity in mind:
|
|
- **Bitboard module** - manages attack tables and bit manipulation
|
|
- **Board module** - handles game state and move application
|
|
- **Movegen module** - generates legal moves
|
|
- **Evaluation module** - assesses positions
|
|
- **Search module** - finds the best move
|
|
- **Notation module** - converts between internal move representation and SAN
|
|
|
|
### Performance Considerations
|
|
|
|
Several optimizations are implemented:
|
|
- **Precomputed attack tables** - eliminate expensive calculations during search
|
|
- **Move ordering** - dramatically improves alpha-beta pruning efficiency
|
|
- **Multithreading** - utilizes all available CPU cores
|
|
- **Bit manipulation** - uses built-in popcount and bit-scan operations
|
|
- **Structure organization** - designed to maximize cache efficiency
|
|
|
|
### Current Capabilities
|
|
|
|
The engine currently:
|
|
- Implements all chess rules correctly, including castling, en passant, and promotions
|
|
- Searches at configurable depths with reasonable performance
|
|
- Uses multiple threads to speed up search
|
|
- Displays evaluation in centipawns
|
|
- Provides a clean terminal interface
|
|
|
|
### Future Improvements
|
|
|
|
Planned enhancements include:
|
|
- Transposition tables to avoid re-searching identical positions
|
|
- Quiescence search to resolve tactical sequences
|
|
- Opening book for stronger play in the early game
|
|
- Endgame tablebases for perfect play in simplified positions
|
|
- UCI protocol support for compatibility with chess GUIs
|
|
- Performance profiling and further optimization
|
|
|
|
### Building and Running
|
|
|
|
|
|
#### Clone the repository
|
|
```bash
|
|
git clone https://git.srtk.in/sarthak/bitchess.git
|
|
cd bitchess
|
|
```
|
|
|
|
#### Build the project
|
|
```bash
|
|
make
|
|
```
|
|
|
|
#### Run the engine
|
|
```bash
|
|
./build/bin/bitchess
|
|
```
|
|
|
|
### Requirements
|
|
|
|
- GCC or Clang compiler with C99 support
|
|
- POSIX-compliant operating system (Linux, macOS, or Windows with WSL)
|
|
- pthread library
|