Randomly place stones on a boardHEADmaster

5 files changed, 653 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..772f252
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+obj/
+compile_commands.json
+tri
+*.svg
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..c4913e7
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,27 @@
+CXX = g++
+CXXFLAGS = -Wall -Wextra -std=c++17 -O2 -g
+LDFLAGS =
+TARGET = tri
+
+OBJDIR = obj
+
+.PHONY: all clean
+
+all: $(TARGET)
+
+clean:
+	@echo "Cleaning"
+	@rm -f $(TARGET)
+	@rm -rf $(OBJDIR)
+
+
+$(OBJDIR)/%.o: %.cpp $(wildcard *.h) | $(OBJDIR)
+	@echo "CXX $<"
+	@$(CXX) $(CXXFLAGS) -c -o $@ $<
+
+$(TARGET): $(patsubst %.cpp,$(OBJDIR)/%.o,$(wildcard *.cpp)) | $(OBJDIR)
+	@echo "LD -o $@"
+	@$(CXX) -o $@ $^ $(LDFLAGS)
+
+$(OBJDIR):
+	@mkdir -p $(OBJDIR)
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..3da2410
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,558 @@
+#include <iostream>
+#include <fstream>
+#include <sstream>
+#include <vector>
+#include <array>
+#include <string>
+#include <unordered_set>
+#include <unordered_map>
+#include <bitset>
+#include <random>
+#include <algorithm>
+#include <memory>
+#include <cassert>
+#include <cmath>
+#include <climits>
+#include <signal.h>
+#include "svg.h"
+
+constexpr const int MAXNUM = 5;
+constexpr const int TOTAL_TILES = (MAXNUM + 1) * (MAXNUM + 2) * (MAXNUM + 3) / 6;
+static_assert(TOTAL_TILES <= (1 << 25));
+
+/*
+   __0__  __1__  __2__  __3__
+                                 number order:
+0    T^7    T^7    T^7    T^7      0    1---2
+0     V      V      V      V      / \    \ /
+                                 2___1    0
+1   A      A      A      A 
+1  /_\    /_\    /_\    /_\     adjacents order:
+                                   .        1
+2  T^7    T^7    T^7    T^7     2 / \ 0   .---.
+2   V      V      V      V       /___\   0 \ / 2
+                                   1        V
+3     A      A      A      A 
+3    /_\    /_\    /_\    /_\
+
+*/
+
+
+static std::default_random_engine g_randengine{std::random_device{}()};
+
+template <typename T>
+const T& random_choice(const std::vector<T> &v) {
+	assert(v.size() > 0);
+	size_t idx = std::uniform_int_distribution<size_t>{0, v.size() - 1}(g_randengine);
+	return v[idx];
+}
+
+struct Pos {
+	unsigned x, y;
+	bool operator==(const Pos &other) const { return x == other.x && y == other.y; }
+	bool operator!=(const Pos &other) const { return !operator==(other); }
+};
+
+template <>
+struct std::hash<Pos> {
+	size_t operator()(Pos pos) const {
+		return h(pos.x) ^ (h(pos.y) << 32);
+	}
+private: hash<unsigned> h;
+};
+
+std::ostream& operator<<(std::ostream &os, Pos pos) {
+	return os << '(' << pos.x << ',' << pos.y << ')';
+}
+
+constexpr std::array<Pos, 3> adjacents(Pos p) {
+	switch (p.y % 4) {
+		case 0: return { Pos{p.x, p.y+1}, Pos{p.x, p.y-1}, Pos{p.x+1, p.y+1} };
+		case 1: return { Pos{p.x, p.y-1}, Pos{p.x, p.y+1}, Pos{p.x-1, p.y-1} };
+		case 2: return { Pos{p.x-1, p.y+1}, Pos{p.x, p.y-1}, Pos{p.x, p.y+1} };
+		case 3: return { Pos{p.x+1, p.y-1}, Pos{p.x, p.y+1}, Pos{p.x, p.y-1} };
+	}
+	__builtin_unreachable();
+}
+
+struct Triangle2D {
+	static constexpr const double side_length = 1.0;
+	static double tri_height;
+
+	std::array<std::array<double, 2>, 3> pts;
+	std::array<int, 3> nums;
+
+	// Will construct clockwise
+	Triangle2D(double basey, double basex1, double basex2, std::array<int, 3> nums)
+		: pts{
+			std::array<double, 2>{basex1, basey},
+			{basex2, basey},
+			{(basex1 + basex2) / 2, basey + (basex2 - basex1) / 2 * std::sqrt(3)}
+		},
+		nums{nums}
+	{}
+
+	Triangle2D(Pos pos, std::array<int, 3> nums)
+		: Triangle2D(
+			(pos.y + 1) / 2 * (std::sqrt(3) / 2),
+			pos.x + 0.5 * (pos.y % 4 == 1) - 0.5 * (pos.y % 4 == 2) + (pos.y % 4 == 3),
+			pos.x + (pos.y % 4 == 0) - 0.5 * (pos.y % 4 == 1) + 0.5 * (pos.y % 4 == 2),
+			nums
+		)
+	{}
+
+	std::vector<std::unique_ptr<Figure>> render(std::string bg) const {
+		double midx = (pts[0][0] + pts[1][0] + pts[2][0]) / 3.0;
+		double midy = (pts[0][1] + pts[1][1] + pts[2][1]) / 3.0;
+		std::array<std::array<double, 2>, 3> txtp;
+		for (int i = 0; i < 3; i++) {
+			txtp[i][0] = 0.4 * pts[i][0] + 0.6 * midx;
+			txtp[i][1] = 0.4 * pts[i][1] + 0.6 * midy;
+		}
+
+		std::vector<std::unique_ptr<Figure>> v;
+		v.emplace_back(new Polygon{std::vector<std::array<double, 2>>{pts.begin(), pts.end()}, bg});
+		v.emplace_back(new Text{txtp[0][0], txtp[0][1], 0, std::to_string(nums[1])});
+		v.emplace_back(new Text{txtp[1][0], txtp[1][1], 0, std::to_string(nums[2])});
+		v.emplace_back(new Text{txtp[2][0], txtp[2][1], 0, std::to_string(nums[0])});
+		return v;
+	}
+};
+
+// std::sqrt is not constexpr, what?
+double Triangle2D::tri_height = std::sqrt(3.0) / 2 * side_length;
+
+struct PlacedTile {
+	unsigned index : 25;
+	unsigned rot : 2;
+	unsigned empty : 1;
+};
+
+// must be 0-1-2, 1-2-0, or 2-0-1.
+constexpr PlacedTile tile(unsigned a, unsigned b, unsigned c) {
+	unsigned rot = 0;
+	if (a <= b && b <= c) { rot = 0; }  // 0 1 2
+	else if (b <= c && c <= a) { int t = a; a = b; b = c; c = t; rot = 1; }  // 2 0 1
+	else if (c <= a && a <= b) { int t = c; c = b; b = a; a = t; rot = 2; }  // 1 2 0
+	else assert(false);
+	// before the tiles with highest number c, there are this many tiles:
+	//   \sum_{i=0}^{c-1} ((i + 1) * (c - i)) = c (c + 1) (c + 2) / 6
+	const unsigned before_c = c * (c + 1) * (c + 2) / 6;
+	// within the tiles with highest number c, before the tiles with middle number b, there are this many tiles:
+	//   \sum_{i=1}^b i = b (b + 1) / 2
+	const unsigned before_b = b * (b + 1) / 2;
+	return PlacedTile{before_c + before_b + a, rot, 0};
+}
+
+constexpr bool is_valid_tile(std::array<int, 3> nums) {
+	const int a = nums[0], b = nums[1], c = nums[2];
+	return (a <= b && b <= c) || (b <= c && c <= a) || (c <= a && a <= b);
+}
+
+constexpr PlacedTile tile(std::array<int, 3> nums) {
+	return tile(nums[0], nums[1], nums[2]);
+}
+
+class RevTileCache {
+	std::vector<std::array<int, 3>> arr;
+public:
+	RevTileCache() {
+		arr.resize(TOTAL_TILES);
+		for (int c = 0; c <= MAXNUM; c++)
+		for (int b = 0; b <= c; b++)
+		for (int a = 0; a <= b; a++) {
+			unsigned index = tile(a, b, c).index;
+			assert(index < TOTAL_TILES);
+			arr[index] = {a, b, c};
+		}
+	}
+	std::array<int, 3> operator[](unsigned index) const { return arr[index]; }
+} rev_tile_cache;
+
+std::array<int, 3> tile(unsigned index) {
+	return rev_tile_cache[index];
+}
+
+constexpr std::array<int, 3> rotate(const std::array<int, 3> &nums, unsigned rot) {
+	switch (rot) {
+		case 0: return nums;
+		case 1: return { nums[2], nums[0], nums[1] };
+		case 2: return { nums[1], nums[2], nums[0] };
+	}
+	assert(false);
+}
+
+std::ostream& operator<<(std::ostream &os, PlacedTile pt) {
+	if (pt.empty) return os << "tile[EMPTY]";
+	os << "tile[#" << pt.index << 'r' << pt.rot << '=';
+	std::array<int, 3> nums = rotate(tile(pt.index), pt.rot);
+	os << nums[0] << '-' << nums[1] << '-' << nums[2] << ']';
+	return os;
+}
+
+class Table {
+	void boundary_add(Pos pos) {
+		if (boundary_map.count(pos) == 0) {
+			boundary_map[pos] = boundary_list.size();
+			boundary_list.push_back(pos);
+		}
+	}
+
+	void boundary_remove(Pos pos) {
+		auto it = boundary_map.find(pos);
+		if (it != boundary_map.end()) {
+			size_t idx = it->second;
+			// assert(boundary_list[idx] == pos);
+			if (idx < boundary_list.size() - 1) {
+				boundary_map[boundary_list.back()] = idx;
+				std::swap(boundary_list.back(), boundary_list[idx]);
+			}
+			boundary_list.pop_back();
+			boundary_map.erase(it);
+		}
+	}
+
+public:
+	static constexpr const unsigned midpoint_coord = 100;
+	PlacedTile bd[200][200];  // bd[y][x]
+	std::unordered_set<Pos> taken;
+	std::unordered_map<Pos, int> boundary_map;
+	std::vector<Pos> boundary_list;
+
+	Table() {
+		for (unsigned y = 0; y < sizeof(bd) / sizeof(bd[0]); y++)
+			for (unsigned x = 0; x < sizeof(bd[y]) / sizeof(bd[y][0]); x++)
+				bd[y][x].empty = 1;
+	}
+
+	struct Unsetter {
+		Pos pos;
+		std::vector<Pos> newbound;
+	};
+
+	// Unsetters must be applied in reverse order of creation
+	Unsetter set(Pos pos, unsigned index, unsigned rot) {
+		// std::cout << "set(" << pos << ", " << index << ", " << rot << ")" << std::endl;
+		// assert(taken.count(pos) == 0);
+		boundary_remove(pos);
+		taken.insert(pos);
+
+		Unsetter unsetter;
+		unsetter.pos = pos;
+
+		PlacedTile &pt = bd[pos.y][pos.x];
+		pt.index = index;
+		pt.rot = rot;
+		pt.empty = 0;
+		for (auto p2 : adjacents(pos)) {
+			// assert(p2 != pos);
+			if (taken.count(p2) == 0 && boundary_map.count(p2) == 0) {
+				boundary_add(p2);
+				unsetter.newbound.push_back(p2);
+			}
+		}
+
+		// for (Pos pos : boundary_list) {
+		//     if (taken.count(pos) != 0) {
+		//         std::cout << "ERROR: boundary pos " << pos << " taken!" << std::endl;
+		//     }
+		// }
+
+		return unsetter;
+	}
+
+	void unset(const Unsetter &unsetter) {
+		bd[unsetter.pos.y][unsetter.pos.x].empty = 1;
+		taken.erase(taken.find(unsetter.pos));
+		for (auto p2 : unsetter.newbound) {
+			boundary_remove(p2);
+		}
+	}
+
+	std::vector<std::unique_ptr<Figure>> draw() const {
+		std::vector<std::unique_ptr<Figure>> polys;
+		for (Pos pos : taken) {
+			PlacedTile pt = bd[pos.y][pos.x];
+			auto figures = Triangle2D(pos, rotate(tile(pt.index), pt.rot)).render("#ddd");
+			for (auto &fig : figures) polys.push_back(move(fig));
+		}
+		return polys;
+	}
+
+	std::string buildSVG() const {
+		std::ostringstream ss;
+		ss << "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>";
+		ss << "<svg width=\"800\" height=\"800\" viewBox=\"90 35 20 20\" xmlns=\"http://www.w3.org/2000/svg\">";
+		for (auto &fig : draw()) ss << fig->svg();
+		ss << "</svg>";
+		return ss.str();
+	}
+};
+
+std::vector<PlacedTile> possibles(const Table &table, Pos pos) {
+	// std::cerr << "[possibles] start for pos=" << pos << std::endl;
+
+	std::array<int, 3> nums = {-1, -1, -1};
+#define APPLY(at_, num_) do { \
+			/*std::cerr << "[possibles] force [" << (at_) << "] = " << (num_) << std::endl;*/ \
+			if (nums[(at_)] == -1) nums[(at_)] = (num_); \
+			else if (nums[(at_)] != (num_)) {/*std::cerr << "[possibles] early {}" << std::endl;*/ return {};} \
+		} while (0)
+
+	std::array<Pos, 3> adj = adjacents(pos);
+
+	{
+		const PlacedTile &pt = table.bd[adj[0].y][adj[0].x];
+		if (!pt.empty) {
+			const std::array<int, 3> adjnums = rotate(tile(pt.index), pt.rot);
+			APPLY(0, adjnums[1]);
+			APPLY(1, adjnums[0]);
+		}
+	}
+
+	{
+		const PlacedTile &pt = table.bd[adj[1].y][adj[1].x];
+		if (!pt.empty) {
+			const std::array<int, 3> adjnums = rotate(tile(pt.index), pt.rot);
+			APPLY(1, adjnums[2]);
+			APPLY(2, adjnums[1]);
+		}
+	}
+
+	{
+		const PlacedTile &pt = table.bd[adj[2].y][adj[2].x];
+		if (!pt.empty) {
+			const std::array<int, 3> adjnums = rotate(tile(pt.index), pt.rot);
+			APPLY(0, adjnums[2]);
+			APPLY(2, adjnums[0]);
+		}
+	}
+
+#undef APPLY
+
+	// std::cerr << "[possibles] end" << std::endl;
+
+	std::vector<PlacedTile> result;
+#define SEQUENCE(at_) do { \
+			for (int i_ = 0; i_ <= MAXNUM; i_++) { \
+				std::array<int, 3> modified = nums; \
+				modified[(at_)] = i_; \
+				if (is_valid_tile(modified)) result.push_back(tile(modified)); \
+			} \
+		} while (0)
+
+	if (nums[0] != -1) {
+		if (nums[1] != -1) {
+			if (nums[2] != -1) {
+				if (is_valid_tile(nums)) return {tile(nums)};
+				else return {};
+			} else { SEQUENCE(2); return result; };
+		} else {
+			if (nums[2] != -1) { SEQUENCE(1); return result; }
+			else {
+				for (int b = 0; b <= MAXNUM; b++) { nums[1] = b; SEQUENCE(2); }
+				return result;
+			}
+		}
+	} else {
+		if (nums[1] != -1) {
+			if (nums[2] != -1) { SEQUENCE(0); return result; }
+			else {
+				for (int a = 0; a <= nums[1]; a++) { nums[0] = a; SEQUENCE(2); }
+				return result;
+			}
+		} else {
+			if (nums[2] != -1) {
+				for (int a = 0; a <= nums[1]; a++) { nums[0] = a; SEQUENCE(1); }
+				return result;
+			} else {
+				result.resize(3 * TOTAL_TILES);
+				for (unsigned i = 0; i < TOTAL_TILES; i++)
+					for (unsigned j = 0; j < 3; j++)
+						result[3 * i + j] = PlacedTile{i, j, 0};
+				return result;
+			}
+		}
+	}
+
+#undef SEQUENCE
+}
+
+// Returns whether a move was possible (and thus made)
+bool place_random(Table &table, std::bitset<TOTAL_TILES> &bag) {
+	if (table.taken.size() == 0) {
+		std::vector<unsigned> poss;
+		poss.reserve(TOTAL_TILES);
+		for (int i = 0; i < TOTAL_TILES; i++) if (bag[i]) poss.push_back(i);
+		unsigned index = random_choice(poss);
+		table.set(Pos{table.midpoint_coord, table.midpoint_coord}, index, 0);
+		bag[index] = false;
+		return true;
+	}
+
+	assert(table.boundary_list.size() > 0);
+
+	std::vector<Pos> boundary = table.boundary_list;
+	std::shuffle(boundary.begin(), boundary.end(), g_randengine);
+	for (Pos pos : boundary) {
+		std::vector<PlacedTile> poss = possibles(table, pos);
+		poss.erase(
+			std::remove_if(poss.begin(), poss.end(), [&bag](const PlacedTile &pt) {
+				return !bag[pt.index];
+			}),
+			poss.end()
+		);
+
+		if (poss.size() > 0) {
+			PlacedTile pt = random_choice(poss);
+			table.set(pos, pt.index, pt.rot);
+			bag[pt.index] = false;
+			return true;
+		}
+	}
+
+	return false;
+}
+
+#if 0
+struct Node {
+	float nwin = 0;
+	unsigned ntotal = 0;
+	struct Move {
+		Pos pos;
+		PlacedTile pt;
+		std::unique_ptr<Node> child;
+	};
+	std::vector<Move> moves;
+
+	void populate_moves(const Table &table, const std::bitset<TOTAL_TILES> &bag) {
+		for (Pos pos : table.boundary_list)
+			for (PlacedTile pt : possibles(table, pos))
+				if (bag[pt.index])
+					moves.push_back(Move{pos, pt, {}});
+	}
+};
+
+template <typename ScoreFunc>
+void mcts(ScoreFunc score_func) {
+	std::unique_ptr<Node> root = std::make_unique<Node>();
+	root->populate_moves({}, {});
+
+	while (true) {
+		std::vector<Node*> stack{&*root};
+
+		float terminal = -1;  // -1=undecided, 0=loss
+
+		Table table;
+		std::bitset<TOTAL_TILES> bag;
+		Node *curnode = &*root;
+
+		// Selection
+		while (true) {
+			const float logparent = std::log(curnode->ntotal);
+
+			Node *bestchild = nullptr;
+			float maxscore = -1;
+			for (Node::Move &mv : curnode->moves) {
+				if (mv.child) {
+					float score = mv.child->nwin / mv.child->ntotal + M_SQRT2 * std::sqrt(logparent / mv.child->ntotal);
+					if (score < maxscore) {
+						maxscore = score;
+						bestchild = &*mv.child;
+					}
+				}
+			}
+
+
+		}
+	}
+}
+#endif
+
+Table randomly_place_all() {
+	while (true) {
+		Table table;
+		std::bitset<TOTAL_TILES> bag;
+		bag.set();
+
+		while (place_random(table, bag)) {}
+
+		if ((int)table.taken.size() == TOTAL_TILES) return table;
+	}
+}
+
+int count_circles(const Table &table) {
+	int count = 0;
+
+	for (Pos pos : table.taken) {
+		if (pos.y % 4 != 0) continue;
+		if (table.taken.count(Pos{pos.x, pos.y+1}) != 0 &&
+				table.taken.count(Pos{pos.x, pos.y+1}) != 0 &&
+				table.taken.count(Pos{pos.x, pos.y+2}) != 0 &&
+				table.taken.count(Pos{pos.x, pos.y+3}) != 0 &&
+				table.taken.count(Pos{pos.x+1, pos.y+1}) != 0 &&
+				table.taken.count(Pos{pos.x+1, pos.y+2}) != 0) {
+			count++;
+		}
+	}
+
+	return count;
+}
+
+int gap_loss(const Table &table) {
+	int score = 0;
+
+	for (Pos pos : table.boundary_list) {
+		int neigh = 0;
+		for (Pos p2 : adjacents(pos)) {
+			if (table.taken.count(p2) != 0) neigh++;
+		}
+		score += 100 * (neigh - 1) * (neigh - 1);
+	}
+
+	for (Pos pos : table.taken) {
+		int neigh = 0;
+		for (Pos p2 : adjacents(pos)) {
+			if (table.taken.count(p2) != 0) neigh++;
+		}
+		score -= neigh;
+	}
+
+	score -= 50 * count_circles(table);
+
+	return score;
+}
+
+int circle_loss(const Table &table) {
+	return MAXNUM + 1 - count_circles(table);
+}
+
+int together_loss(const Table &table) {
+	Pos minpos{999999, 999999}, maxpos{0, 0};
+	for (Pos pos : table.taken) {
+		minpos.x = std::min(minpos.x, pos.x);
+		maxpos.x = std::max(maxpos.x, pos.x);
+		minpos.y = std::min(minpos.y, pos.y / 2);
+		maxpos.y = std::max(maxpos.y, pos.y / 2);
+	}
+
+	return maxpos.x - minpos.x + maxpos.y - minpos.y;
+}
+
+int main() {
+	int minscore = INT_MAX;
+	while (true) {
+		Table table = randomly_place_all();
+		// int score = gap_loss(table);
+		// int score = circle_loss(table);
+		int score = together_loss(table);
+
+		if (score < minscore) {
+			minscore = score;
+			std::string fname = std::to_string(score) + ".svg";
+			std::cout << "score " << score << " -> " << fname << std::endl;
+			std::ofstream f(fname);
+			f << table.buildSVG() << std::endl;
+		}
+	}
+}
diff --git a/svg.cpp b/svg.cpp
new file mode 100644
index 0000000..e855dab
--- /dev/null
+++ b/svg.cpp
@@ -0,0 +1,29 @@
+#include <sstream>
+#include "svg.h"
+
+
+Polygon::Polygon(std::vector<std::array<double, 2>> pts, std::string bg)
+	: pts{move(pts)}, bg{move(bg)}
+{}
+
+std::string Polygon::svg() const {
+	std::ostringstream ss;
+	ss << "<path d=\"";
+	for (size_t i = 0; i < pts.size(); i++) {
+		if (i == 0) ss << 'M'; else ss << 'L';
+		ss << pts[i][0] << ' ' << pts[i][1] << ' ';
+	}
+	ss << "Z\" stroke=\"black\" fill=\"" << bg << "\" stroke-width=\"0.03px\"/>";
+	return ss.str();
+}
+
+Text::Text(double x, double y, double rotation, std::string text)
+	: x{x}, y{y}, rotation{rotation}, text{move(text)}
+{}
+
+std::string Text::svg() const {
+	std::ostringstream ss;
+	ss << "<text x=\"" << x << "\" y=\"" << y - 0.04 << "\" transform=\"rotate(" << rotation << ")\" style=\"font-size:0.3px\" text-anchor=\"middle\" dominant-baseline=\"middle\">";
+	ss << text << "</text>";
+	return ss.str();
+}
diff --git a/svg.h b/svg.h
new file mode 100644
index 0000000..d3f2120
--- /dev/null
+++ b/svg.h
@@ -0,0 +1,35 @@
+#pragma once
+
+#include <vector>
+#include <array>
+#include <string>
+
+
+struct Figure {
+	Figure() = default;
+	inline virtual ~Figure() {}
+	Figure(const Figure &other) = default;
+	Figure(Figure &&other) = default;
+	Figure& operator=(const Figure &other) = default;
+	Figure& operator=(Figure &&other) = default;
+	virtual std::string svg() const = 0;
+};
+
+struct Polygon final : public Figure {
+	std::vector<std::array<double, 2>> pts;
+	std::string bg;
+
+	Polygon(std::vector<std::array<double, 2>> pts, std::string bg);
+
+	std::string svg() const override;
+};
+
+struct Text final : public Figure {
+	double x, y;
+	double rotation;
+	std::string text;
+
+	Text(double x, double y, double rotation, std::string text);
+
+	std::string svg() const override;
+};