# 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 ".