Initial

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));
+}