diff options
Diffstat (limited to 'PROJECT.md')
| -rw-r--r-- | PROJECT.md | 242 |
1 files changed, 242 insertions, 0 deletions
diff --git a/PROJECT.md b/PROJECT.md new file mode 100644 index 0000000..5a3826a --- /dev/null +++ b/PROJECT.md @@ -0,0 +1,242 @@ +# Gacrux + +A chess engine written in C, implementing the Universal Chess Interface (UCI) +protocol. It supports parallel search across multiple threads using a +bitboard-based position representation with magic-bitboard move generation and a +transposition table backed by Zobrist hashing. + +## Project Layout + +``` +gacrux/ +├── build # Self-rebuilding C build binary (compiled from build.c) +├── build.c # Build system: self-rebuilding, uses fork()/exec() to compile sources +├── justfile # Task recipes (dev, test, analysis) +├── shell.nix # Nix devShell flake (gcc, python, optional Rust/Node/web libs) +├── .envrc # direnv: `use nix` +├── LICENSE # GPLv3 +├── include/ # Public headers +│ ├── ints.h # Fixed-width integer typedefs (u8..u128, i8..i128, f32, f64) +│ ├── bitboard.h # position_t bitboard representation, castling/turn enums +│ ├── fen.h # FEN string loader API +│ ├── random.h # PRNG for magic numbers & Zobrist keys +│ ├── engine/ # Engine internals headers +│ │ ├── magic.h # Magic-bitboard attack tables +│ │ ├── moves.h # move_t, moves_t, move generation API +│ │ ├── threads.h # Multi-threaded search thread structs & API +│ │ └── ttable.h # Transposition table (Zobrist hashing, buckets) +│ ├── ipc/ # Inter-process / thread IPC headers +│ │ ├── state.h # ipc_state_t: shared atomic event state +│ │ ├── threads.h # Links engine threads to IPC state +│ │ ├── uci.h # UCI thread entry point & IPC handling +│ │ ├── engine_message.h # Engine info messages (depth, score, pv, bestmove) +│ │ ├── go_args.h # `go` command arguments (time/depth/node limits, etc.) +│ │ └── moves.h # IPC move types (from/to square pairs) +│ └── uci/ # UCI protocol headers +│ ├── state.h # uci_state_t: options, signals, position, FEN +│ └── internals/ +│ ├── command.h # uci_cmd_t: parsed UCI command/token buffer +│ └── response.h # UCI state machine (initial/idle/sync/ping/active/halt) +├── src/ # C source +│ ├── main.c # Entry point: inits magic + zobrist, spawns UCI + engine threads +│ ├── uci.c # UCI stdin read loop + IPC signal handling + engine message emission +│ ├── engine.c # Aggregates all engine .c includes +│ ├── ipc.c # Aggregates all IPC .c includes +│ ├── fen.c # FEN string parser → position_t +│ ├── bitboard.c # position_starting(), print helpers, position validation +│ ├── random.c # xorshift64 PRNG (random_u64, random_magic) +│ ├── uci/ +│ │ ├── command.c # UCI command tokenization/parsing +│ │ ├── state.c # UCI engine option definitions (Threads, Hash, etc.) +│ │ └── response.c # UCI state machine command handlers +│ ├── ipc/ +│ │ ├── state.c # Atomic event wait/set for IPC synchronization +│ │ ├── threads.c # Threads <-> IPC state linking +│ │ ├── engine_message.c # Push/pop engine info messages (atomic ready flag) +│ │ ├── go_args.c # should_continue() for search limit checks +│ │ └── moves.c # ipc_moves_t add/init/deinit +│ └── engine/ +│ ├── moves.c # Legal move generation (pseudolegal + legality filter) +│ ├── threads.c # pthread creation/cancel/cleanup for DTS search +│ ├── thread.c # child_thread() & root_thread() entry points +│ ├── ttable.c # Zobrist init, transposition table insert/find +│ └── moves/ +│ ├── vec.c # Dynamic move list (moves_t) management +│ ├── magic.c # Magic bitboard attack table generation +│ ├── knight.c # Knight move generation +│ ├── pawn.c # Pawn push/capture (incl. en passant) generation +│ ├── rook.c # Rook move generation (magic bitboards) +│ ├── bishop.c # Bishop move generation (magic bitboards) +│ ├── queen.c # Queen move generation +│ ├── king.c # King move generation + castling + tests +│ └── attack.c # square_attacked() detection +├── tests/ +│ ├── main.c # Test runner: executes all discovered tests w/ timing +│ ├── generated.c # Auto-generated test table (created by find_tests.o) +│ ├── generated/ # Directory created at build time +│ └── find_tests.c # Scans src/ for `bool test_*()` functions, emits generated.c +├── symbol_analyzer/ # Python static-analysis tool +│ ├── main.py # Walks include/ + src/, extracts symbols/imports/usage, emits analysis.js +│ ├── parser.py # Token-based C definition parser (structs, enums, functions, typedefs) +│ ├── symbols.py # Struct/enum symbol extraction +│ ├── extractor.py # Character-level C tokenizer (handles macros, depth tracking) +│ └── analysis.js # Output data consumed by an HTML visualization +├── resources/ +│ └── uci/ +│ ├── uci_min.txt # Minimal UCI spec reference +│ └── UCI-Protocol-Specification.txt # Full UCI protocol spec +├── output/ # Build artifacts (.o files) +└── opt/ # External / vendored projects (gitignored) + ├── en-croissant/ # React + Tauri chess GUI + └── stockfish/ # Stockfish binary (for reference testing) +``` + +## Build System + +The build system (`build.c`) is a single C program inspired by +[tsoding/nob.h](https://github.com/tsoding/nob.h). It has three notable +properties: + +1. **Self-rebuilding:** On startup, `build.c` checks `needs_rebuild()` (compares + its own source mtime against the binary). If `build.c` changed since the last + build, it recompiles and `execvp`s itself, then continues. This lets the build + script "upgrade itself" transparently. + +2. **Modes:** Takes a subcommand (`uci`, `test`, `clean`) with an optional `run` + flag: + - `./build uci` — compiles `src/ipc.c`, `src/engine.c`, `src/uci.c`, and + `src/main.c` (with ASan + debug) into `output/main.o`. + - `./build uci run` — compiles then `exec`s the engine (runs the UCI loop). + - `./build test` — compiles `tests/find_tests.c`, runs it to regenerate + `tests/generated.c`, then compiles `tests/main.c` into `output/test.o`. + - `./build test run` — compiles tests then runs the test binary. + - `./build clean` — removes the `output/` directory. + +3. **Compilation** uses `gcc -fsanitize=address -g -Iinclude/` for all targets. + +The `justfile` wraps these: +- `just dev` → builds and runs the engine (`build uci` + `build uci run`). +- `just test` → builds and runs tests (`build test` + `build test run`). +- `just analysis` → runs the Python symbol analyzer and opens the visualization. + +## Architecture + +### Concurrency Model + +The engine uses a **multi-threaded, event-driven** architecture: + +- **UCI thread** (`src/uci.c:uci`): A pthread that continuously reads from stdin + (non-blocking), parses UCI commands, updates `uci_state`, and emits engine info + messages + best moves to stdout. It runs the entire UCI state machine. + +- **Engine search threads** (`src/engine/thread.c`): A pool of pthreads managed + by `src/engine/threads.c`. Thread 0 is the `root_thread`; threads 1..N are + `child_thread`s. These implement a Distributed Tree Search (DTS) pattern where + the root thread owns the search tree and children collaborate on split points + (`split_point_t`). + +- **IPC layer** (`src/ipc/`): Shared `ipc_state_t` containing an atomic `event` + field that acts as a synchronization primitive. Events flow between UCI and + engine threads: + - `EVENT_ENGINE_GO` → engine starts searching. + - `EVENT_ENGINE_RUNNING` → engine is actively searching (UCI loop polls). + - `EVENT_ENGINE_STOP` / `EVENT_QUIT` → engine must stop. + + The UCI thread uses `engine_message_handler_t` (atomic `ready` flag ring buffer + pattern) to push search info (depth, score, principal variation) to the UCI + thread without locks. + +### Position Representation + +Uses **64-bit bitboards** (`bitboard_t`, one per piece type × color, 12 total) +stored in a `position_t` struct. Squares are indexed 0–63 (0 = a1, 7 = h1, +56 = a8, 63 = h8). The starting position is hardcoded in `position_starting()` +(`src/bitboard.c`). + +### Move Generation + +- **Pseudolegal move generation** per piece in `src/engine/moves/*.c`, using + magic bitboards for sliding pieces (rook, bishop, queen) via precomputed attack + tables (`src/engine/moves/magic.c`). +- **Legal move filtering** in `src/engine/moves.c:get_legal_moves()` — generates + pseudolegal moves, then filters out moves that leave own king in check via + `square_attacked()`. +- **Make-move** (`position_make_move`) handles all special moves: castling, + en passant, promotions, captures, castling-right updates. + +### Transposition Table + +- **Zobrist hashing** (`src/engine/ttable.c`): Random 64-bit keys per piece×square, + castling rights, turn, en-passant. Initialized once at startup. +- **Transposition table** (`include/engine/ttable.h`): Bucket-based hash table + (4 entries per bucket, `TT_BUCKET_SIZE`), with atomic keys for lock-free lookup. + Insertion replaces the shallowest entry when a bucket is full (replacement + scheme). + +### UCI Protocol + +- Implements the standard UCI state machine (`include/uci/internals/response.h`): + `INITIAL` → `IDLE` → (`SYNC` / `PING` / `ACTIVE` / `HALT`). +- Supports all standard UCI options: `Threads`, `Hash`, `Clear Hash`, + `UCI_ShowCurrLine`, `UCI_ShowRefutations`, `UCI_LimitStrength`, `UCI_Elo`, + `UCI_AnalyseMode`, `UCI_Opponent`, `UCI_EngineAbout`, `UCI_SetPositionValue`. +- UCI spec reference: `resources/uci/uci_min.txt` and `UCI-Protocol-Specification.txt`. + +### Testing + +- **Embedded tests**: Source files use `#ifdef TEST_MOD` to conditionally compile + `test_*` functions directly into the source (e.g. `test_fen_*`, + `test_ttable_*`, `test_perft_*`, `test_uci_cmd_t`). +- **Test discovery** (`tests/find_tests.c`): Scours `src/` for `bool test_*()` + signatures, generates `tests/generated.c` with a function-pointer table and + name list. +- **Test runner** (`tests/main.c`): Iterates the table, executes each test, prints + pass/fail with timing. Perft tests verify move generation correctness against + known node counts at various depths (starting position, Kiwipete, position 3). + +### Symbol Analyzer + +A Python static-analysis tool (`symbol_analyzer/`) that tokenizes C source files, +extracts struct/enum/function/typedef definitions and symbol usage, resolves +transitive includes, and computes unused/used symbol sets per file. Outputs +`analysis.js` (JSON) for visualization via an HTML page. + +## Building & Running + +```sh +# Build the build system, then build the engine +./build uci + +# Run the engine (reads UCI commands from stdin) +./build uci run + +# Or via just +just dev # build + run + +# Build & run tests +just test +``` + +## Current Status + +The engine is a **work in progress**. The threaded search infrastructure (thread +creation, IPC event signaling, engine message passing, transposition table, +Zobrist hashing) and all move generation are implemented and tested. However, the +search threads themselves (`child_thread`, `root_thread`) currently perform +placeholder work (a busy-wait loop) and emit a hardcoded best move — the actual +mini-max/alpha-beta search and evaluation function are not yet implemented. The +UCI protocol layer is fully functional for position setup, options, and +`isready`/`stop`/`quit`/`go` commands. + +## Dependencies + +- **Build/runtime**: `gcc` (with ASan + pthreads), `python3` (for analysis). +- **DevShell**: Nix expression (`shell.nix`) pins gcc, python313, clang-tools, + and optionally Rust toolchain, Node.js/pnpm, and WebKitGTK (for the symbol + analyzer HTML visualization and the en-croissant GUI). +- **Reference engines**: `opt/stockfish/` bundles the Stockfish binary for + comparison; `opt/en-croissant/` is a React/Tauri chess GUI in `opt/`. + +## License + +[GPLv3](LICENSE) — "Gacrux by Aargh Rai <aarghrai.com>". |