commit 94020bc7570a018b87e0e03c582bd130a0724ea2
Author: MikoĊaj Lenczewski <mblenczewski@gmail.com>
Date: Sun, 5 Jan 2025 01:35:30 +0000
Initial commit
Diffstat:
6 files changed, 720 insertions(+), 0 deletions(-)
diff --git a/.editorconfig b/.editorconfig
@@ -0,0 +1,18 @@
+root = true
+
+[*]
+end_of_line = lf
+charset = utf-8
+trim_trailing_whitespace = true
+insert_final_newline = true
+
+# visual studio editorconfig plugin specific settings
+guidelines = 80, 120, 160
+
+[*.{c,h}]
+indent_style = tab
+indent_size = 8
+
+[*.sh]
+indent_style = tab
+indent_size = 8
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,4 @@
+minimax
+
+imgui.ini
+**/.*.swp
diff --git a/build.sh b/build.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+
+set -ex
+
+cc -o minimax minimax.c -Wall -Wextra -Wpedantic -g -O0 -std=c11 -lm
diff --git a/clean.sh b/clean.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+
+set -ex
+
+rm -rf minimax
diff --git a/debug.sh b/debug.sh
@@ -0,0 +1,3 @@
+#!/bin/sh
+
+lldbgui ./minimax
diff --git a/minimax.c b/minimax.c
@@ -0,0 +1,685 @@
+#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 <alloca.h>
+#include <assert.h>
+#include <stdalign.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <math.h>
+
+#include <sys/mman.h>
+
+/* 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 {
+ struct list_node *prev, *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)
+{
+ if (list->head)
+ list->head->prev = 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.prev = node->list_node.next = NULL;
+}
+
+#define IS_TERMINAL_NODE(node) ((node)->children.head == NULL)
+
+#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(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 max_depth)
+{
+ size_t available_moves = get_available_moves(board, NULL);
+ assert(available_moves);
+
+ struct move moves[available_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_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_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_depth);
+ if (value >= best_value) {
+ best_value = value;
+ best_move = tree->move;
+ }
+ }
+
+ *out = best_value;
+
+ return best_move;
+}
+
+/* main definition
+ * ===========================================================================
+ */
+
+#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)
+{
+ char *line = NULL;
+ size_t len;
+ while (true) {
+ ssize_t res = getline(&line, &len, stdin);
+ if (res < 0)
+ exit(EXIT_FAILURE);
+
+ size_t coord;
+ if (sscanf(line, "%zu", &coord)) {
+ free(line);
+ 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
+ int prot = PROT_READ|PROT_WRITE;
+ int flags = MAP_PRIVATE|MAP_ANONYMOUS;
+ struct arena arena = {
+ .ptr = mmap(NULL, ARENA_SIZE, prot, flags, -1, 0),
+ .cap = ARENA_SIZE,
+ .len = 0,
+ };
+
+ assert(arena.ptr != MAP_FAILED);
+
+ madvise(arena.ptr, arena.cap, MADV_HUGEPAGE);
+
+ 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);
+
+ 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);
+
+ 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, 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);
+
+ 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");
+ }
+
+ break;
+ }
+
+ if (game_over(&board, &winner))
+ break;
+
+ /* ai move */
+ 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
+
+ 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;
+}
