summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAargh Rai <aargh.rai+git@gmail.com>2026-08-23 16:06:42 +0530
committerAargh Rai <aargh.rai+git@gmail.com>2026-08-23 16:06:42 +0530
commit99de764d1d1b936594643e34ae4d2c4a239f69db (patch)
treef45884164774e760e9ae37d3c37ccfe80dbbc836
parent54afeb6dd89fffae92274cb6fe2e9a86fd57c6e3 (diff)
phase C, D & E
-rw-r--r--PLAN.md14
-rw-r--r--include/engine/threads.h16
-rw-r--r--src/engine/thread.c489
-rw-r--r--src/engine/threads.c232
-rw-r--r--src/uci.c36
-rw-r--r--src/uci/response.c10
-rw-r--r--src/uci/state.c1
-rw-r--r--tests/generated.c33
8 files changed, 788 insertions, 43 deletions
diff --git a/PLAN.md b/PLAN.md
index 7bd8bf4..b58db03 100644
--- a/PLAN.md
+++ b/PLAN.md
@@ -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, &current, 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
diff --git a/src/uci.c b/src/uci.c
index 7b1ab8c..903528d 100644
--- a/src/uci.c
+++ b/src/uci.c
@@ -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",