minimax

minimax.c (15024B)

---

 #ifdef _XOPEN_SOURCE
 # undef _XOPEN_SOURCE
 #endif
 
 #define _XOPEN_SOURCE 700
 
 #ifndef _GNU_SOURCE
 # define _GNU_SOURCE 1
 #endif
 
 #ifndef _BSD_SOURCE
 # define _BSD_SOURCE 1
 #endif
 
 #ifndef _DEFAULT_SOURCE
 # define _DEFAULT_SOURCE 1
 #endif
 
 #include <assert.h>
 #include <stdalign.h>
 #include <stddef.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 #include <math.h>
 
 #if defined(__linux__)
 # include <alloca.h>
 # include <sys/mman.h>
 # define alloca_impl alloca
 #elif defined(_WIN32)
 # include <malloc.h>
 # define alloca_impl _alloca
 #endif
 
 /* configuration
  * ===========================================================================
  */
 
 #define KiB 1024ULL
 #define MiB (1024 * KiB)
 #define GiB (1024 * MiB)
 
 #define ARENA_SIZE 1 * GiB
 
 // length of one side of the game board
 #define BOARD_SIZE 3
 
 // maximum depth at which to search using minimax
 // NOTE: this is reduced if the memory arena would not allow for this depth
 #define MAX_SEARCH_DEPTH 11
 
 // test minimax algorithm on first move of game
 #define MINIMAX_DEBUG 0
 
 /* utils
  * ===========================================================================
  */
 
 #define true 1
 #define false 0
 
 #define MAX(a, b) (((a) > (b)) ? (a) : (b))
 #define MIN(a, b) (((a) < (b)) ? (a) : (b))
 
 struct arena {
 	void *ptr;
 	uint64_t cap, len;
 };
 
 static inline void
 arena_reset(struct arena *arena)
 {
 	arena->len = 0;
 }
 
 #define ALIGN_PREV(v, align) ((v) & ~((align) - 1))
 #define ALIGN_NEXT(v, align) ALIGN_PREV((v) + ((align) - 1), (align))
 
 static inline void *
 arena_alloc(struct arena *arena, size_t size, size_t align)
 {
 	uint64_t aligned_len = ALIGN_NEXT(arena->len, align);
 	if (aligned_len + size > arena->cap)
 		return NULL;
 
 	void *ptr = (void *) ((uintptr_t) arena->ptr + aligned_len);
 	arena->len = aligned_len + size;
 
 	return ptr;
 }
 
 #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 *next;
 };
 
 #define FROM_NODE(node, T, member) \
 	((T *) ((uintptr_t) node - offsetof(T, member)))
 
 #define list_node_iter(node) \
 	for (struct list_node *it = node; it; it = it->next)
 
 struct list {
 	struct list_node *head;
 };
 
 #define list_iter(list) \
 	list_node_iter(list->head)
 
 static inline void
 list_push(struct list *restrict list, struct list_node *restrict node)
 {
 	node->next = list->head;
 	list->head = node;
 }
 
 /* tic-tac-toe definitions
  * ===========================================================================
  */
 
 enum player {
 	EMPTY = 0,
 	BLACK = +1,
 	WHITE = -1,
 };
 
 static inline enum player
 get_opponent(enum player player)
 {
 	switch (player) {
 	case EMPTY: return EMPTY;
 	case BLACK: return WHITE;
 	case WHITE: return BLACK;
 	}
 }
 
 static inline char
 get_player_char(enum player player)
 {
 	switch (player) {
 	case EMPTY: return '.';
 	case BLACK: return 'B';
 	case WHITE: return 'W';
 	}
 }
 
 static inline char const *
 get_player_str(enum player player)
 {
 	switch (player) {
 	case EMPTY: return "EMPTY";
 	case BLACK: return "BLACK";
 	case WHITE: return "WHITE";
 	}
 }
 
 struct cell {
 	int8_t state;
 };
 
 struct board {
 	struct cell cells[BOARD_SIZE * BOARD_SIZE];
 };
 
 static inline struct cell *
 get_cell_ptr(struct board *board, size_t i, size_t j)
 {
 	return &board->cells[j * BOARD_SIZE + i];
 }
 
 struct move {
 	uint8_t i, j;
 };
 
 static inline int
 try_play_move(struct board *board, struct move move, enum player player)
 {
 	if (BOARD_SIZE <= move.i || BOARD_SIZE <= move.j)
 		return false;
 
 	struct cell *cell = get_cell_ptr(board, move.i, move.j);
 	if (cell->state != EMPTY)
 		return false;
 
 	cell->state = player;
 
 	return true;
 }
 
 static inline void
 undo_move(struct board *board, struct move move)
 {
 	struct cell *cell = get_cell_ptr(board, move.i, move.j);
 	cell->state = EMPTY;
 }
 
 static size_t
 get_available_moves(struct board *restrict board, struct move *restrict buf)
 {
 	size_t moves = 0;
 	for (size_t j = 0; j < BOARD_SIZE; j++) {
 		for (size_t i = 0; i < BOARD_SIZE; i++) {
 			if (get_cell_ptr(board, i, j)->state == EMPTY) {
 				if (buf)
 					*buf++ = (struct move) {i, j};
 
 				moves++;
 			}
 		}
 	}
 
 	return moves;
 }
 
 static enum player
 get_winner(struct board *board)
 {
 	for (size_t j = 0; j < BOARD_SIZE; j++) { /* check rows */
 		enum player winner = get_cell_ptr(board, 0, j)->state;
 
 		int contiguous = true;
 		for (size_t i = 0; i < BOARD_SIZE; i++) {
 			if (get_cell_ptr(board, i, j)->state != winner)
 				contiguous = false;
 		}
 
 		if (contiguous)
 			return winner;
 	}
 
 	for (size_t i = 0; i < BOARD_SIZE; i++) { /* check cols */
 		enum player winner = get_cell_ptr(board, i, 0)->state;
 
 		int contiguous = true;
 		for (size_t j = 0; j < BOARD_SIZE; j++) {
 			if (get_cell_ptr(board, i, j)->state != winner)
 				contiguous = false;
 		}
 
 		if (contiguous)
 			return winner;
 	}
 
 	{
 		enum player winner = get_cell_ptr(board, 0, 0)->state;
 
 		int contiguous = true;
 		for (size_t k = 0; k < BOARD_SIZE; k++) { /* check (k,k) diagonal */
 			if (get_cell_ptr(board, k, k)->state != winner)
 				contiguous = false;
 		}
 
 		if (contiguous)
 			return winner;
 	}
 
 	{
 		enum player winner = get_cell_ptr(board, 0, BOARD_SIZE - 1)->state;
 
 		int contiguous = true;
 		for (size_t k = 0; k < BOARD_SIZE; k++) { /* check (k,k) diagonal */
 			if (get_cell_ptr(board, k, BOARD_SIZE - 1 - k)->state != winner)
 				contiguous = false;
 		}
 
 		if (contiguous)
 			return winner;
 	}
 
 	return EMPTY;
 }
 
 static int
 game_over(struct board *board, enum player *winner)
 {
 	size_t moves = get_available_moves(board, NULL);
 
 	if ((*winner = get_winner(board)) || !moves) /* winner, or a draw */
 		return true;
 
 	return false;
 }
 
 static inline void
 draw_board_row_divider(void)
 {
 	printf("-");
 	for (size_t i = 0; i < BOARD_SIZE; i++)
 		printf("----");
 	printf("\n");
 }
 
 static void
 print_board(struct board *board)
 {
 	draw_board_row_divider();
 
 	for (size_t j = 0; j < BOARD_SIZE; j++) {
 		printf("|");
 		for (size_t i = 0; i < BOARD_SIZE; i++) {
 			enum player cell = get_cell_ptr(board, i, j)->state;
 			printf(" %c |", get_player_char(cell));
 		}
 		printf("\n");
 
 		draw_board_row_divider();
 	}
 }
 
 /* minimax definitions
  * ===========================================================================
  */
 
 struct minimax {
 	struct list possible_moves;
 };
 
 struct minimax_node {
 	// NOTE: we can use this to avoid false-aliasing of cachelines
 	alignas(64)
 
 	struct move move;
 	int8_t player;
 
 	struct list children;
 	struct list_node list_node;
 };
 
 static inline void
 minimax_node_init(struct minimax_node *node, struct move move, enum player player)
 {
 	node->move = move;
 	node->player = player;
 	node->children.head = 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
 dump_tree(FILE *fp, struct minimax_node const *node, size_t depth, size_t max_depth)
 {
 #define LEADER(fp, depth) \
 	for (size_t i = 0; i < depth; i++) fprintf(fp, "  ");
 
 	LEADER(fp, depth);
 	fprintf(fp, "node: {move: {i: %u, j: %u}, player: %s}\n",
 			node->move.i, node->move.j, get_player_str(node->player));
 
 	if (depth + 1 == max_depth) {
 		LEADER(fp, depth + 1);
 		fprintf(fp, "...\n");
 		return;
 	}
 
 	struct list const *list = &node->children;
 	list_iter(list) {
 		struct minimax_node *child = FROM_NODE(it, struct minimax_node, list_node);
 		dump_tree(fp, child, depth + 1, max_depth);
 	}
 #undef LEADER
 }
 
 static void
 minimax_dump_trees(struct minimax *minimax, FILE *fp, size_t max_depth)
 {
 	struct list *list = &minimax->possible_moves;
 	list_iter(list) {
 		struct minimax_node *tree = FROM_NODE(it, struct minimax_node, list_node);
 		dump_tree(fp, tree, 0, max_depth);
 	}
 }
 
 #endif
 
 static struct minimax_node *
 create_tree(struct board *board, struct move move, enum player player,
 	    struct arena *arena, size_t depth, size_t max_depth)
 {
 	struct minimax_node *node = ALLOC_SIZED(arena, struct minimax_node);
 	assert(node);
 
 	minimax_node_init(node, move, player);
 
 	int res = try_play_move(board, node->move, node->player);
 	assert(res);
 
 	if (depth == max_depth)
 		goto end;
 
 	size_t available_moves = get_available_moves(board, NULL);
 	if (!available_moves)
 		goto end;
 
 	struct move *moves = alloca_impl(available_moves * sizeof *moves);
 	get_available_moves(board, moves);
 
 	for (size_t i = 0; i < available_moves; i++) {
 		struct minimax_node *child = create_tree(board, moves[i],
 							 get_opponent(player),
 							 arena, depth + 1, max_depth);
 
 		list_push(&node->children, &child->list_node);
 	}
 
 end:
 	undo_move(board, node->move);
 
 	return node;
 }
 
 static float
 heuristic(struct minimax_node *node, struct board *board, enum player maximising_player)
 {
 	enum player winner;
 	if ((winner = get_winner(board))) { /* this is a winning move */
 		return (winner == maximising_player) ? +INFINITY : -INFINITY;
 	}
 
 	size_t moves = get_available_moves(board, NULL);
 	if (!moves) /* no winner and no moves left to make, draw */
 		return 0;
 
 	// TODO: is there a better heuristic than assuming a loss?
 	return (node->player == maximising_player) ? -INFINITY : +INFINITY;
 }
 
 static float
 minimax(struct minimax_node *node, struct board *board, enum player maximising_player,
 	size_t max_depth)
 {
 	float result;
 
 	int res = try_play_move(board, node->move, node->player);
 	assert(res);
 
 	if (!max_depth || IS_TERMINAL_NODE(node)) {
 		result = heuristic(node, board, maximising_player);
 		goto end;
 	}
 
 	if (node->player == maximising_player) {
 		float max_value = -INFINITY;
 
 		struct list *list = &node->children;
 		list_iter(list) {
 			struct minimax_node *child = FROM_NODE(it, struct minimax_node, list_node);
 			float value = minimax(child, board, maximising_player, max_depth - 1);
 			max_value = MAX(max_value, value);
 		}
 
 		result = max_value;
 	} else /* node->player == minimising_player */ {
 		float min_value = +INFINITY;
 
 		struct list *list = &node->children;
 		list_iter(list) {
 			struct minimax_node *child = FROM_NODE(it, struct minimax_node, list_node);
 			float value = minimax(child, board, maximising_player, max_depth - 1);
 			min_value = MIN(min_value, value);
 		}
 
 		result = min_value;
 	}
 
 end:
 	undo_move(board, node->move);
 
 	return result;
 }
 
 static struct move
 minimax_get_best_move(struct minimax *self, struct board *board, enum player player,
 		      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 = alloca_impl(available_moves * sizeof *moves);
 	get_available_moves(board, moves);
 
 	self->possible_moves.head = NULL;
 
 	float best_value = -INFINITY;
 	struct move best_move;
 
 	for (size_t i = 0; i < available_moves; i++) {
 		arena_reset(arena);
 
 #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_search_depth);
 #endif
 
 		// NOTE: we limit the depth of the minimax tree to avoid
 		//       running out of memory, but if we could employ
 		//       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_search_depth);
 		assert(tree);
 
 #if MINIMAX_DEBUG
 		fprintf(stderr, "created tree with %zu/%zu nodes\n",
 				arena->len / sizeof(struct minimax_node),
 				arena->cap / sizeof(struct minimax_node));
 #endif
 
 
 		list_push(&self->possible_moves, &tree->list_node);
 
 		float value = minimax(tree, board, player, max_search_depth);
 		if (value >= best_value) {
 			best_value = value;
 			best_move = tree->move;
 		}
 	}
 
 	*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;
 }
 
 /* main definition
  * ===========================================================================
  */
 
 static size_t
 get_input_coord(void)
 {
 	char buf[64];
 	while (true) {
 		char *line = fgets(buf, sizeof buf, stdin);
 
 		size_t coord;
 		if (sscanf(line, "%zu", &coord)) {
 			return coord;
 		} else {
 			printf("invalid coordinate. try again.\n");
 		}
 	}
 }
 
 int
 main(void)
 {
 	// NOTE: we use an arena to avoid expensive system allocators, and so
 	//       that we can easily free all nodes without iterating the tree
 	struct arena arena;
 
 #if defined(__linux__)
 	int prot = PROT_READ|PROT_WRITE;
 	int flags = MAP_PRIVATE|MAP_ANONYMOUS;
 	arena.ptr = mmap(NULL, ARENA_SIZE, prot, flags, -1, 0);
 	arena.cap = ARENA_SIZE;
 	arena.len = 0;
 
 	assert(arena.ptr != MAP_FAILED);
 
 	madvise(arena.ptr, arena.cap, MADV_HUGEPAGE);
 #elif defined(_WIN32)
 	arena.ptr = malloc(ARENA_SIZE);
 	arena.cap = ARENA_SIZE;
 	arean.len = 0;
 
 	assert(arena.ptr);
 #endif
 
 	size_t max_nodes = arena.cap / sizeof(struct minimax_node);
 	fprintf(stderr, "Arena cap: %zu bytes, node size: %zu bytes, max node count: %zu\n",
 			arena.cap, sizeof(struct minimax_node), max_nodes);
 
 	struct minimax minimax;
 	memset(&minimax, 0, sizeof minimax);
 
 	struct board board;
 	memset(&board, 0, sizeof board);
 
 #if MINIMAX_DEBUG
 	float value;
 	struct move move = minimax_get_best_move(&minimax, &board, BLACK, &value, &arena);
 
 	int res = try_play_move(&board, move, BLACK);
 	assert(res);
 
 	return 0;
 
 #endif
 
 	enum player winner;
 	while (true) {
 		print_board(&board);
 
 		/* player move */
 		struct move player_move;
 		while (true) {
 			printf("user x coord (between 0 and %d):\n", BOARD_SIZE - 1);
 			size_t x = get_input_coord();
 
 			printf("user y coord (between 0 and %d):\n", BOARD_SIZE - 1);
 			size_t y = get_input_coord();
 
 			player_move.i = x;
 			player_move.j = y;
 
 			if (!try_play_move(&board, player_move, BLACK)) {
 				printf("move already made! try again.\n");
 				continue;
 			}
 
 			break;
 		}
 
 		if (game_over(&board, &winner))
 			break;
 
 		/* ai move */
 		float value;
 		struct move best_move = minimax_get_best_move(&minimax, &board,
 							      WHITE, &value,
 							      &arena);
 
 		int res = try_play_move(&board, best_move, WHITE);
 		assert(res);
 
 		if (game_over(&board, &winner))
 			break;
 	}
 
 	print_board(&board);
 
 	if (winner == BLACK) {
 		printf("Player won the game.\n");
 	} else if (winner == WHITE) {
 		printf("Player lost the game.\n");
 	} else {
 		printf("Player drew the game.\n");
 	}
 
 	return 0;
 }