# 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 │ │ ├── search.h # Alpha-beta search, qsearch, PV reconstruction │ │ ├── evaluate.h # Static evaluation (material + PST) │ │ ├── threads.h # Multi-threaded DTS 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) │ ├── search.c # Alpha-beta search, qsearch, PV reconstruction, tests │ ├── evaluate.c # Static evaluation (material + PST), tests │ ├── threads.c # pthread creation/cleanup, split-point pool, DTS helpers │ ├── thread.c # child_thread() & root_thread() entry points, tests │ ├── 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/ │ ├── bitboards.html # Bitboard visualization / reference │ ├── search.html # DTS paper by Hyatt et al. (Cray Blitz) │ └── uci/ │ ├── uci_min.txt # Minimal UCI spec reference │ ├── UCI-Protocol-Specification.txt # Full UCI protocol spec │ ├── draft-1.pdf # UCI protocol draft │ └── draft-2.pdf # UCI protocol draft ├── 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`). The root does iterative deepening with alpha-beta search, publishing info messages per depth. Children scan the split-point pool for published work, claim moves, search them, and share results back. - **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. - **Cooperative stop**: Engine threads check an atomic `stop` flag at each iteration (root) or worker loop cycle (children). `threads_stop_all()` sets the flag on all threads; `threads_join()` waits for them to exit; `threads_cleanup()` reinitializes state. The UCI thread (which blocks on stdin) is the only thread that uses `pthread_cancel`. ### 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). ### Search - **Alpha-beta search** (`src/engine/search.c`): Negamax with alpha-beta pruning, TT probing for move ordering and cutoffs, aspiration windows at depth > 4. - **Quiescence search** (`src/engine/search.c`): Stand-pat with delta pruning (margin of 200 cp), searches captures and promotions only at depth 0. - **PV reconstruction** (`src/engine/search.c:reconstruct_pv`): Follows TT best-move entries to rebuild the principal variation after each iteration. ### Evaluation - **Material + PST** (`src/engine/evaluate.c`): Simple material counting (pawn=100, knight/bishop=320, rook=500, queen=900) plus piece-square table bonuses for pawn advancement and knight centralization. Returns a score from the side-to-move's perspective. ### 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. Test families: - `test_fen_*` (3) — FEN parsing - `test_perft_*` (3) — move generation correctness against known node counts - `test_white_king_corners`, `test_black_king_corners` — king/castling moves - `test_uci_cmd_t`, `test_invalid_cmd_uci_cmd_t` — UCI command parsing - `test_ttable_*` (7) — transposition table insert/find/replacement - `test_search_*` (4) — alpha-beta search, mate detection, depth limit, stop - `test_qsearch_finds_capture` — quiescence search captures - `test_pv_reconstruction` — TT-based PV rebuild - `test_eval_*` (2) — evaluation balance and material scaling - `test_root_thread_*` (4) — root iterative deepening, depth/node limits, mate - `test_child_*` (3) — DTS worker claim/share/stop - `test_root_split_*`, `test_root_with_workers_*` (2) — root split with workers - `test_threads_*` (2) — thread args initialization - `test_split_*` (4) — split-point pool, claim, merge, share - `test_help_scan_*` — DTS HELP protocol - `test_thrashing_counter_*` — thrashing guard - `test_cooperative_stop_*` — cooperative shutdown - **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 has a **working threaded search** with iterative deepening, alpha-beta pruning, quiescence search, and a Distributed Tree Search (DTS) multi-threading model. The root thread drives iterative deepening and publishes split points; child workers claim moves, search them, and share results back. The UCI protocol layer is functional for position setup, options, `isready`/`stop`/`quit`/`go` commands, and emits `info depth N ... pv` messages with reconstructed principal variations. The evaluation function is a simple material + PST baseline. **Implemented**: move generation (magic bitboards), alpha-beta search, quiescence search, PV reconstruction, transposition table, Zobrist hashing, DTS split points (with thrashing guard), cooperative stop, UCI protocol, and 44 tests across all modules. **Remaining**: end-to-end UCI integration testing (`./build uci run` with a GUI), deeper evaluation (tapered eval, king safety, passed pawns), time management, node-type aware split-point selection (DTS §3.x). ## 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 ".