aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/action_list.c75
-rw-r--r--include/action_list.h15
-rw-r--r--include/negamax.c46
-rw-r--r--include/negamax.h11
4 files changed, 75 insertions, 72 deletions
diff --git a/include/action_list.c b/include/action_list.c
index 10bbdcf..b338627 100644
--- a/include/action_list.c
+++ b/include/action_list.c
@@ -6,7 +6,7 @@
#define CLR_STONE NUM_MASK
-static inline action_list_t *
+static inline void
action_list_prepend(action_list_t *list, const enum A_TYPE type,
const int8_t loc, const uint8_t data0,
const uint8_t data1);
@@ -16,11 +16,14 @@ action_list_prepend(action_list_t *list, const enum A_TYPE type,
// ===================================================================
void action_list_free(action_list_t *list) {
- action_list_t *n = NULL;
- while (list) {
- n = list->next;
+ if (list) {
+ action_node_t *n = list->head, *nn;
+ while (n) {
+ nn = n->next;
+ free(n);
+ n = nn;
+ }
free(list);
- list = n;
}
}
@@ -35,7 +38,10 @@ void action_list_init(void) {
}
action_list_t *action_list_generate(void) {
- action_list_t *result = NULL;
+ action_list_t *result = malloc(sizeof(struct action_list_s));
+ // TODO: trap errno
+ result->length = 0;
+ result->head = NULL;
const uint8_t black = (ply < 2) ? (ply==1) : (ply & 1),
material = (black) ? black_count : white_count,
@@ -43,9 +49,9 @@ action_list_t *action_list_generate(void) {
cap = (ply >= 2 && (material & 128)),
standing = (ply >= 2 && (material & 127));
- // Step across the board
- for (int8_t row = board_size - 1; row > 0; row--) {
- for (int8_t col = board_size - 1; col > 0; col--) {
+ // Step across the board, reversed because we prepend to the list
+ for (int8_t row = board_size - 1; row >= 0; row--) {
+ for (int8_t col = board_size - 1; col >= 0; col--) {
// We'll need these at various points: the location of this
// square and the maximum number of stones we could pick up
const int8_t loc = THE_COORDS(col, row);
@@ -106,7 +112,7 @@ action_list_t *action_list_generate(void) {
const uint8_t last_drop_check =
(num > 1) ? (gaps & 1<<(num - 2)) : 1;
if (end_stops[dir][1] || last_drop_check)
- result = action_list_prepend(result, A_MOVE, loc, gaps, (dir<<4) | num);
+ action_list_prepend(result, A_MOVE, loc, gaps, (dir<<4) | num);
/*
* With thanks to
* https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
@@ -122,31 +128,22 @@ action_list_t *action_list_generate(void) {
} else if (count == 0 && material) {
// Empty square, generate placements
if (flat) {
- result = action_list_prepend(result,
- A_PLACE,
- loc,
- STONE_FLAT,
- 0);
+ action_list_prepend(result, A_PLACE, loc,
+ STONE_FLAT, 0);
if (standing)
- result = action_list_prepend(result,
- A_PLACE,
- loc,
- STONE_STANDING,
- 0);
+ action_list_prepend(result, A_PLACE, loc,
+ STONE_STANDING, 0);
}
if (cap)
- result = action_list_prepend(result,
- A_PLACE,
- loc,
- STONE_CAPSTONE,
- 0);
+ action_list_prepend(result, A_PLACE, loc,
+ STONE_CAPSTONE, 0);
}
}
}
return result;
}
-void action_take(action_list_t *action) {
+void action_take(action_node_t *action) {
const int8_t loc = action->loc;
if (action->type == A_PLACE) {
const uint8_t black = (current_colour == C_BLACK);
@@ -181,7 +178,7 @@ void action_take(action_list_t *action) {
// Use the Kernighan method to count the set bits
int8_t steps = 1;
- for (uint8_t _gaps = gaps; _gaps > 0; steps++) _gaps &= _gaps - 1;
+ for (uint8_t _gaps = gaps; _gaps; steps++) _gaps &= _gaps - 1;
// Move top stone type to destination
celldat[loc+steps*delta] &= CLR_STONE; // necessary for crushing
@@ -189,14 +186,13 @@ void action_take(action_list_t *action) {
celldat[loc] &= CLR_STONE;
celldat[loc] |= STONE_FLAT; // should be optimised out
- uint8_t gap_bit = 0, total = 0;
+ uint8_t gap_bit = 0, total = 1;
// num == 1 is a special case
if (num > 1) {
gap_bit = 1 << (num - 2);
- total = 1;
}
// move stuff starting at destination
- for (uint8_t d = 0; d + 1 < num; d++, total++, gap_bit >>= 1) {
+ for (uint8_t d = 1; d < num; d++, total++, gap_bit >>= 1) {
// We took a step, move everything over so far
if (gaps & gap_bit) {
colours[loc+steps*delta] <<= total;
@@ -209,7 +205,6 @@ void action_take(action_list_t *action) {
steps--;
}
}
- total++;
// Move what remains (steps == 1 here always, so we simplify)
colours[loc+delta] <<= total;
colours[loc+delta] |= colours[loc] & ((1 << total) - 1);
@@ -227,7 +222,7 @@ void action_take(action_list_t *action) {
}
}
-void action_undo(action_list_t *action) {
+void action_undo(action_node_t *action) {
// Previous ply
if (ply>0) ply--;
if (ply == 1) {
@@ -256,8 +251,8 @@ void action_undo(action_list_t *action) {
const int8_t delta = deltas[dir];
int8_t steps = 1;
- uint8_t gap_bit = 1, total = (num > 1) ? 1 : 0;
- for (uint8_t d = 0; d + 1 < num; d++, total++, gap_bit <<= 1) {
+ uint8_t gap_bit = 1, total = 1;
+ for (uint8_t d = 1; d < num; d++, total++, gap_bit <<= 1) {
if (gaps & gap_bit) {
colours[loc] <<= total;
colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
@@ -268,7 +263,6 @@ void action_undo(action_list_t *action) {
steps++;
}
}
- total++;
colours[loc] <<= total;
colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
colours[loc+steps*delta] >>= total;
@@ -282,7 +276,7 @@ void action_undo(action_list_t *action) {
}
}
-void action_to_ptn(action_list_t* action, char* out_ptn) {
+void action_to_ptn(action_node_t* action, char* out_ptn) {
const int8_t loc = action->loc;
if (action->type == A_PLACE) {
generate_place(loc, action->data0, out_ptn);
@@ -314,16 +308,17 @@ void action_to_ptn(action_list_t* action, char* out_ptn) {
// Helper method implementations
// ===================================================================
-static inline action_list_t *
+static inline void
action_list_prepend(action_list_t *list, const enum A_TYPE type,
const int8_t loc, const uint8_t data0,
const uint8_t data1) {
- action_list_t *new = malloc(sizeof(action_list_t));
+ action_node_t *new = malloc(sizeof(action_list_t));
// TODO: trap errno
+ list->length++;
new->loc = loc;
new->type = type;
- new->next = list;
new->data0 = data0;
new->data1 = data1;
- return new;
+ new->next = list->head;
+ list->head = new;
}
diff --git a/include/action_list.h b/include/action_list.h
index a0f5a34..14c733f 100644
--- a/include/action_list.h
+++ b/include/action_list.h
@@ -5,19 +5,24 @@
enum A_TYPE { A_PLACE, A_MOVE };
-typedef struct action_list_s {
- struct action_list_s *next;
+typedef struct action_node_s {
+ struct action_node_s *next;
enum A_TYPE type;
int8_t loc;
uint8_t data0;
uint8_t data1;
+} action_node_t;
+
+typedef struct action_list_s {
+ struct action_node_s *head;
+ uint32_t length;
} action_list_t;
void action_list_init(void);
void action_list_free(action_list_t *list);
action_list_t *action_list_generate(void);
-void action_take(action_list_t *action);
-void action_undo(action_list_t *action);
+void action_take(action_node_t *action);
+void action_undo(action_node_t *action);
-void action_to_ptn(action_list_t* action, char* out_ptn);
+void action_to_ptn(action_node_t* action, char* out_ptn);
diff --git a/include/negamax.c b/include/negamax.c
index 16eba9a..43fa5f6 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -102,7 +102,7 @@ negamax_generate(void) {
tt_init();
float result = negamax(negamax_search_depth,
-safe_infty, safe_infty,
- (ply&1)?1.0:-1.0);
+ (ply & 1) ? +1.0 : -1.0);
tt_free();
return result;
@@ -113,49 +113,47 @@ static enum WIN_TYPE w;
static float
negamax(const uint8_t cur_depth, float alpha, float beta,
const float colour) {
+
+ if (cur_depth == 0) return colour*cnn1986_evaluate_black_win();
+
float value = -infty;
action_list_t *list = action_list_generate();
+ if (list == NULL) return value; // ???
- for (action_list_t *node=list; node!=NULL; node=node->next) {
- negamax_display_progress(cur_depth);
-
+ for (action_node_t *node=list->head; node!=NULL; node=node->next) {
action_take(node);
// Somebody won?
- if (ply >= 2*board_size - 3 && (w = check_win()) < 0xFF) {
- if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) {
- value = colour*infty;
- if (value > 0) {
- // Always take the win for ourselves
- action_undo(node);
- if (cur_depth == negamax_search_depth)
- action_to_ptn(node, negamax_ptn);
- goto prune;
- }
- } else if (w == WIN_DRAW) value = 0; // Draw is fixed at neutral
+ if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
+ if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) value = colour*infty;
+ else if (w == WIN_DRAW) value = 0; // Draw is fixed at neutral
else value = -colour*infty;
- } else if (cur_depth > 1) {
- // Recurse away from the leaves
- value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour));
+ if (value > 0) {
+ // Always take the win for ourselves
+ action_undo(node);
+ if (cur_depth == negamax_search_depth) {
+ action_to_ptn(node, negamax_ptn);
+ }
+ goto prune;
+ }
} else {
- // Evaluate a leaf
- value = fmax(value, colour * cnn1986_evaluate_black_win());
+ value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour));
}
action_undo(node);
+ negamax_display_progress(cur_depth, list->length);
+
if (value > alpha) {
alpha = value;
if (cur_depth == negamax_search_depth)
action_to_ptn(node, negamax_ptn);
+ if (alpha >= beta) break;
}
- if (alpha >= beta) break;
}
-
- action_list_free(list);
-
prune:
+ action_list_free(list);
return value;
}
diff --git a/include/negamax.h b/include/negamax.h
index 8a67638..c902d3c 100644
--- a/include/negamax.h
+++ b/include/negamax.h
@@ -10,10 +10,15 @@
extern const float infty;
extern char negamax_ptn[9];
extern uint8_t negamax_search_depth;
-extern inline void negamax_display_progress(const uint8_t);
-void negamax_init(const uint8_t new_board_size);
-void negamax_free(void);
+extern inline void
+negamax_display_progress(const uint8_t, const uint32_t length);
+
+void
+negamax_init(const uint8_t new_board_size);
+
+void
+negamax_free(void);
// Do negamax to depth negamax_search_depth and return PTN of best move
// in negamax_ptn, along with its value as the return. The
generated by cgit v1.2.3 (git 2.46.0) at 2026-08-30 14:37:06 +0000