summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore1
-rw-r--r--Makefile15
-rw-r--r--board.c48
-rw-r--r--board.h25
-rwxr-xr-xgenwinmasks.py31
-rw-r--r--main.c77
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)
diff --git a/board.c b/board.c
new file mode 100644
index 0000000..91cee2a
--- /dev/null
+++ b/board.c
@@ -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;
+}
diff --git a/board.h b/board.h
new file mode 100644
index 0000000..f795d03
--- /dev/null
+++ b/board.h
@@ -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("};")
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..6b5cac8
--- /dev/null
+++ b/main.c
@@ -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));
+}