aboutsummaryrefslogtreecommitdiff
path: root/include/action_list.c
diff options
context:
space:
mode:
Diffstat (limited to 'include/action_list.c')
-rw-r--r--include/action_list.c403
1 files changed, 0 insertions, 403 deletions
diff --git a/include/action_list.c b/include/action_list.c
deleted file mode 100644
index 30ca918..0000000
--- a/include/action_list.c
+++ /dev/null
@@ -1,403 +0,0 @@
-#include "action_list.h"
-
-// ===================================================================
-// Helper method declarations
-// ===================================================================
-
-#define DANGER_MIN(a,b) (((a)<(b))?(a):(b))
-
-#define CLR_STONE NUM_MASK
-
-static inline void
-action_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
-inline_next_ply(void);
-
-static inline void
-inline_prev_ply(void);
-
-
-// ===================================================================
-// Exported method implementations
-// ===================================================================
-
-/*
- * void action_list_ensure_at_front(const action_node_t *action,
- * const action_list_t *list) {
- * action_node_t *copy = action_copy(action), *n = list->head, *nn;
- * // ensure it's not there already
- * while (n) {
- * nn = n->next;
- * }
- *
- * copy->next = list->head;
- * }
- */
-
-action_node_t *action_copy(const action_node_t *action) {
- action_node_t *copy = malloc(sizeof(struct action_node_s));
- // TODO: trap
- copy->data0 = action->data0;
- copy->data1 = action->data1;
- copy->loc = action->loc;
- copy->type = action->type;
- copy->next = NULL;
- return copy;
-}
-
-void action_list_free(action_list_t *list) {
- if (list) {
- action_node_t *n = list->head, *nn;
- while (n) {
- nn = n->next;
- free(n);
- n = nn;
- }
- free(list);
- }
-}
-
-// Keep track of move offsets
-static int8_t deltas[4];
-
-void action_list_init(void) {
- deltas[0] = +board_size;
- deltas[1] = -board_size;
- deltas[2] = -1;
- deltas[3] = +1;
-}
-
-action_list_t *action_list_generate(void) {
- action_list_t *list = malloc(sizeof(struct action_list_s));
- // TODO: trap errno
- list->length = 0;
- list->head = NULL;
-
- /*
- * The check for whether it's a black piece to be played is actually
- * black = (ply < 2) ? (ply==1) : (ply & 1),
- * but material will always be sufficient in ply < 2 so we might as
- * well save on the conditional.
- */
-
- const uint8_t material = (ply & 1) ? black_count : white_count,
- flat = material & 0x7F,
- cap = ((ply >= 2) && (material & 0x80)),
- standing = ((ply >= 2) && flat);
-
- // Step across the board
- for (int row = 0; row < board_size; row++) {
- for (int col = 0; col < board_size; col++) {
- // We'll need these at various points: the location of this
- // square and the maximum number of stones we could pick up
- const int loc = THE_COORDS(col, row);
- const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size);
-
- // Only try moves after CPS and if the colour is correct
- if (count) {
- if (ply >= 2 && ((colours[loc] & 1) == current_colour)) {
-
- // Pre-compute end-stops and crushes
- uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0};
-
- // These are upper bounds, not counting walls and such.
- // UP DOWN LEFT RIGHT
- end_stops[0] = DANGER_MIN(board_size - row - 1, count);
- end_stops[1] = DANGER_MIN(row, count);
- end_stops[2] = DANGER_MIN(col, count);
- end_stops[3] = DANGER_MIN(board_size - col - 1, count);
-
- // Now we check for caps and walls
- const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
- for (int d = 0; d < 4; d++){
- const int delta = deltas[d];
- const int stop = end_stops[d];
- end_stops[d] = 0;
- for (int k = 1; k <= stop; k++) {
- const enum STONE_VARIANT stone = STONE_AT(loc+k*delta);
- if (stone == STONE_STANDING) {
- if (cap_top) {
- crushes[d] = 0xFF;
- end_stops[d]++;
- }
- break;
- } else if (stone == STONE_CAPSTONE) {
- break;
- }
- end_stops[d]++;
- }
- }
- /*
- * For each direction, generate all possible ordered integer
- * partitions of 1 ≤ num ≤ count whose number of summands is
- * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we
- * write summands as steps
- */
- for (enum MOVE_DIRECTION dir=M_UP; dir<=M_RIGHT; dir++) {
- for (uint8_t num = 1; num <= count; num++) {
- for (uint8_t steps = 1;
- steps <= end_stops[dir] && steps <= num;
- steps++) {
- // TODO: Generalise to board_size!
- uint8_t gaps = 0x07 >> (board_size-steps-1);
- // 0b0000[0111] because 4-1=3 and 5-1=4
- do {
- /*
- * We skip the partition if it calls for multiple
- * stones at the end with a crush.
- */
- const uint8_t last_drop_check =
- (num > 1) ? (gaps & (1 << (num - 2))) : 1;
- if (crushes[dir] == 0 || last_drop_check) {
- // We have to record a crush!
- const uint8_t crush =
- (steps == end_stops[dir]) && crushes[dir];
- // Store the move
-
- action_list_append(list, A_MOVE, loc,
- (crush << 7) | gaps,
- (dir<<4) | num);
- }
- /*
- * With thanks to
- * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
- * we have the following magic to generate the next
- * permutation of steps-many set bits
- */
- uint8_t t = (gaps | (gaps - 1));
- gaps = (t + 1)
- | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
- } while (gaps && (gaps + 1 <= (1 << (num - 1))));
- }
- }
- }
- }
- } // end of if (count) { ... }
- else if (material) {
- // Empty square, generate placements
- if (flat) {
- action_list_append(list, A_PLACE, loc, STONE_FLAT, 0);
- if (standing)
- action_list_append(list, A_PLACE, loc, STONE_STANDING,0);
- }
- if (cap)
- action_list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0);
- }
- }
- }
- return list;
-}
-
-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);
- switch (action->data0) {
- case STONE_FLAT: {
- if (black) black_count--;
- else white_count--;
- colours[loc] = current_colour;
- celldat[loc] = NUM_INC | STONE_FLAT;
- break;
- }
- case STONE_STANDING: {
- if (black) black_count--;
- else white_count--;
- colours[loc] = current_colour;
- celldat[loc] = NUM_INC | STONE_STANDING;
- break;
- }
- default: {
- if (black) black_count &= 0x7F;
- else white_count &= 0x7F;
- colours[loc] = current_colour;
- celldat[loc] = NUM_INC | STONE_CAPSTONE;
- break;
- }
- }
- } else {
- const uint8_t gaps = action->data0 & 0x7F, // not interested in
- // whether we crushed,
- // it will work out by
- // anyway because we
- // overwrite the top
- // stone type. See (*)
- // later for when we do
- // need to know.
- num = action->data1 & 0x0F, // unpack
- dir = action->data1 >> 4;
- int8_t delta = deltas[dir];
-
- // Use the Kernighan method to count the set bits
- int8_t steps = 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
- celldat[loc+steps*delta] |= STONE_AT(loc);
- celldat[loc] &= CLR_STONE;
- celldat[loc] |= STONE_FLAT; // should be optimised out
-
- uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important
- // what negative
- // shifts do here, we
- // don't use gap_bit
- // if num < 2
- // move stuff starting at destination
- 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;
- colours[loc+steps*delta] |= colours[loc] & ((1 << total) - 1);
- colours[loc] >>= total;
- celldat[loc+steps*delta] += total*NUM_INC;
- celldat[loc] -= total*NUM_INC;
- // Reset for next step
- total = 0;
- steps--;
- }
- }
- // Move what remains (steps == 1 here always, so we simplify)
- colours[loc+delta] <<= total;
- colours[loc+delta] |= colours[loc] & ((1 << total) - 1);
- colours[loc] >>= total;
- celldat[loc+delta] += total*NUM_INC;
- celldat[loc] -= total*NUM_INC;
- }
- // Next ply
- inline_next_ply();
-}
-
-void action_undo(action_node_t *action) {
- // Previous ply
- inline_prev_ply();
-
- const int8_t loc = action->loc;
- if (action->type == A_PLACE) {
- const uint8_t black = (current_colour == C_BLACK);
- celldat[loc] = 0;
- if (action->data0 == STONE_CAPSTONE) {
- if (black) black_count |= 0x80;
- else white_count |= 0x80;
- } else {
- if (black) black_count++;
- else white_count++;
- }
- } else {
- // See action_take for comments, this is the time reversal, but
- // there is one caveat -- undoing a crush! (*)
- const uint8_t gaps = action->data0 & 0x7F,
- crush = action->data0 & 0x80,
- num = action->data1 & 0x0F,
- dir = action->data1 >> 4;
- const int8_t delta = deltas[dir];
-
- int8_t steps = 1;
- uint8_t gap_bit = 1, total = 1;
- for (int8_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);
- colours[loc+steps*delta] >>= total;
- celldat[loc] += total*NUM_INC;
- celldat[loc+steps*delta] -= total*NUM_INC;
- total = 0;
- steps++;
- }
- }
- colours[loc] <<= total;
- colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
- colours[loc+steps*delta] >>= total;
-
- celldat[loc] += total*NUM_INC;
- // celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0
- celldat[loc] |= STONE_AT(loc+steps*delta);
- celldat[loc+steps*delta] -= total*NUM_INC;
- celldat[loc+steps*delta] &= CLR_STONE;
- if (crush) {
- celldat[loc+steps*delta] |= STONE_STANDING;
- } else {
- celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out
- }
- }
-}
-
-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);
- } else {
- const uint8_t gaps = action->data0 & 0x7F,
- num = action->data1 & 0x0F, // unpack
- dir = action->data1 >> 4;
-
- uint8_t drops[board_size]; // we only ever need board_size-1 in
- // drops actually, the last spot is to
- // skip a bounds check at (**)
- uint8_t mask = 1, steps = 0;
- // Translate to a drop sequence
- drops[0] = 1; mask = 1;
- for (uint8_t d = 1; d < num; d++) {
- if (gaps & mask) {
- steps++;
- drops[steps] = 1; // (**) no bounds check
- } else {
- drops[steps] += 1;
- }
- mask <<= 1;
- }
- generate_move(loc, dir, steps+1, drops, out_ptn);
- }
-}
-
-// ===================================================================
-// Helper method implementations
-// ===================================================================
-
-static inline void
-action_list_append(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->loc = loc;
- new->type = type;
- new->data0 = data0;
- new->data1 = data1;
- new->next = NULL;
-
- if (list->length) {
- list->tail->next = new;
- list->tail = new;
- } else {
- list->head = new;
- list->tail = new;
- }
-
- list->length++;
-}
-
-static inline void
-inline_next_ply(void) {
- ply++;
- if (ply == 2) {
- current_colour = C_WHITE;
- } else {
- if (current_colour == C_BLACK) current_colour = C_WHITE;
- else current_colour = C_BLACK;
- }
-}
-
-static inline void
-inline_prev_ply(void) {
- if (ply>0) ply--;
- if (ply == 1) {
- current_colour = C_WHITE;
- } else {
- if (current_colour == C_BLACK) current_colour = C_WHITE;
- else current_colour = C_BLACK;
- }
-}
generated by cgit v1.3.1 (git 2.54.0) at 2026-08-30 16:53:26 +0000