diff options
Diffstat (limited to 'PROJECT.md')
| -rw-r--r-- | PROJECT.md | 86 |
1 files changed, 71 insertions, 15 deletions
@@ -23,7 +23,9 @@ gacrux/ │ ├── 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 +│ │ ├── 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 @@ -57,8 +59,10 @@ gacrux/ │ │ └── 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 +│ ├── 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 @@ -82,9 +86,13 @@ gacrux/ │ ├── 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 +│ ├── 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 @@ -133,7 +141,9 @@ The engine uses a **multi-threaded, event-driven** architecture: 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`). + (`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 @@ -146,6 +156,12 @@ The engine uses a **multi-threaded, event-driven** architecture: 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) @@ -173,6 +189,22 @@ stored in a `position_t` struct. Squares are indexed 0–63 (0 = a1, 7 = h1, 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`): @@ -185,8 +217,24 @@ stored in a `position_t` struct. Squares are indexed 0–63 (0 = a1, 7 = h1, ### 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_*` 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. @@ -219,14 +267,22 @@ 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. +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 |