.gitignore

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

.gitmodules

[submodule "ae"]
	path = ae
	url = git@github.com: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.2495"
	dependency "x11" version="==1.0.16"
+/

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

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;
import ae.utils.regex;

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

// 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.copy;
}

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

int windowX, windowY, windowW, windowH;

void focus()
{
	//warpMouse(ScreenCoord(windowW / 2, windowH / 2));
	stderr.writeln("Waiting for game window...");
	auto result = execute(["xdotool", "search", "--sync", "--name", "SHENZHEN I/O", "windowactivate", "getwindowgeometry"]);
	enforce(result.status == 0, "xdotool failed");
	result.output.matchInto(`Window .*
  Position: (\d+),(\d+) \(screen: \d+\)
  Geometry: (\d+)x(\d+)
`, windowX, windowY, windowW, windowH);
	assert(windowW, "Couldn't parse window info: " ~ result.output);
}

Screen captureScreen()
{
	static bool focused;
	if (!focused)
	{
		focus();
		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
	{
		writefln("Trying with cardsLeftThreshold=%d", cardsLeftThreshold);

		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 = float.nan;

@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");

static if (is(typeof({import deimos.X11.X;})))
{
	// Official Deimos bindings
	import deimos.X11.X;
	import deimos.X11.Xlib;
}
else
{
	// Gary Willoughby's bindings (dub build)
	import x11.X;
	import 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 = int.min;
		static int lastY = int.min;
		if (lastX == int.min) lastX = windowW / 2;
		if (lastY == int.min) 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.toString(game));
		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, in float speed = 1f, int depth = 3)
{
	.speed = speed;
	.initialCardsLeftThreshold = depth;
	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 "step":
		{
			learn();
			auto screen = captureScreen();
			auto game = recognize(screen);
			auto moves = solve(game);
			if (moves.length)
				executeSolution(game, moves[0..1], screen);
			else
				writeln("No solution");
			break;
		}
		case "playloop":
			learn();
			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);

Hello Sir,

I try to use your bot on Win7. I have installed everything as described in http://worms2d.info/4/Development_setup with success.
From github I cloned this page with git clone https://gist.github.com/218d1ac4033b5d67d99ba5ec4e433b46.git with success

When in Geany I try to compile play.d I receive the following message:
play.d(1138): Error: module X is in file 'deimos\X11\X.d' which cannot be read

Can you please help?
A further question is that Shenzen's Solitaire has to be run parallel with Geany? Or an executable will start it somehow?

Thank you!

@fodormik you might need to use the dub package manager to install the dependencies ae and x11 and to build everything. I made it this far, but it looks like the x11 symbol names don't link on macOS.

brew install dmd dub
dub init   # supplying 'x11' and 'ae' as dependencies
dub generate build
mv play.d ./source/app.d   # renaming the source file will change the default build to 'application' instead of 'library'
dub run  # fails in the linking to X11 ... so close

If you even do get it to build and run, you would still have to manually edit all of the coordinates for the resolution of your display.

Well, I'm trying my best to build this but it keeps failing on one specific line, related to ae and I don't get why it fails (I tried to use older versions of ae in case a newer update broke something but to no avail):

play.d(674): Error: cannot implicitly convert expression `parseViaIMConvert(read(fileName, 4294967295u))` of type `BMP` to `Image!(Color!(ubyte, "b", "g", "r"))

@PewnyPL Breakage was due to this change in ae: CyberShadow/ae@aeafe98

Would not have happened if you built it with Dub (as per the shebang line), as the ae version is pinned in the header.

Pushed a fix for non-Dub builds for you :)

@CyberShadow Ooooh, I actually didn't notice the version posted in there. I actually ended up downloading a way older version of ae, got a different error, so I also downloaded an older version of dmd, at which point it compiled finally. Now, looking at dependencies here would be way smarter...

Hi All, maybe a very stupid question, however I am new to this. What program do you use to copy this code in? and how do you amend the size of the screen? Thanks for your help.

Failed to invoke the compiler dmd to determine the build platform: /bin/sh: line 1: dmd: command not found

nvm forgot to install dmd, now i have this

../../.dub/packages/x11-1.0.16/x11/source/x11/extensions/XI.d(3,8): Error: module `std.string` import `string` not found, did you mean alias `object.string`?
/usr/bin/dmd failed with exit code 1.

i fixed it by replacing import std.string : string; with import std.string; in that file, now i get this error and a bunch of deprecation warnings

play.d(1413,12): Error: template instance benchmark!benchFun template benchmark is not defined

i commented out line, now i get this https://pastebin.com/raw/FbzXvBsD

ok that seems to be because i've set the resolution incorrectly, i have a 1920x1080 screen (and 1366x768 right of that as my secondary one but shenzhen io is on the primary one), what do i set the variables to?

ok i've set the variables, but nope, they're completely wrong, i'm assuming cardStackX/Y is the top left pixel of the top left card, and foundation is the three free slots

nvm foundation is where all the cards should end up when you finish the game

I might port this to Kotlin as an exercise because it will teach me more about automation.