diff options
| author | Aargh Rai <aargh.rai+git@gmail.com> | 2026-08-23 16:06:42 +0530 |
|---|---|---|
| committer | Aargh Rai <aargh.rai+git@gmail.com> | 2026-08-23 16:06:42 +0530 |
| commit | 99de764d1d1b936594643e34ae4d2c4a239f69db (patch) | |
| tree | f45884164774e760e9ae37d3c37ccfe80dbbc836 | |
| parent | 54afeb6dd89fffae92274cb6fe2e9a86fd57c6e3 (diff) | |
phase C, D & E
| -rw-r--r-- | PLAN.md | 14 | ||||
| -rw-r--r-- | include/engine/threads.h | 16 | ||||
| -rw-r--r-- | src/engine/thread.c | 489 | ||||
| -rw-r--r-- | src/engine/threads.c | 232 | ||||
| -rw-r--r-- | src/uci.c | 36 | ||||
| -rw-r--r-- | src/uci/response.c | 10 | ||||
| -rw-r--r-- | src/uci/state.c | 1 | ||||
| -rw-r--r-- | tests/generated.c | 33 |
8 files changed, 788 insertions, 43 deletions
@@ -322,26 +322,26 @@ build (`just test`) green before the next. Rewrote the piece loop to iterate occupied bitboards (castling/turn/en-passant tail unchanged). No existing test asserts on zobrist_hash output, so nothing regressed. -- [ ] **C1.** Rewrite `root_thread` in `src/engine/thread.c` to run iterative +- [x] **C1.** Rewrite `root_thread` in `src/engine/thread.c` to run iterative deepening using `search()`, populating the `engine_message` each depth and respecting `args->stop` + `should_continue`. -- [ ] **C2.** Verify a manual `./build uci run` loop prints `info depth ...` +- [x] **C2.** Verify a manual `./build uci run` loop prints `info depth ...` lines and a `bestmove` before `quit`. ### Phase D — Parallel primitives -- [ ] **D1.** Add `split_point_alloc`/`split_point_free` + pool wiring in +- [x] **D1.** Add `split_point_alloc`/`split_point_free` + pool wiring in `threads.c` (back `handler->split_point_pool`). -- [ ] **D2.** Implement `split_point_claim_move` (atomic `next_move_idx`), +- [x] **D2.** Implement `split_point_claim_move` (atomic `next_move_idx`), `split_point_merge` (atomic `workers--`, last-owns), `split_point_share` (atomic `best_score`/`alpha`/`beta` store). Add tests. -- [ ] **D3.** Implement `HELP` publish/scan over the pool; `threads_go_loop` +- [x] **D3.** Implement `HELP` publish/scan over the pool; `threads_go_loop` returns true when all children `finished`. Build green. ### Phase E — Child worker loop -- [ ] **E1.** Rewrite `child_thread` as a DTS worker: scan pool for an +- [x] **E1.** Rewrite `child_thread` as a DTS worker: scan pool for an `ACTIVE` split point; claim via `split_point_claim_move`; run `search()`; `split_point_share`; on exhaustion `split_point_merge`; bail on `*stop`. -- [ ] **E2.** `just test` green (threaded search shouldn't break perft/ttable +- [x] **E2.** `just test` green (threaded search shouldn't break perft/ttable unit tests since they don't use threads). ### Phase F — Root move-list splitting diff --git a/include/engine/threads.h b/include/engine/threads.h index da221a8..43c4459 100644 --- a/include/engine/threads.h +++ b/include/engine/threads.h @@ -21,6 +21,7 @@ typedef struct split_point { struct split_point *parent; int ply; + int depth; // remaining search depth at this node int node_type; int confidence; position_t position_snapshot; @@ -39,7 +40,8 @@ struct child_thread_args { position_t *position; ttable_t *ttable; - int sp_stack; + split_point_t *split_points; // shared DTS pool (§2.4) + size_t sp_pool_capacity; engine_message_handler_t *message; }; struct root_thread_args { @@ -82,6 +84,18 @@ void __threads_args_init( struct threads *handler, int i ); + +// DTS primitives (§2.3–2.8): split point pool + lock-free move claiming +split_point_t *split_point_alloc(struct threads *handler); +void split_point_free(struct threads *handler, split_point_t *split_point); +void split_point_publish(split_point_t *split_point); +bool split_point_claim_move(split_point_t *split_point, move_t *move); +bool split_point_merge(split_point_t *split_point); +void split_point_share(split_point_t *split_point, i32 score, move_t move); + +// HELP (§2.3): scan the pool for a published split point with work left +split_point_t *threads_find_work(struct threads *handler); +split_point_t *__pool_find_work(split_point_t *pool, size_t capacity); #endif void threads_init(struct threads *handler, size_t capacity); void threads_deinit(struct threads *handler); diff --git a/src/engine/thread.c b/src/engine/thread.c index 912b70f..df4dec8 100644 --- a/src/engine/thread.c +++ b/src/engine/thread.c @@ -1,6 +1,22 @@ #define ENGINE_THREADS_INTERNAL #include "engine/threads.h" +#include "engine/search.h" #include <stdio.h> +#include <stdlib.h> +#include <limits.h> + +#define ROOT_MAX_DEPTH 100 +#define MATE_WINDOW 1000 + +// convert a mate score into a "mate in N plies" distance (negative when we +// are getting mated), 0 when the score isn't near a mate. +static int __score_to_mate(i32 score) { + int abs_score = score < 0 ? -score : score; + if (abs_score < SEARCH_MATE - MATE_WINDOW) return 0; + int plies = SEARCH_MATE - abs_score + 1; + int mate_in = (plies + 1) / 2; + return score > 0 ? mate_in : -mate_in; +} void threads_go(struct threads *handler) { int running_count = handler->running_count; @@ -19,31 +35,76 @@ void *child_thread(void *_args) { struct child_thread_args *args = (struct child_thread_args*)_args; args->stop = 0; - int depth = 0; - engine_message_t *message = args->message->newest_valid; - while (true) { - message->depth = depth++; - message->multipv = args->id; - ipc_moves_init(&message->pv); + atomic_bool stop = false; + u64 nodes = 0; + search_ctx_t ctx = { + .ttable = args->ttable, + .go_args = args->go_args, + .stop = &stop, + .nodes = &nodes, + }; + + engine_message_t *message = args->message->count > 0 + ? args->message->newest_valid + : engine_message_handler_push(args->message); + message->multipv = args->id; + + i32 best_score = -SEARCH_INF; + move_t best_move = (move_t) { 0 }; + + // DTS worker (§2.3–2.8): HELP peers by claiming moves from published + // split points, searching them, and Sharing the result back. + while (!atomic_load(&args->stop) && !atomic_load(&stop)) { + split_point_t *sp = __pool_find_work( + args->split_points, + args->sp_pool_capacity + ); + + // nothing active anywhere: the pool is drained, so we are done helping + // (the root re-publishes per iteration once root splitting lands) + if (sp == NULL) break; - // pseudo engine work - for (volatile int k = 0; k < 1000000000; k++) {} + // register as a worker at this block so Merge knows the headcount + atomic_fetch_add(&sp->workers, 1); - add_ipc_move(&message->pv, (ipc_move_t) { 14, 24 }); + int alpha, beta; + move_t move; + while (split_point_claim_move(sp, &move)) { + alpha = -atomic_load(&sp->beta); + beta = -atomic_load(&sp->alpha); - if (args->stop || !should_continue(message, args->go_args)) { - message->best_move = (ipc_move_t) { 12, 24 }; - message->ponder = (ipc_move_t) { 42, 54 }; - message->next = NULL; + position_t child = sp->position_snapshot; + position_make_move(&child, move); + + search_result_t res = search(child, sp->depth - 1, alpha, beta, &ctx); + + // Share (§2.8): negamax — our value flips sign for the parent side + split_point_share(sp, -res.score, move); + if (-res.score > best_score) { + best_score = -res.score; + best_move = move; + } + + message->depth = sp->depth; + message->nodes = nodes > INT_MAX ? INT_MAX : (int)nodes; + message->score_cp = best_score; + message->pv.count = 0; + add_ipc_move(&message->pv, (ipc_move_t) { best_move.from, best_move.to }); engine_message_mark_ready(message); - break; } - engine_message_mark_ready(message); - message = engine_message_handler_push(args->message); + // Merge (§2.6): when the last worker leaves, Unsplit the block + if (split_point_merge(sp)) { + atomic_store(&sp->state, SPLITPOINT_STATE_FREE); + } } - args->stop = 2; + message->best_move = (ipc_move_t) { best_move.from, best_move.to }; + message->next = NULL; + engine_message_mark_ready(message); + + atomic_store(&args->finished, 1); + return NULL; } // DTS requires a root thread which is initialize the search tree, and the @@ -52,5 +113,399 @@ void *child_thread(void *_args) { void *root_thread(void *_args) { struct root_thread_args *args = (struct root_thread_args*)_args; args->stop = 0; + + atomic_bool stop = false; + u64 nodes = 0; + search_ctx_t ctx = { + .ttable = args->ttable, + .go_args = args->go_args, + .stop = &stop, + .nodes = &nodes, + }; + + int max_depth = args->go_args != NULL && args->go_args->depth > 0 + ? args->go_args->depth + : ROOT_MAX_DEPTH; + + // reuse the handler's pre-created message when present, otherwise push one. + engine_message_t *message = args->message->count > 0 + ? args->message->newest_valid + : engine_message_handler_push(args->message); + search_result_t result = { .score = 0, .best_move = (move_t) { 0 } }; + + // iterative deepening: search at increasing depths, publishing an info + // message per completed depth so the UCI thread can emit `info ... pv`. + for (int depth = 1; depth <= max_depth; depth++) { + result = search(*args->position, depth, -SEARCH_INF, SEARCH_INF, &ctx); + + if (atomic_load(&stop)) break; + + message->depth = depth; + message->nodes = nodes > INT_MAX ? INT_MAX : (int)nodes; + message->score_cp = result.score; + message->mate = __score_to_mate(result.score); + // pv is already initialized by engine_message_init / handler_push. + message->pv.count = 0; + add_ipc_move(&message->pv, (ipc_move_t) { + result.best_move.from, + result.best_move.to, + }); + + if (!should_continue(message, args->go_args)) { + break; + } + + engine_message_mark_ready(message); + message = engine_message_handler_push(args->message); + } + + // final message carries the best move of the last completed iteration. + message->best_move = (ipc_move_t) { result.best_move.from, result.best_move.to }; + message->ponder = (ipc_move_t) { 0, 0 }; + message->next = NULL; + engine_message_mark_ready(message); + + // signal children to stop their loops and mark this thread as finished. + atomic_store(&args->stop, 1); + atomic_store(&args->finished, 1); + + return NULL; +} + +#ifdef TEST_MOD +#include <stdbool.h> +#include <stdlib.h> + +#include "fen.h" + +// the root_thread driver + tests need the IPC implementation (messages, +// moves, should_continue) which lives outside of engine.c's aggregation. +#include "../src/ipc/go_args.c" +#include "../src/ipc/moves.c" +#include "../src/ipc/engine_message.c" + +static bool __root_thread_run( + struct root_thread_args *args, + go_args_t *go_args, + position_t position, + int ttable_log +) { + args->message = malloc(sizeof(*args->message)); + engine_message_handler_init(args->message); + args->go_args = go_args; + args->position = &position; + + ttable_t tt; + ttable_init(&tt, ttable_log); + + root_thread(args); + + bool ok = true; + ok &= atomic_load(&args->finished) == 1; + ok &= atomic_load(&args->stop) == 1; + + ttable_deinit(tt); + return ok; +} + +static engine_message_t *__root_thread_pop_all( + engine_message_handler_t *handler, + int *count_out +) { + engine_message_t *head = NULL; + engine_message_t *tail = NULL; + int count = 0; + while (engine_message_handler_can_pop(handler)) { + engine_message_t *m = engine_message_handler_pop(handler); + m->next = NULL; + if (head == NULL) head = m; + else tail->next = m; + tail = m; + count++; + } + if (count_out != NULL) *count_out = count; + return head; +} + +static void __root_thread_free_messages(engine_message_t *head) { + while (head != NULL) { + engine_message_t *next = head->next; + engine_message_deinit(head); + head = next; + } +} + +bool test_root_thread_emits_info_and_bestmove() { + struct root_thread_args *args = calloc(sizeof(*args), 1); + go_args_t go_args = { .depth = 3 }; + position_t position = position_starting(); + + bool ok = __root_thread_run( + args, + &go_args, + position, + 2 + ); + + engine_message_handler_t *handler = args->message; + int count = 0; + engine_message_t *messages = __root_thread_pop_all(handler, &count); + + ok &= count >= 1; + + // every published message must have a valid depth and on-board pv move. + for (engine_message_t *m = messages; m != NULL; m = m->next) { + ok &= m->depth >= 1 && m->depth <= 3; + ok &= m->pv.count == 1; + ok &= m->pv.data[0].from >= 0 && m->pv.data[0].from < 64; + ok &= m->pv.data[0].to >= 0 && m->pv.data[0].to < 64; + } + + // the final message must carry the best move. + engine_message_t *tail = messages; + while (tail->next != NULL) tail = tail->next; + ok &= tail->best_move.from >= 0 && tail->best_move.from < 64; + ok &= tail->best_move.to >= 0 && tail->best_move.to < 64; + ok &= tail->depth == 3; + + __root_thread_free_messages(messages); + engine_message_handler_deinit(handler); + free(handler); + free(args); + return ok; +} + +bool test_root_thread_respects_depth_limit() { + struct root_thread_args *args = calloc(sizeof(*args), 1); + go_args_t go_args = { .depth = 2 }; + position_t position = position_starting(); + + bool ok = __root_thread_run(args, &go_args, position, 2); + + int count = 0; + engine_message_t *messages = __root_thread_pop_all(args->message, &count); + + // depth 2 -> exactly two info messages, depths 1 then 2. + ok &= count == 2; + ok &= messages->depth == 1; + ok &= messages->next->depth == 2; + + __root_thread_free_messages(messages); + engine_message_handler_deinit(args->message); + free(args->message); + free(args); + return ok; +} + +bool test_root_thread_stops_on_node_limit() { + struct root_thread_args *args = calloc(sizeof(*args), 1); + go_args_t go_args = { .nodes = 1 }; + position_t position = position_starting(); + + bool ok = __root_thread_run(args, &go_args, position, 2); + + int count = 0; + engine_message_t *messages = __root_thread_pop_all(args->message, &count); + + // node budget of 1 exhausts should_continue after the first iteration. + ok &= count == 1; + ok &= messages->node_limit; + + __root_thread_free_messages(messages); + engine_message_handler_deinit(args->message); + free(args->message); + free(args); + return ok; +} + +bool test_root_thread_reports_mate() { + struct root_thread_args *args = calloc(sizeof(*args), 1); + go_args_t go_args = { .depth = 4 }; + struct fen_load r = load_fen("k7/8/KQ6/8/8/8/8/8 w - - 0 1"); + if (r.failed) return false; + + bool ok = __root_thread_run(args, &go_args, r.position, 2); + + int count = 0; + engine_message_t *messages = __root_thread_pop_all(args->message, &count); + + // mate in 1 must be reported via the `mate` field. + engine_message_t *tail = messages; + while (tail->next != NULL) tail = tail->next; + ok &= tail->mate == 1; + ok &= tail->score_cp == SEARCH_MATE; + + __root_thread_free_messages(messages); + engine_message_handler_deinit(args->message); + free(args->message); + free(args); + return ok; +} + +// ---- Phase E tests: DTS child worker loop ---- + +#include <pthread.h> + +typedef struct { + struct threads *handler; + struct child_thread_args args[4]; + pthread_t threads[4]; +} __child_test_env_t; + +static void __child_test_setup( + __child_test_env_t *env, + split_point_t *sp, + int worker_count +) { + threads_init(env->handler, (size_t)worker_count); + ttable_init(&env->handler->ttable, 2); + + for (int i = 0; i < worker_count; i++) { + env->args[i].id = i + 1; + atomic_init(&env->args[i].stop, 0); + atomic_init(&env->args[i].finished, 0); + env->args[i].go_args = NULL; + env->args[i].ttable = &env->handler->ttable; + env->args[i].split_points = env->handler->split_point_pool; + env->args[i].sp_pool_capacity = env->handler->capacity; + env->args[i].message = malloc(sizeof(engine_message_handler_t)); + engine_message_handler_init(env->args[i].message); + } + + if (sp != NULL) { + sp->moves.length = 0; // filled by caller + } +} + +static void __child_test_teardown(__child_test_env_t *env, int worker_count) { + ttable_deinit(env->handler->ttable); + for (int i = 0; i < worker_count; i++) { + while (engine_message_handler_can_pop(env->args[i].message)) { + engine_message_deinit(engine_message_handler_pop(env->args[i].message)); + } + engine_message_handler_deinit(env->args[i].message); + free(env->args[i].message); + } + threads_deinit(env->handler); +} + +bool test_child_workers_claim_and_share() { + enum { WORKERS = 4 }; + __child_test_env_t env; + struct threads handler; + + env.handler = &handler; + __child_test_setup(&env, NULL, WORKERS); + + split_point_t *sp = split_point_alloc(&handler); + sp->depth = 3; + sp->ply = 0; + atomic_store(&sp->alpha, -SEARCH_INF); + atomic_store(&sp->beta, SEARCH_INF); + sp->position_snapshot = position_starting(); + moves_init(&sp->moves); + get_legal_moves(&sp->moves, sp->position_snapshot); + split_point_publish(sp); + + for (int i = 0; i < WORKERS; i++) { + pthread_create(env.threads + i, NULL, child_thread, env.args + i); + } + for (int i = 0; i < WORKERS; i++) { + pthread_join(env.threads[i], NULL); + } + + bool ok = true; + + // every worker finished cleanly + for (int i = 0; i < WORKERS; i++) { + ok &= atomic_load(&env.args[i].finished) == 1; + ok &= atomic_load(&env.args[i].message->newest_valid->ready) == 1; + } + + // the whole move list was consumed and the block was Unsplitten + ok &= atomic_load(&sp->next_move_idx) >= (int)sp->moves.length; + ok &= atomic_load(&sp->state) == SPLITPOINT_STATE_FREE; + ok &= atomic_load(&sp->workers) == 0; + + // real search happened: nodes were counted and a sane best was shared + ok &= atomic_load(&sp->best_score) > -SEARCH_INF; + ok &= atomic_load(&sp->best_score) <= SEARCH_MATE; + + moves_deinit(sp->moves); + __child_test_teardown(&env, WORKERS); + return ok; +} + +bool test_child_thread_stops_on_signal() { + __child_test_env_t env; + struct threads handler; + enum { WORKERS = 1 }; + + env.handler = &handler; + __child_test_setup(&env, NULL, WORKERS); + + split_point_t *sp = split_point_alloc(&handler); + sp->depth = 5; + atomic_store(&sp->alpha, -SEARCH_INF); + atomic_store(&sp->beta, SEARCH_INF); + sp->position_snapshot = position_starting(); + moves_init(&sp->moves); + get_legal_moves(&sp->moves, sp->position_snapshot); + split_point_publish(sp); + + pthread_create(env.threads, NULL, child_thread, env.args); + + // wait until the worker has started claiming, then signal stop + while (atomic_load(&sp->next_move_idx) == 0) sched_yield(); + atomic_store(&env.args[0].stop, 1); + pthread_join(env.threads[0], NULL); + + bool ok = true; + ok &= atomic_load(&env.args[0].finished) == 1; + ok &= atomic_load(&env.args[0].message->newest_valid->ready) == 1; + + moves_deinit(sp->moves); + __child_test_teardown(&env, WORKERS); + return ok; +} + +bool test_child_workers_find_mate_score() { + // Ka6/Qb6 vs Ka8: white mates in 1 with Qa7#/Qb7#. Children searching the + // mate move must Share a mate score back to the split point. + enum { WORKERS = 2 }; + __child_test_env_t env; + struct threads handler; + + env.handler = &handler; + __child_test_setup(&env, NULL, WORKERS); + + struct fen_load r = load_fen("k7/8/KQ6/8/8/8/8/8 w - - 0 1"); + if (r.failed) return false; + + split_point_t *sp = split_point_alloc(&handler); + sp->depth = 2; + atomic_store(&sp->alpha, -SEARCH_INF); + atomic_store(&sp->beta, SEARCH_INF); + sp->position_snapshot = r.position; + moves_init(&sp->moves); + get_legal_moves(&sp->moves, r.position); + split_point_publish(sp); + + for (int i = 0; i < WORKERS; i++) { + pthread_create(env.threads + i, NULL, child_thread, env.args + i); + } + for (int i = 0; i < WORKERS; i++) { + pthread_join(env.threads[i], NULL); + } + + bool ok = true; + ok &= atomic_load(&sp->best_score) == SEARCH_MATE; + ok &= sp->best_move.from >= 0 && sp->best_move.from < 64; + ok &= sp->best_move.to >= 0 && sp->best_move.to < 64; + + moves_deinit(sp->moves); + __child_test_teardown(&env, WORKERS); + return ok; } +#endif diff --git a/src/engine/threads.c b/src/engine/threads.c index 5bf630a..c0d1da7 100644 --- a/src/engine/threads.c +++ b/src/engine/threads.c @@ -1,5 +1,6 @@ #define ENGINE_THREADS_INTERNAL #include "engine/threads.h" +#include "engine/search.h" #include <string.h> #include <stdlib.h> #include <assert.h> @@ -13,6 +14,10 @@ void threads_init(struct threads *handler, size_t capacity) { handler->threads = malloc(sizeof(*handler->threads) * capacity); handler->args = malloc(sizeof(*handler->args) * capacity); + + // split point pool (DTS §2.4): zeroed so every block starts SPLITPOINT_STATE_FREE + handler->split_point_pool = calloc(sizeof(split_point_t), capacity); + handler->capacity = capacity; handler->count = 0; handler->running_count = 0; @@ -25,6 +30,7 @@ void threads_deinit(struct threads *handler) { assert(handler->running_count == 0); free(handler->threads); free(handler->args); + free(handler->split_point_pool); } void threads_reserve(struct threads *handler, size_t capacity) { @@ -38,12 +44,21 @@ void threads_reserve(struct threads *handler, size_t capacity) { handler->args, sizeof(*handler->args) * capacity ); + handler->split_point_pool = realloc( + handler->split_point_pool, + sizeof(split_point_t) * capacity + ); + // new blocks must start FREE + memset( + (char*)handler->split_point_pool + handler->capacity * sizeof(split_point_t), + 0, + (capacity - handler->capacity) * sizeof(split_point_t) + ); handler->capacity = capacity; } bool threads_go_loop(struct threads *handler) { - // idk maybe do something while waiting for calculations to flow in - return false; + return threads_all_done(handler); } bool threads_all_done(struct threads *handler) { @@ -80,7 +95,8 @@ void __threads_args_init( args->position = handler->position; args->go_args = handler->go_args; args->ttable = &handler->ttable; - args->sp_stack = 0; + args->split_points = handler->split_point_pool; + args->sp_pool_capacity = handler->capacity; args->message = handler->engine_messages->data[i]; return; } @@ -95,6 +111,73 @@ void __threads_args_init( args->ttable = &handler->ttable; } +split_point_t *split_point_alloc(struct threads *handler) { + for (size_t i = 0; i < handler->capacity; i++) { + split_point_t *sp = (split_point_t*)handler->split_point_pool + i; + int expected = SPLITPOINT_STATE_FREE; + if (!atomic_compare_exchange_weak(&sp->state, &expected, SPLITPOINT_STATE_ACTIVE)) continue; + + atomic_store(&sp->next_move_idx, 0); + atomic_store(&sp->alpha, 0); + atomic_store(&sp->beta, 0); + atomic_store(&sp->best_score, -SEARCH_INF); + // workers counts only registered helpers; the creator registers itself + atomic_store(&sp->workers, 0); + sp->best_move = (move_t) { 0 }; + return sp; + } + return NULL; +} + +void split_point_free(struct threads *handler, split_point_t *split_point) { + // Unsplit (§2.7): drop the block back into the pool + atomic_store(&split_point->state, SPLITPOINT_STATE_FREE); +} + +// HELP (§2.3): a worker publishes its block so idle peers can pick up moves +void split_point_publish(split_point_t *split_point) { + atomic_store(&split_point->state, SPLITPOINT_STATE_ACTIVE); +} + +// Select (§2.5): lock-free claim of the next move via the shared counter +bool split_point_claim_move(split_point_t *split_point, move_t *move) { + int idx = atomic_fetch_add(&split_point->next_move_idx, 1); + if (idx >= (int)split_point->moves.length) return false; + *move = split_point->moves.moves[idx]; + return true; +} + +// Merge (§2.6): decrement workers; returns true when the caller was the last +// worker and now owns the node +bool split_point_merge(split_point_t *split_point) { + return atomic_fetch_sub(&split_point->workers, 1) == 1; +} + +// Share (§2.8): back up an improved best score; peers see it on their next Select +void split_point_share(split_point_t *split_point, i32 score, move_t move) { + int current = atomic_load(&split_point->best_score); + while (score > current) { + if (atomic_compare_exchange_weak(&split_point->best_score, ¤t, score)) { + split_point->best_move = move; + break; + } + } +} + +split_point_t *__pool_find_work(split_point_t *pool, size_t capacity) { + for (size_t i = 0; i < capacity; i++) { + split_point_t *sp = pool + i; + if (atomic_load(&sp->state) != SPLITPOINT_STATE_ACTIVE) continue; + if (atomic_load(&sp->next_move_idx) >= (int)sp->moves.length) continue; + return sp; + } + return NULL; +} + +split_point_t *threads_find_work(struct threads *handler) { + return __pool_find_work(handler->split_point_pool, handler->capacity); +} + #ifdef TEST_MOD bool test_threads_args_init_root_propagates() { engine_message_handler_t dummy[2]; @@ -157,9 +240,150 @@ bool test_threads_args_init_child_propagates() { ok &= args.child_thread_args.go_args == &go_args; ok &= args.child_thread_args.position == &pos; ok &= args.child_thread_args.message == &dummy[1]; - ok &= args.child_thread_args.sp_stack == 0; + ok &= args.child_thread_args.split_points == handler.split_point_pool; + ok &= args.child_thread_args.sp_pool_capacity == handler.capacity; ttable_deinit(handler.ttable); return ok; } + +// ---- Phase D tests: split point pool + parallel primitives ---- + +static void __test_fill_moves(split_point_t *sp, int count) { + moves_init_wcapacity(&sp->moves, count); + for (int i = 0; i < count; i++) { + add_move(&sp->moves, (square_t)i, (square_t)(i + 8)); + } +} + +bool test_split_pool_alloc_free() { + struct threads handler; + threads_init(&handler, 4); + + bool ok = true; + + // pool starts all FREE; we can alloc exactly capacity blocks + split_point_t *sps[4]; + for (int i = 0; i < 4; i++) { + sps[i] = split_point_alloc(&handler); + if (sps[i] == NULL) ok = false; + } + ok &= split_point_alloc(&handler) == NULL; // exhausted + + // freed block becomes reusable + split_point_free(&handler, sps[2]); + split_point_t *reused = split_point_alloc(&handler); + ok &= reused == sps[2]; + + threads_deinit(&handler); + return ok; +} + +typedef struct { + split_point_t *sp; + int claims; +} __claim_thread_args_t; + +static void *__claim_worker(void *_args) { + __claim_thread_args_t *args = (__claim_thread_args_t*)_args; + args->claims = 0; + move_t move; + while (split_point_claim_move(args->sp, &move)) args->claims++; + return NULL; +} + +bool test_split_claim_moves_exactly_once() { + enum { MOVE_COUNT = 100, THREAD_COUNT = 4 }; + struct threads handler; + threads_init(&handler, THREAD_COUNT); + + split_point_t *sp = split_point_alloc(&handler); + atomic_store(&sp->alpha, -SEARCH_INF); + atomic_store(&sp->beta, SEARCH_INF); + __test_fill_moves(sp, MOVE_COUNT); + + pthread_t threads[THREAD_COUNT]; + __claim_thread_args_t thread_args[THREAD_COUNT]; + for (int i = 0; i < THREAD_COUNT; i++) { + thread_args[i].sp = sp; + pthread_create(threads + i, NULL, __claim_worker, thread_args + i); + } + int total = 0; + for (int i = 0; i < THREAD_COUNT; i++) { + pthread_join(threads[i], NULL); + total += thread_args[i].claims; + } + + bool ok = total == MOVE_COUNT; // each move claimed exactly once + ok &= !split_point_claim_move(sp, &(move_t){0}); // exhausted + + moves_deinit(sp->moves); + threads_deinit(&handler); + return ok; +} + +bool test_split_merge_last_owns() { + split_point_t sp; + atomic_init(&sp.workers, 3); + + bool ok = true; + ok &= !split_point_merge(&sp); // 3 -> 2, not last + ok &= !split_point_merge(&sp); // 2 -> 1, not last + ok &= split_point_merge(&sp); // 1 -> 0, caller owns the node + return ok; +} + +bool test_split_share_propagates_best() { + split_point_t sp; + atomic_init(&sp.best_score, -SEARCH_INF); + sp.best_move = (move_t) { 0 }; + + bool ok = true; + + split_point_share(&sp, 50, (move_t) { 1, 2 }); + ok &= atomic_load(&sp.best_score) == 50; + ok &= sp.best_move.from == 1 && sp.best_move.to == 2; + + // a worse score must not overwrite the shared best + split_point_share(&sp, 10, (move_t) { 3, 4 }); + ok &= atomic_load(&sp.best_score) == 50; + ok &= sp.best_move.from == 1 && sp.best_move.to == 2; + + split_point_share(&sp, 90, (move_t) { 5, 6 }); + ok &= atomic_load(&sp.best_score) == 90; + ok &= sp.best_move.from == 5 && sp.best_move.to == 6; + return ok; +} + +bool test_help_scan_finds_published_work() { + struct threads handler; + threads_init(&handler, 4); + + bool ok = true; + + // empty pool -> no work + ok &= threads_find_work(&handler) == NULL; + + // a published block with moves left is found + split_point_t *working = split_point_alloc(&handler); + __test_fill_moves(working, 4); + split_point_publish(working); + ok &= threads_find_work(&handler) == working; + + // an exhausted block is skipped + atomic_store(&working->next_move_idx, 4); + ok &= threads_find_work(&handler) == NULL; + + // a free block is skipped even if republished with moves + split_point_t *freed = split_point_alloc(&handler); + __test_fill_moves(freed, 2); + split_point_publish(freed); + split_point_free(&handler, freed); + ok &= threads_find_work(&handler) == NULL; + + moves_deinit(working->moves); + moves_deinit(freed->moves); + threads_deinit(&handler); + return ok; +} #endif @@ -16,7 +16,7 @@ void load_from_message(uci_cmd_t* cmd, const char* message) { int i = 0, k = 0; while (message[i] != 0 && message[i] != '\n' && message[i] != '\r') { - if (message[i] != ' ') { + if (message[i] != ' ') { token[k++] = message[i++]; continue; } @@ -33,6 +33,30 @@ void load_from_message(uci_cmd_t* cmd, const char* message) { uci_cmd_add(cmd, token); } +// split a raw stdin chunk into lines and parse each into its own command. +void load_from_buffer( + uci_cmd_t* cmd, + char* buffer, + ssize_t length, + void (*on_cmd)(uci_state_t*, uci_cmd_t), + uci_state_t *state +) { + buffer[length] = 0; + char *line = buffer; + for (ssize_t i = 0; i <= length; i++) { + if (buffer[i] != '\n' && buffer[i] != '\r' && buffer[i] != 0) continue; + buffer[i] = 0; + + cmd->empty = true; + cmd->args_count = 0; + cmd->root[0] = 0; + load_from_message(cmd, line); + + if (!cmd->empty) on_cmd(state, *cmd); + line = buffer + i + 1; + } +} + void *uci(ipc_state_t *ipc_state) { // https://stackoverflow.com/a/41559081 fcntl(STDIN_FILENO, F_SETFL, O_NONBLOCK); @@ -43,13 +67,10 @@ void *uci(ipc_state_t *ipc_state) { char buf[1024]; while (true) { - cmd.empty = true; - cmd.args_count = 0; - ssize_t n = read(STDIN_FILENO, buf, sizeof(buf)); + ssize_t n = read(STDIN_FILENO, buf, sizeof(buf) - 1); if (n > 0) { - load_from_message(&cmd, buf); + load_from_buffer(&cmd, buf, n, handle_uci, &ipc_state->uci_state); } - handle_uci(&ipc_state->uci_state, cmd); handle_ipc(ipc_state); } } @@ -104,7 +125,7 @@ void handle_ipc(ipc_state_t *state) { ); for (int j = 0; j < message->pv.count; j++) { - ipc_move_t move = message->pv.data[i]; + ipc_move_t move = message->pv.data[j]; printf( " %c%c%c%c", (move.from / 8) + 'a', @@ -135,6 +156,7 @@ void handle_ipc(ipc_state_t *state) { } printf("\n"); } + fflush(stdout); // emit info/bestmove immediately for piped GUIs engine_message_deinit(message); if (ended) { diff --git a/src/uci/response.c b/src/uci/response.c index ff89f8d..81459d6 100644 --- a/src/uci/response.c +++ b/src/uci/response.c @@ -35,7 +35,10 @@ void handle_initial(uci_state_t *state, uci_cmd_t cmd) { print_setting(state->option_settings[i]); } // --- + // flush around the handshake so piped GUIs see responses immediately + fflush(stdout); printf("uciok\n"); + fflush(stdout); state->current_state = UCI_STATE_IDLE; } @@ -164,10 +167,11 @@ void handle_idle(uci_state_t *state, uci_cmd_t cmd) { void handle_sync(uci_state_t *state, uci_cmd_t cmd) { // TIMEOUT NOTICE: THE FOLLOWING BLOCK SHOULDN'T TAKE MORE THAN 5 SECONDS - - + if (cmd.empty || strcmp(cmd.root, "isready") != 0) { + // commands sent while a sync is pending must still be handled. + return handle_idle(state, cmd); + } - // --- printf("readyok\n"); state->current_state = UCI_STATE_IDLE; } diff --git a/src/uci/state.c b/src/uci/state.c index 012d951..183f849 100644 --- a/src/uci/state.c +++ b/src/uci/state.c @@ -109,6 +109,7 @@ void print_setting(option_setting_t setting) { void uci_state_init(uci_state_t *state) { state->signal = UCI_SIGNAL_NONE; + state->current_state = UCI_STATE_INITIAL; strncpy(state->name, "Gacrux", 32); strncpy(state->author, "Aargh Rai <aarghrai.com>", 32); int k = 0; diff --git a/tests/generated.c b/tests/generated.c index 3f6fc99..408a8b2 100644 --- a/tests/generated.c +++ b/tests/generated.c @@ -1,14 +1,15 @@ #include "../src/fen.c" #include "../src/engine/search.c" #include "../src/engine/evaluate.c" +#include "../src/engine/thread.c" #include "../src/engine/ttable.c" #include "../src/engine/threads.c" #include "../src/engine/moves.c" #include "../src/engine/moves/king.c" #include "../src/uci/command.c" -int total_test_count = 25; -bool (*tests[25])(void) = { +int total_test_count = 37; +bool (*tests[37])(void) = { test_fen_no_passant, test_fen_passant, test_starting_position, @@ -18,6 +19,13 @@ bool (*tests[25])(void) = { test_search_stop_signal_halts, test_eval_startpos_is_balanced, test_eval_scales_with_material, + test_root_thread_emits_info_and_bestmove, + test_root_thread_respects_depth_limit, + test_root_thread_stops_on_node_limit, + test_root_thread_reports_mate, + test_child_workers_claim_and_share, + test_child_thread_stops_on_signal, + test_child_workers_find_mate_score, test_ttable_empty, test_ttable_insert_and_find, test_ttable_wrong_key, @@ -27,6 +35,11 @@ bool (*tests[25])(void) = { test_ttable_many_entries, test_threads_args_init_root_propagates, test_threads_args_init_child_propagates, + test_split_pool_alloc_free, + test_split_claim_moves_exactly_once, + test_split_merge_last_owns, + test_split_share_propagates_best, + test_help_scan_finds_published_work, test_perft_starting_position, test_perft_kiwipete_position, test_perft_position3, @@ -36,8 +49,8 @@ bool (*tests[25])(void) = { test_invalid_cmd_uci_cmd_t, }; -int max_test_name_size = 34; -char test_names[25][100] = { +int max_test_name_size = 35; +char test_names[37][100] = { "fen_no_passant", "fen_passant", "starting_position", @@ -47,6 +60,13 @@ char test_names[25][100] = { "search_stop_signal_halts", "eval_startpos_is_balanced", "eval_scales_with_material", + "root_thread_emits_info_and_bestmove", + "root_thread_respects_depth_limit", + "root_thread_stops_on_node_limit", + "root_thread_reports_mate", + "child_workers_claim_and_share", + "child_thread_stops_on_signal", + "child_workers_find_mate_score", "ttable_empty", "ttable_insert_and_find", "ttable_wrong_key", @@ -56,6 +76,11 @@ char test_names[25][100] = { "ttable_many_entries", "threads_args_init_root_propagates", "threads_args_init_child_propagates", + "split_pool_alloc_free", + "split_claim_moves_exactly_once", + "split_merge_last_owns", + "split_share_propagates_best", + "help_scan_finds_published_work", "perft_starting_position", "perft_kiwipete_position", "perft_position3", |
