Working on caching move generationaction_list_caching

1 files changed, 149 insertions, 127 deletions

diff --git a/include/actions.c b/include/actions.c
index 0b7d860..10cb74e 100644
--- a/include/actions.c
+++ b/include/actions.c
@@ -18,6 +18,21 @@
 #include "actions.h"
 
 // ===================================================================
+// Types
+// ===================================================================
+
+typedef struct action_list_cache_s {
+	action_list_t *list;
+	// TODO: Add locks to ensure matches
+} action_list_cache_t;
+
+// ===================================================================
+// Variable
+// ===================================================================
+
+static hashtable_t table;
+
+// ===================================================================
 // Helper method declarations
 // ===================================================================
 
@@ -25,6 +40,8 @@
 
 #define CLR_STONE NUM_MASK
 
+static action_list_t *action_list_really_generate(void);
+
 static inline void
 list_append(action_list_t *list, const enum A_TYPE type,
 						const int8_t loc, const uint8_t data0,
@@ -64,7 +81,6 @@ int action_move_to_front(const action_t action,
 	return EXIT_FAILURE;
 }
 
-
 void action_list_free(action_list_t *list) {
 	if (list) {
 		action_node_t *n = list->head, *nn;
@@ -87,133 +103,9 @@ 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));
-
-	// 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 = move_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.
-					 *
-					 * We exploit the `gaps' bijection here and elsewhere
-					 * between ordered {integer partitions of n with s summands}
-					 * and {binary strings of length n-1 with s-1 set bits}.
-					 */
-					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++) {
-								uint8_t gaps =
-									((1<<(board_size - 2)) - 1) >> (board_size-steps-1);
-								// For 5x5 this givess 0b0000[0XXX] where steps-1 of
-								// those X's are 1s (starting with LSB) 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_t *action_list_generate(const uint64_t hash) {
+	// We're going to try our luck first in the table
 
-										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) {
-					list_prepend(list, A_PLACE, loc, STONE_FLAT, 0);
-					if (standing)
-						list_prepend(list, A_PLACE, loc, STONE_STANDING,0);
-				}
-				if (cap)
-					list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0);
-			}
-		}
-	}
 	return list;
 }
 
@@ -382,6 +274,136 @@ void action_to_ptn(const action_t action, char* out_ptn) {
 // Helper method implementations
 // ===================================================================
 
+// We bias place over move by prepending place actions and appending
+// move actions to the generated list
+action_list_t *action_list_really_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 = move_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.
+					 *
+					 * We exploit the `gaps' bijection here and elsewhere
+					 * between ordered {integer partitions of n with s summands}
+					 * and {binary strings of length n-1 with s-1 set bits}.
+					 */
+					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++) {
+								uint8_t gaps =
+									((1<<(board_size - 2)) - 1) >> (board_size-steps-1);
+								// For 5x5 this givess 0b0000[0XXX] where steps-1 of
+								// those X's are 1s (starting with LSB) 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
+
+										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) {
+					list_prepend(list, A_PLACE, loc, STONE_FLAT, 0);
+					if (standing)
+						list_prepend(list, A_PLACE, loc, STONE_STANDING,0);
+				}
+				if (cap)
+					list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0);
+			}
+		}
+	}
+	return list;
+}
+
 static inline void
 list_append(action_list_t *list, const enum A_TYPE type,
 						const int8_t loc, const uint8_t data0,