hexes.h (11440B)
1 #ifndef HEXES_H 2 #define HEXES_H 3 4 #ifdef _XOPEN_SOURCE 5 #undef _XOPEN_SOURCE 6 #endif 7 8 #define _XOPEN_SOURCE 700 9 10 #ifndef _GNU_SOURCE 11 #define _GNU_SOURCE 1 12 #endif 13 14 #ifndef _DEFAULT_SOURCE 15 #define _DEFAULT_SOURCE 1 16 #endif 17 18 #include "hex.h" 19 20 #include <assert.h> 21 #include <errno.h> 22 #include <inttypes.h> 23 #include <stdalign.h> 24 #include <stdarg.h> 25 #include <stdbool.h> 26 #include <stddef.h> 27 #include <stdint.h> 28 #include <stdio.h> 29 #include <stdlib.h> 30 #include <string.h> 31 32 #include <arpa/inet.h> 33 #include <math.h> 34 #include <time.h> 35 #include <unistd.h> 36 37 #include <sys/types.h> 38 #include <sys/socket.h> 39 #include <netdb.h> 40 41 #include <sys/mman.h> 42 43 typedef int32_t b32; 44 45 typedef unsigned char c8; 46 47 typedef uint8_t u8; 48 typedef uint16_t u16; 49 typedef uint32_t u32; 50 typedef uint64_t u64; 51 52 typedef int8_t s8; 53 typedef int16_t s16; 54 typedef int32_t s32; 55 typedef int64_t s64; 56 57 typedef float f32; 58 typedef double f64; 59 60 #define ARRLEN(arr) (sizeof (arr) / sizeof (arr)[0]) 61 62 #define MIN(a, b) ((a) > (b) ? (a) : (b)) 63 #define MAX(a, b) ((a) < (b) ? (b) : (a)) 64 65 /* NOTE: we define a relative pointer helper to allow fully relocatable data 66 * structures, for example to allow for trees that survive a memcpy() 67 */ 68 69 #define RELPTR_NULL (0) 70 71 #define _RELPTR_MASK(ty_relptr) ((ty_relptr)1 << ((sizeof(ty_relptr) * 8) - 1)) 72 73 #define _RELPTR_ENC(ty_relptr, ptroff) \ 74 ((ty_relptr) ((ptroff) ^ _RELPTR_MASK(ty_relptr))) 75 76 #define _RELPTR_DEC(ty_relptr, relptr) \ 77 ((ty_relptr) ((relptr) ^ _RELPTR_MASK(ty_relptr))) 78 79 #define RELPTR_ABS2REL(ty_relptr, base, absptr) \ 80 ((absptr) \ 81 ? _RELPTR_ENC(ty_relptr, (u8 *) absptr - (u8 *) base) \ 82 : RELPTR_NULL) 83 84 #define RELPTR_REL2ABS(ty_absptr, ty_relptr, base, relptr) \ 85 (((relptr) != RELPTR_NULL) \ 86 ? ((ty_absptr) ((u8 *) base + _RELPTR_DEC(ty_relptr, relptr))) \ 87 : NULL) 88 89 #define NANOSECS (1000000000ULL) 90 91 #define TIMESPEC_TO_NANOS(sec, nsec) (((u64) (sec) * NANOSECS) + (nsec)) 92 93 #define KiB (1024ULL) 94 #define MiB (1024ULL * KiB) 95 #define GiB (1024ULL * MiB) 96 97 struct opts { 98 u32 log_level, agent_type; 99 char *host, *port; 100 }; 101 102 extern struct opts opts; 103 104 /* utility definitions 105 * =========================================================================== 106 */ 107 108 enum log_level { 109 LOG_ERROR, 110 LOG_WARN, 111 LOG_INFO, 112 LOG_DEBUG, 113 }; 114 115 inline void 116 dbglog(enum log_level log_level, char const *fmt, ...) 117 { 118 if (opts.log_level < log_level) return; 119 120 switch (log_level) { 121 case LOG_ERROR: fputs("[ERROR]", stderr); break; 122 case LOG_WARN: fputs("[WARN] ", stderr); break; 123 case LOG_INFO: fputs("[INFO] ", stderr); break; 124 case LOG_DEBUG: fputs("[DEBUG]", stderr); break; 125 } 126 127 fputc(' ', stderr); 128 129 va_list ap; 130 va_start(ap, fmt); 131 vfprintf(stderr, fmt, ap); 132 va_end(ap); 133 } 134 135 136 inline void 137 swap(void *restrict lhs, void *restrict rhs, size_t size) 138 { 139 assert(lhs); 140 assert(rhs); 141 assert(size); 142 143 u8 tmp[size]; 144 145 memcpy(tmp, rhs, size); 146 memcpy(rhs, lhs, size); 147 memcpy(lhs, tmp, size); 148 } 149 150 inline void 151 shuffle(void *arr, size_t size, size_t len) 152 { 153 assert(arr); 154 assert(size); 155 156 for (size_t i = 0; i < len - 2; i++) { 157 size_t j = (i + random()) % len; 158 159 swap((u8 *) arr + (i * size), 160 (u8 *) arr + (j * size), 161 size); 162 } 163 } 164 165 inline void 166 difftimespec(struct timespec *restrict lhs, struct timespec *restrict rhs, struct timespec *restrict out) 167 { 168 if (lhs->tv_sec <= rhs->tv_sec && lhs->tv_nsec < rhs->tv_nsec) { 169 out->tv_sec = 0; 170 out->tv_nsec = 0; 171 } else { 172 out->tv_sec = lhs->tv_sec - rhs->tv_sec - (lhs->tv_nsec < rhs->tv_nsec); 173 out->tv_nsec = lhs->tv_nsec - rhs->tv_nsec + (lhs->tv_nsec < rhs->tv_nsec) * NANOSECS; 174 } 175 } 176 177 #define IS_POW2(v) (((v) & ((v) - 1)) == 0) 178 #define IS_ALIGNED(v, align) (((v) & ((align) - 1)) == 0) 179 180 #define ALIGN_PREV(v, align) ((v) & ~((align) - 1)) 181 #define ALIGN_NEXT(v, align) ALIGN_PREV((v) + ((align) - 1), (align)) 182 183 struct arena { 184 void *ptr; 185 uint64_t cap, len; 186 }; 187 188 inline void 189 arena_reset(struct arena *arena) 190 { 191 arena->len = 0; 192 } 193 194 inline void * 195 arena_alloc(struct arena *arena, size_t size, size_t align) 196 { 197 assert(arena); 198 assert(size); 199 assert(align); 200 assert(IS_POW2(align)); 201 202 size_t aligned_len = ALIGN_NEXT(arena->len, align); 203 if (aligned_len + size > arena->cap) 204 return NULL; 205 206 void *ptr = (void *) ((intptr_t) arena->ptr + aligned_len); 207 arena->len = aligned_len + size; 208 209 return ptr; 210 } 211 212 #define ALLOC_ARRAY(arena, T, n) \ 213 arena_alloc((arena), sizeof(T) * (n), alignof(T)) 214 215 #define ALLOC_SIZED(arena, T) ALLOC_ARRAY((arena), T, 1) 216 217 typedef s64 list_node_relptr_t; 218 219 struct list_node; 220 221 #define FROM_NODE(node, T, member) \ 222 ((T *) ((uintptr_t) node - offsetof(T, member))) 223 224 struct list_node { 225 list_node_relptr_t prev, next; 226 }; 227 228 inline list_node_relptr_t 229 list_node_abs2rel(void const *restrict base, struct list_node *restrict absptr) 230 { 231 return RELPTR_ABS2REL(list_node_relptr_t, base, absptr); 232 } 233 234 inline struct list_node * 235 list_node_rel2abs(void const *base, list_node_relptr_t relptr) 236 { 237 return RELPTR_REL2ABS(struct list_node *, list_node_relptr_t, base, relptr); 238 } 239 240 #define list_node_iter(node) \ 241 for (struct list_node *it = node; it; it = list_node_rel2abs(it, it->next)) 242 243 #define list_node_riter(node) \ 244 for (struct list_node *it = node; it ; it = list_node_rel2abs(it, it->prev)) 245 246 struct list { 247 list_node_relptr_t head, tail; 248 }; 249 250 #define list_iter(list) \ 251 list_node_iter(list_node_rel2abs(list, list->head)) 252 253 #define list_riter(list) \ 254 list_node_riter(list_node_rel2abs(list, list->tail)) 255 256 inline void 257 list_push_head(struct list *restrict list, struct list_node *restrict node) 258 { 259 if (list->tail == RELPTR_NULL) 260 list->tail = list_node_abs2rel(list, node); 261 262 struct list_node *head = list_node_rel2abs(list, list->head); 263 if (head) 264 head->prev = list_node_abs2rel(head, node); 265 266 node->next = list_node_abs2rel(node, head); 267 list->head = list_node_abs2rel(list, node); 268 } 269 270 inline void 271 list_push_tail(struct list *restrict list, struct list_node *restrict node) 272 { 273 if (list->head == RELPTR_NULL) 274 list->head = list_node_abs2rel(list, node); 275 276 struct list_node *tail = list_node_rel2abs(list, list->tail); 277 if (tail) 278 tail->next = list_node_abs2rel(tail, node); 279 280 node->prev = list_node_abs2rel(node, tail); 281 list->tail = list_node_abs2rel(list, node); 282 } 283 284 inline struct list_node * 285 list_pop_head(struct list *list) 286 { 287 if (list->head == RELPTR_NULL) 288 return NULL; 289 290 struct list_node *node = list_node_rel2abs(list, list->head); 291 list->head = list_node_abs2rel(list, list_node_rel2abs(node, node->next)); 292 return node; 293 } 294 295 inline struct list_node * 296 list_pop_tail(struct list *list) 297 { 298 if (list->tail == RELPTR_NULL) 299 return NULL; 300 301 struct list_node *node = list_node_rel2abs(list, list->tail); 302 list->tail = list_node_abs2rel(list, list_node_rel2abs(node, node->prev)); 303 return node; 304 } 305 306 /* network definitions 307 * =========================================================================== 308 */ 309 310 struct network { 311 int sockfd; 312 }; 313 314 bool 315 network_init(struct network *self, char const *host, char const *port); 316 317 void 318 network_free(struct network *self); 319 320 bool 321 network_send(struct network *self, struct hex_msg const *msg); 322 323 bool 324 network_recv(struct network *self, struct hex_msg *out, enum hex_msg_type *expected, 325 size_t len); 326 327 /* board definitions 328 * =========================================================================== 329 */ 330 331 enum cell { 332 CELL_BLACK = HEX_PLAYER_BLACK, 333 CELL_WHITE = HEX_PLAYER_WHITE, 334 CELL_EMPTY, 335 }; 336 337 typedef s16 segment_relptr_t; 338 339 struct segment { 340 enum cell occupant; 341 u32 rank; 342 segment_relptr_t parent; 343 }; 344 345 inline segment_relptr_t 346 segment_abs2rel(void const *restrict base, struct segment *restrict absptr) 347 { 348 return RELPTR_ABS2REL(segment_relptr_t, base, absptr); 349 } 350 351 inline struct segment * 352 segment_rel2abs(void const *base, segment_relptr_t relptr) 353 { 354 return RELPTR_REL2ABS(struct segment *, segment_relptr_t, base, relptr); 355 } 356 357 enum board_edges { 358 BLACK_SOURCE, 359 BLACK_SINK, 360 WHITE_SOURCE, 361 WHITE_SINK, 362 _BOARD_EDGE_COUNT, 363 }; 364 365 struct board { 366 u32 size; 367 struct segment *segments; 368 }; 369 370 inline struct segment * 371 board_black_source(struct board *self) 372 { 373 return &self->segments[self->size * self->size + BLACK_SOURCE]; 374 } 375 376 inline struct segment * 377 board_black_sink(struct board *self) 378 { 379 return &self->segments[self->size * self->size + BLACK_SINK]; 380 } 381 382 inline struct segment * 383 board_white_source(struct board *self) 384 { 385 return &self->segments[self->size * self->size + WHITE_SOURCE]; 386 } 387 388 inline struct segment * 389 board_white_sink(struct board *self) 390 { 391 return &self->segments[self->size * self->size + WHITE_SINK]; 392 } 393 394 struct move { 395 u8 x, y; 396 }; 397 398 bool 399 board_init(struct board *self, u32 size); 400 401 void 402 board_free(struct board *self); 403 404 void 405 board_copy(struct board const *restrict self, struct board *restrict other); 406 407 bool 408 board_play(struct board *self, enum hex_player player, u32 x, u32 y); 409 410 void 411 board_swap(struct board *self); 412 413 size_t 414 board_available_moves(struct board const *restrict self, struct move *restrict buf); 415 416 bool 417 board_winner(struct board *self, enum hex_player *out); 418 419 /* agent definitions 420 * =========================================================================== 421 */ 422 423 struct threadpool { 424 u32 threads; 425 }; 426 427 bool 428 threadpool_init(struct threadpool *self, u32 threads); 429 430 void 431 threadpool_free(struct threadpool *self); 432 433 struct agent_random { 434 size_t len; 435 struct move *moves; 436 }; 437 438 bool 439 agent_random_init(struct agent_random *self, struct board const *board); 440 441 void 442 agent_random_free(struct agent_random *self); 443 444 void 445 agent_random_play(struct agent_random *self, enum hex_player player, u32 x, u32 y); 446 447 void 448 agent_random_swap(struct agent_random *self); 449 450 bool 451 agent_random_next(struct agent_random *self, struct timespec timeout, 452 u32 *restrict out_x, u32 *restrict out_y); 453 454 typedef s64 mcts_node_relptr_t; 455 456 struct mcts_node { 457 alignas(64) 458 459 mcts_node_relptr_t parent; 460 enum hex_player player; 461 u8 x, y; 462 463 s32 wins, rave_wins; 464 u32 plays, rave_plays; 465 466 u32 children_cap, children_len; 467 468 struct list children; 469 struct list_node list_node; 470 }; 471 472 inline mcts_node_relptr_t 473 mcts_node_abs2rel(void *restrict base, struct mcts_node *restrict absptr) 474 { 475 return RELPTR_ABS2REL(mcts_node_relptr_t, base, absptr); 476 } 477 478 inline struct mcts_node * 479 mcts_node_rel2abs(void *base, mcts_node_relptr_t relptr) 480 { 481 return RELPTR_REL2ABS(struct mcts_node *, mcts_node_relptr_t, base, relptr); 482 } 483 484 struct agent_mcts { 485 struct board const *board; 486 struct threadpool *threadpool; 487 488 struct board shadow_board; 489 490 struct arena pool; 491 struct mcts_node *root; 492 }; 493 494 bool 495 agent_mcts_init(struct agent_mcts *self, struct board const *board, struct threadpool *threadpool, 496 u32 mem_limit_mib, enum hex_player player); 497 498 void 499 agent_mcts_free(struct agent_mcts *self); 500 501 void 502 agent_mcts_play(struct agent_mcts *self, enum hex_player player, u32 x, u32 y); 503 504 void 505 agent_mcts_swap(struct agent_mcts *self); 506 507 bool 508 agent_mcts_next(struct agent_mcts *self, struct timespec timeout, 509 u32 *restrict out_x, u32 *restrict out_y); 510 511 enum agent_type { 512 AGENT_RANDOM, 513 AGENT_MCTS, 514 }; 515 516 #define HEXES_RESERVED_MEM (MiB) 517 518 struct agent { 519 enum agent_type type; 520 union { 521 struct agent_random random; 522 struct agent_mcts mcts; 523 } backend; 524 }; 525 526 bool 527 agent_init(struct agent *self, enum agent_type type, struct board const *board, 528 struct threadpool *threadpool, u32 mem_limit_mib, enum hex_player player); 529 530 void 531 agent_free(struct agent *self); 532 533 void 534 agent_play(struct agent *self, enum hex_player player, u32 x, u32 y); 535 536 void 537 agent_swap(struct agent *self); 538 539 bool 540 agent_next(struct agent *self, struct timespec timeout, u32 *restrict out_x, 541 u32 *restrict out_y); 542 543 #endif /* HEXES_H */