minimax

commit 8f973f3838bff33f539d02acae5b4ed7c05e5113
parent 94020bc7570a018b87e0e03c582bd130a0724ea2
Author: Mikołaj Lenczewski <mblenczewski@gmail.com>
Date:   Sun,  5 Jan 2025 14:17:51 +0000

Make max search depth adaptive

Diffstat:
M
minimax.c
 | 
102
+++++++++++++++++++++++++++++++++++--------------------------------------------

1 file changed, 45 insertions(+), 57 deletions(-)
diff --git a/minimax.c b/minimax.c
@@ -89,9 +89,8 @@ arena_alloc(struct arena *arena, size_t size, size_t align)
 #define ALLOC_ARRAY(arena, T, n) arena_alloc((arena), sizeof(T) * (n), alignof(T))
 #define ALLOC_SIZED(arena, T) ALLOC_ARRAY((arena), T, 1)
 
-struct list_node;
 struct list_node {
-	struct list_node *prev, *next;
+	struct list_node *next;
 };
 
 #define FROM_NODE(node, T, member) \
@@ -110,9 +109,6 @@ struct list {
 static inline void
 list_push(struct list *restrict list, struct list_node *restrict node)
 {
-	if (list->head)
-		list->head->prev = node;
-
 	node->next = list->head;
 	list->head = node;
 }
@@ -320,7 +316,7 @@ struct minimax {
 
 struct minimax_node {
 	// NOTE: we can use this to avoid false-aliasing of cachelines
-	//alignas(64)
+	alignas(64)
 
 	struct move move;
 	int8_t player;
@@ -335,11 +331,33 @@ minimax_node_init(struct minimax_node *node, struct move move, enum player playe
 	node->move = move;
 	node->player = player;
 	node->children.head = NULL;
-	node->list_node.prev = node->list_node.next = NULL;
+	node->list_node.next = NULL;
 }
 
 #define IS_TERMINAL_NODE(node) ((node)->children.head == NULL)
 
+static inline size_t
+nodecount(size_t available_moves, size_t max_depth)
+{
+	size_t res = available_moves;
+
+	while (max_depth-- && --available_moves)
+		res = res * available_moves;
+
+	return res;
+}
+
+static size_t
+max_depth_for_node_cap(size_t available_moves, size_t cap)
+{
+	size_t depth, nodes;
+	for (depth = 0; depth < available_moves; depth++)
+		if ((nodes = nodecount(available_moves, depth)) > cap)
+			return depth;
+
+	return depth;
+}
+
 #if 0
 
 static void
@@ -476,11 +494,20 @@ end:
 
 static struct move
 minimax_get_best_move(struct minimax *self, struct board *board, enum player player,
-		      float *out, struct arena *arena, size_t max_depth)
+		      float *out, struct arena *arena)
 {
 	size_t available_moves = get_available_moves(board, NULL);
 	assert(available_moves);
 
+	size_t max_nodes = arena->cap / sizeof(struct minimax_node);
+	size_t max_search_depth = MIN(MAX_SEARCH_DEPTH,
+				      max_depth_for_node_cap(available_moves, max_nodes));
+
+#if MINIMAX_DEBUG
+	fprintf(stderr, "Maximum search depth: %zu, using %zu/%zu nodes\n",
+			max_search_depth, nodecount(available_moves, max_search_depth), max_nodes);
+#endif
+
 	struct move moves[available_moves];
 	get_available_moves(board, moves);
 
@@ -494,7 +521,7 @@ minimax_get_best_move(struct minimax *self, struct board *board, enum player pla
 
 #if MINIMAX_DEBUG
 		fprintf(stderr, "starting minimax tree for root node: {i: %u, j: %u} with depth: %zu\n",
-				moves[i].i, moves[i].j, max_depth);
+				moves[i].i, moves[i].j, max_search_depth);
 #endif
 
 		// NOTE: we limit the depth of the minimax tree to avoid
@@ -502,7 +529,7 @@ minimax_get_best_move(struct minimax *self, struct board *board, enum player pla
 		//       memoization of similar game states we could greatly
 		//       reduce the need for this limit
 		struct minimax_node *tree = create_tree(board, moves[i], player,
-							arena, 0, max_depth);
+							arena, 0, max_search_depth);
 		assert(tree);
 
 #if MINIMAX_DEBUG
@@ -514,7 +541,7 @@ minimax_get_best_move(struct minimax *self, struct board *board, enum player pla
 
 		list_push(&self->possible_moves, &tree->list_node);
 
-		float value = minimax(tree, board, player, max_depth);
+		float value = minimax(tree, board, player, max_search_depth);
 		if (value >= best_value) {
 			best_value = value;
 			best_move = tree->move;
@@ -523,6 +550,11 @@ minimax_get_best_move(struct minimax *self, struct board *board, enum player pla
 
 	*out = best_value;
 
+#if MINIMAX_DEBUG
+		fprintf(stderr, "Best move for %s: {i: %u, j: %u}, value: %f\n",
+				get_player_str(player), best_move.i, best_move.j, best_value);
+#endif
+
 	return best_move;
 }
 
@@ -530,36 +562,6 @@ minimax_get_best_move(struct minimax *self, struct board *board, enum player pla
  * ===========================================================================
  */
 
-#define BOARD_SIZE2 (BOARD_SIZE * BOARD_SIZE)
-
-static inline size_t
-factorial(size_t n, size_t steps)
-{
-	size_t res = n;
-
-	while (steps-- && --n)
-		res = res * n;
-
-	return res;
-}
-
-static inline size_t
-nodecount(size_t depth)
-{
-	return factorial(BOARD_SIZE2, depth);
-}
-
-static size_t
-max_tree_depth_for_node_cap(size_t cap)
-{
-	size_t depth, nodes;
-	for (depth = 0; depth < BOARD_SIZE2; depth++)
-		if ((nodes = nodecount(depth)) > cap)
-			return depth;
-
-	return depth;
-}
-
 static size_t
 get_input_coord(void)
 {
@@ -601,12 +603,6 @@ main(void)
 	fprintf(stderr, "Arena cap: %zu bytes, node size: %zu bytes, max node count: %zu\n",
 			arena.cap, sizeof(struct minimax_node), max_nodes);
 
-	size_t max_search_depth = MIN(MAX_SEARCH_DEPTH,
-				      max_tree_depth_for_node_cap(max_nodes));
-
-	fprintf(stderr, "Max tree depth: %zu (%zu/%zu nodes)\n",
-			max_search_depth, nodecount(max_search_depth), max_nodes);
-
 	struct minimax minimax;
 	memset(&minimax, 0, sizeof minimax);
 
@@ -615,10 +611,7 @@ main(void)
 
 #if MINIMAX_DEBUG
 	float value;
-	struct move move = minimax_get_best_move(&minimax, &board, BLACK, &value, &arena, max_search_depth);
-
-	fprintf(stderr, "Best move for %s: {i: %u, j: %u}, value: %f\n",
-			get_player_str(BLACK), move.i, move.j, value);
+	struct move move = minimax_get_best_move(&minimax, &board, BLACK, &value, &arena);
 
 	int res = try_play_move(&board, move, BLACK);
 	assert(res);
@@ -657,12 +650,7 @@ main(void)
 		float value;
 		struct move best_move = minimax_get_best_move(&minimax, &board,
 							      WHITE, &value,
-							      &arena, max_search_depth);
-
-#if MINIMAX_DEBUG
-		fprintf(stderr, "Best move for %s: {i: %u, j: %u}, value: %f\n",
-				get_player_str(WHITE), best_move.i, best_move.j, value);
-#endif
+							      &arena);
 
 		int res = try_play_move(&board, best_move, WHITE);
 		assert(res);