An Untitled Story Black Jack solver

.gitignore

/solve
/game.txt
/make_table_hands
/make_table_heap
/graph
/data
/bot_server
/extract_card_fingerprints
/extract_cards
/bot
/make_decision_tree

bot.d

import core.thread;

import std.algorithm.comparison;
import std.algorithm.iteration;
import std.algorithm.searching;
import std.conv;
import std.exception;
import std.file;
import std.process;
import std.range;
import std.stdio;
import std.string;

import ae.sys.cmd;
import ae.sys.sendinput;
import ae.utils.geometry : Rect;
import ae.utils.graphics.color;
import ae.utils.graphics.im_convert;
import ae.utils.graphics.image;
import ae.utils.graphics.view;
import ae.utils.json;
import ae.utils.meta : enumLength;

import expand : Score, Move;
import game;

/*

cards
86x112
@ 116x344
fingerprint @ 118x144
 hand   offset: x += 100
 player offset: y += 200
 */

enum fingerprintSize = 84;

immutable ubyte[/*fingerprintSize*/][numCardValues] cardFingerprints = [
	null,
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
	[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
];

struct Screenshot
{
	enum State
	{
		unknown,    /// OCR failed (e.g. animation is obscuring cards)
		bet,        /// Player is asked to place a bet
		playing,    /// An animation during the player's turn, or the dealer's turn
		playerTurn, /// Player is asked to choose to be hit or to stay
		message,    /// The round is done and the outcome is displayed (cards are obscured)
	}
	State state;

	uint deckSize;

	Card[maxHandSize][enumLength!Character] hands;
}

Screenshot parseScreenshot(Image)(Image image)
{
	enum black  = BGRA(0x00, 0x00, 0x00, 0xFF);
	enum white  = BGRA(0xFF, 0xFF, 0xFF, 0xFF);
	enum red    = BGRA(0x00, 0x00, 0xFF, 0xFF);
	enum table  = BGRA(0x00, 0x58, 0xB0, 0xFF);
	enum table2 = BGRA(0x00, 0x45, 0x8A, 0xFF);
	enum menu   = BGRA(0x00, 0x12, 0x23, 0xFF);

	Screenshot s;

	// State
	{
		if (image[153, 300] == table && image[154, 300] == white)
			s.state = Screenshot.State.message;
		else
		if (image[239, 120] == table && image[240, 120] == menu)
			s.state = Screenshot.State.bet;
		else
		if (image[339, 120] == table && image[340, 120] == menu)
			s.state = Screenshot.State.playerTurn;
		else
			s.state = Screenshot.State.playing;
	}

	// Deck size
	{
		auto x = 21;
		auto y = 358;
		while (image[x, y] == black && image[x, y-1] == black && image[x, y-2] == white)
		{
			s.deckSize++;
			y -= 3;
		}

		if (s.deckSize == 0 && image[x, y] != table)
			s.state = Screenshot.State.unknown; // Could be some cards sliding in front of the bottom of the deck
	}

	// Hands
	foreach (c; Character.init .. enumLength!Character)
	{
		if (s.state.among(Screenshot.State.bet))
			continue;
		if (s.state.among(Screenshot.State.playerTurn, Screenshot.State.message) && c == Character.dealer)
			continue;

		foreach (n; 0 .. maxHandSize)
		{
			auto x0 = 118 + n * 100;
			auto y0 = 344 - c * 200;

			s.hands[c][n] = {
				auto diagonal = fingerprintSize.iota.map!(i => image[x0 + i, y0 + i]);
				if (diagonal.all!(c => c == table || c == table2))
					return Card(0);

				foreach (Card v; 0 .. numCardValues)
				{
					auto fingerprint = cardFingerprints[v].map!(b => b ? red : white);
					if (equal(fingerprint, diagonal))
						return v;
				}

				s.state = Screenshot.State.unknown;
				return Card.max;
			}();
		}
	}

	return s;
}

Image!BGRA screenshotImage;
Window window;

Screenshot getScreenshot()
{
	//screenshotImage = captureWindow(window);
	auto g = getWindowGeometry(window);
	captureWindowRect(window, Rect!int(0, 0, g.w, g.h), screenshotImage);
	return parseScreenshot(screenshotImage);
}

void press(string key)
{
	stderr.writeln("Pressing ", key);
	Thread.sleep(200.msecs);
	run(["xdotool", "key",
		"--window", window.to!string,
		"--delay", "100",
		key,
	]);
}

void main()
{
	stderr.writeln("Initializing...");

	// foreach (fn; dirEntries(".", "*.png", SpanMode.shallow))
	// 	writeln(fn, ": ", fn.read.parseViaIMConvert!BGRA.parseScreenshot);

	window = query(`comm -12 <(xdotool search --onlyvisible --class '^anuntitledstory\.exe$' | sort) <(xdotool search --onlyvisible --name '^$' | sort)`).to!Window;
	// captureWindow(window).colorMap!(channelMap!RGBA).toPNG.toFile("screenshot.png");

	scope(failure) screenshotImage.colorMap!(channelMap!RGBA).toPNG.toFile("error.png");

	Screenshot screenshot = getScreenshot();

	enforce(screenshot.state == Screenshot.State.bet && screenshot.deckSize == 52,
		"Invalid initial state: " ~ screenshot.to!string);

	void leaveState(Screenshot.State state)
	{
		stderr.writeln("Waiting to leave ", state);
		while (screenshot.state == state)
		{
			Thread.sleep(10.msecs);
			screenshot = getScreenshot();
		}
		stderr.writeln("Reached state ", screenshot.state);
	}

	Screenshot waitForState(Screenshot.State[] states...)
	{
		stderr.writeln("Waiting for ", states);
		Screenshot lastPlayingScreenshot;
		while (true)
		{
			if (states.canFind(screenshot.state))
			{
				stderr.writeln("Reached state ", screenshot.state);
				return lastPlayingScreenshot;
			}
			else
			if (screenshot.state == Screenshot.State.playing)
				lastPlayingScreenshot = screenshot;

			Thread.sleep(10.msecs);
			screenshot = getScreenshot();
		}
	}

	auto server = pipeProcess(["./bot_server"], Redirect.stdin | Redirect.stdout);
	T getNextBestMove(T)(Game game)
	{
		stderr.write(game, " -> "); stderr.flush();
		static struct Result { T bestMove; Score bestScore; }
		server.stdin.writeln(game.toJson());
		server.stdin.flush();
		auto result = server.stdout.readln().strip().jsonParse!Result;
		stderr.writeln(result);
		return result.bestMove;
	}

	Game game;

	void applyChanges(Screenshot oldScreenshot, Screenshot newScreenshot)
	{
		scope(failure)
		{
			stderr.writeln("Old: ", oldScreenshot);
			stderr.writeln("New: ", newScreenshot);
		}

		enforce(oldScreenshot.deckSize == game.heap[].sum, "Deck size mismatch: expected %s, seeing %s".format(game.heap[].sum, oldScreenshot.deckSize));
		enforce(oldScreenshot.state.among(Screenshot.State.playerTurn, Screenshot.State.playing, Screenshot.State.message));
		enforce(newScreenshot.state.among(Screenshot.State.playerTurn, Screenshot.State.playing, Screenshot.State.message));

		foreach (c; Character.init .. enumLength!Character)
			foreach (i; 0 .. maxHandSize)
			{
				if (oldScreenshot.hands[c][i] == newScreenshot.hands[c][i])
					continue;
				else
				if (oldScreenshot.hands[c][i] == 0)
				{
					auto expectedState = c == Character.player ? Game.State.playerTurn : Game.State.dealerTurn;
					enforce(game.state == expectedState);
					auto newCard = newScreenshot.hands[c][i];
					game.hand.totalValue += newCard;
					game.hand.numCards++;
					if (game.heap[].sum() == 0)
					{
						stderr.writeln("Reshuffling deck.");
						game.heap = Game.init.heap;
					}
					game.heap[newCard]--;
					stderr.writefln("%s got card #%d: %d", c, 1 + i, newCard);
				}
				else
					enforce(false, "Unexpected card change");
			}

		enforce(newScreenshot.deckSize == game.heap[].sum, "Deck size mismatch: expected %s, seeing %s".format(game.heap[].sum, newScreenshot.deckSize));
	}

	stderr.writeln("Starting.");

	while (true)
	{
		// Reset game
		game = Game(game.heap);

		// Sanity check
		enforce(screenshot.deckSize == game.heap[].sum,
			"Deck size mismatch: expected %s, seeing %s".format(game.heap[].sum, screenshot.deckSize));

		// Select bet

		enforce(screenshot.state == Screenshot.State.bet);
		{
			game.state = Game.State.bet;
			auto allIn = getNextBestMove!bool(game);
			game.state = Game.State.playerTurn;
			game.allIn = allIn;

			foreach (i; 0 .. 4)
				press("Up");
			auto optionIndex = allIn ? 4 : 1;
			foreach (i; 0 .. optionIndex)
				press("Down");
			press("space");
		}

		// The screenshot at the start of the turn, for applyChanges
		Screenshot turnStart = screenshot;

		// Player turn

		{
			turnStart = screenshot;
			turnStart.state = Screenshot.State.playing;

			leaveState(Screenshot.State.bet);

		playerTurn:
			while (true)
			{
				waitForState(Screenshot.State.playerTurn, Screenshot.State.message);
				applyChanges(turnStart, screenshot);
				turnStart = screenshot;

				switch (screenshot.state)
				{
					case Screenshot.State.playerTurn:
						auto bestMove = getNextBestMove!Move(game);
						press(bestMove == Move.stay ? "Up" : "Down");
						press("space");
						leaveState(Screenshot.State.playerTurn);
						if (bestMove == Move.hit)
							continue playerTurn;
						else
						{
							game.state = Game.State.dealerTurn;
							game.playerHandTotalValue = game.hand.totalValue;
							game.hand = Hand.init;
							break playerTurn;
						}

					case Screenshot.State.message:
						// We busted, or hit exactly 21
						goto endRound;

					default:
						assert(false);
				}
			}
		}

		// Dealer turn

		{
			auto lastPlayingScreenshot = waitForState(Screenshot.State.message);
			enforce(lastPlayingScreenshot.hands[Character.dealer] != Screenshot.init.hands[Character.dealer],
				"Don't see dealer's cards");
			enforce(lastPlayingScreenshot.deckSize == screenshot.deckSize,
				"Missed some dealer cards");
			applyChanges(turnStart, lastPlayingScreenshot);
		}

	endRound:
		assert(screenshot.state == Screenshot.State.message);
		Thread.sleep(1400.msecs);
		press("x");
		leaveState(Screenshot.State.message);
		Thread.sleep(2.seconds); screenshot = getScreenshot(); // Wait for animation to finish, so that we can see the deck size at the top of the loop
		waitForState(Screenshot.State.bet);
	}
}

bot_server.d

import ae.sys.data;
import ae.sys.datamm;
import ae.utils.array;
import ae.utils.json;
import ae.utils.meta;

import std.algorithm.iteration;
import std.algorithm.searching;
import std.conv;
import std.exception;
import std.file;
import std.stdio;
import std.string;

import driver;
import game;
import gamelogic;
import graph;
import packing;

static struct GraphDriver
{
	static GraphDriver create()
	{
		GraphDriver d;
		d.scores = mapFile(scoreFileName(), MmMode.read).asDataOf!PackedScore;
		return d;
	}

	TData!PackedScore scores;

	enum interactive = false;

	void log(scope string delegate() message) /*nothrow @nogc*/ {}

	Score recurse(const ref Game game) nothrow @nogc
	{
		// return expand(game, &this);
		return scores[game.packGame()].unpackScore;
	}

	alias GetScore(T) = Score delegate(T) /*nothrow @nogc*/;

	// alias choice = graphChoice!GetScore;

	bool topLevel = true;
	string bestMove; Score bestScore;

	Score choice(ChoiceMode mode, T)(
		scope string delegate() description,
		scope Score delegate(T) /*nothrow @nogc*/ getScore,
		scope string delegate(T) getDescription,
		scope const(T)[] items...
	) //nothrow @nogc
	{
		alias impl = graphChoice!GetScore;

		if (topLevel)
		{
			static if (mode == ChoiceMode.best && (is(T == Move) || is(T == bool)))
			{
				topLevel = false; scope(exit) topLevel = true;
				bestScore = 0;
				foreach (item; items)
				{
					auto score = getScore(item);
					if (score > bestScore)
					{
						bestScore = score;
						bestMove = item.toJson;
					}
				}
				return Score.nan; // We got what we needed
			}
			else
				assert(false);
		}
		else
			return impl!(mode, T)(description, getScore, getDescription, items);
	}

	alias gameOver = graphGameOver;
}

void main()
{
	loadTables();

	string line;
	while ((line = stdin.readln()) !is null)
	{
		line = line.strip();
		if (!line.length)
			continue;

		auto game = line.jsonParse!Game;
		auto driver = GraphDriver.create();
		expand(game, &driver);

		struct Result { JSONFragment bestMove; Score bestScore; }
		stdout.writeln(Result(JSONFragment(driver.bestMove), driver.bestScore).toJson);
		stdout.flush();
	}
}

driver.d

import std.math.traits;

import game : Game;

alias Score = double;
enum Score scoreLose = 0;
enum Score scoreWin = 1;
enum Score scoreIndeterminate = (scoreLose + scoreWin) / 2;

/// For `Driver.choice`
enum ChoiceMode
{
	/// Something the game would choose at random.
	/// All odds are equal.
	random,
	/// Same as "random", but each item must be a struct with
	/// a "weight" field, which reflects its relative weight.
	/// A weight of 0 is allowed, which means that it is only
	/// relevant if chosen manually by the user in the explorer.
	randomWeighted,
	/// Something the player decides,
	/// so we should pick the best option for the player.
	best,
	/// Something a hypothetical perfect opponent would choose.
	worst,
	/// Something the game decides in an unpredictable way.
	/// For calculating the win chance, we treat this
	/// in the same way as "worst", to be safe.
	unknown,
	/// Something that's usually always decided in some way,
	/// but overridable in interactive mode.
	first,
}

/// Helper type constructor for randomWeighted.
struct Weighted(T, Weight = size_t)
{
	T value;
	Weight weight = 0;
}

/// Standard `Driver.choice` implementation.
template graphChoice(alias GetScore)
{
	Score graphChoice(ChoiceMode mode, T)(
		scope string delegate() description,
		scope GetScore!T getScore,
		scope string delegate(T) getDescription,
		scope const(T)[] items...
	) {
		static if (mode == ChoiceMode.random)
		{
			Score sum = 0;
			size_t total = 0;
			foreach (item; items)
			{
				auto itemScore = getScore(item);
				if (!itemScore.isNaN)
				{
					sum += itemScore;
					total ++;
				}
			}
			return sum / total;
		}
		else static if (mode == ChoiceMode.randomWeighted)
		{
			Score sum = 0;
			size_t total = 0;
			foreach (item; items)
			{
				if (!item.weight)
					continue;

				auto itemScore = getScore(item);
				if (!itemScore.isNaN)
				{
					sum += itemScore * item.weight;
					total += item.weight;
				}
			}
			return sum / total;
		}
		else static if (mode == ChoiceMode.best)
		{
			Score bestScore = -Score.max;
			foreach (item; items)
			{
				auto itemScore = getScore(item);
				if (itemScore > bestScore) // Comparison with NaN will yield false
					bestScore = itemScore;
			}
			assert(bestScore != -Score.max, "All choices are invalid");
			return bestScore;
		}
		else static if (mode == ChoiceMode.worst || mode == ChoiceMode.unknown)
		{
			Score worstScore = Score.max;
			foreach (item; items)
			{
				auto itemScore = getScore(item);
				if (itemScore < worstScore) // Comparison with NaN will yield false
					worstScore = itemScore;
			}
			assert(worstScore != Score.max, "All choices are invalid");
			return worstScore;
		}
		else static if (mode == ChoiceMode.first)
			return getScore(items[0]);
		else
			static assert(false);
	}
}

struct TestDriver
{
	enum interactive = false;

	/// Make a note.
	void log(scope string delegate() message) nothrow @nogc {}

	/// Recursive search.
	/// Get the score of another game state,
	/// as if we descended recursively into it.
	Score recurse(const ref Game game) nothrow @nogc { return scoreIndeterminate; }

	/// A choice is happening.
	/// Filter out NaNs!
	/// Caller should be careful to not mutate external state in `getScore`!
	Score choice(ChoiceMode mode, T)(
		scope string delegate() description,
		scope Score delegate(T) nothrow @nogc getScore,
		scope string delegate(T) getDescription,
		scope const(T)[] items...
	) nothrow @nogc { return scoreIndeterminate; }

	/// End condition.
	Score gameOver(bool playerWon) nothrow @nogc { return playerWon ? scoreWin : scoreLose; }
}

Score graphGameOver(bool playerWon) nothrow @nogc { return playerWon ? scoreWin : scoreLose; }

extract_card_fingerprints.d

import std.algorithm.searching;
import std.algorithm.sorting;
import std.array;
import std.conv;
import std.digest.md;
import std.exception;
import std.file;
import std.stdio;

import ae.utils.array;
import ae.utils.graphics.color;
import ae.utils.graphics.im_convert;
import ae.utils.graphics.image;
import ae.utils.graphics.view;

void main()
{
	static immutable BGRA[2] colors = [
		BGRA(0xFF, 0xFF, 0xFF, 0xFF), // white
		BGRA(0x00, 0x00, 0xFF, 0xFF), // red
	];
	foreach (fn; dirEntries("cards", "*.png", SpanMode.shallow).array.sort)
	{
		stderr.writeln(fn);
		ubyte[] fingerprint;
		auto image = fn.read.parseViaIMConvert!BGRA;
		foreach (p; 0 .. image.w - 2)
		{
			auto c = image[2 + p, p];
			auto ci = colors[].countUntil(c);
			enforce(ci >= 0, "Unknown color: " ~ c.to!string);
			fingerprint ~= cast(ubyte)ci;
		}
		writefln("%s\t%s", fn, fingerprint);
	}
}

extract_cards.d

import std.digest.md;
import std.file;
import std.stdio;

import ae.utils.array;
import ae.utils.graphics.color;
import ae.utils.graphics.im_convert;
import ae.utils.graphics.image;
import ae.utils.graphics.view;

void main()
{
	foreach (fn; dirEntries(".", "screenshot_*.png", SpanMode.shallow))
	{
		auto image = fn.read.parseViaIMConvert!BGRA;
		foreach (y; 0 .. 2)
			foreach (x; 0 .. 5)
			{
// 86x112
// @ 116x344
//  hand   offset: x += 100
//  player offset: y += 200
				auto x0 = 116 + x * 100;
				auto y0 = 144 + y * 200;
				auto card = image.crop(x0, y0, x0 + 86, y0 + 112);
				auto png = card.colorMap!(channelMap!RGBA).toPNG;
				png.toFile("cards/" ~ png.hexDigest!MD5.idup ~ ".png");
			}
	}
}

game.d

import std.algorithm.iteration;
import std.typecons;

import ae.utils.meta;

enum Character : ubyte
{
	player,
	dealer,
}

Character other(Character character) nothrow @nogc { return cast(Character)(1 - character); }

alias Card = ubyte;
enum maxCardValue = 11;
enum numCardValues = maxCardValue + 1;
enum maxHandSize = 5;
enum maxDeckCards = 52;

struct Hand
{
	ubyte numCards;
	ubyte totalValue;
}

alias Deck = ubyte[numCardValues];

static immutable Deck fullDeck = [
	 0, // 0
	 2, // 1
	 4, // 2
	 4, // 3
	 4, // 4
	 4, // 5
	 4, // 6
	 4, // 7
	 4, // 8
	 4, // 9
	16, // 10
	 2, // 11
];

enum Bet : ubyte
{
	minimum,
	maximum,
}

static immutable string[enumLength!Bet] betDescription = ["Min Bet", "Max Bet"];

struct Game
{
	Deck deck = fullDeck;

	enum State : ubyte
	{
		bet,
		playerTurn,
		dealerTurn,
	}
	State state;

	Bet bet; // [state != State.bet]
	Hand hand; // current player's hand [state != State.bet]
	ubyte playerHandTotalValue; // [state == State.dealerTurn]
}

static assert(Game.init.deck[].sum == maxDeckCards);

gamelogic.d

import std.algorithm.comparison;
import std.algorithm.iteration;
import std.algorithm.sorting;
import std.array : join;
import std.conv : to;
import std.stdio;
import std.string : capitalize;
import std.traits;
import std.typecons;

import ae.utils.math.combinatorics;
import ae.utils.meta;

import driver;
import game;

enum Move : ubyte
{
	hit,
	stay,
}

string getMoveDescription(Move move, Character who)
{
	return move.to!string;
}

Score expand(Driver)(const ref Game game, Driver driver)
{
	// Ugly hack to work around attribute inference with recursion not working, TODO
	template Dg(string def, Args...)
	{
		enum noGC = is(typeof({ static assert(driver.interactive == false); }));
		static if (noGC)
			mixin(`alias Dg = ` ~ def ~ ` nothrow @nogc;`);
		else
			mixin(`alias Dg = ` ~ def ~ `;`);
	}

	Score drawCard(ref const Game game, scope Dg!q{Score delegate(ref const Game newGame)} handler)
	{
		assert(game.hand.numCards < maxHandSize);

		struct Choice
		{
			Card card;
			ubyte weight;
		}
		Choice[numCardValues] choices;
		size_t numChoices;

		foreach (Card card, count; game.deck)
			if (count)
				choices[numChoices++] = Choice(card, count);

		if (!numChoices)
		{
			Game newGame = game;
			newGame.deck = fullDeck;
			return drawCard(newGame, handler);
		}

		return driver.choice!(ChoiceMode.randomWeighted, Choice)(
			() => "Which card is drawn?",
			(choice) {
				assert(choice.card);
				assert(choice.weight);
				assert(game.deck[choice.card] > 0);

				Game newGame = game;
				newGame.deck[choice.card]--;
				newGame.hand.numCards++;
				newGame.hand.totalValue += choice.card;
				return handler(newGame);
			},
			card => card.to!string,
			choices[0 .. numChoices],
		);
	}

	Score endRound(ref const Game game, bool win)
	{
		assert(game.state == Game.State.playerTurn || game.state == Game.State.dealerTurn);
		auto outcomeScore = win ? scoreWin : scoreLose;
		final switch (game.bet)
		{
			case Bet.maximum:
				// Model as 100% chance of using the outcome ("all-in")
				return outcomeScore;

			case Bet.minimum:
				// Reset
				Game newGame = Game(game.deck);
				auto recursedScore = driver.recurse(newGame);
				// Model as 5% of using the outcome, and 95% chance of the game continuing
				// (Minimum bet is 5 crystals, maximum is 100)
				return
					recursedScore * 95 / 100 +
					outcomeScore  *  5 / 100;
		}
	}

	final switch (game.state)
	{
		case Game.State.bet:
			return driver.choice!(ChoiceMode.best, Bet)(
				() => "What to bet?",
				(bet) {
					assert(game.bet is Bet.init);
					Game newGame = game;
					newGame.bet = bet;
					newGame.state = Game.State.playerTurn;
					return driver.recurse(newGame);
				},
				bet => betDescription[bet],
				EnumMembers!Bet
			);

		case Game.State.playerTurn:
			// Assume that the player will proceed according to what's best for them.
			return driver.choice!(ChoiceMode.best, Move)(
				() => "What will you do?",
				(move) {
					assert(game.state == Game.State.playerTurn);
					final switch (move)
					{
						case Move.hit:
							return drawCard(game, (ref const Game game) {
								auto handValue = game.hand.totalValue;
								if (handValue == 21)
									return endRound(game, true); // Exact hit
								if (handValue > 21)
									return endRound(game, false); // We busted
								if (game.hand.numCards == maxHandSize)
									return endRound(game, true); // We have a full hand

								return driver.recurse(game);
							});

						case Move.stay:
							if (game.hand.numCards == 0)
								return Score.nan; // Can't stay with no cards
							Game newGame = game;
							newGame.state = Game.State.dealerTurn;
							assert(game.playerHandTotalValue == 0);
							newGame.playerHandTotalValue = game.hand.totalValue;
							newGame.hand = Hand.init;
							return driver.recurse(newGame);
					}
				},
				move => getMoveDescription(move, Character.player),
				EnumMembers!Move,
			);

		case Game.State.dealerTurn:
			return drawCard(game, (ref const Game game) {
				assert(game.playerHandTotalValue > 0);
				if (game.hand.totalValue > 21)
					return endRound(game, true); // Dealer busted
				if (game.hand.totalValue > game.playerHandTotalValue)
					return endRound(game, false); // Dealer won
				if (game.hand.numCards == maxHandSize)
					return endRound(game, false); // Dealer has a full hand
				return driver.recurse(game);
			});
	}
}

nothrow @nogc
unittest
{
	Game game;
	TestDriver driver;
	expand(game, driver);
}

graph.d

import std.algorithm.comparison;
import std.algorithm.iteration;
import std.conv;
import std.file;
import std.math.algebraic;
import std.math.rounding;
import std.parallelism;
import std.range;
import std.stdio : File, stderr;

import ae.sys.data;
import ae.sys.datamm;
import ae.sys.file : allocate, atomic, atomicExchange;
import ae.utils.meta;
import ae.utils.parallelism;
import ae.utils.text;

import driver;
import game;
import gamelogic;
import packing;

struct PackedScore
{
	alias Value = ushort;
	Value value;
}

PackedScore packScore(Score score) nothrow @nogc
{
	if (0 <= score && score <= 1)
		return PackedScore(cast(PackedScore.Value)round(score * PackedScore.Value.max));
	else
		assert(false, "Bad score");
}

Score unpackScore(PackedScore packed) nothrow @nogc
{
	return Score(packed.value) / PackedScore.Value.max;
}

unittest
{
	foreach (score; [0, 0.25, 0.5, 0.75, 1])
		assert(abs(score - score.packScore.unpackScore) < 1.0 / PackedScore.Value.max);
}

alias ScoreTable = PackedScore[/*packedGameCard*/];

string scoreFileName()
{
	return "data/scores.i" ~ text(PackedScore.Value.sizeof * 8);
}

struct Stats
{
	double scoreSum = 0;
	double totalChange = 0;
	double maxChange = 0;
	ulong numChanged;
}

Stats propagateScores(const ScoreTable source, ScoreTable target)
{
	struct Driver
	{
		enum interactive = false;
		void log(scope string delegate() message) nothrow @nogc {}

		Score recurse(const ref Game game) nothrow @nogc
		{
			if (game.canPack())
				return source[game.packGame()].unpackScore;
			else
				return expand(game, &this);
		}

		alias GetScore(T) = Score delegate(T) nothrow @nogc;
		alias choice = graphChoice!GetScore;
		alias gameOver = graphGameOver;
	}
	auto driver = Driver();

	Stats stats;
	{
		PackedGame numDone;
		auto chunkSize = 0x100000;
		foreach (chunk; packedGameCard.iota.chunks(chunkSize).parallel(1))
		{
			Stats chunkStats;
			foreach (packedGame; chunk)
			{
				auto game = packedGame.unpackGame();
				auto score = expand(game, &driver);
				auto packedScore = score.packScore;
				target[packedGame] = packedScore;

				{
					auto oldPackedScore = source[packedGame];
					auto oldUnpackedScore = oldPackedScore.unpackScore;
					auto newExactScore = score;
					auto newPackedScore = packedScore;
					auto newUnpackedScore = newPackedScore.unpackScore;
					chunkStats.scoreSum += newExactScore;
					auto change = abs(oldUnpackedScore - newUnpackedScore);
					chunkStats.totalChange += change;
					chunkStats.maxChange = chunkStats.maxChange.max(change);
					chunkStats.numChanged += oldPackedScore != newPackedScore;
				}
			}
			synchronized
			{
				stats.scoreSum += chunkStats.scoreSum;
				stats.totalChange += chunkStats.totalChange;
				stats.maxChange = stats.maxChange.max(chunkStats.maxChange);
				stats.numChanged += chunkStats.numChanged;

				numDone += chunkSize;
				stderr.write(100.0 * numDone / packedGameCard, "%     \r"); stderr.flush();
			}
		}
	}

	return stats;
}

void generateScoreFile()
{
	import std.stdio : writeln;

	stderr.writeln("=== Generating scores");

	auto fn = scoreFileName();
	if (!fn.exists)
	{
		writeln("Initializing scores...");
		void createFile(string target)
		{
			File(target, "wb").allocate(packedGameCard * PackedScore.sizeof);
			mapFile(target, MmMode.readWrite)
				.asDataOf!PackedScore
				.enter((scope PackedScore[] scores) {
					//scores[] = scoreIndeterminate;
					foreach (packedGame; packedGameCard.iota.parallel(packedGameCard / totalCPUs / 128))
						scores[packedGame] = scoreIndeterminate.packScore;
				});
		}
		atomic!createFile(fn);
	}

	bool stop = false;
	for (size_t iter = 0; !stop; iter++)
	{
		writeln("Iteration #", iter);

		auto nextFn = fn ~ "-next";
		{
			auto currentData = mapFile(fn, MmMode.read).asDataOf!PackedScore;
			auto current = currentData.unsafeContents;

			File(nextFn, "ab").allocate(packedGameCard * PackedScore.sizeof);

			auto nextData = mapFile(nextFn, MmMode.readWrite).asDataOf!PackedScore;
			auto next = nextData.unsafeContents;

			auto stats = propagateScores(current, next);

			Score changeLimit = 0.001;
			writeln(" > Avg.: ", stats.scoreSum / packedGameCard,
				", Change: num=", stats.numChanged, " / ", packedGameCard, " (", stats.numChanged * 100 / packedGameCard, "%)",
				// ", total=", stats.totalChange,
				", avg=", (double(stats.totalChange) / packedGameCard).fpToString,
				", max=", stats.maxChange, " / ", changeLimit,
			);

			if (stats.maxChange <= changeLimit)
			// if (crc in sawCRC)
				stop = true;
			// sawCRC[crc] = true;
		}

		atomicExchange(fn, nextFn);
	}
	stderr.writeln("Change threshold reached.");
}

version (main_graph)
void main()
{
	loadTables();
	generateScoreFile();
}

make_decision_tree.d

import core.atomic;

import ae.sys.data;
import ae.sys.datamm;
import ae.sys.file;
import ae.utils.array;
import ae.utils.math : TypeForBits;
import ae.utils.meta;
import ae.utils.parallelism;

import std.algorithm.comparison;
import std.algorithm.iteration;
import std.algorithm.searching;
import std.algorithm.sorting;
import std.array;
import std.digest.sha;
import std.format;
import std.math.algebraic;
import std.math.exponential;
import std.parallelism;
import std.range;
import std.stdio;
import std.sumtype;
import std.typecons;

import gamelogic : Move, expand;
import driver;
import game;
import graph;
import packing;

/// Consider choices which affect score by less than this as inconsequential
enum Score scoreThreshold = 0.25;

template makeTree(Game.State state)
{
	static if (state == Game.State.bet)
		alias Decision = Bet;
	else
	static if (state == Game.State.playerTurn)
		alias Decision = Move;
	else
		static assert(false);

	alias Outcomes = Score[enumLength!Decision];
	alias SignificantDecision = Nullable!Decision;
	enum SignificantDecision inconsequential = SignificantDecision.init;

	SignificantDecision getSignificantDecision(ref const Outcomes outcomes)
	{
		auto minScore = outcomes[].reduce!min;
		auto maxScore = outcomes[].reduce!max;
		if (maxScore - minScore < scoreThreshold)
			return inconsequential;
		foreach (Decision decision, outcome; outcomes)
			if (outcome == maxScore)
				return SignificantDecision(decision);
		assert(false);
	}

	static struct GraphDriver
	{
		PackedScore[] scores;
		this(PackedScore[] scores) { this.scores = scores; }

		enum interactive = false;
		void log(scope string delegate() message) /*nothrow @nogc*/ {}
		Score recurse(const ref Game game) nothrow @nogc
		{
			return scores[game.packGame()].unpackScore;
		}

		alias GetScore(T) = Score delegate(T) /*nothrow @nogc*/;

		// alias choice = graphChoice!GetScore;

		bool topLevel = true;
		bool decisionRecorded = false;
		SignificantDecision bestDecision;

		Score choice(ChoiceMode mode, T)(
			scope string delegate() description,
			scope Score delegate(T) /*nothrow @nogc*/ getScore,
			scope string delegate(T) getDescription,
			scope const(T)[] items...
		) //nothrow @nogc
		{
			alias impl = graphChoice!GetScore;

			if (topLevel)
			{
				assert(!decisionRecorded);
				static if (mode == ChoiceMode.best && (is(T == Decision)))
				{
					topLevel = false; scope(exit) topLevel = true;

					Outcomes outcomes;
					foreach (item; items)
						outcomes[item] = getScore(item);
					bestDecision = getSignificantDecision(outcomes);

					decisionRecorded = true;
					return Score.nan; // We got what we needed
				}
				else
					assert(false);
			}
			else
				return impl!(mode, T)(description, getScore, getDescription, items);
		}

		alias gameOver = graphGameOver;
	}

	SignificantDecision getBestDecision(ref const Game game, PackedScore[] scores)
	{
		auto driver = GraphDriver(scores);
		expand(game, &driver);
		assert(driver.decisionRecorded);
		return driver.bestDecision;
	}

	enum Variable : ubyte
	{
		// All states
		deckSize,
		deck1s,
		deck2s,
		deck3s,
		deck4s,
		deck5s,
		deck6s,
		deck7s,
		deck8s,
		deck9s,
		deck10s,
		deck11s,
		deckTotalValue,

		// Player turn only
		bet,
		handNumCards,
		handTotalValue,
	}

	enum variableCard = state == Game.State.bet ? Variable.bet : enumLength!Variable;

	alias VariableValue = ubyte;
	enum variableValueCard = VariableValue.max + 1;

	VariableValue getVariable(ref const Game game, Variable v)
	{
		final switch (v)
		{
			case Variable.deckSize:
				return cast(VariableValue)game.deck[].sum();
			case Variable.deck1s:
				return game.deck[1];
			case Variable.deck2s:
				return game.deck[2];
			case Variable.deck3s:
				return game.deck[3];
			case Variable.deck4s:
				return game.deck[4];
			case Variable.deck5s:
				return game.deck[5];
			case Variable.deck6s:
				return game.deck[6];
			case Variable.deck7s:
				return game.deck[7];
			case Variable.deck8s:
				return game.deck[8];
			case Variable.deck9s:
				return game.deck[9];
			case Variable.deck10s:
				return game.deck[10];
			case Variable.deck11s:
				return game.deck[11];
			case Variable.deckTotalValue:
				uint totalValue;
				foreach (value, count; game.deck)
					totalValue += value * count;
				if (totalValue > VariableValue.max)
					return VariableValue.max;
				return cast(VariableValue)totalValue;
			case Variable.bet:
				return cast(VariableValue)game.bet;
			case Variable.handNumCards:
				return game.hand.numCards;
			case Variable.handTotalValue:
				return game.hand.totalValue;
		}
	}

	enum Operation : ubyte
	{
		equals,      // yes = variable value == threshold
		greaterThan, // yes = variable value >= threshold
	}

	struct Question
	{
		Variable variable;
		VariableValue threshold;
		Operation operation;
	}

	bool query(ref const Question question, VariableValue value)
	{
		final switch (question.operation)
		{
			case Operation.greaterThan:
				return value >= question.threshold;
			case Operation.equals:
				return value == question.threshold;
		}
	}

	struct QuestionNode
	{
		Question question;
		Node*[2] leaves;
	}

	struct LeafNode
	{
		Decision decision;
	}

	alias Node = SumType!(QuestionNode, LeafNode);

	enum maxDepth = 64;
	alias Selection = TypeForBits!maxDepth;

	void makeTree()
	{
		auto scoresData = mapFile(scoreFileName(), MmMode.read).asDataOf!PackedScore;
		auto scores = scoresData.unsafeContents;

		stderr.writeln("Enumerating states...");

		auto packedGamesFileName = "data/states-%s-%s.u%d".format(state, scoreThreshold, PackedGame.sizeof * 8);
		packedGamesFileName.cached!((string target) {
			PackedGame[] packedGames;
			{
				stderr.writefln(" > Allocating...");
				auto gameViableData = TData!bool(packedGameCard);
				auto gameViable = gameViableData.unsafeContents;
				stderr.writefln(" > Filtering...");
				foreach (PackedGame packedGame; packedGameCard.iota.parallel)
				{
					auto game = packedGame.unpackGame();
					gameViable[packedGame] =
						game.state == state
						&&
						!getBestDecision(game, scores).isNull
					;
				}
				stderr.writefln(" > Counting...");
				packedGames.length = gameViable.sum();
				stderr.writefln(" > Collecting...");
				size_t i;
				foreach (PackedGame packedGame, bool isViable; gameViable)
					if (isViable)
						packedGames[i++] = packedGame;
				assert(i == packedGames.length);
			}
			packedGames.toFile(target);
		})();
		auto packedGamesData = packedGamesFileName.mapFile(MmMode.read).asDataOf!PackedGame;
		PackedGame[] packedGames = packedGamesData.unsafeContents;
		stderr.writefln(" > %d / %d states.", packedGames.length, packedGameCard);

		stderr.writeln("Getting best decisions...");

		auto bestDecisions = new Decision[packedGames.length];
		foreach (i, packedGame; packedGames.parallel)
		{
			auto game = packedGame.unpackGame();
			bestDecisions[i] = getBestDecision(game, scores).get();
		}

		auto selections = new Selection[packedGames.length];

		Node* search(size_t depth, Selection selection)
		{
			if (depth == maxDepth)
				assert(false, "Too deep!");
			stderr.writefln("Searching @ %d / %b...", depth, selection);

			Selection mask = (Selection(1) << depth) - 1;

			// Check if we've reached a leaf node
			{
				bool[enumLength!Decision] sawDecision;
				foreach (i, decision; bestDecisions)
					if ((selections[i] & mask) == selection)
					{
						if (!sawDecision[decision])
						{
							sawDecision[decision] = true;
							if (sawDecision[].sum > 1)
								break;
						}
					}
				assert(sawDecision[].sum > 0, "Zero-state division");
				if (sawDecision[].sum == 1)
				{
					foreach (Decision decision, saw; sawDecision)
						if (saw)
							return new Node(LeafNode(decision));
					assert(false);
				}
			}

			double bestScore = -double.infinity;
			Question bestQuestion;

			alias GameCount = PackedGame;

			foreach (Variable variable; Variable.init .. variableCard)
			{
				GameCount[enumLength!Decision][variableValueCard] values =
					packedGames.length.iota.parallelChunks((typeof(packedGames.length.iota) chunk) {
						PackedGame[enumLength!Decision][variableValueCard] chunkValues;
						foreach (i; chunk)
							if ((selections[i] & mask) == selection)
							{
								auto packedGame = packedGames[i];
								auto game = packedGame.unpackGame();
								auto value = getVariable(game, variable);
								chunkValues[value][bestDecisions[i]]++;
							}
						return chunkValues;
					})
					.reduce!((ref a, ref b) {
						auto v = a;
						foreach (i, ref row; v)
							row[] += b[i][];
						return v;
					});

				// How many states with each outcome we have in total
				GameCount[enumLength!Decision] totalValues = values                .reduce!((ref a, ref b) { auto v = a; v[] += b[]; return v; });
				GameCount totalStates = totalValues[].sum;

				foreach (Operation operation; Operation.init .. enumLength!Operation)
					foreach (VariableValue threshold; VariableValue(1) .. variableValueCard)
					{
						auto question = Question(variable, threshold, operation);

						// How many states with each outcome we have on each side
						GameCount[enumLength!Decision] leftValues  = variableValueCard.iota.filter!(value => query(question, cast(VariableValue)value) == false).map!(value => values[value]).reduce!((ref a, ref b) { auto v = a; v[] += b[]; return v; });
						GameCount[enumLength!Decision] rightValues = variableValueCard.iota.filter!(value => query(question, cast(VariableValue)value) == true ).map!(value => values[value]).reduce!((ref a, ref b) { auto v = a; v[] += b[]; return v; });

						// Total states on both sides
						GameCount leftStates  = leftValues [].sum;
						GameCount rightStates = rightValues[].sum;
						if (leftStates == 0 || rightStates == 0)
							continue;

						double score;

						{
							double entropy(ref const GameCount[enumLength!Decision] values)
							{
								GameCount total = values[].sum();
								double entropy = 0;
								foreach (GameCount value; values)
								{
									if (value > 0)
									{
										double p = double(value) / total;
										entropy -= p * log2(p);
									}
								}
								return entropy;
							}

							double entropyBeforeSplit = entropy(totalValues);
							double entropyAfterSplit = (
								entropy( leftValues) *  leftStates +
								entropy(rightValues) * rightStates
							) / totalStates;

							score = entropyBeforeSplit - entropyAfterSplit;
						}

						if (score > bestScore)
						{
							bestScore = score;
							bestQuestion = question;
							stderr.writefln(" > %s (%s): [%s : %s, %s : %s]",
								bestQuestion, bestScore,
								leftStates , leftValues [].filter!(n => n > 0).walkLength,
								rightStates, rightValues[].filter!(n => n > 0).walkLength,
							);
						}
					}
			}

			assert(bestScore > -double.infinity);

			// Apply selection
			foreach (i, packedGame; packedGames.parallel)
				if ((selections[i] & mask) == selection)
				{
					auto game = packedGame.unpackGame();
					auto value = getVariable(game, bestQuestion.variable);
					auto answer = query(bestQuestion, value);
					auto bit = Selection(answer) << depth;
					selections[i] = (selections[i] & mask) | bit;
				}

			return new Node(QuestionNode(bestQuestion, [
				search(depth + 1, selection),
				search(depth + 1, selection | (Selection(1) << depth)),
			]));
		}

		auto rootNode = search(0, 0);

		{
			auto f = File(format("%s-%s.dot", state, scoreThreshold), "wb");
			f.writeln("digraph {");
			f.writeln("\tnode [shape=box];");
			void dump(Node* node)
			{
				string text;
				ubyte[] bytes;
				Node*[string] children;

				(*node).match!(
					(ref QuestionNode n) {
						text = format("%s %s %d ?",
							n.question.variable,
							["=", "≥"][n.question.operation],
							n.question.threshold,
						);
						bytes = n.question.asBytes;
						children = [
							"No"  : n.leaves[0],
							"Yes" : n.leaves[1],
						];
					},
					(ref LeafNode n) {
						text = format("%s", n.decision);
						bytes = n.decision.asBytes;
					},
				);

				f.writefln("\tnode_%s [label=%(%s%)]", cast(void*)node, [text]);
				foreach (edgeLabel, child; children)
					f.writefln("\tnode_%s -> node_%s [label=%(%s%)];", cast(void*)node, cast(void*)child, [edgeLabel]);

				foreach (edgeLabel, child; children)
					dump(child);
			}
			dump(rootNode);
			f.writeln("}");
		}
	}
}

void main()
{
	loadTables();

	makeTree!(Game.State.bet)();
	makeTree!(Game.State.playerTurn)();
}

make_table_hands.d

import ae.utils.array;

import std.algorithm.comparison;
import std.algorithm.iteration;
import std.algorithm.sorting;
import std.array;
import std.stdio;

import packing;
import game;

PrePackedHand[] hands;

alias PlayerTurn = Hand;

void iterate(uint numRemainingCards, uint type, const Hand handSoFar)
{
	if (numRemainingCards > sum(fullDeck[type .. $]))
		return; // too many cards to fit
	if (handSoFar.totalValue >= 21)
		return; // win or bust

	if (type == 12)
	{
		assert(numRemainingCards == 0);
		assert(handSoFar.numCards <= 5);
		assert(handSoFar.totalValue <= 20);
		hands ~= handSoFar;
	}
	else
	{
		foreach (n; 0 .. min(numRemainingCards, fullDeck[type] * 2) + 1)
		{
			Hand nextHand = handSoFar;
			nextHand.numCards += n;
			nextHand.totalValue += n * type;
			iterate(numRemainingCards - n, type + 1, nextHand);
		}
	}
}

void main()
{
	foreach (n; 0 .. 5)
		iterate(n, 0, Hand.init);

	hands = hands.sort!((a, b) => a.asBytes < b.asBytes).uniq.array;
	writeln("Player: ", hands.length);
	File("data/player_turn.bin", "wb").rawWrite(hands);

	PrePackedDealerTurn[] dealerTurns;

	foreach (hand; hands)
		//writeln(numCards, " ", totalValue);
		foreach (ubyte playerTotalValue; hand.totalValue .. 21)
			dealerTurns ~= PrePackedDealerTurn(hand, playerTotalValue);

	dealerTurns = dealerTurns.sort!((a, b) => a.asBytes < b.asBytes).uniq.array;
	File("data/dealer_turn.bin", "wb").rawWrite(dealerTurns);
	writeln("Dealer: ", dealerTurns.length);
}

packing.d

import std.algorithm.iteration;
import std.algorithm.searching;
import std.algorithm.sorting;
import std.file;
import std.format;
import std.parallelism;
import std.range;
import std.sumtype;
import std.typecons;

import ae.sys.data;
import ae.sys.datamm;
import ae.sys.file;
import ae.utils.array;
import ae.utils.math.combinatorics;
import ae.utils.math.mixed_radix;
import ae.utils.meta;

import game;

// ------------------------- Items

private struct WithMax(T, T maxValue)
{
	this(PrePackedGameField value) in(value >= 0 && value <= maxValue) { this.value = cast(T)value; }
	T value;
	alias value this;
	enum T max = maxValue;
}

enum packedDeckCard = 59_765_625;
alias PackedDeck = WithMax!(uint, packedDeckCard - 1);

alias PrePackedHand = game.Hand; static assert(PrePackedHand.sizeof == 2);
struct PrePackedPlayerTurn { PrePackedHand hand; }
enum packedPlayerTurnCard = 66;
alias PackedPlayerTurn = WithMax!(ubyte, packedPlayerTurnCard - 1);

struct PrePackedDealerTurn { PrePackedHand hand; ubyte playerHandTotalValue; }
enum packedDealerTurnCard = 700;
alias PackedDealerTurn = WithMax!(ushort, packedDealerTurnCard - 1);

struct PackedLookup(Packed, PrePacked, alias compare = (ref a, ref b) => a < b)
{
	TData!PrePacked data;
	PrePacked[] prePacked;

	this(string filename)
	{
		data = mapFile(filename, MmMode.read).asDataOf!PrePacked;
		prePacked = data.unsafeContents;
		if (prePacked.length != Packed.max + 1)
			assert(false, "Data length mismatch: expected %s, got %s".format(Packed.max + 1, prePacked.length));
	}

	PrePacked unpack(Packed p) const
	in (p <= Packed.max)
	{
		return prePacked[p];
	}

	Packed pack(ref const PrePacked p) const
	{
		auto lb = prePacked
			.assumeSorted!compare
			.lowerBound(p);
		Packed packed; packed += lb.length;
		if (packed != lb.length)
			assert(false, "Overflow");
		if (prePacked[packed] != p)
		{
			debug
				assert(false, "Unknown pre-packed value: %s".format(p));
			else
				assert(false, "Unknown pre-packed value");
		}
		return packed;
	}

	Packed pack(const PrePacked p) const { return pack(p); }
}

int compare(T)(ref const T a, ref const T b)
{
	static if (is(T == struct))
	{
		static foreach (i; 0 .. T.tupleof.length)
		{{
			auto c = compare(a.tupleof[i], b.tupleof[i]);
			if (c)
				return c;
		}}
		return 0;
	}
	else
	static if (is(T == E[n], size_t n))
	{
		static foreach (i; 0 .. n)
		{{
			auto c = compare(a[i], b[i]);
			if (c)
				return c;
		}}
		return 0;
	}
	else
	static if (is(T : ulong))
		return a < b ? -1 : a > b ? 1 : 0;
	else
		static assert(false, "Unsupported type: " ~ T.stringof);
}

alias compareBytes = (ref a, ref b) => compare(a, b) < 0;
__gshared PackedLookup!(PackedPlayerTurn, PrePackedPlayerTurn, compareBytes) packedPlayerTurns;
__gshared PackedLookup!(PackedDealerTurn, PrePackedDealerTurn, compareBytes) packedDealerTurns;

void loadTables()
{
	packedPlayerTurns = typeof(packedPlayerTurns)("data/player_turn.bin");
	packedDealerTurns = typeof(packedDealerTurns)("data/dealer_turn.bin");
}


alias DeckCoder = MixedRadixCoder!(Card, PackedDeck);

PackedDeck packDeck(ref const Deck deck) nothrow @nogc
{
	DeckCoder.RetroEncoder e;
	foreach_reverse (i, value; deck)
	{
		auto cardinality = Game.init.deck[i]; cardinality++;
		e.put(value, cardinality);
	}
	return e.finish();
}

Deck unpackDeck(PackedDeck p) nothrow @nogc
{
	auto d = DeckCoder.Decoder(p);
	Deck deck;
	foreach (i, ref value; deck)
	{
		auto cardinality = Game.init.deck[i]; cardinality++;
		value = d.get(cardinality);
	}
	return deck;
}


struct PrePackedGame
{
	PackedDeck deck;

	struct BetState {}
	struct PlayerTurnState { PackedPlayerTurn turn; Bet bet; }
	struct DealerTurnState { PackedDealerTurn turn; Bet bet; }
	alias State = SumType!(
		BetState,
		PlayerTurnState,
		DealerTurnState,
	);
	State state;

	this(ref const Game game) nothrow @nogc
	{
		this.deck = packDeck(game.deck);
		this.state = {
			final switch (game.state)
			{
				case Game.State.bet:
					return State(BetState());
				case Game.State.playerTurn:
					return State(PlayerTurnState(
						packedPlayerTurns.pack(PrePackedPlayerTurn(game.hand)),
						game.bet,
					));
				case Game.State.dealerTurn:
					return State(DealerTurnState(
						packedDealerTurns.pack(PrePackedDealerTurn(game.hand, game.playerHandTotalValue)),
						game.bet,
					));
			}
		}();
	}

	Game unpack() nothrow @nogc
	{
		Game game;
		game.deck = unpackDeck(deck);
		state.match!(
			(BetState _) {
				game.state = Game.State.bet;
			},
			(PlayerTurnState state) {
				auto prePacked = packedPlayerTurns.unpack(state.turn);
				game.state = Game.State.playerTurn;
				game.hand = prePacked.hand;
				game.bet = state.bet;
			},
			(DealerTurnState state) {
				auto prePacked = packedDealerTurns.unpack(state.turn);
				game.state = Game.State.dealerTurn;
				game.hand = prePacked.hand;
				game.playerHandTotalValue = prePacked.playerHandTotalValue;
				game.bet = state.bet;
			},
		);
		return game;
	}
}

alias PrePackedGameField = uint; // biggest pre-packed game field
alias PackedGame = ulong;

alias GameSerializer = SerializationCoder!(MixedRadixCoder!(PrePackedGameField, PackedGame), PrePackedGame);

static assert(GameSerializer.minValue == 0);
immutable PackedGame packedGameCard = GameSerializer.cardinality;
// pragma(msg, packedGameCard);

bool canPack(ref const Game game) nothrow @nogc { return true; }
PackedGame packGame(Game game) nothrow @nogc { return GameSerializer.serialize(PrePackedGame(game)); }
Game unpackGame(PackedGame packed) nothrow @nogc { return GameSerializer.deserialize(packed).unpack(); }

version (main_packing)
void main()
{
	import std.stdio: stderr;

	// foreach (i; 0 .. packedGameCard)
	// {
	// 	if (i % 100_000 == 0) stderr.writeln(i, " / ", packedGameCard);
	// 	assert(i.unpackGame().packGame() == i);
	// }

	// while (true)
	// {
	// 	import std.random : uniform;
	// 	auto i = uniform(0, packedGameCard);
	// 	if (i % 100_000 == 0) stderr.writeln(i, " / ", packedGameCard);
	// 	assert(i.unpackGame().packGame() == i);
	// }

	while (true)
	{
		import std.random : uniform;
		import gamelogic : expand;
		import driver : Score, graphChoice, scoreIndeterminate;

		auto i = uniform(0, packedGameCard);
		if (i % 100_000 == 0) stderr.writeln(i, " / ", packedGameCard);
		auto game = i.unpackGame();

		struct Driver
		{
			enum interactive = false;
			void log(scope string delegate() message) nothrow @nogc {}

			Score recurse(const ref Game game) nothrow @nogc
			{
				assert(game.packGame().unpackGame() == game);
				return scoreIndeterminate;
			}

			alias choice = graphChoice;
			alias gameOver = graphGameOver;
		}
		auto driver = Driver();

		scope(failure) stderr.writeln(game);
		expand(game, driver, Opponent.init);
	}
}

solve.d

import ae.sys.data;
import ae.sys.datamm;
import ae.utils.array;
import ae.utils.meta;

import std.algorithm.iteration;
import std.algorithm.searching;
import std.conv;
import std.exception;
import std.file;
import std.stdio;
import std.string;

import driver;
import game;
import gamelogic;
import graph;
import packing;

static struct GraphDriver
{
	static GraphDriver create()
	{
		GraphDriver d;
		d.scores = mapFile(scoreFileName(), MmMode.read).asDataOf!PackedScore;
		return d;
	}

	TData!PackedScore scores;

	enum interactive = false;

	void log(scope string delegate() message) /*nothrow @nogc*/ {}

	Score recurse(const ref Game game) nothrow @nogc
	{
		// return expand.expand(game, &this);
		return scores[game.packGame()].unpackScore;
	}

	alias GetScore(T) = Score delegate(T) /*nothrow @nogc*/;

	// alias choice = graphChoice!GetScore;

	bool topLevel = true;
	string bestMove; Score bestScore;

	Score choice(ChoiceMode mode, T)(
		scope string delegate() description,
		scope Score delegate(T) /*nothrow @nogc*/ getScore,
		scope string delegate(T) getDescription,
		scope const(T)[] items...
	) //nothrow @nogc
	{
		alias impl = graphChoice!GetScore;

		if (topLevel)
		{
			static if (mode == ChoiceMode.best && (is(T == Move) || is(T == Bet)))
			{
				topLevel = false; scope(exit) topLevel = true;
				bestScore = 0;
				foreach (item; items)
				{
					auto score = getScore(item);
					if (score > bestScore)
					{
						bestScore = score;
						bestMove = getDescription(item);
					}
				}
				return Score.nan; // We got what we needed
			}
			else
				assert(false);
		}
		else
			return impl!(mode, T)(description, getScore, getDescription, items);
	}

	alias gameOver = graphGameOver;
}

void main()
{
	Game game;

	auto lines = "game.txt".readText.split1("\n");
	foreach (i, line; lines)
	{
		if (i % 3 == 2)
			enforce(line.length == 0, "Expected empty line");
		auto character = i % 3 == 0 ? Character.player : Character.dealer;
		Bet bet = Bet.minimum;
		if (character == Character.player && line.skipOver("M"))
			bet = Bet.maximum;
		auto cards = line.strip.split.map!(to!Card);
		// if (character == Character.player)
		// 	enforce(cards.length, "Unexpected empty line");

		foreach (card; cards)
		{
			enforce(game.deck[card], "No more cards with value %d".format(card));
			game.deck[card]--;
			if (game.deck[].sum == 0)
				game.deck = fullDeck; // shuffle
			if (character == Character.player && i + 1 == lines.length)
			{
				assert(character == Character.player);
				game.state = Game.State.playerTurn;
				game.bet = bet;
				game.hand.numCards++;
				game.hand.totalValue += card;
			}
		}
	}

	if (lines.length % 3 == 1)
	{
		loadTables();
		auto driver = GraphDriver.create();
		expand(game, &driver);

		writefln("Best move: %s (%s%%)", driver.bestMove, driver.bestScore * 100);
	}
	else
		writeln("OK (awaiting data)");
}