ref: e68590c590e898ce6b03bc4328aee4e99537b418
parent: ca74d3cb47485ed6b052a7b0ef57b845eb8326cf
author: zamfofex <zamfofex@twdb.moe>
date: Fri Nov 22 02:42:19 EST 2024
add threading support
--- a/README.md
+++ b/README.md
@@ -9,7 +9,7 @@
[](https://lichess.org/@/munfish/perf/rapid)
[](https://lichess.org/@/munfish/perf/blitz)
-**moonfish** is a simple chess bot written in C89.
+**moonfish** is a simple chess bot written in C89 (using just a few POSIX and C11 APIs).
You may [play moonfish on Lichess]! You don’t need a Lichess account, just make sure to choose “real time” and select a fast enough time control.
@@ -81,9 +81,21 @@
Conversely, you may also invoke your compiler by hand. (Feel free to replace `cc` with your compiler of choice.)
~~~
-cc -ansi -O3 -D_POSIX_C_SOURCE=199309L -o moonfish chess.c search.c main.c -lm
+cc -O3 -o moonfish chess.c search.c main.c -lm -pthread
~~~
+By default, moonfish uses C11 `<threads.h>`, but it is possible to have it use POSIX `<pthread.h>` instead by passing `-Dmoonfish_pthreads` to the compiler. (This is necessary if you’re on Mac OS.)
+
+~~~
+cc -O3 -Dmoonfish_pthreads -o moonfish chess.c search.c main.c -lm -pthread
+~~~
+
+It is also possible to compile moonfish without a dependency on threads by passing `-Dmoonfish_no_threads` to the compiler.
+
+~~~
+cc -O3 -Dmoonfish_no_threads -o moonfish chess.c search.c main.c -lm
+~~~
+
using “analyse”
---
@@ -158,7 +170,7 @@
~~~
# (example for x86-64)
-6c -I/sys/include/npe chess.c search.c main.c
+6c -I/sys/include/npe -Dmoonfish_pthreads chess.c search.c main.c
6l -o moonfish chess.6 search.6 main.6
moonfish
~~~
--- a/main.c
+++ b/main.c
@@ -5,10 +5,11 @@
#include <errno.h>
#include <string.h>
#include <stdio.h>
+#include <strings.h>
#include "moonfish.h"
-static void moonfish_go(struct moonfish_node *node)
+static void moonfish_go(struct moonfish_node *node, int thread_count)
{static struct moonfish_result result;
static struct moonfish_options options;
@@ -77,6 +78,7 @@
options.max_time = time;
options.our_time = our_time;
+ options.thread_count = thread_count;
moonfish_best_move(node, &result, &options);
moonfish_to_uci(&chess, &result.move, name);
@@ -149,9 +151,49 @@
if (!moonfish_equal(&chess0, &chess)) moonfish_reroot(node, &chess);
}
+static void moonfish_setoption(int *thread_count)
+{+ char *arg, *end;
+ long int count;
+
+ arg = strtok(NULL, "\r\n\t ");
+ if (arg == NULL || strcmp(arg, "name")) {+ fprintf(stderr, "malformed 'setoption' command\n");
+ exit(1);
+ }
+
+ arg = strtok(NULL, "\r\n\t ");
+ if (arg == NULL || strcasecmp(arg, "Threads")) {+ fprintf(stderr, "unknown option '%s'\n", arg);
+ exit(1);
+ }
+
+ arg = strtok(NULL, "\r\n\t ");
+ if (arg == NULL || strcmp(arg, "value")) {+ fprintf(stderr, "malformed 'setoption' command\n");
+ exit(1);
+ }
+
+ arg = strtok(NULL, "\r\n\t ");
+ if (arg == NULL) {+ fprintf(stderr, "missing value\n");
+ exit(1);
+ }
+
+ errno = 0;
+ count = strtol(arg, &end, 10);
+ if (errno || *end != 0 || count < 1 || count > 256) {+ fprintf(stderr, "malformed thread count\n");
+ exit(1);
+ }
+
+ *thread_count = count;
+}
+
int main(int argc, char **argv)
{static char line[2048];
+ int thread_count;
char *arg;
struct moonfish_node *node;
@@ -162,6 +204,7 @@
}
node = moonfish_new();
+ thread_count = 1;
for (;;) {@@ -177,7 +220,7 @@
if (arg == NULL) continue;
if (!strcmp(arg, "go")) {- moonfish_go(node);
+ moonfish_go(node, thread_count);
continue;
}
@@ -191,6 +234,9 @@
if (!strcmp(arg, "uci")) { printf("id name moonfish\n"); printf("id author zamfofex\n");+#ifndef moonfish_no_threads
+ printf("option name Threads type spin default 1 min 1 max 256\n");+#endif
printf("uciok\n");continue;
}
@@ -200,7 +246,14 @@
continue;
}
- if (!strcmp(arg, "debug") || !strcmp(arg, "setoption") || !strcmp(arg, "ucinewgame") || !strcmp(arg, "stop")) continue;
+#ifndef moonfish_no_threads
+ if (!strcmp(arg, "setoption")) {+ moonfish_setoption(&thread_count);
+ continue;
+ }
+#endif
+
+ if (!strcmp(arg, "debug") || !strcmp(arg, "ucinewgame") || !strcmp(arg, "stop")) continue;
fprintf(stderr, "warning: unknown command '%s'\n", arg);
}
--- a/makefile
+++ b/makefile
@@ -1,7 +1,7 @@
# moonfish is licensed under the AGPL (v3 or later)
# copyright 2023, 2024 zamfofex
-CFLAGS ?= -ansi -O3 -Wall -Wextra -Wpedantic
+CFLAGS ?= -O3 -Wall -Wextra -Wpedantic
PREFIX ?= /usr/local
BINDIR ?= $(PREFIX)/bin
RM ?= rm -f
@@ -13,10 +13,10 @@
all: moonfish lichess analyse chat
moonfish: moonfish.h chess.c search.c main.c
- $(cc) $(filter %.c,$^) -D_POSIX_C_SOURCE=199309L -o $@ -lm
+ $(cc) $(filter %.c,$^) -o $@ -lm -pthread -latomic
%: moonfish.h tools/tools.h tools/utils.c chess.c tools/%.c
- $(cc) $(filter %.c,$^) -D_POSIX_C_SOURCE=200809L -o $@ $(cflags)
+ $(cc) $(filter %.c,$^) -o $@ $(cflags)
analyse: cflags := -pthread
analyse: tools/pgn.c
--- a/mini.c
+++ b/mini.c
@@ -22,6 +22,7 @@
node = moonfish_new();
moonfish_root(node, &chess);
+ options.thread_count = 1;
for (;;) {@@ -70,7 +71,11 @@
if (!moonfish_equal(&chess0, &chess)) moonfish_reroot(node, &chess);
}
- if (!strcmp(line, "uci")) printf("uciok\n");+ if (!strncmp(line, "setoption ", 10)) {+ sscanf(line, "setoption name Threads value %d", &options.thread_count);
+ }
+
+ if (!strcmp(line, "uci")) printf("option name Threads type spin default 1 min 1 max 256\nuciok\n"); if (!strcmp(line, "isready")) printf("readyok\n");if (!strcmp(line, "quit")) return 0;
}
--- a/moonfish.h
+++ b/moonfish.h
@@ -97,6 +97,7 @@
struct moonfish_options {long int max_time;
long int our_time;
+ int thread_count;
};
/* represents a search result */
--- a/scripts/minify.sh
+++ b/scripts/minify.sh
@@ -7,7 +7,7 @@
header='#!/bin/sh
t=`mktemp`
-tail -n+5 "$0"|unxz -Fraw|'""${CC:-cc}""' -ansi -O3 -o $t -xc - -lm+tail -n+5 "$0"|unxz -Fraw|'""${CC:-cc}""' -O3 -o $t -xc - -lm -pthread -latomic(sleep 3;rm $t)&exec $t'
# for each C source file
@@ -40,7 +40,7 @@
scripts/rename.sh |
# put spaces between identifiers
-awk '/^[^a-zA-Z0-9]/ { n = 0 ; print $0 ; next } { if (++n > 1) print " " ; } 1' |+awk '/^[^a-zA-Z0-9_]/ { n = 0 ; print $0 ; next } { if (++n > 1) print " " ; } 1' |# remove line breaks (except in '#include' lines)
awk '/^#/ { print $0 ; next } { printf "%s", $0 }' |--- a/scripts/rename.sh
+++ b/scripts/rename.sh
@@ -9,7 +9,7 @@
alphabet2=("${alphabet[@]}")declare -A names
-functions="main fopen fread printf fprintf sscanf fgets fflush stdin stdout stderr strcmp strncmp strcpy strtok strstr strchr malloc realloc free exit errno clock_gettime timespec tv_sec tv_nsec pthread_create pthread_join pthread_t typedef memmove fabs sqrt log pow qsort"
+functions="main fopen fread printf fprintf sscanf fgets fflush stdin stdout stderr strcmp strncmp strcpy strtok strstr strchr malloc realloc free exit errno clock_gettime timespec tv_sec tv_nsec typedef memmove fabs sqrt log pow qsort thrd_t atomic_compare_exchange_strong atomic_fetch_add thrd_create thrd_success thrd_join"
keywords="do while for if else switch case break continue return extern static struct enum unsigned signed long short int char double float void const sizeof $functions"
while read -r name
--- a/search.c
+++ b/search.c
@@ -13,6 +13,41 @@
#include <time.h>
#endif
+#ifdef moonfish_no_threads
+
+#define moonfish_result_t int
+#define moonfish_value 0
+#define _Atomic
+
+#else
+
+#include <stdatomic.h>
+
+#ifndef moonfish_pthreads
+
+#include <threads.h>
+#define moonfish_result_t int
+#define moonfish_value 0
+
+#else
+
+#include <pthread.h>
+#define thrd_t pthread_t
+#define thrd_create(thread, fn, arg) pthread_create(thread, NULL, fn, arg)
+#define thrd_join pthread_join
+#define moonfish_result_t void *
+#define moonfish_value NULL
+#define thrd_success 0
+
+#endif
+
+#endif
+
+#ifdef moonfish_mini
+#undef atomic_compare_exchange_strong
+#undef atomic_fetch_add
+#endif
+
#include "moonfish.h"
#ifdef _WIN32
@@ -42,13 +77,19 @@
struct moonfish_move move;
struct moonfish_node *parent;
struct moonfish_node *children;
- double chance;
double score;
- long int visits;
- float bounds[2];
- int count;
+ _Atomic double chance;
+ _Atomic long int visits;
+ _Atomic float bounds[2];
+ _Atomic int count;
+ _Atomic unsigned char ignored;
};
+struct moonfish_data {+ struct moonfish_node *node;
+ long int time, time0;
+};
+
double moonfish_values[] = {0,0,0,0,103,124,116,101,104,120,104,108,106,118,107,112,122,131,118,123,170,183,170,167,243,249,232,223,0,0,0,0,293,328,339,338,338,342,357,365,338,368,378,391,362,386,397,401,377,389,418,419,367,395,416,424,347,367,394,400,249,342,356,371,373,383,375,379,390,403,404,398,395,405,409,415,395,408,414,426,400,416,423,432,409,419,422,423,383,403,409,407,378,390,384,394,592,607,611,616,586,602,606,606,594,608,604,608,610,619,619,623,631,636,642,645,643,651,655,655,652,655,661,663,649,652,653,654,1181,1168,1172,1190,1178,1189,1199,1195,1187,1197,1203,1200,1191,1208,1209,1214,1211,1213,1226,1231,1217,1224,1240,1240,1197,1189,1233,1238,1214,1227,1239,1243,-21,2,-24,-31,-6,-2,-6,-8,-17,-1,4,8,-12,10,18,23,6,32,34,33,20,44,40,29,5,34,27,16,-50,-1,-5,-10};double moonfish_score(struct moonfish_chess *chess)
@@ -91,6 +132,7 @@
node->count = 0;
node->chance = 0;
node->visits = 0;
+ node->ignored = 0;
node->bounds[0] = 0;
node->bounds[1] = 1;
}
@@ -108,8 +150,10 @@
struct moonfish_move moves[32];
int x, y;
int count, i;
+ int child_count;
node->children = NULL;
+ child_count = 0;
for (y = 0 ; y < 8 ; y++) {@@ -118,7 +162,7 @@
count = moonfish_moves(&node->move.chess, moves, (x + 1) + (y + 2) * 10);
if (count == 0) continue;
- node->children = realloc(node->children, (node->count + count) * sizeof *node->children);
+ node->children = realloc(node->children, (child_count + count) * sizeof *node->children);
if (node->children == NULL) { perror("realloc");exit(1);
@@ -127,23 +171,21 @@
for (i = 0 ; i < count ; i++) {if (!moonfish_validate(&moves[i].chess)) continue;
- moonfish_node(node->children + node->count);
- node->children[node->count].move = moves[i];
- node->children[node->count].parent = node;
+ moonfish_node(node->children + child_count);
+ node->children[child_count].move = moves[i];
+ node->children[child_count].parent = node;
- node->children[node->count].score = moonfish_score(&moves[i].chess);
- if (!moves[i].chess.white) node->children[node->count].score *= -1;
+ node->children[child_count].score = moonfish_score(&moves[i].chess);
+ if (!moves[i].chess.white) node->children[child_count].score *= -1;
- node->count++;
+ child_count++;
}
}
}
- qsort(node->children, node->count, sizeof *node, &moonfish_compare);
-
- if (node->count == 0 && node->children != NULL) {- free(node->children);
- }
+ qsort(node->children, child_count, sizeof *node, &moonfish_compare);
+ if (child_count == 0 && node->children != NULL) free(node->children);
+ node->count = child_count;
}
static double moonfish_confidence(struct moonfish_node *node)
@@ -157,13 +199,23 @@
struct moonfish_node *next;
double max_confidence, confidence;
int i;
+ int n;
- while (node->count > 0) {+ for (;;) {+#ifdef moonfish_no_threads
+ if (node->count == 0) break;
+#else
+ n = 0;
+ if (atomic_compare_exchange_strong(&node->count, &n, -1)) break;
+ if (n == -1) continue;
+#endif
+
next = NULL;
max_confidence = -1;
for (i = 0 ; i < node->count ; i++) {+ if (node->children[i].ignored) continue;
confidence = moonfish_confidence(node->children + i);
if (confidence > max_confidence) {next = node->children + i;
@@ -179,51 +231,50 @@
static void moonfish_propagate(struct moonfish_node *node, double chance)
{+ double value;
+
while (node != NULL) {- node->visits++;
+
+#ifdef moonfish_no_threads
node->chance += chance;
+ node->visits++;
+#else
+ value = node->chance;
+ for (;;) {+ if (atomic_compare_exchange_strong(&node->chance, &value, value + chance)) {+ break;
+ }
+ }
+ atomic_fetch_add(&node->visits, 1);
+#endif
+
node = node->parent;
chance = 1 - chance;
}
}
-static void moonfish_remove(struct moonfish_node *node, int i)
-{- int j;
-
- node->count--;
- moonfish_discard(node->children + i);
- memmove(node->children + i, node->children + i + 1, (node->count - i) * sizeof *node);
-
- for (;;) {- if (i >= node->count) break;
- for (j = 0 ; j < node->children[i].count ; j++) {- node->children[i].children[j].parent = node->children + i;
- }
- i++;
- }
-}
-
static void moonfish_propagate_bounds(struct moonfish_node *node, int i)
{int j;
+ float bound;
while (node != NULL) {- node->bounds[i] = 0;
+ bound = 0;
for (j = 0 ; j < node->count ; j++) {- if (1 - node->children[j].bounds[1 - i] > node->bounds[i]) {- node->bounds[i] = 1 - node->children[j].bounds[1 - i];
+ if (1 - node->children[j].bounds[1 - i] > bound) {+ bound = 1 - node->children[j].bounds[1 - i];
}
}
for (j = 0 ; j < node->count ; j++) {- if (1 - node->children[j].bounds[1 - i] < node->bounds[i]) {- moonfish_remove(node, j--);
+ if (1 - node->children[j].bounds[1 - i] < bound) {+ node->children[j].ignored = 1;
}
}
+ node->bounds[i] = bound;
node = node->parent;
i = 1 - i;
}
@@ -241,6 +292,7 @@
if (moonfish_checkmate(&leaf->move.chess)) {moonfish_propagate_bounds(leaf, 1);
}
+ leaf->count = 0;
continue;
}
moonfish_expand(leaf);
@@ -248,30 +300,73 @@
}
}
+static moonfish_result_t moonfish_start(void *data0)
+{+ struct moonfish_data *data;
+ int i, count;
+
+ data = data0;
+
+ moonfish_search(data->node, 0x100);
+ while (moonfish_clock() - data->time0 < data->time) {+ count = data->node->count;
+ for (i = 0 ; i < data->node->count ; i++) {+ if (data->node->children[i].ignored) count--;
+ }
+ if (count == 1) break;
+ moonfish_search(data->node, 0x1000);
+ }
+
+ return moonfish_value;
+}
+
void moonfish_best_move(struct moonfish_node *node, struct moonfish_result *result, struct moonfish_options *options)
{+ struct moonfish_data data;
struct moonfish_node *best_node;
- long int time, time0;
- int i;
+ long int time;
long int best_visits;
+ int i;
+#ifndef moonfish_no_threads
+ thrd_t threads[256];
+#endif
- time0 = moonfish_clock();
time = LONG_MAX;
-
if (options->max_time >= 0 && time > options->max_time) time = options->max_time;
if (options->our_time >= 0 && time > options->our_time / 16) time = options->our_time / 16;
time -= time / 32 + 125;
- moonfish_search(node, 0x800);
- while (moonfish_clock() - time0 < time) {- if (node->count == 1) break;
- moonfish_search(node, 0x2000);
+ data.node = node;
+ data.time = time;
+ data.time0 = moonfish_clock();
+
+#ifdef moonfish_no_threads
+
+ moonfish_start(&data);
+
+#else
+
+ for (i = 0 ; i < options->thread_count ; i++) {+ if (thrd_create(threads + i, &moonfish_start, &data) != thrd_success) {+ fprintf(stderr, "could not create thread\n");
+ exit(1);
+ }
}
+ for (i = 0 ; i < options->thread_count ; i++) {+ if (thrd_join(threads[i], NULL) != thrd_success) {+ fprintf(stderr, "could not join thread\n");
+ exit(1);
+ }
+ }
+
+#endif
+
best_visits = -1;
best_node = NULL;
for (i = 0 ; i < node->count ; i++) {+ if (node->children[i].ignored) continue;
if (node->children[i].visits > best_visits) {best_node = node->children + i;
best_visits = best_node->visits;
--
⑨