This matches alpha-beta!

1 files changed, 25 insertions, 346 deletions

diff --git a/include/negamax.c b/include/negamax.c
index 856f3fc..f6a7525 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -128,26 +128,19 @@ static float
 negamax(const uint8_t cur_depth, float alpha, float beta,
 				const float colour) {
 
-	/*
-	 * uint64_t hash = zobrist_compute();
-	 * tt_entry_t *entry = tt_seek(hash);
-	 * const float alpha_orig = alpha;
-	 *
-	 * if (entry != NULL && entry->depth == cur_depth) {
-	 *	if (entry->flag == TT_EXACT) {
-	 *		return entry->value;
-	 *	} else if (entry->flag == TT_LOWERBOUND) {
-	 *		alpha = fmax(alpha, entry->value);
-	 *	} else if (entry->flag == TT_UPPERBOUND) {
-	 *		beta = fmin(beta, entry->value);
-	 *	}
-	 *	if (alpha >= beta) {
-	 *		if (cur_depth == negamax_search_depth)
-	 *			action_to_ptn(entry->action, negamax_ptn);
-	 *		return entry->value;
-	 *	}
-	 * }
-	 */
+	uint64_t hash = zobrist_compute();
+	tt_entry_t *entry = tt_seek(hash);
+
+	if (entry != NULL && entry->depth == cur_depth) {
+		if (entry->flag == TT_EXACT) {
+			return entry->value;
+		} else if (entry->flag == TT_LOWERBOUND && entry->value > alpha) {
+			alpha = entry->value;
+		} else if (entry->flag == TT_UPPERBOUND && entry->value < beta) {
+			beta = entry->value;
+		}
+		if (alpha >= beta) return entry->value;
+	}
 
 	action_list_t *list;
 	if ((list = action_list_generate()) == NULL)
@@ -162,7 +155,6 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 	for (action_node_t *node=list->head; node!=NULL; node=node->next) {
 
 		action_take(node);
-
 		// Compute the value of the node
 		float node_value;
 		if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
@@ -192,331 +184,18 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 
 	action_list_free(list);
 
-	/*
-	 * flag = TT_EXACT;
-	 * if (value <= alpha_orig) flag = TT_UPPERBOUND;
-	 * else if (value >= beta) flag = TT_UPPERBOUND;
-	 *
-	 * if (entry == NULL) {
-	 *	tt_insert(hash, flag, cur_depth, value);
-	 * }
-	 */
-	/*
-	 * else {
-	 *	entry->flag = flag;
-	 *	entry->value = value;
-	 *	entry->depth = cur_depth;
-	 *	entry->action = best;
-	 * }
-	 */
+	flag = TT_EXACT;
+	if (value >= beta) flag = TT_LOWERBOUND;
+	else if (value <= alpha) flag = TT_UPPERBOUND;
+
+	if (entry == NULL) {
+		tt_insert(hash, flag, cur_depth, value);
+	} else {
+		entry->flag = flag;
+		entry->value = value;
+		entry->depth = cur_depth;
+		// entry->action = best;
+	}
 
 	return value;
 }
-
-
-/*
- * // Movement steps, orderd with the enum: UP DOWN LEFT RIGHT
- * static int8_t deltas[4];
- *
- * void negamax_init(const uint8_t new_board_size) {
- *	board_size = new_board_size;
- *	deltas[0] = +board_size;
- *	deltas[1] = -board_size;
- *	deltas[2] = -1;
- *	deltas[3] = +1;
- *	negamax_free_zobrist();
- *	negamax_init_zobrist();
- * }
- *
- * static void previous_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;
- *	}
- * }
- *
- * static void push_stones(const int8_t location,
- *												const uint8_t count,
- *												const uint8_t new_colours,
- *												const enum STONE_VARIANT top_stone) {
- *	colours[location]  = (colours[location] << count) | new_colours;
- *	celldat[location]  = top_stone
- *		| ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK);
- * }
- *
- * static enum WIN_TYPE w;
- *
- * #define WIN_EVALUATE_OR_RECURSE(store,reset) {		\
- *		w = 0xFF; \
- *		if (ply >= 2*board_size - 3) w = check_win(); \
- *		if (w < 0xFF) { \
- *			/\* Somebody won, assign weights accordingly. *\/ \
- *			if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { \
- *				value = colour*infty; \
- *				/\* Always take the win *\/ \
- *				if (value > 0) { \
- *					{ reset }; \
- *					if (cur_depth == negamax_search_depth) { store }; \
- *					goto prune; \
- *				} \
- *				/\* Fix draw value to be completely neutral *\/ \
- *			} else if (w == WIN_DRAW) value = 0; \
- *			else value = -colour*infty; \
- *		} if (cur_depth == 0) { \
- *			/\* We're at the bottom, evaluate *\/ \
- *			value = fmax(value, colour * cnn1986_evaluate_black_win()); \
- *		} else { \
- *			/\* We're not at the bottom, recurse first *\/ \
- *			next_ply(); \
- *			value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); \
- *			previous_ply(); \
- *		} \
- *		{ reset }; \
- *		/\* Update the optimal value, which alpha carries *\/ \
- *		if (value > alpha) { \
- *			alpha = value; \
- *			if (cur_depth == negamax_search_depth) { store }; \
- *			/\* Prune *\/ \
- *			if (alpha >= beta) goto prune; \
- *		} \
- *	}
- *
- * float negamax(const uint8_t cur_depth, float alpha, float beta,
- *							const float colour) {
- *
- *	/\*
- *	 * uint64_t hash = negamax_compute_zobrist();
- *	 * tt_entry_t *entry = tt_seek(hash);
- *	 * const float alpha_orig = alpha;
- *	 *
- *	 * if (entry != NULL && entry->depth >= cur_depth) {
- *	 *	if (entry->flag == TT_EXACT) {
- *	 *		return entry->value;
- *	 *	} else if (entry->flag == TT_LOWERBOUND) {
- *	 *		alpha = fmax(alpha, entry->value);
- *	 *	} else if (entry->flag == TT_UPPERBOUND) {
- *	 *		beta = fmin(beta, entry->value);
- *	 *	}
- *	 *	if (alpha >= beta) return entry->value;
- *	 * }
- *	 * enum TT_FLAG flag;
- *	 *\/
- *
- *	float value = -infty;
- *	const uint8_t black = (ply & 1),
- *		material = (black) ? black_count : white_count,
- *		flat = material & 127,
- *		cap = (ply > 2 && (material & 128)),
- *		standing = (ply > 2 && (material & 127));
- *
- *	// Step across the board
- *	for (uint8_t row = 0; row < board_size; row++) {
- *		for (uint8_t col = 0; col < board_size; col++) {
- *			// Try all valid actions for this square. Is it empty?
- *			const uint8_t loc = THE_COORDS(col, row);
- *			const uint8_t count = (COUNT_AT(loc) > board_size) ? board_size : COUNT_AT(loc);
- *			// Only try moves after CPS
- *			if (count && ((colours[loc] & 1) == current_colour) && ply>2) {
- *				// There are stones, let's try moving them
- *
- *				// Pre-compute end-stops
- *				uint8_t end_stops[4][2]; // (end, not_crush)
- *				// UP DOWN LEFT RIGHT
- *				end_stops[0][0] = (board_size - row - 1 > count) ? count : board_size - row - 1;
- *				end_stops[1][0] = (row > count) ? count : row;
- *				end_stops[2][0] = (col > count) ? count : col;
- *				end_stops[3][0] = (board_size - col - 1 > count) ? count : board_size - col - 1;
- *				const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
- *				for (uint8_t d = 0; d < board_size-1; d++){
- *					end_stops[d][1] = 1;
- *					const uint8_t stop = end_stops[d][0];
- *					end_stops[d][0] = 0;
- *					for (uint8_t k = 1; k <= stop; k++) {
- *						const uint8_t stone = STONE_AT(loc+k*deltas[d]);
- *						if (stone == STONE_STANDING) {
- *							if (cap_top) {
- *								end_stops[d][1] = 0;
- *								end_stops[d][0]++;
- *							}
- *							break;
- *						} else if (stone == STONE_CAPSTONE) {
- *							break;
- *						}
- *						end_stops[d][0]++;
- *					}
- *				}
- *
- *				uint16_t colours_backup[board_size];
- *				uint8_t celldat_backup[board_size], drops[board_size];
- *				// we only ever need board_size-1 in drops actually, the
- *				// last spot is to skip a bounds check at (*)
- *
- *				//Back up the rows of the board
- *				for (uint8_t y = 0; y < board_size; y++) {
- *					colours_backup[y] = colours[THE_COORDS(col, y)];
- *					celldat_backup[y] = celldat[THE_COORDS(col, y)];
- *				}
- *
- *				// I'm not a huge fan of looping through enums, but it's
- *				// better than manually unrolling this. Sufficiently smart
- *				// compilers?
- *				for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) {
- *					// Back-up the column once we start looking horizontally
- *					if (dir == M_LEFT) {
- *						for (uint8_t x = 0; x < board_size; x++) {
- *							colours_backup[x] = colours[THE_COORDS(x, row)];
- *							celldat_backup[x] = celldat[THE_COORDS(x, row)];
- *						}
- *					}
- *					/\*
- *					 * We don't do anything terribly efficient here just try
- *					 * all the ordered partitions of num ∈ {1 … end_stop}, and
- *					 * skip the partition if it calls for multiple stones at
- *					 * the end with a crush.
- *					 *\/
- *					uint8_t gaps, t, idx, mask;
- *					for (uint8_t num = 1; num <= count; num++) {
- *						for (uint8_t steps = 1;
- *								 steps <= end_stops[dir][0] && steps <= num;
- *								 steps++) {
- *							// TODO: Generalise to board_size!
- *							gaps = 0x07 >> (board_size-steps-1);
- *							// 0b0000[0111] because 4-1=3 and 5-1=4
- *							do  {
- *								// Ensure legal move if we have to crush
- *								const uint8_t last_drop_check =
- *									(num > 1) ? (gaps & 1<<(num - 2)) : 1;
- *								if (end_stops[dir][1] || last_drop_check) {
- *									// Translate to a drop sequence
- *									drops[0] = 1; mask = 1; idx = 0;
- *									for (uint8_t d = 0; d + 1 < num; d++) {
- *										if (gaps & mask) {
- *											idx++;
- *											drops[idx] = 1; // (*) no bounds check
- *										} else {
- *											drops[idx] += 1;
- *										}
- *										mask <<= 1;
- *									}
- *									// Do it, and manually check for win if it's valid
- *									uint8_t j = num;
- *									for (uint8_t k = 0; k < steps; k++) {
- *										j -= drops[k];
- *										push_stones(loc+(k+1)*deltas[dir],
- *																drops[k],
- *																(colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])),
- *																(k == steps - 1) ? STONE_AT(loc) : STONE_FLAT);
- *									}
- *									// Then we drop them from the source
- *									colours[loc] >>= num;
- *									const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT);
- *									celldat[loc] = dec_count & NUM_MASK;
- *
- *									// First check for wins, if we're at the bottom
- *									// evaluate, otherwise recurse
- *									WIN_EVALUATE_OR_RECURSE({
- *											// If we did update the optimal value, store
- *											// this move
- *											generate_move(loc, dir, steps, drops, negamax_ptn);
- *										},{
- *											// Reset the board data after recursing or
- *											// before returning
- *											if (dir <= M_DOWN) {
- *												for (uint8_t y = 0; y < board_size; y++) {
- *													colours[THE_COORDS(col, y)] = colours_backup[y];
- *													celldat[THE_COORDS(col, y)] = celldat_backup[y];
- *												}
- *											} else {
- *												for (uint8_t x = 0; x < board_size; x++) {
- *													colours[THE_COORDS(x, row)] = colours_backup[x];
- *													celldat[THE_COORDS(x, row)] = celldat_backup[x];
- *												}
- *											}
- *										});
- *								}
- *								/\*
- *								 * 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
- *								 *\/
- *								t = (gaps | (gaps - 1));
- *								gaps = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
- *							} while (gaps && (gaps + 1 <= (1<<(num-1))));
- *						}
- *					}
- *				}
- *			} else if (material && count == 0) {
- *				// Empty square, try placements
- *
- *				if (flat) {
- *					// Generate the placement
- *					if (black) black_count--;
- *					else white_count--;
- *					colours[loc] = current_colour;
- *					celldat[loc] = NUM_INC | STONE_FLAT;
- *					WIN_EVALUATE_OR_RECURSE({
- *							// If we did update the optimal value, store
- *							generate_place(loc, STONE_FLAT, negamax_ptn);
- *						},{
- *							// Reset the state
- *							celldat[loc] = 0;
- *							if (black) black_count++;
- *							else white_count++;
- *						});
- *					// Do the same for walls, can't happen without flats
- *					if (standing) {
- *						if (black) black_count--;
- *						else white_count--;
- *						colours[loc] = current_colour;
- *						celldat[loc] = NUM_INC | STONE_STANDING;
- *						WIN_EVALUATE_OR_RECURSE({
- *								generate_place(loc, STONE_STANDING, negamax_ptn);
- *							},{
- *								celldat[loc] = 0;
- *								if (black) black_count++;
- *								else white_count++;
- *							});
- *					}
- *				}
- *
- *				// and for caps
- *				if (cap) {
- *					if (black) black_count &= 127;
- *					else white_count &= 127;
- *					colours[loc] = current_colour;
- *					celldat[loc] = NUM_INC | STONE_CAPSTONE;
- *					WIN_EVALUATE_OR_RECURSE({
- *							generate_place(loc, STONE_CAPSTONE, negamax_ptn);
- *						},{
- *							celldat[loc] = 0;
- *							if (black) black_count |= 128;
- *							else white_count |= 128;
- *						});
- *				}
- *			}
- *			negamax_display_progress(cur_depth);
- *		}
- *	}
- *
- *  prune:
- *	/\*
- *	 * flag = TT_EXACT;
- *	 * if (value <= alpha_orig) flag = TT_UPPERBOUND;
- *	 * else if (value >= beta) flag = TT_UPPERBOUND;
- *	 *
- *	 * if (entry == NULL) {
- *	 *	tt_insert(hash, flag, cur_depth, value);
- *	 * } else {
- *	 *	entry->flag = flag;
- *	 *	entry->value = value;
- *	 *	entry->depth = cur_depth;
- *	 * }
- *	 *\/
- *
- *	return value;
- * }
- */