From 84ad2e3c12cb505e3c5e3dd29d05edb529b82174 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Sat, 30 Jan 2021 16:47:48 -0500 Subject: Try to squeeze out a little more performance ``Common wisdom'' dictates that placements are often better than stack moves, so we bias the generated move list in this fashion. Seems to be a little faster. --- Makefile | 12 ++++++------ include/actions.c | 31 ++++++++++++++++++++++++++++--- include/actions.h | 24 ++++++++++++------------ include/negamax.c | 15 +++++++-------- 4 files changed, 53 insertions(+), 29 deletions(-) diff --git a/Makefile b/Makefile index e519a3c..a62f2f7 100644 --- a/Makefile +++ b/Makefile @@ -2,11 +2,11 @@ STRIP=strip IDIR=include DEFINES=-DDETERMINISTIC -CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) -lm +CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) CTAK=include/tak.c CTAK_OBJS=$(CTAK:.c=.o) -SRCS=$(wildcard include/*.c) +SRCS=$(filter-out include/lcdlib.c,$(wildcard include/*.c)) OBJS=$(SRCS:.c=.o) BUILDROOT_DIR=buildroot-2020.11.1 @@ -22,10 +22,6 @@ ctaklm: src/ctaklm.o $(OBJS) $(CC) $(CFLAGS) src/ctaklm.o $(OBJS) -o ctaklm $(STRIP) ctaklm -ct1986: src/ct1986.o $(OBJS) - $(CC) $(CFLAGS) src/ct1986.o $(OBJS) -o ct1986 - $(STRIP) ct1986 - pptdb: src/pptdb.o $(CTAK_OBJS) $(CC) $(CFLAGS) src/pptdb.o $(CTAK_OBJS) -o pptdb @@ -38,6 +34,10 @@ native: clean ctaklm pptdb $(CROSS_CC): ./resources/do_buildroot.sh $(BUILDROOT_DIR) +ct1986: src/ct1986.o include/lcdlib.o $(OBJS) + $(CC) $(CFLAGS) src/ct1986.o $(OBJS) include/lcdlib.o -o ct1986 + $(STRIP) ct1986 + pi: CC=$(CROSS_CC) pi: STRIP=$(CROSS_STRIP) pi: $(CROSS_CC) clean ctaklm ct1986 diff --git a/include/actions.c b/include/actions.c index 800a2d4..316b19f 100644 --- a/include/actions.c +++ b/include/actions.c @@ -30,6 +30,11 @@ list_append(action_list_t *list, const enum A_TYPE type, const int8_t loc, const uint8_t data0, const uint8_t data1); +static inline void +list_prepend(action_list_t *list, const enum A_TYPE type, + const int8_t loc, const uint8_t data0, + const uint8_t data1); + static inline void inline_next_ply(void); @@ -82,6 +87,8 @@ void action_list_init(void) { move_deltas[3] = +1; } +// We bias place over move by prepending place actions and appending +// move actions to the generated list action_list_t *action_list_generate(void) { action_list_t *list = malloc(sizeof(struct action_list_s)); @@ -198,12 +205,12 @@ action_list_t *action_list_generate(void) { else if (material) { // Empty square, generate placements if (flat) { - list_append(list, A_PLACE, loc, STONE_FLAT, 0); + list_prepend(list, A_PLACE, loc, STONE_FLAT, 0); if (standing) - list_append(list, A_PLACE, loc, STONE_STANDING,0); + list_prepend(list, A_PLACE, loc, STONE_STANDING,0); } if (cap) - list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0); + list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0); } } } @@ -396,6 +403,24 @@ list_append(action_list_t *list, const enum A_TYPE type, list->length++; } +static inline void +list_prepend(action_list_t *list, const enum A_TYPE type, + const int8_t loc, const uint8_t data0, + const uint8_t data1) { + action_node_t *new = malloc(sizeof(action_list_t)); + // TODO: trap errno + + new->next = list->head; + list->head = new; + new->action = A_BUILD(type, loc, data0, data1); + + if (list->length == 0) { + list->tail = new; + } + + list->length++; +} + static inline void inline_next_ply(void) { ply++; diff --git a/include/actions.h b/include/actions.h index a1c90cc..181aec2 100644 --- a/include/actions.h +++ b/include/actions.h @@ -31,18 +31,18 @@ enum A_TYPE { A_PLACE, A_MOVE }; typedef uint32_t action_t; -#define A_TYPE_SHIFT 24 -#define A_LOC_SHIFT 16 -#define A_DATA0_SHIFT 8 - -#define A_GET_TYPE(a) (enum A_TYPE)((a)>>A_TYPE_SHIFT) -#define A_GET_LOC(a) (int8_t)(((a)>>A_LOC_SHIFT) & 0xFF) -#define A_GET_DATA0(a) (uint8_t)(((a)>>A_DATA0_SHIFT) & 0xFF) -#define A_GET_DATA1(a) (uint8_t)((a) & 0xFF) -#define A_BUILD(type,loc,data0,data1) ((type) << A_TYPE_SHIFT \ - | (loc) << A_LOC_SHIFT \ - | (data0) << A_DATA0_SHIFT \ - | (data1)) +#define A_DATA1_SHIFT 24 +#define A_DATA0_SHIFT 16 +#define A_LOC_SHIFT 8 + +#define A_GET_DATA1(a) (enum A_TYPE)((a)>>A_DATA1_SHIFT) +#define A_GET_DATA0(a) (int8_t)(((a)>>A_DATA0_SHIFT) & 0xFF) +#define A_GET_LOC(a) (uint8_t)(((a)>>A_LOC_SHIFT) & 0xFF) +#define A_GET_TYPE(a) (uint8_t)((a) & 0xFF) +#define A_BUILD(type,loc,data0,data1) ((type) \ + | (loc) << A_LOC_SHIFT \ + | (data0) << A_DATA0_SHIFT \ + | (data1) << A_DATA1_SHIFT) typedef struct action_node_s { struct action_node_s *next; diff --git a/include/negamax.c b/include/negamax.c index cdcfcf9..44deea9 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -30,7 +30,7 @@ uint8_t negamax_search_depth = 3; // =================================================================== static float negamax(const uint8_t cur_depth, float alpha, float beta, - const float colour); + const float colour, const uint64_t hash); // =================================================================== // Exported functions @@ -54,9 +54,8 @@ float negamax_generate(void) { tt_init(); float result = - negamax(negamax_search_depth, - -safe_infty, safe_infty, - (ply & 1) ? +1.0 : -1.0); + negamax(negamax_search_depth, -safe_infty, safe_infty, + (ply & 1) ? +1.0 : -1.0, zobrist_compute()); tt_free(); return result; @@ -71,9 +70,8 @@ static enum TT_FLAG flag; static enum WIN_TYPE w; static float negamax(const uint8_t cur_depth, float alpha, float beta, - const float colour) { + const float colour, const uint64_t hash) { - uint64_t hash = zobrist_compute(); tt_entry_t *entry = tt_seek(hash); // CAUTION: ≥ breaks search stability (vs =) on shallow depths @@ -117,7 +115,8 @@ static float negamax(const uint8_t cur_depth, float alpha, float beta, } } else if (cur_depth > 1) { // If nobody won, or too early and not leaf, recurse - node_value = -negamax(cur_depth - 1, -beta, -alpha, -colour); + node_value = -negamax(cur_depth - 1, -beta, -alpha, + -colour, zobrist_compute()); } else { node_value = colour * cnn1986_evaluate_black_win(); } @@ -130,7 +129,7 @@ static float negamax(const uint8_t cur_depth, float alpha, float beta, action_to_ptn(node->action, negamax_ptn); } - alpha = fmax(best_value, alpha); + if (best_value > alpha) alpha = best_value; if (alpha >= beta) break; } -- cgit v1.2.3