.gitignore

/play
/*.png
/*.bmp
/solitaire

.gitmodules

[submodule "ae"]
	path = ae
	url = [email protected]:CyberShadow/ae.git

README.md

Yeah. I wrote a bot for the solitaire game in SHENZHEN I/O.

Wait, I'll explain everything.

It all started yesterday evening, when I returned home from a birthday party. All great stuff, except that the hosts had a cat. And, even though cats are my favorite animal, I'm terribly allergic to them. Even though I had never even seen the fluffball that evening, the effects of his mere proximity would soon exert suffering upon me.

First, the headache. I thought I just had too much to drink - half a glass of red, but I'm a real lightweight. But then came the coughing and sneezing. Even though I had been home for hours, the delayed effects of exposure would still be felt for days to come.

Well, I could've just gone to bed. But then I saw a Steam news popup in the corner of the screen: SHENZHEN I/O had been updated, with added achievements. And one of them was:

BECOME IMMORTAL

Win 100 games of solitaire.

Well then.

At which point, a though came - "Hey, I haven't written any game bots in a while. How about another one?" And since I knew I would be mentally and physically incapable for much useful in the near future, here it is.

Anyway, the bot is a simple breadth-first search with no few shenanigans other than a bit of culling to keep video viewers from falling asleep, and sorting (normalizing) the game state to bin equivalent game states together. I've tried to keep the code reasonably readable, so have at it. And I've probably spent more time making the video look nice than working on the solver itself. (And I've had to reupload the video because dumbass me put a spoiler in like the first 5 seconds the first time.)

The moral implications of "BECOMING IMMORTAL" through technology rather than the intended long and diffult spiritual path to enlightenment, or whatever it was supposed to represent, and whether or not this solver counts as a Deus Ex Machina, is left as an exercise to the reader.

By the way, so far I hadn't encountered a dealt game that this solver couldn't find a solution for, so this puts it way ahead of me in the ratio of games I thought were solvable. Although this doesn't disprove that some games are impossible to solve, it does add some weight there.

play.d

#!/usr/bin/env dub
/+ dub.sdl:
	name "solitaire"
	dependency "ae" version="==0.0.1814"
	dependency "x11" version="==1.0.16"
+/

// ---------------------------------------------------------------------------------------------------------------------
// Configuration: Set these to the coordinates of the SHENZHEN I/O window.

// enum windowX = 1920;
// enum windowY = 0;
// enum windowW = 3840;
// enum windowH = 2160;

enum windowX = 1920 + (3840-windowW)/2;
enum windowY = (2160-windowH)/2;
enum windowW = 1366;
enum windowH = 768;

// ---------------------------------------------------------------------------------------------------------------------

import core.thread;

import std.algorithm.iteration;
import std.algorithm.mutation;
import std.algorithm.sorting;
import std.bitmanip;
import std.conv;
import std.datetime;
import std.exception;
import std.file;
import std.math;
import std.net.curl;
import std.parallelism;
import std.process;
import std.random;
import std.range;
import std.stdio;
import std.string;

import ae.utils.array;
import ae.utils.graphics.color;
import ae.utils.graphics.im_convert;
import ae.utils.graphics.image;
import ae.utils.math;
import ae.utils.meta;

// ---------------------------------------------------------------------------------------------------------------------

// Following coordinates are for a 4K (3840x2160) screen.

enum coordBaseW = 3840;
enum coordBaseH = 2160;

/// Distance, in pixels, from the top of a card to the top of the card it's stacked on
enum cardStackVDistance = 31;

/// Distance, in pixels, from the left edge of a stack of cards to the left edge of the stack of cards next to it.
enum cardStackHDistance = 152;

enum cardFreeCellHDistance = cardStackHDistance;

enum cardFoundationHDistance = cardStackHDistance;

enum cardStackX = 1364; // 163
enum cardStackY = 930;  // 299

enum cardFoundationX = 2124;
enum cardFoundationY = 666;

enum foundationMaxStackHeight = 8; // How many pixels are foundation cards allowed to creep up

enum cardFreeCellX = cardStackX; // Approx.
enum cardFreeCellY = cardFoundationY;  // Approx.

enum cardFlowerX = 1932; // Approx.
enum cardFlowerY = cardFoundationY; // Approx.

enum cardSigilDX = 8;
enum cardSigilDY = 8;
enum cardSigilW = 20;
enum cardSigilH = 20;

enum dragonButtonW = 57;
enum dragonButtonH = dragonButtonW;
enum dragonButtonLeftX = 1820;
enum dragonButton1TopY = 671;
enum dragonButtonVDistance = 83;

enum cardW = 121;
enum cardH = 232;

enum newGameBtnX = 2353;
enum newGameBtnY = 1453;
enum newGameBtnW = 244;
enum newGameBtnH = 45;

enum CardArea
{
	heap,
	freeCell,
	flower,
	foundation,
}

struct CardPos
{
	CardArea area;
	uint column;
	uint depth;
}

struct ScreenCoord { int x, y; }

int hOffset(int w)
{
	return w == 1366 ? -10 : 0;
}

int vOffset(int h)
{
	return h ==  768 ?  50 : 0;
}

ScreenCoord adjustByResolution(ScreenCoord coord, int w, int h)
{
	return ScreenCoord(
		coord.x - (coordBaseW - w) / 2 + hOffset(w),
		coord.y - (coordBaseH - h) / 2 + vOffset(h),
	);
}

ScreenCoord getScreenCoord(CardPos pos)
{
	final switch (pos.area)
	{
		case CardArea.heap:
			return ScreenCoord(
				cardStackX + pos.column * cardStackHDistance,
				cardStackY + pos.depth  * cardStackVDistance,
			);
		case CardArea.freeCell:
			return ScreenCoord(
				cardFreeCellX + pos.column * cardFreeCellHDistance,
				cardFreeCellY,
			);
		case CardArea.flower:
			return ScreenCoord(cardFlowerX, cardFlowerY);
		case CardArea.foundation:
			return ScreenCoord(
				cardFoundationX + pos.column * cardFoundationHDistance,
				cardFoundationY,
			);
	}
}

alias Screen = Image!BGR;

auto getCardImage(Screen screen, CardPos pos, int dy = 0)
{
	auto coord = getScreenCoord(pos).adjustByResolution(screen.w, screen.h);
	coord.x += cardSigilDX;
	coord.y += cardSigilDY;
	coord.y += dy;
	return screen.crop(
		coord.x,
		coord.y,
		coord.x + cardSigilW,
		coord.y + cardSigilH,
	);
}
alias CardImage = typeof(getCardImage(Screen.init, CardPos.init));

// ---------------------------------------------------------------------------------------------------------------------

enum freeCellCount = 3;
enum foundationCount = 3;
enum stackCount = 8;

enum CardSuit : ubyte
{
	empty,
	invalid,
	faceDown,
	flower,
	red,	// Colors are in dragon button order
	green,
	black,
	firstColor = red,
	lastColor = black,
}

enum CardRank : ubyte
{
	none,
	dragon,
	flower,
	rank1,
	rank2,
	rank3,
	rank4,
	rank5,
	rank6,
	rank7,
	rank8,
	rank9,
}

enum colorSuitCount = CardSuit.lastColor - CardSuit.firstColor + 1;
enum digitSuitCount = CardRank.rank9 - CardRank.rank1 + 1;
enum dragonPerSuitCount = 4;

enum initialCardCount = colorSuitCount * (digitSuitCount + dragonPerSuitCount) + 1 /* flower */;
static assert(initialCardCount == 40);

enum initialStackSize = initialCardCount / stackCount;
static assert(initialStackSize == 5);

struct Card
{
	mixin(bitfields!(
		CardSuit, "suit", 4,
		CardRank, "rank", 4,
	));

	static const char[enumLength!CardSuit] suitChars = "_X?FRGB";
	static const char[enumLength!CardRank] rankChars = "_DF123456789";

	string toString() const
	{
		return [suitChars[suit], rankChars[rank]].idup;
	}

	@property string longName() const
	{
		final switch (suit)
		{
			case CardSuit.empty:
				return "(empty)";
			case CardSuit.invalid:
				return "(invalid)";
			case CardSuit.faceDown:
				return "(face down)";
			case CardSuit.flower:
				return "flower card";
			case CardSuit.red:
			case CardSuit.green:
			case CardSuit.black:
				if (rank == CardRank.dragon)
					return "%s %s".format(suit, rank);
				else
					return "%s %s".format(suit, int(rank - CardRank.rank1 + 1));
		}
	}

	this(CardSuit suit, CardRank rank = CardRank.none)
	{
		this.suit = suit;
		this.rank = rank;
	}

	this(string s)
	{
		assert(s.length == 2);
		suit = cast(CardSuit)suitChars.indexOf(s[0]);
		rank = cast(CardRank)rankChars.indexOf(s[1]);
		assert(isValid, "Bad specification: " ~ s);
	}

	bool isValid() const
	{
		return cast(int)suit >= 0 && cast(int)rank >= 0;
	}
}

// ---------------------------------------------------------------------------------------------------------------------

// enum maxStackSize = 15;
enum maxStackSize = initialStackSize + (CardRank.rank9 - CardRank.rank1); // 5 (initial stack size) + 8 (max. cards stackable on top of the initial stack)
static assert(maxStackSize == 13);

struct Stack
{
	ubyte size;
	Card[maxStackSize] cards;
}

struct Game
{
	Stack[stackCount] stacks;
	Card[freeCellCount] freeCells;
	Card[foundationCount] foundations; // so we know what we can discard to there

	string toString() const
	{
		return format(
			"%-(%s %)   %s  %-(%s %)\n\n%-(%-(%s %)\n%)",
			freeCells,
			flowerDiscarded ? Card("FF") : Card.init,
			foundations,
			stacks[].map!((ref stack) => stack.cards[]).array.transposed,
		);
	}

	@property bool flowerDiscarded() const
	{
		foreach (ref stack; stacks)
			foreach (card; stack.cards)
				if (card.suit == CardSuit.flower)
					return false;
		return true;
	}

	@property uint cardsLeft() const
	{
		uint result;
		foreach (ref stack; stacks)
			result += stack.size;
		foreach (card; freeCells)
			result += card.suit >= CardSuit.firstColor ? 1 : 0;
		return result;
	}

	Card getCard(CardPos pos) const
	{
		final switch (pos.area)
		{
			case CardArea.heap:
				return stacks[pos.column].cards[pos.depth];
			case CardArea.freeCell:
				return freeCells[pos.column];
			case CardArea.foundation:
				return foundations[pos.column];
			case CardArea.flower:
				return flowerDiscarded ? Card.init : Card("FF");
		}
	}

	static Game randomGame()
	{
		Game game;
		game.stacks =
			chain(
				iota(CardSuit.firstColor, cast(CardSuit)(CardSuit.lastColor + 1)).map!(suit =>
					chain(
						iota(CardRank.rank1, cast(CardRank)(CardRank.rank9 + 1)),
						iota(dragonPerSuitCount).map!(n => CardRank.dragon),
					)
					.map!(rank => Card(suit, rank))
				)
				.joiner,
				Card("FF").only,
			)
			.array
			.randomCover
			.array
			.chunks(initialStackSize).map!(chunk =>
				Stack(initialStackSize, chain(
						chunk,
						Card.init.repeat(maxStackSize - initialStackSize),
					)
					.array[0..maxStackSize])
			)
			.array;
		return game;
	}
}

enum MoveKind : ubyte
{
	none, // start game
	moveCards,
	slayDragons,
}

/// Terse card position descriptor for moves.
/// 0..stackCount - that stack
/// stackCount..freeCellCount - that free cell
/// freeCellCount - foundation (target only)
alias Place = ubyte;

struct Move
{
	MoveKind kind;

	union
	{
		// MoveKind.moveCards:
		struct
		{
			Place from, to;
			ubyte count;
		}
		// MoveKind.slayDragons:
		struct
		{
			CardSuit suit;
		}
	}

	string toString(lazy string cardStr) const
	{
		final switch (kind)
		{
			case MoveKind.none:
				return "Start the game";
			case MoveKind.moveCards:
			{
				string placeStr(Place p)
				{
					return
						p < stackCount ? format("stack %d", p + 1) :
						p < stackCount + freeCellCount ? format("free cell %d", p - stackCount + 1) :
						format("the foundation");
				}
				return format("Move %s from %s to %s",
					cardStr,
					placeStr(from),
					placeStr(to),
				);
			}		
			case MoveKind.slayDragons:
				return "Slay the %s dragon".format(suit);
		}
	}

	string toString() const
	{
		return toString(count == 1 ? "a card" : format("%s cards", count));
	}

	string toString(const ref Game game) const
	{
		if (count == 1)
			return toString("the " ~ game.getCard(placeToCardPos(from, from, count, game)).longName);
		else
			return toString("%s cards (%s through %s)".format(count,
					game.getCard(placeToCardPos(from, from, count, game)).longName,
					game.getCard(placeToCardPos(from, from, 1, game)).longName));
	}
}

/// Is it allowed to stack the lower card on the upper card?
bool canStack(Card upper, Card lower)
{
	if (lower.rank < CardRank.rank1)
		return false;
	if (upper.suit == lower.suit)
		return false;
	if (upper.rank != lower.rank + 1)
		return false;
	return true;
}

ubyte getFoundationIndex(bool normalized)(CardSuit suit, const ref Game game)
{
	static if (normalized)
	{
		assert(suit >= CardSuit.firstColor && suit <= CardSuit.lastColor);
		return cast(ubyte)(suit - CardSuit.firstColor);
	}
	else
		foreach (ubyte foundationIndex, foundationCard; game.foundations)
			if (foundationCard.suit == suit || foundationCard.suit == CardSuit.empty)
				return foundationIndex;
	assert(false);
}

/// Attempt a move. Return true if successful.
/// If not, do not modify game.
bool tryMove(bool normalized)(Move move, ref Game game)
{
	final switch (move.kind)
	{
		case MoveKind.none:
			assert(false);
		case MoveKind.moveCards:
		{
			assert(move.from != move.to);
			assert(move.count > 0 && move.count <= maxStackSize);

			// Validate and collect source
			Card[] cards;
			if (move.from < stackCount)
			{
				assert(move.count <= game.stacks[move.from].size);
				auto stackSize = game.stacks[move.from].size;
				cards = game.stacks[move.from].cards[stackSize - move.count .. stackSize];
				foreach (i; 0..cards.length-1)
					if (!canStack(cards[i], cards[i+1]))
						return false; // TODO: Optimize? N^2
			}
			else
			{
				assert(move.from < stackCount + freeCellCount);
				auto freeCellIndex = move.from - stackCount;
				assert(move.count == 1);
				if (game.freeCells[freeCellIndex].suit <= CardSuit.faceDown)
					return false;
				cards = (&game.freeCells[freeCellIndex])[0..1];
			}

			// Validate and apply destination
			if (move.to < stackCount)
			{
				auto stackSize = game.stacks[move.to].size;
				if (stackSize)
				{
					if (!canStack(game.stacks[move.to].cards[stackSize-1], cards[0]))
						return false;
				}
				assert(stackSize + move.count <= maxStackSize);
				game.stacks[move.to].cards[stackSize..stackSize+move.count] = cards;
				game.stacks[move.to].size += move.count;
			}
			else
			if (move.to < stackCount + freeCellCount)
			{
				auto freeCellIndex = move.to - stackCount;
				assert(move.count == 1);
				if (game.freeCells[freeCellIndex].suit != CardSuit.empty)
					return false;
				game.freeCells[freeCellIndex] = cards[0];
			}
			else
			{
				assert(move.to == stackCount + freeCellCount);
				assert(move.count == 1);
				size_t foundationIndex = getFoundationIndex!normalized(cards[0].suit, game);
				if (game.foundations[foundationIndex].suit == CardSuit.empty)
				{
					if (cards[0].rank != CardRank.rank1)
						return false;
				}
				else
				{
					assert(game.foundations[foundationIndex].suit == cards[0].suit);
					if (cards[0].rank != game.foundations[foundationIndex].rank + 1)
						return false;
				}
				game.foundations[foundationIndex] = cards[0];
			}

			// Apply source
			if (move.from < stackCount)
			{
				auto stackSize = game.stacks[move.from].size -= move.count;
				game.stacks[move.from].cards[stackSize  .. stackSize + move.count] = Card.init;
			}
			else
			{
				auto freeCellIndex = move.from - stackCount;
				game.freeCells[freeCellIndex] = Card.init;
			}

			return true;
		}
		case MoveKind.slayDragons:
		{
			int haveFreeCellDragon = -1;
			uint exposedDragons;
			foreach (freeCellIndex; 0..freeCellCount)
			{
				auto card = game.freeCells[freeCellIndex];
				if (card.rank == CardRank.dragon && card.suit == move.suit)
				{
					if (haveFreeCellDragon < 0)
						haveFreeCellDragon = freeCellIndex;
					exposedDragons++;
				}
			}
			if (haveFreeCellDragon < 0)
			{
				foreach (freeCellIndex; 0..freeCellCount)
					if (game.freeCells[freeCellIndex].suit == CardSuit.empty)
					{
						haveFreeCellDragon = freeCellIndex;
						break;
					}
			}
			if (haveFreeCellDragon < 0)
				return false;

			foreach (stackIndex; 0..stackCount)
				if (game.stacks[stackIndex].size)
				{
					auto card = game.stacks[stackIndex].cards[game.stacks[stackIndex].size-1];
					if (card.rank == CardRank.dragon && card.suit == move.suit)
						exposedDragons++;
				}
			if (exposedDragons != dragonPerSuitCount)
				return false;

			foreach (freeCellIndex; 0..freeCellCount)
			{
				auto card = &game.freeCells[freeCellIndex];
				if (card.rank == CardRank.dragon && card.suit == move.suit)
					*card = Card.init;
			}
			foreach (stackIndex; 0..stackCount)
				if (game.stacks[stackIndex].size)
				{
					auto card = &game.stacks[stackIndex].cards[game.stacks[stackIndex].size-1];
					if (card.rank == CardRank.dragon && card.suit == move.suit)
					{
						*card = Card.init;
						game.stacks[stackIndex].size--;
					}
				}

			game.freeCells[haveFreeCellDragon].suit = CardSuit.faceDown;
			return true;
		}
	}
}

void findMoves(ref const Game game, void delegate(Move move, ref Game newGame) handler)
{
	Game newGame = game;
	Move move;
	move.kind = MoveKind.moveCards;
	foreach (Place from; 0..stackCount+freeCellCount)
	{
		if (from < stackCount && !game.stacks[from].size)
			continue;

		move.from = from;
		foreach (Place to; 0..stackCount+freeCellCount+1)
			if (from != to)
			{
				move.to = to;
				foreach (ubyte count; 1 .. ((from < stackCount && to < stackCount) ? game.stacks[from].size : 1) + 1)
				{
					move.count = count;
					if (tryMove!true(move, newGame))
					{
						handler(move, newGame);
						newGame = game;
					}
				}
			}
	}

	move.kind = MoveKind.slayDragons;
	foreach (CardSuit suit; CardSuit.firstColor .. cast(CardSuit)(CardSuit.lastColor+1))
	{
		move.suit = suit;
		if (tryMove!true(move, newGame))
		{
			handler(move, newGame);
			newGame = game;
		}
	}
}

// ---------------------------------------------------------------------------------------------------------------------

int imageDiff(CardImage a, CardImage b)
{
	assert(a.w == b.w);
	assert(a.h == b.h);

	ubyte norm(ubyte a, ubyte b)
	{
		auto d = cast(ubyte)abs(int(a) - int(b));
		return d < 50 ? 0 : cast(ubyte)(d - 50);
	}

	int diff;
	foreach (y; 0..a.h)
		foreach (x; 0..a.w)
		{
			diff += norm(a[x, y].r, b[x, y].r);
			diff += norm(a[x, y].g, b[x, y].g);
			diff += norm(a[x, y].b, b[x, y].b);
		}
	return diff;
}

CardImage[Card] cardImages;
CardImage[CardPos] blankImages;

Screen loadScreen(string fileName)
{
	return fileName.read.parseViaIMConvert!BGR;
}

Screen getReference(string fileName, string md5sum)
{
	if (!fileName.exists)
	{
		auto url = "https://dump.thecybershadow.net/" ~ md5sum ~ "/" ~ fileName;
		stderr.writeln("Downloading reference image from " ~ url);
		download(url, fileName);
	}
	return loadScreen(fileName);
}

Screen captureScreen()
{
	static bool focused;
	if (!focused)
	{
		warpMouse(ScreenCoord(windowW / 2, windowH / 2));
		focused = true;
	}
	enum fn = "screen.bmp";
	stderr.writeln("Invoking maim...");
	enforce(spawnProcess(["scrot", "--focused", fn]).wait() == 0, "scrot failed");
	//enforce(spawnProcess(["maim", "--geometry", "%dx%d+%d+%d".format(windowW, windowH, windowX, windowY), fn]).wait() == 0, "maim failed");
	stderr.writeln("Loading screen...");
	return loadScreen(fn);
}

void learn()
{
	stderr.writeln("Learning...");
	auto screen = getReference("reference.png", "3f360f09fc625901366cb724715b8ef4");
	void study(CardPos pos, Card card)
	{
		auto image = getCardImage(screen, pos);
		if (card.suit == CardSuit.empty)
			blankImages[pos] = image;
		else
		if (card in cardImages)
		{
			// stderr.writefln("Duplicate card %s already exists; diff = %d", card, imageDiff(cardImages[card], image));
			// image.toBMP.toFile(card.toString() ~ format("%s", imageDiff(cardImages[card], image)) ~ ".bmp");
		}
		else
		{
			cardImages[card] = image;
			//image.toBMP.toFile(card.toString() ~ ".bmp");
		}
	}

	study(CardPos(CardArea.heap, 0, 0), Card("R3"));
	study(CardPos(CardArea.heap, 0, 1), Card("RD"));
	study(CardPos(CardArea.heap, 0, 2), Card("B5"));
	study(CardPos(CardArea.heap, 0, 3), Card("B6"));
	study(CardPos(CardArea.heap, 0, 4), Card("BD"));

	study(CardPos(CardArea.heap, 1, 0), Card("G2"));
	study(CardPos(CardArea.heap, 1, 1), Card("FF"));
	study(CardPos(CardArea.heap, 1, 2), Card("B7"));
	study(CardPos(CardArea.heap, 1, 3), Card("R6"));

	study(CardPos(CardArea.heap, 2, 0), Card("G9"));
	study(CardPos(CardArea.heap, 2, 1), Card("R8"));
	study(CardPos(CardArea.heap, 2, 2), Card("BD"));
	study(CardPos(CardArea.heap, 2, 3), Card("RD"));
	study(CardPos(CardArea.heap, 2, 4), Card("B8"));

	study(CardPos(CardArea.heap, 3, 0), Card("G5"));
	study(CardPos(CardArea.heap, 3, 1), Card("B9"));
	study(CardPos(CardArea.heap, 3, 2), Card("RD"));
	study(CardPos(CardArea.heap, 3, 3), Card("B2"));
	study(CardPos(CardArea.heap, 3, 4), Card("GD"));

	study(CardPos(CardArea.heap, 4, 0), Card("G6"));
	study(CardPos(CardArea.heap, 4, 1), Card("G3"));
	study(CardPos(CardArea.heap, 4, 2), Card("GD"));
	study(CardPos(CardArea.heap, 4, 3), Card("RD"));
	study(CardPos(CardArea.heap, 4, 4), Card("B4"));

	study(CardPos(CardArea.heap, 5, 0), Card("BD"));
	study(CardPos(CardArea.heap, 5, 1), Card("G4"));
	study(CardPos(CardArea.heap, 5, 2), Card("R1"));
	study(CardPos(CardArea.heap, 5, 3), Card("R7"));
	study(CardPos(CardArea.heap, 5, 4), Card("R9"));

	study(CardPos(CardArea.heap, 6, 0), Card("G1"));
	study(CardPos(CardArea.heap, 6, 1), Card("R2"));
	study(CardPos(CardArea.heap, 6, 2), Card("BD"));
	study(CardPos(CardArea.heap, 6, 3), Card("B3"));
	study(CardPos(CardArea.heap, 6, 4), Card("G7"));

	study(CardPos(CardArea.heap, 7, 0), Card("R5"));
	study(CardPos(CardArea.heap, 7, 1), Card("GD"));
	study(CardPos(CardArea.heap, 7, 2), Card("R4"));
	study(CardPos(CardArea.heap, 7, 3), Card("G8"));
	study(CardPos(CardArea.heap, 7, 4), Card("GD"));

	study(CardPos(CardArea.foundation, 0, 0), Card("B1"));
	// study(CardPos(CardArea.foundation, 1, 0), Card("__"));
	// study(CardPos(CardArea.foundation, 2, 0), Card("__"));

	screen = getReference("reference2.png", "a8cd22a35b5d12f6f06192978353f5eb");

	study(CardPos(CardArea.freeCell, 1, 0), Card("?_"));

	screen = getReference("reference3.png", "22f78ac55347ff4352e2b8ff0766cef4");

	study(CardPos(CardArea.heap, 0, 0), Card("__"));
	study(CardPos(CardArea.heap, 1, 0), Card("__"));
	study(CardPos(CardArea.heap, 2, 0), Card("__"));
	study(CardPos(CardArea.heap, 3, 0), Card("__"));
	study(CardPos(CardArea.heap, 4, 0), Card("__"));
	study(CardPos(CardArea.heap, 5, 0), Card("__"));
	study(CardPos(CardArea.heap, 6, 0), Card("__"));
	study(CardPos(CardArea.heap, 7, 0), Card("__"));

	study(CardPos(CardArea.freeCell, 0, 0), Card("__"));
	study(CardPos(CardArea.freeCell, 1, 0), Card("__"));
	study(CardPos(CardArea.freeCell, 2, 0), Card("__"));

	study(CardPos(CardArea.foundation, 0, 0), Card("__"));
	study(CardPos(CardArea.foundation, 1, 0), Card("__"));
	study(CardPos(CardArea.foundation, 2, 0), Card("__"));

	stderr.writeln("Done learning.");
}

Game recognize(Screen screen)
{
	Card read(CardPos pos)
	{
		foreach (dy; 0 .. (pos.area == CardArea.foundation ? foundationMaxStackHeight : 0) + 1)
		{
			auto image = getCardImage(screen, pos, -dy);
			if (dy == 0 && pos in blankImages && imageDiff(blankImages[pos], image)==0)
				return Card(CardSuit.empty);
			foreach (card, cardImage; cardImages)
				if (imageDiff(image, cardImage) == 0)
					return card;
		}
		return Card(pos.area == CardArea.heap ? CardSuit.empty : CardSuit.invalid);
	}

	Game game;
	foreach (stack; 0..stackCount)
		foreach (ubyte col; 0..maxStackSize)
		{
			game.stacks[stack].cards[col] = read(CardPos(CardArea.heap, stack, col));
			if (game.stacks[stack].cards[col].suit != CardSuit.empty)
				game.stacks[stack].size = cast(ubyte)(col+1);
		}
	foreach (stack; 0..freeCellCount)
		game.freeCells[stack] = read(CardPos(CardArea.freeCell, stack));
	foreach (stack; 0..foundationCount)
		game.foundations[stack] = read(CardPos(CardArea.foundation, stack));
	writeln(game);
	return game;
}

// ---------------------------------------------------------------------------------------------------------------------

void prepareGame(ref Game game)
{
	Card[enumLength!CardSuit] foundationSuits;
	foreach (card; game.foundations)
		foundationSuits[card.suit] = card;
	foreach (i, ref card; game.foundations)
		card = foundationSuits[CardSuit.firstColor + i];
}

/// Perform any automatic changes after a player move,
/// such as automatically discarding the flower card.
/// Returns the number of such actions done.
uint settleGame(bool gameIsNormalized)(ref Game game)
{
	uint actions;
recheck:
	// Discard flower
	foreach (stackIndex; 0..stackCount)
	{
		auto stackSize = game.stacks[stackIndex].size;
		if (stackSize && game.stacks[stackIndex].cards[stackSize-1].suit == CardSuit.flower)
		{
			game.stacks[stackIndex].cards[stackSize-1] = Card.init;
			game.stacks[stackIndex].size--;
			actions++;
		}
	}
	// Forcibly discard ranks into foundation (also to avoid search space explosion)
	{
		CardRank minRank = CardRank.rank9;
		foreach (card; game.foundations)
			if (minRank > card.rank)
				minRank = card.rank;
		if (minRank < CardRank.rank1)
			minRank = CardRank.rank1;
		minRank++; // at or one above minimal rank

		bool tryCard(Card card)
		{
			if (card.suit >= CardSuit.firstColor)
			{
				size_t foundationIndex = getFoundationIndex!gameIsNormalized(card.suit, game);
				auto foundationCard = &game.foundations[foundationIndex];
				if (card.rank >= CardRank.rank1 && card.rank <= minRank && ((foundationCard.rank == CardRank.none && card.rank == CardRank.rank1) || (card.rank == foundationCard.rank + 1)))
				{
					*foundationCard = card;
					return true;
				}
			}
			return false;
		}

		foreach (stackIndex; 0..stackCount)
		{
			auto stackSize = game.stacks[stackIndex].size;
			if (stackSize)
			{
				auto card = game.stacks[stackIndex].cards[stackSize-1];
				if (tryCard(card))
				{
					game.stacks[stackIndex].cards[stackSize-1] = Card.init;
					game.stacks[stackIndex].size--;
					actions++;
					goto recheck;
				}
			}
		}

		foreach (ref card; game.freeCells)
			if (tryCard(card))
			{
				card = Card.init;
				actions++;
				goto recheck;
			}
	}
	return actions;
}

/// Given a game state, its normalized version, and a move for the normalized version,
/// translate the move to have the same effect on the un-normalized game state.
Move denormalizeMove(ref Game normalizedGame, ref Game unnormalizedGame, Move normalizedMove)
{
	if (normalizedMove.kind != MoveKind.moveCards)
		return normalizedMove;

	ubyte[][Stack] stackOrder;
	ubyte[][Card] freeCellOrder;
	foreach (ubyte stackIndex; 0..stackCount)
		stackOrder[unnormalizedGame.stacks[stackIndex]] ~= stackIndex;
	foreach (ubyte freeCellIndex; 0..freeCellCount)
		freeCellOrder[unnormalizedGame.freeCells[freeCellIndex]] ~= freeCellIndex;

	Place translatePlace(Place place)
	{
		if (place < stackCount)
			return stackOrder[normalizedGame.stacks[place]].queuePop();
		// Free cells
		if (place < stackCount + freeCellCount)
		{
			auto freeCellIndex = place - stackCount;
			return cast(Place)(stackCount + freeCellOrder[normalizedGame.freeCells[freeCellIndex]].queuePop());
		}
		// Foundations
		return place;
	}

	Move denormalizedMove;
	denormalizedMove.kind = normalizedMove.kind;
	denormalizedMove.from = translatePlace(normalizedMove.from);
	denormalizedMove.to = translatePlace(normalizedMove.to);
	denormalizedMove.count = normalizedMove.count;
	return denormalizedMove;
}

/// Normalize functionally equivalent game states into a single canonical representation.
void normalizeGame(ref Game game)
{
	// Sort stuff
	sort(cast(ubyte[])(game.freeCells[]));
	sort(cast(ubyte[Stack.sizeof][])(game.stacks[]));
}

shared int initialCardsLeftThreshold = 3;

Move[] solve(Game origGame)
{
	stderr.writeln("Thinking...");
	auto initGame = origGame;
	prepareGame(initGame);
	normalizeGame(initGame);

	static struct Step
	{
		Game* game;
		Move move;
	}

	// Try to find a solution as quickly as possible.
	// As such, start out in rather greedy mode
	// (cull game states that have many more cards than
	// the best solution so far), and get less greedy
	// if we exhaust the search.
	int cardsLeftThreshold = initialCardsLeftThreshold;

	Step[Game] sawGame;
	Game* solution;

	do
	{
		sawGame = null;
		sawGame[initGame] = Step.init;

		solution = null;
		Game[] queue = [initGame];

		int minCardsLeft = initGame.cardsLeft;

		while (queue.length && !solution)
		{
			auto game = queue.ptr;
			queue = queue[1..$];

			if (game.cardsLeft > minCardsLeft + cardsLeftThreshold)
				continue; // Cull!

			findMoves(*game,
				(Move move, ref Game newGame)
				{
					settleGame!true(newGame);
					normalizeGame(newGame);
					if (newGame !in sawGame)
					{
						sawGame[newGame] = Step(game, move);
						queue ~= newGame;
						// if (queue.length % 10000 == 0)
						// 	writeln(newGame.cardsLeft, " ", queue.length);
						// 	writeln(newGame);
						static bool[initialCardCount + 1] sawCardsLeft;
						auto cardsLeft = newGame.cardsLeft;
						if (!sawCardsLeft[cardsLeft])
						{
							writeln(cardsLeft, " ", queue.length);
							sawCardsLeft[cardsLeft] = true;
						}
						if (minCardsLeft > cardsLeft)
							minCardsLeft = cardsLeft;
						if (cardsLeft == 0)
							solution = &queue[$-1];
					}
				});
		}
		if (solution)
			break;
		cardsLeftThreshold += (cardsLeftThreshold/5) + 1;
	} while (cardsLeftThreshold < initialCardCount);

	if (solution)
	{
		writefln("Found solution with cardsLeftThreshold=%d", cardsLeftThreshold);

		Step[] path;
		for (Step step = sawGame[*solution]; step.game; step = sawGame[*step.game])
			path ~= step;
		path.reverse();

		auto denormalizedGame = origGame;

		Move[] denormalizedMoves;
		foreach (ref step; path)
		{
			auto move = denormalizeMove(*step.game, denormalizedGame, step.move);
			denormalizedMoves ~= move;
			auto result = tryMove!false(move, denormalizedGame);
			assert(result);
			settleGame!false(denormalizedGame);
		}
		return denormalizedMoves;
	}
	else
		return null;
}

void printSolution(Game game, Move[] moves)
{
	foreach (move; moves)
	{
		writeln(game);
		writeln(move.toString(game));
		auto result = tryMove!false(move, game);
		assert(result);
		settleGame!false(game);
	}
	writeln(game);
}

// ---------------------------------------------------------------------------------------------------------------------

/// Get the center-most coordinates from which we can start dragging a specific card.
ScreenCoord getCardCoord(CardPos pos, Screen screen, const ref Game game, bool topOnly)
{
	auto coords = getScreenCoord(pos).adjustByResolution(screen.w, screen.h);
	coords.x += cardW / 2;
	coords.y += (topOnly ? cardStackVDistance : cardH) / 2;
	if (pos.area == CardArea.foundation)
	{
		auto card = game.getCard(pos);
		if (card.suit != CardSuit.empty)
			coords.y -= card.rank - CardRank.rank1;
	}
	return coords;
}

CardPos placeToCardPos(Place place, Place from, ubyte depth, const ref Game game)
{
	if (place < stackCount)
		return CardPos(CardArea.heap, place, game.stacks[place].size - depth);
	else
	if (place < stackCount + freeCellCount)
		return CardPos(CardArea.freeCell, place - stackCount, 0);
	else
	if (place == stackCount + freeCellCount)
		return CardPos(CardArea.foundation, getFoundationIndex!false(game.getCard(placeToCardPos(from, from, 1, game)).suit, game), 0);
	else
		assert(false);
}

Duration scaleDuration(Duration d, float f) { return hnsecs(cast(long)(d.total!"hnsecs" * f)); }

enum instantMove = false;
float speed = 1f;

@property moveDurationBase() { return 200.msecs.scaleDuration(speed); }
@property moveDurationPerPixel() { return 1.msecs.scaleDuration(speed); }
@property moveDelay() { return 0.msecs + 100.msecs.scaleDuration(speed); }
@property clickDelay() { return 20.msecs + 100.msecs.scaleDuration(speed); }

enum settleDelay = 265.msecs; // per action
enum dragonDelay = 400.msecs;
enum waterfallDelay = 2500.msecs;
enum dealDelay = 4500.msecs + 3*settleDelay;

pragma(lib, "X11");

import deimos.X11.X;
import deimos.X11.Xlib;

void warpMouse(ScreenCoord coord)
{
	//enforce(spawnProcess(["xdotool", "mousemove", text(windowX + coord.x), text(windowY + coord.y)]).wait() == 0, "xdotool failed");

	static Display *dpy;
	if (!dpy)
		dpy = XOpenDisplay(null);
	enforce(dpy, "Can't open display!");

	auto rootWindow = XRootWindow(dpy, 0);
	XSelectInput(dpy, rootWindow, KeyReleaseMask);
	XWarpPointer(dpy, None, rootWindow, 0, 0, 0, 0, windowX + coord.x, windowY + coord.y);
	XFlush(dpy);
}

float ease(float t, float speed)
{
	speed = 0.3f + speed * 0.4f;
	t = t * 2 - 1;
	t = (1-pow(1-abs(t), 1/speed)) * sign(t);
	t = (t + 1) / 2;
	return t;
}

void mouseMove(ScreenCoord coord)
{
	if (!instantMove)
	{
		static int lastX = windowW / 2;
		static int lastY = windowH / 2;

		auto xSpeed = uniform01!float;
		auto ySpeed = uniform01!float;

		auto moveDuration = moveDurationBase + cast(int)sqrt(float(sqr(coord.x - lastX) + sqr(coord.y - lastY))) * moveDurationPerPixel;

		auto start = MonoTime.currTime();
		auto end = start + moveDuration;
		while (true)
		{
			auto now = MonoTime.currTime();
			if (now >= end)
				break;
			float t = 1f * (now - start).total!"hnsecs" / moveDuration.total!"hnsecs";
			warpMouse(ScreenCoord(
				lastX + cast(int)(ease(t, xSpeed) * (coord.x - lastX)),
				lastY + cast(int)(ease(t, ySpeed) * (coord.y - lastY)),
			));
			Thread.sleep(1.msecs);
		}
		lastX = coord.x;
		lastY = coord.y;
	}
	warpMouse(coord);
	Thread.sleep(moveDelay);
}

void mouseButton(bool down)
{
	// Clicking is hard, just use xdotool
	enforce(spawnProcess(["xdotool", down ? "mousedown" : "mouseup", "1"]).wait() == 0, "xdotool failed");
	Thread.sleep(clickDelay);
}

void executeMove(Screen screen, Move move, const ref Game game)
{
	final switch (move.kind)
	{
		case MoveKind.none:
			assert(false);
		case MoveKind.moveCards:
			mouseMove(getCardCoord(placeToCardPos(move.from, move.from, move.count, game), screen, game, move.count > 1));
			mouseButton(true);
			mouseMove(getCardCoord(placeToCardPos(move.to, move.from, 0, game), screen, game, move.count > 1));
			mouseButton(false);
			break;
		case MoveKind.slayDragons:
			mouseMove(ScreenCoord(
				dragonButtonLeftX + dragonButtonW / 2,
				dragonButton1TopY + dragonButtonH / 2 + dragonButtonVDistance * (move.suit - CardSuit.firstColor),
			).adjustByResolution(screen.w, screen.h));
			mouseButton(true);
			mouseButton(false);
			Thread.sleep(dragonDelay);
			break;
	}
}

void newGame(Screen screen)
{
	auto coord = ScreenCoord(
		newGameBtnX + newGameBtnW / 2,
		newGameBtnY + newGameBtnH / 2,
	).adjustByResolution(screen.w, screen.h);
	if (screen.h == 768)
		coord.y = screen.h - 17 - newGameBtnH / 2;
	mouseMove(coord);
	mouseButton(true);
	mouseButton(false);
}

void runSolitaire(Screen screen)
{
	mouseMove(ScreenCoord(752, screen.h-187));
	mouseButton(true);
	mouseButton(false);
}

void home(Screen screen)
{
	mouseMove(ScreenCoord(20, screen.h/2-55));
	mouseButton(true);
	mouseButton(false);
}

void exitGame(Screen screen)
{
	mouseMove(ScreenCoord(screen.w-57, 56));
	mouseButton(true);
	mouseButton(false);
	warpMouse(ScreenCoord(screen.w + 10, screen.h - 10));
}

void executeSolution(Game game, Move[] moves, Screen screen)
{
	foreach (move; moves)
	{
		writeln(game);
		writeln(move);
		executeMove(screen, move, game);
		auto result = tryMove!false(move, game);
		assert(result);
		auto actions = settleGame!false(game);
		Thread.sleep(actions * settleDelay);
	}
	writeln(game);
	Thread.sleep(waterfallDelay);
}

// ---------------------------------------------------------------------------------------------------------------------

void solitaire(string action)
{
	switch (action)
	{
		case "solve":
		{
			learn();
			auto screen = captureScreen();
			auto game = recognize(screen);
			auto moves = solve(game);
			printSolution(game, moves);
			break;
		}
		case "solve-last":
		{
			learn();
			auto screen = loadScreen("screen.bmp");
			auto game = recognize(screen);
			auto moves = solve(game);
			printSolution(game, moves);
			break;
		}
		case "play":
		{
			learn();
			auto screen = captureScreen();
			auto game = recognize(screen);
			auto moves = solve(game);
			executeSolution(game, moves, screen);
			newGame(screen);
			Thread.sleep(dealDelay);
			break;
		}
		case "playloop":
			learn();
			speed = 0.5f;
			while (true)
			{
				auto screen = captureScreen();
				auto game = recognize(screen);
				auto moves = solve(game);
				enforce(moves, "Failed to solve the game");
				executeSolution(game, moves, screen);

				newGame(screen);
				Thread.sleep(dealDelay);
			}
		case "demo":
		{
			learn();
			foreach_reverse (n; 0..5)
			{
				writefln("Starting demo in %d...", n);
				Thread.sleep(1.seconds);
			}
			auto shenzhenIO = spawnProcess(["/home/vladimir/.steam/root/steamapps/common/SHENZHEN IO/Shenzhen.bin.x86_64"]);
			Thread.sleep(10.seconds);

			speed = 2f;
			auto screen = captureScreen();
			runSolitaire(screen);
			Thread.sleep(1.seconds);
			Thread.sleep(dealDelay);

			enum games = 5;
			foreach (n; 0..games)
			{
				speed = 1f - (1f * n / (games-1));
				screen = captureScreen();
				auto game = recognize(screen);
				auto moves = solve(game);
				enforce(moves, "Failed to solve the game");
				executeSolution(game, moves, screen);

				speed = 1f;
				if (n + 1 < games)
				{
					newGame(screen);
					Thread.sleep(dealDelay);
				}
			}

			speed = 2f;
			home(screen);
			exitGame(screen);
			Thread.sleep(5.seconds);
			break;
		}
		case "new-game":
			newGame(captureScreen());
			break;
		case "bench":
		{
			initialCardsLeftThreshold = 0;
			enum games = 10;
			enum runs = 10;
			static void benchFun()
			{
				rndGen.seed(1);
				foreach (n; 0..games)
				{
					auto game = Game.randomGame();
					settleGame!false(game);
					solve(game);
				}
			}
			writeln(benchmark!benchFun(runs)[0].to!Duration);
			break;
		}
		case "solve-random-loop":
		{
			initialCardsLeftThreshold = 0;
			int solved, unsolved;
			foreach (n; long.max.iota.parallel)
			{
				auto game = Game.randomGame();
				settleGame!false(game);
				writeln(game);
				auto moves = solve(game);
				synchronized
				{
					(moves ? solved : unsolved)++;
					auto total = solved+unsolved;
					//printSolution(game, moves);
					writefln("Solved %d/%d (%d%%)", solved, total, 100*solved/total);
				}
			}
			assert(false);
		}
		default:
			throw new Exception("Unknown action: " ~ action);
	}
}

import ae.utils.funopt;
import ae.utils.main;
mixin main!(funopt!solitaire);