shithub: moonfish

--- a/main.c

+++ b/main.c

@@ -11,7 +11,7 @@

 int main(int argc, char **argv)

 	static char line[2048];

-	struct moonfish *ctx;

+	struct moonfish_analysis *analysis;

 	char *arg;

 	struct moonfish_move move;

 	char name[6];

@@ -18,6 +18,7 @@

 	long int wtime, btime, *xtime;

 	int score;

 	int depth;

+	struct moonfish_chess chess;

 	if (argc > 1)

@@ -25,16 +26,9 @@

 		return 1;

-	ctx = malloc(sizeof *ctx);

-	if (ctx == NULL)

-	{

-		perror(argv[0]);

-		return 1;

-	}

+	analysis = moonfish_analysis(argv[0]);

+	moonfish_chess(&chess);

-	ctx->argv0 = argv[0];

-	moonfish_chess(&ctx->chess);

 	for (;;)

 		errno = 0;

@@ -42,7 +36,6 @@

 			if (errno)

-				free(ctx);

 				perror(argv[0]);

 				return 1;

@@ -72,7 +65,6 @@

 					if (arg == NULL || sscanf(arg, "%ld", xtime) != 1 || *xtime < 0)

-						free(ctx);

 						fprintf(stderr, "%s: malformed 'go' command\n", argv[0]);

 						return 1;

@@ -84,7 +76,6 @@

 					if (arg == NULL || sscanf(arg, "%d", &depth) != 1 || depth < 0)

-						free(ctx);

 						fprintf(stderr, "%s: malformed 'go depth' command\n", argv[0]);

 						return 1;

@@ -99,12 +90,12 @@

 #ifdef moonfish_mini

 				exit(1);

 #else

-				score = moonfish_best_move_depth(ctx, &move, depth);

+				score = moonfish_best_move_depth(analysis, &move, depth);

 #endif

-			else if (ctx->chess.white)

-				score = moonfish_best_move_time(ctx, &move, &depth, wtime, btime);

+			else if (chess.white)

+				score = moonfish_best_move_time(analysis, &move, &depth, wtime, btime);

 			else

-				score = moonfish_best_move_time(ctx, &move, &depth, btime, wtime);

+				score = moonfish_best_move_time(analysis, &move, &depth, btime, wtime);

 			printf("info depth %d ", depth);

 			if (score >= moonfish_omega || score <= -moonfish_omega)

@@ -124,19 +115,18 @@

 			if (arg == NULL)

 				fprintf(stderr, "incomplete 'position' command\n");

-				free(ctx);

 				return 1;

 			if (!strcmp(arg, "startpos"))

-				moonfish_chess(&ctx->chess);

+				moonfish_chess(&chess);

 #ifndef moonfish_mini

 			else if (!strcmp(arg, "fen"))

 				arg = strtok(NULL, "\r\n");

-				moonfish_fen(&ctx->chess, arg);

+				moonfish_fen(&chess, arg);

 				arg = strstr(arg, "moves");

 				if (arg != NULL)

@@ -155,7 +145,6 @@

 			else

 				fprintf(stderr, "malformed 'position' command\n");

-				free(ctx);

 				return 1;

@@ -164,10 +153,12 @@

 				while ((arg = strtok(NULL, "\r\n\t ")) != NULL)

-					moonfish_from_uci(&ctx->chess, &move, arg);

-					moonfish_play(&ctx->chess, &move);

+					moonfish_from_uci(&chess, &move, arg);

+					moonfish_play(&chess, &move);

+			moonfish_new(analysis, &chess);

 		else if (!strcmp(arg, "uci"))

@@ -192,6 +183,6 @@

 		fflush(stdout);

-	free(ctx);

+	moonfish_free(analysis);

 	return 0;

--- a/moonfish.h

+++ b/moonfish.h

@@ -49,12 +49,6 @@

 	int score;

};

-struct moonfish

-{

-	struct moonfish_chess chess;

-	char *argv0;

-};

 struct moonfish_move

 	unsigned char from, to;

@@ -66,6 +60,8 @@

 	int score;

};

+struct moonfish_analysis;

 void moonfish_chess(struct moonfish_chess *chess);

 void moonfish_moves(struct moonfish_chess *chess, struct moonfish_move *moves, unsigned char from);

@@ -73,9 +69,13 @@

 void moonfish_play(struct moonfish_chess *chess, struct moonfish_move *move);

 void moonfish_unplay(struct moonfish_chess *chess, struct moonfish_move *move);

-int moonfish_best_move_time(struct moonfish *ctx, struct moonfish_move *move, int *depth, long int our_time, long int their_time);

+int moonfish_best_move_time(struct moonfish_analysis *analysis, struct moonfish_move *move, int *depth, long int our_time, long int their_time);

 int moonfish_countdown(int score);

+struct moonfish_analysis *moonfish_analysis(char *argv0);

+void moonfish_new(struct moonfish_analysis *analysis, struct moonfish_chess *chess);

+void moonfish_free(struct moonfish_analysis *analysis);

 void moonfish_move(struct moonfish_chess *chess, struct moonfish_move *move, unsigned char from, unsigned char to);

 void moonfish_from_uci(struct moonfish_chess *chess, struct moonfish_move *move, char *name);

 void moonfish_to_uci(char *name, struct moonfish_move *move);

@@ -86,7 +86,7 @@

 #ifndef moonfish_mini

 int moonfish_fen(struct moonfish_chess *chess, char *fen);

-int moonfish_best_move_depth(struct moonfish *ctx, struct moonfish_move *move, int depth);

+int moonfish_best_move_depth(struct moonfish_analysis *analysis, struct moonfish_move *move, int depth);

 int moonfish_finished(struct moonfish_chess *chess);

 int moonfish_checkmate(struct moonfish_chess *chess);

--- a/search.c

+++ b/search.c

@@ -47,127 +47,164 @@

 struct moonfish_node

-	unsigned char from, to;

 	struct moonfish_node *children;

+	int score;

+	int visits;

+	unsigned char from, to;

 	unsigned char count;

-	short int score;

};

 struct moonfish_info

-	struct moonfish *ctx;

+	struct moonfish_analysis *analysis;

 	pthread_t thread;

+	struct moonfish_node *node;

 	struct moonfish_move move;

 	struct moonfish_chess chess;

 	int depth;

 	int score;

-	struct moonfish_node node;

-	struct moonfish_node *nodes;

-	int count;

};

-static void moonfish_free(struct moonfish_node *node)

+struct moonfish_analysis

+	char *argv0;

+	struct moonfish_chess chess;

+	struct moonfish_info info[256];

+	struct moonfish_node root;

+	int depth;

+};

+static void moonfish_free_node(struct moonfish_node *node)

+{

 	int i;

 	for (i = 0 ; i < node->count ; i++)

-		moonfish_free(node->children + i);

+		moonfish_free_node(node->children + i);

 	if (node->count > 0)

 		free(node->children);

+	node->count = 0;

-static int moonfish_quiesce(struct moonfish_chess *chess, int alpha, int beta, int depth, int i)

+struct moonfish_analysis *moonfish_analysis(char *argv0)

-	int x, y;

+	struct moonfish_analysis *analysis;

+	struct moonfish_chess chess;

+	analysis = malloc(sizeof *analysis);

+	if (analysis == NULL)

+	{

+		perror(argv0);

+		exit(1);

+	}

+	analysis->argv0 = argv0;

+	analysis->root.count = 0;

+	moonfish_chess(&chess);

+	moonfish_new(analysis, &chess);

+	return analysis;

+}

+void moonfish_new(struct moonfish_analysis *analysis, struct moonfish_chess *chess)

+{

+	moonfish_free_node(&analysis->root);

+	analysis->root.visits = 0;

+	analysis->root.count = 0;

+	analysis->chess = *chess;

+	analysis->depth = 1;

+}

+void moonfish_free(struct moonfish_analysis *analysis)

+{

+	struct moonfish_chess chess;

+	moonfish_new(analysis, &chess);

+	free(analysis);

+}

+static void moonfish_expand(char *argv0, struct moonfish_node *node, struct moonfish_chess *chess)

+{

 	struct moonfish_move moves[32];

 	struct moonfish_move *move;

-	int score;

+	int x, y;

+	int done;

-	score = chess->score;

-	if (!chess->white) score *= -1;

+	if (node->count != 0) return;

-	if (i >= depth) return score;

-	if (score >= beta) return beta;

-	if (score > alpha) alpha = score;

+	done = 0;

+	node->children = NULL;

-	for (y = 0 ; y < 8 ; y++)

-	for (x = 0 ; x < 8 ; x++)

+	for (y = 0 ; y < 8 && !done ; y++)

+	for (x = 0 ; x < 8 && !done ; x++)

 		moonfish_moves(chess, moves, (x + 1) + (y + 2) * 10);

 		for (move = moves ; move->piece != moonfish_outside ; move++)

-			if (move->captured == moonfish_empty)

-			if (move->promotion == move->piece)

-				continue;

+			node->children = realloc(node->children, (node->count + 1) * sizeof *node->children);

+			if (node->children == NULL)

+			{

+				perror(argv0);

+				exit(1);

+			}

-			if (move->captured % 16 == moonfish_king)

-				return moonfish_omega * (moonfish_depth - i);

-			moonfish_play(chess, move);

-			score = -moonfish_quiesce(chess, -beta, -alpha, depth, i + 1);

-			moonfish_unplay(chess, move);

-			if (score >= beta) return beta;

-			if (score > alpha) alpha = score;

+			node->children[node->count].from = move->from;

+			node->children[node->count].to = move->to;

+			node->children[node->count].count = 0;

+			node->children[node->count].visits = 0;

+			node->count++;

-	return alpha;

-static int moonfish_search(struct moonfish_info *info, struct moonfish_node *node, int alpha, int beta, int depth, int qdepth, int i)

+static int moonfish_search(struct moonfish_info *info, struct moonfish_node *parent, struct moonfish_node *node, int alpha, int beta, int depth, int i)

-	int x, y;

-	struct moonfish_move moves[32];

-	struct moonfish_move *move;

 	int score;

 	int j, k;

 	struct moonfish_node swap_node;

-	int done;

-	struct moonfish_move move0;

+	struct moonfish_move move;

+	int group_count;

+	unsigned char adjust[256];

-	if (i >= depth) return moonfish_quiesce(&info->chess, alpha, beta, depth + qdepth, i);

+	if (i >= depth)

+	{

+		node->visits++;

+		score = info->chess.score;

+		if (!info->chess.white) score *= -1;

+		return score;

+	}

-	if (node->count == 0)

+	moonfish_expand(info->analysis->argv0, node, &info->chess);

+	group_count = (parent->visits / parent->count) / (node->visits + 1) / 16 + 1;

+	for (j = 0 ; j < node->count ; j++)

-		done = 0;

-		node->children = NULL;

-		for (y = 0 ; y < 8 && !done ; y++)

-		for (x = 0 ; x < 8 && !done ; x++)

+		if (node->children[j].visits == 0)

-			moonfish_moves(&info->chess, moves, (x + 1) + (y + 2) * 10);

-			for (move = moves ; move->piece != moonfish_outside ; move++)

-			{

-				node->children = realloc(node->children, (node->count + 1) * sizeof *node->children);

-				if (node->children == NULL)

-				{

-					perror(info->ctx->argv0);

-					exit(1);

-				}

-				node->children[node->count].from = move->from;

-				node->children[node->count].to = move->to;

-				node->children[node->count].count = 0;

-				node->count++;

-			}

+			adjust[j] = 0;

+			continue;

+		if (node->children[j].score >= moonfish_omega || node->children[j].score <= -moonfish_omega)

+		{

+			adjust[j] = 0xFF;

+			continue;

+		}

+		adjust[j] = j * group_count / node->count;

 	for (j = 0 ; j < node->count ; j++)

-		moonfish_move(&info->chess, &move0, node->children[j].from, node->children[j].to);

+		moonfish_move(&info->chess, &move, node->children[j].from, node->children[j].to);

-		if (move0.captured % 16 == moonfish_king)

+		if (move.captured % 16 == moonfish_king)

 			score = moonfish_omega * (moonfish_depth - i);

 		else

-			moonfish_play(&info->chess, &move0);

-			score = -moonfish_search(info, node->children + j, -beta, -alpha, depth, qdepth, i + 1);

-			moonfish_unplay(&info->chess, &move0);

+			moonfish_play(&info->chess, &move);

+			score = -moonfish_search(info, node, node->children + j, -beta, -alpha, depth - adjust[j], i + 1);

+			moonfish_unplay(&info->chess, &move);

 		node->children[j].score = score;

@@ -182,10 +219,15 @@

 			break;

 		if (score > alpha) alpha = score;

+	node->visits = 0;

 	for (j = 1 ; j < node->count ; j++)

+		node->visits += node->children[j].visits;

+	for (j = 1 ; j < node->count ; j++)

 	for (k = j ; k > 0 && node->children[k - 1].score < node->children[k].score ; k--)

 		swap_node = node->children[k];

@@ -193,6 +235,12 @@

 		node->children[k - 1] = swap_node;

+	if (i > 5 && node->count > 0)

+	{

+		free(node->children);

+		node->count = 0;

+	}

 	return alpha;

@@ -208,97 +256,63 @@

 	struct moonfish_info *info;

 	info = data;

-	info->score = -moonfish_search(info, &info->node, -100 * moonfish_omega, 100 * moonfish_omega, info->depth, 4, 0);

+	info->score = -moonfish_search(info, &info->analysis->root, info->node, -100 * moonfish_omega, 100 * moonfish_omega, info->depth, 0);

 	return moonfish_value;

-static int moonfish_iteration(struct moonfish *ctx, struct moonfish_move *best_move, int depth, int init)

+static int moonfish_iteration(struct moonfish_analysis *analysis, struct moonfish_move *best_move, int depth)

-	static struct moonfish_move all_moves[256];

-	static struct moonfish_info infos[256];

-	static struct moonfish_move move_array[32];

-	static int init0 = 0;

-	int x, y;

+	struct moonfish_move move;

 	int best_score;

-	int move_count;

-	int i;

+	int i, j;

 	int result;

-	if (!init0)

-	{

-		init0 = 1;

-		for (i = 0 ; i < 256 ; i++)

-			infos[i].node.count = 0;

-	}

+	moonfish_expand(analysis->argv0, &analysis->root, &analysis->chess);

-	if (!init)

-	{

-		for (i = 0 ; i < 256 ; i++)

-			moonfish_free(&infos[i].node),

-			infos[i].node.count = 0;

-	}

+	j = 0;

-	if (ctx == NULL) return 0;

-	best_score = -200 * moonfish_omega;

-	move_count = 0;

-	for (y = 0 ; y < 8 ; y++)

-	for (x = 0 ; x < 8 ; x++)

+	for (i = 0 ; i < analysis->root.count ; i++)

-		moonfish_moves(&ctx->chess, move_array, (x + 1) + (y + 2) * 10);

+		analysis->info[j].chess = analysis->chess;

-		for (i = 0 ; move_array[i].piece != moonfish_outside ; i++)

-		{

-			moonfish_play(&ctx->chess, move_array + i);

-			if (moonfish_validate(&ctx->chess))

-			{

-				all_moves[move_count] = move_array[i];

-				move_count++;

-			}

-			moonfish_unplay(&ctx->chess, move_array + i);

-		}

-	}

-	if (move_count == 1)

-	{

-		*best_move = *all_moves;

-		return 0;

-	}

-	for (i = 0 ; i < move_count ; i++)

-	{

-		moonfish_play(&ctx->chess, all_moves + i);

+		moonfish_move(&analysis->info[j].chess, &move, analysis->root.children[i].from, analysis->root.children[i].to);

+		moonfish_play(&analysis->info[j].chess, &move);

-		infos[i].ctx = ctx;

-		infos[i].move = all_moves[i];

-		infos[i].chess = ctx->chess;

-		infos[i].depth = depth;

+		if (!moonfish_validate(&analysis->chess)) continue;

-		result = pthread_create(&infos[i].thread, NULL, &moonfish_start_search, infos + i);

+		analysis->info[j].analysis = analysis;

+		analysis->info[j].node = analysis->root.children + i;

+		analysis->info[j].move = move;

+		analysis->info[j].depth = depth;

+		result = pthread_create(&analysis->info[j].thread, NULL, &moonfish_start_search, analysis->info + j);

 		if (result)

-			fprintf(stderr, "%s: %s\n", ctx->argv0, strerror(result));

+			fprintf(stderr, "%s: %s\n", analysis->argv0, strerror(result));

 			exit(1);

-		moonfish_unplay(&ctx->chess, all_moves + i);

+		j++;

-	for (i = 0 ; i < move_count ; i++)

+	best_score = -200 * moonfish_omega;

+	analysis->root.visits = 0;

+	for (i = 0 ; i < j ; i++)

-		result = pthread_join(infos[i].thread, NULL);

+		result = pthread_join(analysis->info[i].thread, NULL);

 		if (result)

-			fprintf(stderr, "%s: %s\n", ctx->argv0, strerror(result));

+			fprintf(stderr, "%s: %s\n", analysis->argv0, strerror(result));

 			exit(1);

-		if (infos[i].score > best_score)

+		analysis->root.visits += analysis->info[i].node->visits;

+		if (analysis->info[i].score > best_score)

-			*best_move = infos[i].move;

-			best_score = infos[i].score;

+			*best_move = analysis->info[i].move;

+			best_score = analysis->info[i].score;

@@ -307,20 +321,15 @@

 #ifndef moonfish_mini

-int moonfish_best_move_depth(struct moonfish *ctx, struct moonfish_move *best_move, int depth)

+int moonfish_best_move_depth(struct moonfish_analysis *analysis, struct moonfish_move *best_move, int depth)

-	int i;

 	int score;

-	moonfish_iteration(NULL, NULL, 0, 0);

-	score = 0;

-	i = 3;

-	do score = moonfish_iteration(ctx, best_move, i++, 1);

-	while (i <= depth);

-	return score;

+	for (;;)

+	{

+		score = moonfish_iteration(analysis, best_move, analysis->depth);

+		if (analysis->depth >= depth) return score;

+		analysis->depth++;

+	}

 #endif

@@ -327,21 +336,21 @@

 #ifdef _WIN32

-static long int moonfish_clock(struct moonfish *ctx)

+static long int moonfish_clock(struct moonfish_analysis *analysis)

-	(void) ctx;

+	(void) analysis;

 	return GetTickCount();

 #else

-static long int moonfish_clock(struct moonfish *ctx)

+static long int moonfish_clock(struct moonfish_analysis *analysis)

 	struct timespec ts;

 	if (clock_gettime(CLOCK_MONOTONIC, &ts))

-		perror(ctx->argv0);

+		perror(analysis->argv0);

 		exit(1);

@@ -350,7 +359,7 @@

 #endif

-int moonfish_best_move_time(struct moonfish *ctx, struct moonfish_move *best_move, int *i, long int our_time, long int their_time)

+int moonfish_best_move_time(struct moonfish_analysis *analysis, struct moonfish_move *best_move, int *depth, long int our_time, long int their_time)

 	long int d, t, t0, t1;

 	int score;

@@ -363,13 +372,11 @@

 	if (d < 0) d = 0;

 	d += our_time / 8;

-	moonfish_iteration(NULL, NULL, 0, 0);

-	for (*i = 1 ; *i < 32 ; (*i)++)

+	for (;;)

-		t0 = moonfish_clock(ctx);

-		score = moonfish_iteration(ctx, best_move, *i, 1);

-		t1 = moonfish_clock(ctx) + 50;

+		t0 = moonfish_clock(analysis);

+		score = moonfish_iteration(analysis, best_move, analysis->depth);

+		t1 = moonfish_clock(analysis) + 50;

 		if (t >= 0) r = (t1 - t0) * 2048 / (t + 1);

 		t = t1 - t0;

@@ -376,7 +383,10 @@

 		d -= t;

 		if (t * r > d * 2048) break;

+		analysis->depth++;

+	*depth = analysis->depth;

 	return score;

--

⑨