diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile | 15 | ||||
| -rw-r--r-- | board.c | 48 | ||||
| -rw-r--r-- | board.h | 25 | ||||
| -rwxr-xr-x | genwinmasks.py | 31 | ||||
| -rw-r--r-- | main.c | 77 |
6 files changed, 197 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..d9b6f50 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +ttt3d diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..3652a5d --- /dev/null +++ b/Makefile @@ -0,0 +1,15 @@ +CC = gcc +CFLAGS = -Wall -Wextra -std=c11 -O3 -fwrapv -flto +LDFLAGS = +TARGET = ttt3d + +.PHONY: all clean + +all: $(TARGET) + +clean: + rm -f $(TARGET) + + +$(TARGET): $(wildcard *.c *.h) + $(CC) $(CFLAGS) -o $@ $(filter %.c,$^) $(LDFLAGS) @@ -0,0 +1,48 @@ +#include "board.h" + + +void b_set(board_t B, cboard_t C) { + B[0] = C[0]; + B[1] = C[1]; +} + +void b_drop(board_t B, int xy, int v) { + u64 mask = 0xfULL << (4 * xy), stkbot = 0x1ULL << (4 * xy); + u64 bit = ((B[0] | B[1]) & mask) + stkbot; + B[v] = B[v] | bit; +} + +bool b_stk_full(cboard_t B, int xy) { + u64 mask = 0xfULL << (4 * xy); + return ((B[0] | B[1]) & mask) == mask; +} + +static u64 winmasks[61] = { + 0xfULL, 0xf0ULL, 0xf00ULL, 0x1111ULL, + 0x2222ULL, 0x4444ULL, 0x8421ULL, 0x8888ULL, + 0xf000ULL, 0xf0000ULL, 0xf00000ULL, 0xf000000ULL, + 0x11110000ULL, 0x22220000ULL, 0x44440000ULL, 0x84210000ULL, + 0x88880000ULL, 0xf0000000ULL, 0xf00000000ULL, 0xf000000000ULL, + 0xf0000000000ULL, 0x111100000000ULL, 0x222200000000ULL, 0x444400000000ULL, + 0x842100000000ULL, 0x888800000000ULL, 0xf00000000000ULL, 0x1000100010001ULL, + 0x2000200020002ULL, 0x4000400040004ULL, 0x8000400020001ULL, 0x8000800080008ULL, + 0xf000000000000ULL, 0x10001000100010ULL, 0x20002000200020ULL, 0x40004000400040ULL, + 0x80004000200010ULL, 0x80008000800080ULL, 0xf0000000000000ULL, 0x100010001000100ULL, + 0x200020002000200ULL, 0x400040004000400ULL, 0x800040002000100ULL, 0x800080008000800ULL, + 0xf00000000000000ULL, 0x1000010000100001ULL, 0x1000100010001000ULL, 0x1111000000000000ULL, + 0x2000020000200002ULL, 0x2000200020002000ULL, 0x2222000000000000ULL, 0x4000040000400004ULL, + 0x4000400040004000ULL, 0x4444000000000000ULL, 0x8000040000200001ULL, 0x8000080000800008ULL, + 0x8000400020001000ULL, 0x8000800080008000ULL, 0x8421000000000000ULL, 0x8888000000000000ULL, + 0xf000000000000000ULL, +}; + +enum win_t b_win(cboard_t B) { + if ((B[0] | B[1]) == ~0ULL) return WIN_DRAW; + + for (int i = 0; i < (int)(sizeof(winmasks) / sizeof(winmasks[0])); i++) { + if ((B[0] & winmasks[i]) == winmasks[i]) return WIN_P0; + if ((B[1] & winmasks[i]) == winmasks[i]) return WIN_P1; + } + + return WIN_NONE; +} @@ -0,0 +1,25 @@ +#pragma once + +#include <stdbool.h> +#include <stdint.h> + +typedef uint64_t u64; +typedef uint8_t u8; + + +// as bit array: [16 * y + 4 * x + z] +// (x,y) = floor position, z = height with z=0 on the bottom +typedef u64 board_t[2]; +typedef const u64 cboard_t[2]; + +enum win_t { + WIN_NONE, + WIN_P0, + WIN_P1, + WIN_DRAW, +}; + +void b_set(board_t B, cboard_t C); +void b_drop(board_t B, int xy, int v); +bool b_stk_full(cboard_t B, int xy); +enum win_t b_win(cboard_t B); diff --git a/genwinmasks.py b/genwinmasks.py new file mode 100755 index 0000000..45a9f58 --- /dev/null +++ b/genwinmasks.py @@ -0,0 +1,31 @@ +#!/usr/bin/env python3 + +masks = [] + +def gen(x, y, z, dx, dy, dz): + if dx == 0 and dy == 0 and dz == 0: return + if x + 4 * dx > 4 or y + 4 * dy > 4 or z + 4 * dz > 4: return + + n = 0 + for i in range(4): + n |= 1 << (16 * y + 4 * x + z) + x, y, z = x + dx, y + dy, z + dz + + masks.append(n) + + +for x in range(4): + for y in range(4): + for z in range(4): + for dx in range(2): + for dy in range(2): + for dz in range(2): + gen(x, y, z, dx, dy, dz) + + +masks.sort() + +print("static u64 winmasks[{}] = {{".format(len(masks))) +for i in range((len(masks) + 3) // 4): + print("\t" + " ".join(hex(n) + "ULL," for n in masks[4*i:4*i+4])) +print("};") @@ -0,0 +1,77 @@ +#include <stdio.h> +#include <stdlib.h> +#include "board.h" + +#define LARGE 100000 + + +static inline int min(int a, int b) { + return a < b ? a : b; +} + +static inline int max(int a, int b) { + return a < b ? b : a; +} + + +static int win_score[4] = { + [WIN_NONE] = 0, + [WIN_P0] = 1000, + [WIN_P1] = -1000, + [WIN_DRAW] = 0, +}; + +static int evaluate(cboard_t B) { + (void)B; + return 0; +} + +static int minimax_p0(cboard_t B, int alpha, int beta, int depth); + +static int minimax_p1(cboard_t B, int alpha, int beta, int depth) { + if (depth == 0) return evaluate(B); + enum win_t win = b_win(B); + if (win != WIN_NONE) return win_score[win]; + + int best = LARGE; + for (int i = 0; i < 16; i++) { + if (b_stk_full(B, i)) continue; + board_t C; b_set(C, B); + b_drop(C, i, 1); + int sc = minimax_p0(C, alpha, beta, depth - 1); + best = min(sc, best); + beta = min(best, beta); + if (beta <= alpha) break; + } + + return best; +} + +static int minimax_p0(cboard_t B, int alpha, int beta, int depth) { + if (depth == 0) return evaluate(B); + enum win_t win = b_win(B); + if (win != WIN_NONE) return win_score[win]; + + if (depth >= 36) { + printf("depth=%d alpha=%d beta=%d\n", depth, alpha, beta); + } + + int best = -LARGE; + for (int i = 0; i < 16; i++) { + if (b_stk_full(B, i)) continue; + board_t C; b_set(C, B); + b_drop(C, i, 0); + int sc = minimax_p1(C, alpha, beta, depth - 1); + best = max(sc, best); + alpha = max(best, alpha); + if (beta <= alpha) break; + } + + return best; +} + + +int main(void) { + board_t B = {0, 0}; + printf("%d\n", minimax_p0(B, -LARGE, LARGE, 64)); +} |