Inscryption solver

.gitignore

/problem
/solution.txt

game.d

import core.bitop : popcnt;

import std.algorithm.comparison : min, among;
import std.algorithm.iteration;
import std.algorithm.mutation : swap;
import std.algorithm.searching;
import std.array;
import std.conv;
import std.math.algebraic : abs;
import std.random;
import std.range;
import std.string;
import std.traits : EnumMembers;

import ae.utils.meta;
import ae.utils.text : camelCaseJoin;

enum AbilityIndex
{
	rabbitHole,
	beesWithin,
	sprinter,
	touchOfDeath,
	fledgling,
	damBuilder,
	hoarder,
	burrower,
	fecundity,
	looseTail,
	corpseEater,
	boneKing,
	waterborne, // the one with the tail
	unkillable,
	sharpQuills,
	hefty,
	antSpawner,
	guardian,
	airborne,
	manyLives,
	repulsive,
	worthySacrifice,
	mightyLeap,
	bifurcatedStrike,
	trifurcatedStrike,
	frozenAway,
	trinketBearer,
	steelTrap,
	amorphous,
	tidalLock,
	omniStrike,
	leader,
	brittle,
	bellist,
	annoying,
	stinky,
	waterborne2, // the one with the tentacle
	madeOfStone,
}

mixin({
	string s;
	s ~= `enum Abilities : ulong {`;
	s ~= `none = 0,`;
	s ~= `unknown = cast(ulong)-1L,`;
	foreach (index; EnumMembers!AbilityIndex)
	{
		enum name = __traits(identifier, EnumMembers!AbilityIndex[index]);
		s ~= name ~ " = 1UL << AbilityIndex." ~ name ~ ",";
	}
	s ~= "}";
	return s;
}());

enum ClanIndex
{
	squirrel,
	canine,
	deer,
	bug,
	reptile,
	bird,
}

mixin({
	string s;
	s ~= `enum Clans : ubyte {`;
	s ~= `none = 0,`;
	s ~= `unknown = cast(ubyte)-1,`;
	foreach (index; EnumMembers!ClanIndex)
	{
		enum name = __traits(identifier, EnumMembers!ClanIndex[index]);
		s ~= name ~ " = 1UL << ClanIndex." ~ name ~ ",";
	}
	s ~= "}";
	return s;
}());

// Special values
enum : byte
{
	unknown = -100,
	ants,
	oneHalfBones,
	mirrorSomething, // ?
	bellRinger, // ?
	cardCounter, // ?
	spilledBlood,
}

private struct CostDef
{
	enum Type : ubyte
	{
		blood,
		bones,
	}
	Type type;
	byte amount;

	byte totalBlood() const { return type == Type.blood ? amount : 0; }
	byte totalBones() const { return type == Type.bones ? amount : 0; }
}

enum CardFlags : ubyte
{
	none = 0,
	// Definitions
	noSacrifice = 1 << 0, // cannot attack; can't be sacrificed
	rare        = 1 << 1,
	// Transient state
	sprintLeft  = 1 << 2,
}

CostDef blood(byte amount) { return CostDef(CostDef.Type.blood, amount); }
CostDef bones(byte amount) { return CostDef(CostDef.Type.bones, amount); }
enum CostDef noCost = 0.blood;
enum CostDef unknownCost = (-1).blood;

private struct CardDef
{
	string name;
	CostDef cost;
	byte attack = unknown;
	byte health = unknown;
	CardFlags flags = CardFlags.none;
	Clans clans = Clans.unknown;
	Abilities abilities = Abilities.unknown;
}

private immutable CardDef[] cardDefs = {
	alias F = CardFlags;
	alias C = Clans;
	alias A = Abilities;

	immutable CardDef[] result = [
		{"None"},

		//                                Cost       Attack HP  Flags          Clan        Ability
		{"Squirrel"              ,      noCost,           0, 1, F.none,        C.squirrel, A.none}, // note: clan is implicit; totem head exists
		{"Stoat"                 ,     1.blood,           1, 3, F.none,        C.none,     A.none},
		{"Wolf"                  ,     2.blood,           3, 2, F.none,        C.canine,   A.none},
		{"Wolf Cub"              ,     1.blood,           1, 1, F.none,        C.canine,   A.fledgling},
		{"River Snapper"         ,     2.blood,           1, 6, F.none,        C.reptile,  A.none},
		{"Grizzly"               ,     3.blood,           4, 6, F.none,        C.none,     A.none},
		{"Sparrow"               ,     1.blood,           1, 2, F.none,        C.bird,     A.airborne},
		{"Cat"                   ,     1.blood,           0, 1, F.none,        C.unknown,  A.manyLives},
		{"Porcupine"             , unknownCost,           1, 2, F.none,        C.unknown,  A.sharpQuills},
		{"Elk"                   ,     2.blood,           2, 4, F.none,        C.deer,     A.sprinter},
		{"Elk Fawn"              ,     1.blood,           1, 1, F.none,        C.deer,     A.sprinter | A.fledgling},
		{"Stinkbug"              ,     2.bones,           1, 2, F.none,        C.bug,      A.stinky},
		{"Bullfrog"              ,     1.blood,           1, 4, F.none,        C.reptile,  A.mightyLeap},
		// {"Corpse Maggots"        ,     5.bones,           1, 2, F.none,        C.unknown,  A.corpseEater},
		// {"Strange Larva"         ,     1.blood,           0, 3, F.rare,        C.unknown,  A.fledgling}, // TODO evolution
		{"Worker Ant"            ,     1.blood,        ants, 2, F.none,        C.bug,      A.unknown},
		{"Ant Queen"             ,     2.blood,        ants, 3, F.none,        C.unknown,  A.antSpawner},
		{"Caged Wolf"            ,     2.blood,           0, 6, F.noSacrifice, C.canine,   A.none},
		{"Kingfisher"            ,     1.blood,           1, 1, F.none,        C.bird,     A.airborne | A.waterborne},
		{"Ring Worm"             ,     1.blood,           0, 1},
		{"Pack Rat"              ,     2.blood,           2, 2, F.none,        C.none,     A.trinketBearer},
		{"Child 13"              ,     1.blood,           0, 1, F.rare,        C.deer,     A.manyLives},
		{"Rattler"               ,     6.bones,           3, 1, F.none,        C.reptile,  A.none},
		{"Adder"                 ,     2.blood,           1, 1, F.none,        C.reptile,  A.touchOfDeath},
		{"Magpie"                ,     2.blood,           1, 1, F.none,        C.bird,     A.airborne | A.hoarder},
		{"Coyote"                ,     4.bones,           2, 1, F.none,        C.canine,   A.none},
		{"Cockroach"             ,     4.bones,           1, 1, F.none,        C.bug,      A.unkillable},
		{"Bee"                   , /*?*/noCost,           1, 1, F.none,        C.bug,      A.airborne},
		{"Opossum"               ,     2.bones,           1, 1, F.none,        C.none,     A.none},
		{"Rat King"              ,     2.blood,           2, 1, F.none,        C.none,     A.boneKing},
		{"Urayuli"               ,     4.blood,           7, 7, F.rare,        C.none,     A.none},
		{"Turkey Vulture"        ,     8.bones,           3, 3, F.none,        C.bird,     A.airborne},
		{"Skunk"                 ,     1.blood,           0, 3, F.none,        C.none,     A.stinky},
		{"Bat"                   , unknownCost,           2, 1, F.none,        C.none,     A.airborne},
		{"River Otter"           , unknownCost,           1, 1, F.none,        C.none,     A.waterborne},
		{"Raven Egg"             ,     1.blood,           0, 2, F.none,        C.bird,     A.fledgling},
		{"Raven"                 ,     2.blood,           2, 3, F.none,        C.bird,     A.airborne},
		{"Great White"           ,     3.blood,           4, 2, F.none,        C.none,     A.waterborne},
		{"Ouroboros"             ,     2.blood,           1, 1, F.rare,        C.reptile,  A.unkillable},
		{"Moose Buck"            ,     3.blood,           3, 7, F.none,        C.deer,     A.hefty},
		{"Mole"                  ,     1.blood,           0, 4, F.none,        C.none,     A.burrower},
		{"Mole Man"              , unknownCost,           0, 6, F.none,        C.none,     A.burrower | A.mightyLeap},
		{"Black Goat"            ,     1.blood,           0, 1, F.none,        C.deer,     A.worthySacrifice},
		{"Frozen Opossum"        ,      noCost,           0, 5, F.noSacrifice, C.none,     A.frozenAway},
		{"Pronghorn"             ,     2.blood,           1, 3, F.none,        C.deer,     A.sprinter | A.bifurcatedStrike},
		{"Skink"                 ,     1.blood,           1, 2, F.none,        C.reptile,  A.looseTail},
		{"Wriggling Tail"        ,      noCost,           0, 2, F.none,        C.reptile,  A.none},
		{"Strange Frog"          , unknownCost,           1, 2, F.noSacrifice, C.reptile,  A.mightyLeap},
		{"Leaping Trap"          , unknownCost,           0, 1, F.noSacrifice, C.none,     A.steelTrap | A.mightyLeap},
		{"Mantis God"            ,     1.blood,           1, 1, F.rare,        C.bug,      A.trifurcatedStrike},
		{"The Daus"              ,     2.blood,           2, 2, F.rare,        C.deer,     A.bellist},
		{"Chime" /*?*/           ,      noCost,           0, 1, F.noSacrifice, C.none,     A.none}, // ?
		{"Bloodhound"            ,     2.blood,           2, 3, F.none,        C.canine,   A.guardian},
		{"Amalgam"               ,     2.blood,           3, 3, F.rare,        cast(C)(C.bird | C.canine | C.deer | C.bug | C.reptile), A.none},
		{"Geck"                  ,      noCost,           1, 1, F.rare,        C.reptile,  A.none},

		{"Hand Tentacle"         ,     1.blood, cardCounter, 1, F.none,        C.none,     A.none},

		{"Greater Smoke"         ,      noCost,           1, 3, F.none,        C.none,     A.boneKing},
		{"Moon"                  , unknownCost,           1,40, F.none,        C.none,     A.mightyLeap | A.omniStrike | A.tidalLock},
		{"Moon proxy"            , unknownCost,           0, 0, F.none,        C.none,     A.none},

		{"Rabbit Pelt"           ,      noCost,           0, 1, F.noSacrifice, C.none,     A.none},
		{"Wolf Pelt"             ,      noCost,           0, 2, F.noSacrifice, C.none,     A.none},
		{"Golden Pelt"           ,      noCost,           0, 3, F.noSacrifice, C.none,     A.none},

		{"Stump"                 ,      noCost,           0, 3, F.noSacrifice, C.none,     A.none},
		{"Boulder"               ,      noCost,           0, 5, F.noSacrifice, C.none,     A.none},
		{"Grand Fir"             , unknownCost,           0, 3, F.noSacrifice, C.unknown,  A.mightyLeap},
		{"Snowy Fir"             , unknownCost,           0, 4, F.noSacrifice, C.none,     A.mightyLeap},
		{"Gold Nugget"           , unknownCost,           0, 2, F.noSacrifice, C.none,     A.none},
		{"Bait Bucket"           , unknownCost,           0, 1, F.noSacrifice, C.none,     A.none},

		{"Reginald"              , unknownCost,           1, 3, F.none,        C.none,     A.touchOfDeath},
		{"Kaminski"              , unknownCost,           0, 1, F.none,        C.none,     A.guardian | A.sharpQuills},

		{"Second"                ,     2.bones,           4, 2, F.none,        C.none,     A.mightyLeap},
	];
	return result;
}();

mixin({
	string s;
	s ~= `enum CardIndex : ubyte {`;
	foreach (cardDef; cardDefs)
		s ~= cardDef.name.toLower.split.camelCaseJoin ~ ",";
	s ~= "}";
	return s;
}());

struct Card
{
	CardIndex index = CardIndex.none;
	byte bloodCost = unknown;
	byte bonesCost = unknown;
	byte attack = unknown;
	byte health = unknown;
	byte damage = 0; // damage sustained
	CardFlags flags;
	Clans clans;
	Abilities abilities;

	T opCast(T)() const if (is(T == bool)) { return index != CardIndex.none; }
	byte sprintDir() const @nogc nothrow { return (flags & CardFlags.sprintLeft) ? -1 : +1; }
}

enum Card noCard = Card.init;

immutable Card[enumLength!CardIndex] cards = {
	Card[enumLength!CardIndex] cards;
	foreach (index, cardDef; cardDefs)
	{
		Card card = {
			index: cast(CardIndex)index,
			bloodCost: cardDef.cost.totalBlood,
			bonesCost: cardDef.cost.totalBones,
			attack: cardDef.attack,
			health: cardDef.health,
			flags: cardDef.flags,
			abilities: cardDef.abilities,
			clans: cardDef.clans,
		};
		cards[index] = card;
	}
	return cards;
}();

immutable string[enumLength!CardIndex] cardNames = cardDefs.map!(def => def.name).array;

enum maxHandSize = 16;
enum maxDeckSize = 32;

enum boardWidth = 4;
enum Player { me, ai }

static immutable string[enumLength!E] enumNames(E) = {
	string[enumLength!E] names;
	static foreach (i, index; EnumMembers!E)
		names[i] = __traits(identifier, EnumMembers!E[i]);
	return names;
}();

struct Totem
{
	Clans clan = Clans.none;
	Abilities ability = Abilities.none;
}

enum maxItems = 3;

enum Item : ubyte
{
	none,
	placeholder, // Random item granted by trinketBearer

	harpiesBirdlegFan,
	magickalBleach,
	fishHook,
	frozenOpossumBottle,
	blackGoatBottle,
	// failure,
	hourglass,
	magpiesGlass,
	hoggyBank,
	pliers,
	wiseclock,
	scissors,
	specialDagger,
	squirrelInABottle,
	boulderInABottle,
	skinningKnife,
}

enum SpecialState : ubyte
{
	none,
	anglerPassive,
	anglerActive,
}

enum Row : ubyte
{
	my,
	ai,
	aiNext,
}

enum Boons : ubyte
{
	none = 0,
	ambidextrous = 1 << 0, // "You may draw twice at the beginning of your turn."
	magpiesEye = 1 << 1, // "When you draw from your deck, you may choose any card in your deck to draw."
}

struct Game
{
	Card[maxHandSize] hand = noCard;
	Card[maxDeckSize] deck = noCard;
	union
	{
		Card[boardWidth][enumLength!Row] board;
		Card[boardWidth * enumLength!Row] boardCards;
	}
	byte draws = 0; // If positive, the next move must be a draw
	byte deckPicks = 0; // For the next draw, the card may be picked from the deck
	int[enumLength!Player] playerDamage;
	byte bones;
	bool cagedWolfBonus;
	ubyte ouroborosBonus;
	Totem[enumLength!Player] totems;
	Item[maxItems] items;
	Boons boons;
	SpecialState specialState;
	ubyte lastPlacement;
	bool harpiesBirdlegFanActive;
}

struct Action
{
	enum Type : ubyte
	{
		none,
		drawSquirrel,
		drawFromDeck,
		pickFromDeck,
		playCard,
		useItem,
		endTurn,
	}
	Type type;

	byte deckIndex; // for drawFromDeck, pickFromDeck
	ubyte sacrificeOrder; // for playCard
	byte handIndex; // for playCard
	byte boardColumn; // for playCard
	byte itemIndex; // for useItem
}

Player other(Player player) @nogc nothrow { return player == Player.me ? Player.ai : Player.me; }

bool isOver(ref const Game game) @nogc nothrow { return abs(game.playerDamage[Player.me] - game.playerDamage[Player.ai]) >= 5; }

int bonusScore(ref const Game game) @nogc nothrow
{
	int score = 0;
	score += game.items[].count!(item => item != Item.none) * 500;
	score += game.cagedWolfBonus * 5000;
	score += game.ouroborosBonus * 1000;
	return score;
}

byte resolveSigil(ref const Game game, byte value, Player player) @nogc nothrow
{
	if (value >= 0)
		return value;

	switch (value)
	{
		case ants:
			value = 0;
			foreach (ref card; game.board[player])
				if (card.index.among(
					CardIndex.workerAnt,
					CardIndex.antQueen,
				))
					value++;
			return value;

		case cardCounter:
			if (player != Player.me)
				return 0;
			return cast(byte)game.hand[].count!(card => !!card);

		default:
			string error = "Unknown special value";
			debug error ~= ": " ~ text(value);
			assert(false, error);
	}
}

static immutable ubyte[][] sacrificeOrders = [
	[],

	[0],
	[1],
	[2],
	[3],

	[0, 1],
	[0, 2],
	[0, 3],
	[1, 0],
	[1, 2],
	[1, 3],
	[2, 0],
	[2, 1],
	[2, 3],
	[3, 0],
	[3, 1],
	[3, 2],

	[0, 1, 2],
	[0, 1, 3],
	[0, 2, 1],
	[0, 2, 3],
	[0, 3, 1],
	[0, 3, 2],
	[1, 0, 2],
	[1, 0, 3],
	[1, 2, 0],
	[1, 2, 3],
	[1, 3, 0],
	[1, 3, 2],
	[2, 0, 1],
	[2, 0, 3],
	[2, 1, 0],
	[2, 1, 3],
	[2, 3, 0],
	[2, 3, 1],
	[3, 0, 1],
	[3, 0, 2],
	[3, 1, 0],
	[3, 1, 2],
	[3, 2, 0],
	[3, 2, 1],

	[0, 1, 2, 3],
	[0, 1, 3, 2],
	[0, 2, 1, 3],
	[0, 2, 3, 1],
	[0, 3, 1, 2],
	[0, 3, 2, 1],
	[1, 0, 2, 3],
	[1, 0, 3, 2],
	[1, 2, 0, 3],
	[1, 2, 3, 0],
	[1, 3, 0, 2],
	[1, 3, 2, 0],
	[2, 0, 1, 3],
	[2, 0, 3, 1],
	[2, 1, 0, 3],
	[2, 1, 3, 0],
	[2, 3, 0, 1],
	[2, 3, 1, 0],
	[3, 0, 1, 2],
	[3, 0, 2, 1],
	[3, 1, 0, 2],
	[3, 1, 2, 0],
	[3, 2, 0, 1],
	[3, 2, 1, 0],
];

private void checkCard(ref const Card card) @nogc nothrow
{
	if (!card)
		return;
	debug assert(card.abilities != Abilities.unknown, "Card abilities unknown: " ~ cardNames[card.index]);
	debug assert(card.clans != Clans.unknown, "Card clans unknown: " ~ cardNames[card.index]);
}

private void checkCards(ref const Game game) @nogc nothrow
{
	foreach (ref card; game.hand)
		card.checkCard();
	foreach (ref card; game.deck)
		card.checkCard();
	foreach (row; Row.init .. enumLength!Row)
		foreach (ref card; game.board[row])
			card.checkCard();
}

private void applyTotem(ref Card card, ref const Totem totem) @nogc nothrow
{
	if (card && (card.clans & totem.clan))
		card.abilities |= totem.ability;
}

private void applyTotems(ref Game game)
{
	foreach (ref card; game.hand)
		card.applyTotem(game.totems[Player.me]);
	foreach (ref card; game.deck)
		card.applyTotem(game.totems[Player.me]);
	foreach (player; Player.init .. enumLength!Player)
		foreach (ref card; game.board[player])
			card.applyTotem(game.totems[player]);
	foreach (ref card; game.board[Row.aiNext])
		card.applyTotem(game.totems[Player.ai]);
}

void initialize(ref Game game)
{
	game.checkCards();
	game.applyTotems();
}

private Card makeCard(ref const Game game, ref const Card sample, Player player) @nogc nothrow
{
	Card card = sample;
	debug checkCard(card);
	card.applyTotem(game.totems[player]);
	return card;
}

struct BoardPosition
{
	@nogc nothrow:
	ubyte index = ubyte.max; // Game.boardCards[boardIndex]
	this(Row row, ubyte boardColumn) { index = cast(ubyte)(row * boardWidth + boardColumn); }
	this(Player player, ubyte boardColumn) { this(cast(Row)player, boardColumn); }
	@property Row row() const { return cast(Row)(index / boardWidth); }
	@property ubyte column() const { return index % boardWidth; }
	T opCast(T)() if (is(T == bool)) { return this !is typeof(this).init; }
}

void applyAction(ref Game game, Action action) @nogc nothrow
{
	void addToHand(Card card)
	{
		auto handIndex = game.hand[].countUntil(noCard);
		assert(handIndex >= 0, "No more space in hand");
		game.hand[handIndex] = card;
	}

	ref Card cardAt(BoardPosition cardPosition)
	{
		auto card = &game.boardCards[cardPosition.index];
		if (card.index == CardIndex.moonProxy)
		{
			card = &game.board[Row.ai][0];
			assert(card.index == CardIndex.moon);
		}
		return *card;
	}

	enum DamageSource : ubyte
	{
		sacrifice,
		attack,
		overkill,
		retribution,
	}

	bool isByCombat(DamageSource damageSource) { return !!damageSource.among(DamageSource.attack, DamageSource.overkill, DamageSource.retribution); }

	void killCard(BoardPosition cardPosition, DamageSource damageSource)
	{
		auto card = &cardAt(cardPosition);
		auto owner = cardPosition.row == Row.my ? Player.me : Player.ai;

		byte bones = (card.abilities & Abilities.boneKing) ? 4 : 1;
		auto cardIndex = card.index;
		if ((card.abilities & Abilities.unkillable) && owner == Player.me)
		{
			auto card2 = *card;
			card2.damage = 0;
			if (cardIndex == CardIndex.ouroboros)
			{
				card2.attack++;
				card2.health++;
				game.ouroborosBonus++;
			}
			addToHand(card2);
		}

		if (owner == Player.me && card.index == CardIndex.cagedWolf)
			game.cagedWolfBonus = true;

		bool frozenAway = !!(card.abilities & Abilities.frozenAway);
		bool steelTrap = (card.abilities & Abilities.steelTrap) && cardPosition.row != Row.aiNext;

		*card = noCard;
		if (owner == Player.me)
			game.bones += bones;

		// "If a creature that you own perishes by combat, a card bearing this sigil in your hand is automatically played in its place."
		if (owner == Player.me && isByCombat(damageSource))
			foreach (ref handCard; game.hand)
				if (handCard.abilities & Abilities.corpseEater)
				{
					swap(handCard, *card);
					break;
				}

		if (cardIndex == CardIndex.baitBucket)
			*card = game.makeCard(cards[CardIndex.greatWhite], owner);

		if (cardIndex == CardIndex.strangeFrog)
			*card = game.makeCard(cards[CardIndex.leapingTrap], owner);

		if (cardIndex == CardIndex.moon)
			foreach (ref boardCard; game.boardCards)
				if (boardCard.index == CardIndex.moonProxy)
					boardCard = noCard;

		// "When a card bearing this sigil perishes, the creature inside is released in its place."
		if (frozenAway)
		{
			switch (cardIndex)
			{
				case CardIndex.frozenOpossum:
					*card = game.makeCard(cards[CardIndex.opossum], owner);
					break;
				default:
					assert(false, "Don't know how to unfreeze");
			}
		}

		// "When a card bearing this sigil perishes, the creature opposing it perishes as well. A pelt is created in your hand."
		if (steelTrap)
		{
			auto oppositePosition = BoardPosition(owner.other, cardPosition.column);
			auto oppositeCard = &cardAt(oppositePosition);
			if (*oppositeCard)
			{
				killCard(oppositePosition, DamageSource.retribution);
				addToHand(game.makeCard(cards[CardIndex.wolfPelt], Player.me));
			}
		}
	}

	void damageCard(BoardPosition cardPosition, ref byte attackPower, DamageSource damageSource, BoardPosition attackingCardPosition)
	{
		auto card = &cardAt(cardPosition);
		auto owner = cardPosition.row == Row.my ? Player.me : Player.ai;
		auto attackingCard = attackingCardPosition ? &cardAt(attackingCardPosition) : null;

		assert(*card);
		assert(card.damage < card.health);
		if (damageSource == DamageSource.attack)
			assert(attackingCard && *attackingCard);

		// "When a card bearing this sigil would be struck, a tail is created in its place and a card bearing this sigil moves to the right."
		if ((card.abilities & Abilities.looseTail) &&
			damageSource == DamageSource.attack &&
			cardPosition.column + 1 < boardWidth &&
			!game.board[cardPosition.row][cardPosition.column + 1])
		{
			card.abilities &= ~Abilities.looseTail;
			game.board[cardPosition.row][cardPosition.column + 1] = *card;
			*card = game.makeCard(cards[CardIndex.wrigglingTail], owner);
		}

		// "Once a card bearing this sigil is struck, the striker is then dealt a single damage point."
		bool sharpQuills = damageSource == DamageSource.attack && (card.abilities & Abilities.sharpQuills);
		// "Once a card bearing this sigil is struck, a bee is created in your hand."
		bool beesWithin = damageSource == DamageSource.attack && (card.abilities & Abilities.beesWithin) && owner == Player.me;
		// "When a card bearing this sigil damages another creature, that creature perishes."
		bool touchOfDeath = attackingCard && *attackingCard && (attackingCard.abilities & Abilities.touchOfDeath);

		auto healthRemaining = card.health - card.damage;
		auto usedAttackPower = min(attackPower, healthRemaining);
		card.damage += usedAttackPower;
		attackPower -= usedAttackPower;

		if (card.damage >= card.health || touchOfDeath)
			killCard(cardPosition, damageSource);

		if (sharpQuills)
		{
			byte sharpQuillsAttackPower = 1;
			damageCard(attackingCardPosition, sharpQuillsAttackPower, DamageSource.retribution, cardPosition);
		}
		if (beesWithin)
			addToHand(game.makeCard(cards[CardIndex.bee], Player.me));
	}

	final switch (action.type)
	{
		case Action.Type.none:
			assert(false, "Null action");

		case Action.Type.drawSquirrel:
			assert(game.draws, "Can't draw right now");
			game.draws--;
			addToHand(game.makeCard(cards[CardIndex.squirrel], Player.me));
			break;

		case Action.Type.drawFromDeck:
			assert(game.draws, "Can't draw right now");
			game.draws--;
			assert(game.deck[action.deckIndex], "No such card in deck");
			addToHand(game.deck[action.deckIndex]);
			game.deck[action.deckIndex] = noCard;
			break;

		case Action.Type.pickFromDeck:
			assert(game.draws, "Can't draw right now");
			game.draws--;

			if (game.deckPicks)
				game.deckPicks--;
			else if (game.boons & Boons.magpiesEye)
			{}
			else
				assert(false, "Can't pick right now");

			assert(game.deck[action.deckIndex], "No such card in deck");
			addToHand(game.deck[action.deckIndex]);
			game.deck[action.deckIndex] = noCard;
			break;

		case Action.Type.playCard:
			auto card = game.hand[action.handIndex];
			assert(card, "No such card in hand");
			assert(card.bloodCost >= 0, {
				string s = "Unknown card cost";
				debug s ~= ": " ~ cardNames[card.index];
				return s;
			}());

			byte blood = 0;
			foreach (ubyte boardColumn; sacrificeOrders[action.sacrificeOrder])
			{
				assert(blood < card.bloodCost, "Too much sacrifice blood");
				auto sacrificeCardPosition = BoardPosition(Row.my, boardColumn);
				auto sacrificedCard = &cardAt(sacrificeCardPosition);
				assert(*sacrificedCard, "No card to sacrifice");
				assert(!(sacrificedCard.flags & CardFlags.noSacrifice), "Can't sacrifice this card");
				blood += (sacrificedCard.abilities & Abilities.worthySacrifice) ? 3 : 1;
				if (sacrificedCard.abilities & Abilities.manyLives)
				{
					if (sacrificedCard.index == CardIndex.child13)
					{
						if (sacrificedCard.abilities & Abilities.airborne)
						{
							// Awakened -> Passive
							// TODO: don't delete patched ability - need to store it separately
							sacrificedCard.abilities &= ~Abilities.airborne;
							sacrificedCard.attack -= 2;
						}
						else
						{
							// Passive -> Awakened
							sacrificedCard.abilities |= Abilities.airborne;
							sacrificedCard.attack += 2;
						}
					}
				}
				else
					killCard(sacrificeCardPosition, DamageSource.sacrifice);
			}
			assert(blood >= card.bloodCost, "Not enough sacrifice blood");

			assert(card.bonesCost <= game.bones, "Not enough bones");
			game.bones -= card.bonesCost;

			assert(!game.board[Row.my][action.boardColumn], "Space is occupied");
			game.board[Row.my][action.boardColumn] = card;
			game.hand[action.handIndex] = noCard;

			if (card.abilities & Abilities.hoarder)
				if (game.deck[].canFind!((ref card) => card))
				{
					game.deckPicks++;
					game.draws++;
				}

			// "When a card bearing this sigil is played, an ant is created in your hand."
			if (card.abilities & Abilities.antSpawner)
				addToHand(game.makeCard(cards[CardIndex.workerAnt], Player.me)); // TODO: accurate? What is an "ant"?

			// "When a card bearing this sigil is played, you will receive a random item as long as your pack is not full."
			if (card.abilities & Abilities.trinketBearer)
				foreach (ref item; game.items)
					if (!item)
					{
						item = Item.placeholder;
						break;
					}

			// "When a card bearing this sigil is played, a chime is created on each empty adjacent space. A chime is defined as: 0 power, 1 health."
			if (card.abilities & Abilities.bellist)
				foreach (chimeColumn; only(action.boardColumn - 1, action.boardColumn + 1))
					if (chimeColumn >= 0 && chimeColumn < boardWidth && !game.board[Row.my][chimeColumn])
						game.board[Row.my][chimeColumn] = game.makeCard(cards[CardIndex.chime], Player.me);

			// Guardian: "When an opposing creature is placed opposite to an empty space, a card bearing this sigil will move to that empty space."
			{
				auto opposingSpace = &game.board[Row.ai][action.boardColumn];
				if (!*opposingSpace)
					foreach (ref guardianCard; game.board[Row.ai])
						if (guardianCard && (guardianCard.abilities & Abilities.guardian))
						{
							swap(*opposingSpace, guardianCard);
							break;
						}
			}

			game.lastPlacement = action.boardColumn;

			break;

		case Action.Type.useItem:
			auto item = game.items[action.itemIndex];
			assert(item, "No such item");
			game.items[action.itemIndex] = Item.none;

			switch (item)
			{
				case Item.pliers:
					assert(action.boardColumn == -1);
					game.playerDamage[Player.ai]++;
					break;

				case Item.hoggyBank:
					assert(action.boardColumn == -1);
					game.bones += 4;
					break;

				case Item.harpiesBirdlegFan:
					assert(action.boardColumn == -1);
					game.harpiesBirdlegFanActive = true;
					break;

				case Item.squirrelInABottle:
					assert(action.boardColumn == -1);
					addToHand(game.makeCard(cards[CardIndex.squirrel], Player.me));
					break;

				case Item.boulderInABottle:
					assert(action.boardColumn == -1);
					addToHand(game.makeCard(cards[CardIndex.boulder], Player.me));
					break;

				case Item.frozenOpossumBottle:
					assert(action.boardColumn == -1);
					addToHand(game.makeCard(cards[CardIndex.frozenOpossum], Player.me));
					break;

				case Item.blackGoatBottle:
					assert(action.boardColumn == -1);
					addToHand(game.makeCard(cards[CardIndex.blackGoat], Player.me));
					break;

				case Item.fishHook:
					assert(action.boardColumn >= 0);
					assert(game.board[Row.ai][action.boardColumn]);
					assert(!game.board[Row.my][action.boardColumn]);
					swap(game.board[Row.ai][action.boardColumn], game.board[Row.my][action.boardColumn]);
					break;

				case Item.scissors:
					assert(action.boardColumn >= 0);
					assert(game.board[Row.ai][action.boardColumn]);
					game.board[Row.ai][action.boardColumn] = noCard;
					break;

				default:
					assert(false, {
						string s = "Don't know how to use item";
						debug s ~= ": " ~ enumNames!Item[item];
						return s;
					}());
			}

			break;

		case Action.Type.endTurn:
			void runCardsTurnStart(Player player) @nogc nothrow
			{
				foreach (boardColumn; 0 .. boardWidth)
				{
					auto myCard = &game.board[player][boardColumn];

					if (myCard.abilities & Abilities.fledgling)
					{
						void evolveTo(CardIndex targetCard)
						{
							// TODO evolution logic?
							// Does damage carry over? Do abilities carry over?
							*myCard = game.makeCard(cards[targetCard], Player.me);
						}

						switch (myCard.index)
						{
							case CardIndex.elkFawn:
								evolveTo(CardIndex.elk);
								break;
							case CardIndex.wolfCub:
								evolveTo(CardIndex.wolf);
								break;
							case CardIndex.ravenEgg:
								evolveTo(CardIndex.raven);
								break;
							default:
								// Elder
								// TODO stats!
								myCard.health++;
								if (myCard.attack > 0)
									myCard.attack++;
								break;
						}
					}

					if (myCard.abilities & Abilities.tidalLock)
					{
						foreach (ref card; game.boardCards)
							if (card && card.index.among(
								CardIndex.squirrel,
								// ???
							))
								card = noCard;
					}
				}
			}

			void runCardsTurnEnd(Player player) @nogc nothrow
			{
				foreach (ubyte boardColumn; 0 .. boardWidth)
				{
					auto myCardPosition = BoardPosition(player, boardColumn);
					auto myCard = &cardAt(myCardPosition);
					if (*myCard)
					{
						if (myCard.index == CardIndex.moon && myCardPosition != BoardPosition(Row.ai, 0))
							continue; // proxies don't attack

						auto oppositeCardPosition = BoardPosition(player.other, boardColumn);
						auto oppositeCard = &cardAt(oppositeCardPosition);

						debug checkCard(*myCard);
						foreach (index; AbilityIndex.init .. enumLength!AbilityIndex)
						{
							auto mask = 1UL << index;
							if (myCard.abilities & mask)
							{
								switch (index)
								{
									case AbilityIndex.manyLives:
									case AbilityIndex.airborne:
									case AbilityIndex.waterborne:
									case AbilityIndex.waterborne2:
									case AbilityIndex.mightyLeap:
									case AbilityIndex.stinky:
									case AbilityIndex.sharpQuills:
									case AbilityIndex.sprinter:
									case AbilityIndex.beesWithin:
									case AbilityIndex.unkillable:
									case AbilityIndex.hoarder:
									case AbilityIndex.boneKing:
									case AbilityIndex.corpseEater:
									case AbilityIndex.fledgling:
									case AbilityIndex.worthySacrifice:
									case AbilityIndex.touchOfDeath:
									case AbilityIndex.burrower:
									case AbilityIndex.antSpawner:
									case AbilityIndex.trinketBearer:
									case AbilityIndex.hefty:
									case AbilityIndex.frozenAway:
									case AbilityIndex.looseTail:
									case AbilityIndex.bifurcatedStrike:
									case AbilityIndex.trifurcatedStrike:
									case AbilityIndex.omniStrike:
									case AbilityIndex.steelTrap:
									case AbilityIndex.bellist:
									case AbilityIndex.guardian:
									case AbilityIndex.tidalLock:
										break; // implemented
									default:
										static immutable names = {
											string[enumLength!AbilityIndex] names;
											static foreach (i, index; EnumMembers!AbilityIndex)
												names[i] = __traits(identifier, EnumMembers!AbilityIndex[i]);
											return names;
										}();
										string error = "Ability not implemented";
										debug error ~= ": " ~ enumNames!AbilityIndex[index];
										assert(false, error);
								}
							}
						}

						auto initialAttackPower = resolveSigil(game, myCard.attack, player);

						// Stinky: "The creature opposing a card bearing this sigil loses 1 power."
						if (initialAttackPower && *oppositeCard && (oppositeCard.abilities & Abilities.stinky))
							initialAttackPower--;

						void attackTheColumn(ubyte attackColumn)
						{
							auto attackPower = initialAttackPower;

							if (attackPower <= 0)
								return;

							auto otherCardPosition = BoardPosition(player.other, attackColumn);
							auto otherCard = &cardAt(otherCardPosition);

							// Burrower: "When an empty space would be struck, a card bearing this sigil will move to that space to receive the strike instead."
							if (!*otherCard)
							{
								foreach (ref burrowCard; game.board[player.other])
									if (burrowCard && (burrowCard.abilities & Abilities.burrower))
									{
										swap(*otherCard, burrowCard);
										break;
									}
							}

							bool canAttackCard = {
								if (!*otherCard)
									return false; // No card to attack
								bool airborne = (myCard.abilities & Abilities.airborne) || (player == Player.me && game.harpiesBirdlegFanActive);
								if (airborne && !(otherCard.abilities & Abilities.mightyLeap))
									return false; // Airborne cards attack the user, unless countered by Mighty Leap
								if ((otherCard.abilities & Abilities.waterborne) || (otherCard.abilities & Abilities.waterborne2))
									return false; // Cannot attack waterborne cards
								return true;
							}();
							if (canAttackCard)
							{
								damageCard(otherCardPosition, attackPower, DamageSource.attack, myCardPosition);

								// Overkill: attack next row
								if (*myCard && attackPower > 0 && player == Player.me)
								{
									auto nextCardPosition = BoardPosition(Row.aiNext, attackColumn);
									auto nextCard = &cardAt(nextCardPosition);
									if (*nextCard)
										damageCard(nextCardPosition, attackPower, DamageSource.overkill, myCardPosition); // TODO: check if damageSource has same semantics as attack (sharpQuills?)
								}
							}
							else
								game.playerDamage[player.other] += attackPower;
						}

						foreach (byte attackColumn; 0 .. boardWidth)
						{
							bool canAttackColumn = {
								if (myCard.abilities & Abilities.trifurcatedStrike)
									return abs(boardColumn - attackColumn) <= 1;
								if (myCard.abilities & Abilities.bifurcatedStrike)
									return abs(boardColumn - attackColumn) == 1;
								// "A card bearing this sigil will strike each opposing space that is occupied by a creature. It will strike directly if no creatures oppose it."
								if (myCard.abilities & Abilities.omniStrike)
									return game.board[player.other][attackColumn] || (
										attackColumn == 0 && game.board[player.other][].all!((ref card) => !card)
									);
								return boardColumn == attackColumn;
							}();
							if (canAttackColumn)
							{
								attackTheColumn(attackColumn);
								if (!*myCard)
									break; // was killed in retribution
							}
						}
					}
				}

				// Sprinter: "At the end of the owner's turn, a card bearing this sigil will move in the direction inscribed in the sigil."
				// Hefty: "At the end of the owner's turn, a card bearing this sigil will move in the direction inscribed in this sigil. Creatures in the way will be pushed in the same direction."
				for (byte boardColumn = 0; boardColumn < boardWidth; boardColumn++)
				{
					auto myCard = &game.board[player][boardColumn];
					if (myCard.abilities & (Abilities.sprinter | Abilities.hefty))
					{
						bool vacate(byte targetIndex)
						{
							if (targetIndex < 0 || targetIndex >= boardWidth)
								return false; // out of bounds
							if (!game.board[player][targetIndex])
								return true; // already free
							if (!(myCard.abilities & Abilities.hefty))
								return false; // can't push
							auto nextIndex = targetIndex;
							nextIndex += myCard.sprintDir;
							if (!vacate(nextIndex))
								return false; // couldn't push
							assert(!game.board[player][nextIndex]);
							swap(game.board[player][nextIndex], game.board[player][targetIndex]);
							return true; // push successful
						}

						byte targetIndex = boardColumn;
						targetIndex += myCard.sprintDir;

						if (!vacate(targetIndex))
						{
							myCard.flags ^= CardFlags.sprintLeft; // Can't go, turn around
							targetIndex = boardColumn;
							targetIndex += myCard.sprintDir;
						}

						if (!vacate(targetIndex))
							{} // Can't move even after turning around
						else
							swap(*myCard, game.board[player][targetIndex]);

						if (targetIndex > boardColumn)
							boardColumn = targetIndex; // Don't process the same sprinter twice!
					}
				}
			}

			runCardsTurnEnd(Player.me);

			game.harpiesBirdlegFanActive = false;

			if (game.isOver)
				return;

			runCardsTurnStart(Player.ai);

			// Angler boss
			if (game.specialState == SpecialState.anglerPassive)
				game.specialState = SpecialState.anglerActive;
			else
			if (game.specialState == SpecialState.anglerActive)
			{
				if (game.board[Row.my][game.lastPlacement]
					&&
					(
						! game.board[Row.ai    ][game.lastPlacement]
						||
						! game.board[Row.aiNext][game.lastPlacement]
					))
				{
					if (game.board[Row.ai][game.lastPlacement])
						swap(
							game.board[Row.ai    ][game.lastPlacement],
							game.board[Row.aiNext][game.lastPlacement],
						);
					swap(
						game.board[Row.my][game.lastPlacement],
						game.board[Row.ai][game.lastPlacement],
					);
					assert(!game.board[Row.my][game.lastPlacement]);
				}
				game.specialState = SpecialState.anglerPassive;
			}

			foreach (boardColumn; 0 .. boardWidth)
				if (game.board[Row.aiNext][boardColumn] && !game.board[Row.ai][boardColumn])
				{
					game.board[Row.ai][boardColumn] = game.board[Row.aiNext][boardColumn];
					game.board[Row.aiNext][boardColumn] = noCard;

					// Guardian: "When an opposing creature is placed opposite to an empty space, a card bearing this sigil will move to that empty space."
					{
						auto opposingSpace = &game.board[Row.my][action.boardColumn];
						if (!*opposingSpace)
							foreach (ref guardianCard; game.board[Row.my])
								if (guardianCard && (guardianCard.abilities & Abilities.guardian))
								{
									swap(*opposingSpace, guardianCard);
									break;
								}
					}
				}

			runCardsTurnEnd(Player.ai);

			runCardsTurnStart(Player.me); // TODO: is this right?

			game.draws = 1;
			if (game.boons & Boons.ambidextrous)
				game.draws++;

			break;
	}
}

string describeAction(ref const Game game, ref const Action action)
{
	static immutable boardPositions = [
		"left-most",
		"center-left",
		"center-right",
		"right-most",
	];
	final switch (action.type)
	{
		case Action.Type.none:
			return "(no action)";

		case Action.Type.drawSquirrel:
			return "Draw a squirrel";

		case Action.Type.drawFromDeck:
			return "Draw a card from your deck";

		case Action.Type.pickFromDeck:
			return "Pick the " ~ cardNames[game.deck[action.deckIndex].index] ~ " card from your deck";

		case Action.Type.playCard:
			auto card = game.hand[action.handIndex];
			string s;
			s ~= "Play the " ~ cardNames[card.index];
			s ~= " on the " ~ boardPositions[action.boardColumn] ~ " tile";

			if (action.sacrificeOrder)
				s ~= ", sacrificing " ~ (
					sacrificeOrders[action.sacrificeOrder]
					.map!(boardColumn => "the " ~ cardNames[game.board[Row.my][boardColumn].index] ~ " on the " ~ boardPositions[boardColumn] ~ " tile")
					.join(" and ")
				);

			return s;

		case Action.Type.useItem:
			string s;
			s ~= "Use the " ~ enumNames!Item[game.items[action.itemIndex]];
			if (action.boardColumn >= 0)
				s ~= " on the " ~ boardPositions[action.boardColumn] ~ " tile";
			return s;

		case Action.Type.endTurn:
			return "End your turn";
	}
}

string bitsToString(Index, Bits, string name)(Bits cardBits, Bits referenceBits)
{
	string s;
	if (referenceBits & ~cardBits)
	{
		s ~= ".clear" ~ name ~ "()";
		referenceBits = Bits.none;
	}
	foreach (index; EnumMembers!Index)
		if ((cardBits & (1UL << index)) && !(referenceBits & (1UL << index)))
			s ~= format(".patch(%s.%s)", name, enumNames!Index[index]);
	return s;
}

string toString(Card card)
{
	if (!card)
		return "noCard";
	string s = "cards[CardIndex." ~ enumNames!CardIndex[card.index] ~ "]";
	assert(card.bloodCost == cards[card.index].bloodCost);
	assert(card.bonesCost == cards[card.index].bonesCost);
	if (card.attack != cards[card.index].attack) s ~= format(".addAttack(%d)", card.attack - cards[card.index].attack);
	if (card.health != cards[card.index].health) s ~= format(".addHealth(%d)", card.health - cards[card.index].health);
	if (card.damage != cards[card.index].damage) s ~= format(".addDamage(%d)", card.damage - cards[card.index].damage);
	if (card.sprintDir != +1) s ~= ".sprintLeft()";
	s ~= bitsToString!(ClanIndex, Clans, "Clans")(card.clans, cards[card.index].clans);
	s ~= bitsToString!(AbilityIndex, Abilities, "Abilities")(card.abilities, cards[card.index].abilities);
	return s;
}

string toString(Totem totem)
{
	if (totem == Totem.init)
		return "{}";
	return "{ " ~
		size_t(enumLength!ClanIndex).iota.filter!(index => (1UL << index) & totem.clan).map!(index => "Clans." ~ enumNames!ClanIndex[index]).join(" | ") ~
		", " ~
		size_t(enumLength!AbilityIndex).iota.filter!(index => (1UL << index) & totem.ability).map!(index => "Abilities." ~ enumNames!AbilityIndex[index]).join(" | ") ~
		" }";
}

string toString(Game game)
{
	string[] lines;

	lines ~= "	Game game = {";
	lines ~= "		hand: [";
	foreach (card; game.hand)
		if (card)
			lines ~= "			" ~ card.toString() ~ ",";
	lines ~= "		],";

	lines ~= "		deck: [";
	foreach (card; game.deck)
		if (card)
			lines ~= "			" ~ card.toString() ~ ",";
	lines ~= "		],";

	lines ~= "		board: [[";
	foreach (card; game.board[Row.my])
		lines ~= "			" ~ card.toString() ~ ",";
	lines ~= "		], [";
	foreach (card; game.board[Row.ai])
		lines ~= "			" ~ card.toString() ~ ",";
	lines ~= "		], [";
	foreach (card; game.board[Row.aiNext])
		lines ~= "			" ~ card.toString() ~ ",";
	lines ~= "		]],";

	lines ~= "		draws: " ~ game.draws.text ~ ",";
	if (game.deckPicks)
		lines ~= "		deckPicks: " ~ game.deckPicks.text ~ ",";

	lines ~= "		playerDamage: " ~ game.playerDamage.text ~ ",";
	lines ~= "		bones: " ~ game.bones.text ~ ",";

	if (game.cagedWolfBonus)
		lines ~= "		cagedWolfBonus: " ~ game.cagedWolfBonus.text ~ ",";
	if (game.ouroborosBonus)
		lines ~= "		ouroborosBonus: " ~ game.ouroborosBonus.text ~ ",";

	lines ~= "		totems: [";
	lines ~= "			" ~ game.totems[Player.me].toString() ~ ",";
	lines ~= "			" ~ game.totems[Player.ai].toString() ~ ",";
	lines ~= "		],";

	lines ~= "		items: [";
	foreach (item; game.items)
		if (item)
			lines ~= "			Item." ~ item.text ~ ",";
	lines ~= "		],";

	if (game.boons)
		lines ~= "		boons: cast(Boons)(" ~ [EnumMembers!Boons].filter!(boon => boon & game.boons).map!(boon => "Boons." ~ boon.text).join(" | ") ~ "),";
	if (game.specialState)
		lines ~= "		specialState: SpecialState." ~ game.specialState.text ~ ",";
	if (game.specialState.among(SpecialState.anglerActive, SpecialState.anglerPassive))
		lines ~= "		lastPlacement: " ~ game.lastPlacement.text ~ ",";
	if (game.harpiesBirdlegFanActive)
		lines ~= "		harpiesBirdlegFanActive: " ~ game.harpiesBirdlegFanActive.text ~ ",";

	lines ~= "	};";

	return lines.join("\n") ~ "\n";
}

alias RNG = Xorshift;

// Create a random situation with the given Game's persistent aspects (deck, totems...)
Game randomGame(ref const Game base, ref RNG rng) pure
{
	Game game = base;

	void randomizeCard(ref Card card)
	{
		card.damage = uniform(byte(0), card.health, rng);
	}

	void placeAICard(ref Card card)
	{
		if (uniform(0, 3, rng) == 0)
		{
			card = cards[uniform(1, $, rng)];
			if (card.clans == Clans.unknown) card.clans = Clans.none;
			if (card.abilities == Abilities.unknown) card.abilities = Abilities.none;
			randomizeCard(card);
		}
	}

	game.deck[].randomShuffle(rng);
	size_t deckIndex;
	Card draw()
	{
		while (deckIndex < maxDeckSize)
		{
			auto card = &game.deck[deckIndex++];
			if (*card)
			{
				auto result = *card;
				*card = noCard;
				return result;
			}
		}
		return noCard;
	}

	foreach (ref card; game.hand[0 .. uniform(0, 5, rng)])
		card = draw();
	foreach (ref card; game.board[Row.my])
		if (uniform(0, 3, rng) == 0)
		{
			card = draw();
			if (card)
				randomizeCard(card);
		}

	foreach (ref card; game.board[Row.ai])
		placeAICard(card);
	foreach (ref card; game.board[Row.aiNext])
		placeAICard(card);
	game.draws = uniform(ubyte(0), ubyte(2), rng);
	game.bones = uniform(byte(0), byte(3), rng);

	return game;
}

memory.d

import core.stdc.stdlib;

enum arenaSize = 48UL * 1024 * 1024 * 1024;

// TODO MT

struct Arena
{
	this(string name, size_t size)
	{
		this.name = name;

		start = malloc(size);
		if (!start) assert(false, "malloc failed");
		end = start + size;

		next = start;
	}

	~this()
	{
		if (start)
		{
			free(start);
			start = end = next = null;
		}
	}

	@disable this(this);

	string name;
	void* start, end;
	void* next;

	void[] allocBytes(size_t n)
	{
		auto p = next;
		next += n;
		if (next > end)
		{
			import core.stdc.stdio : fprintf, stderr;
			fprintf(stderr, "Arena %.*s out of memory\n",
				cast(int)name.length, name.ptr,
			);
			throw new Exception("Out of arena memory");
		}
		return p[0 .. n];
	}

	T[] alloc(T, bool initialize=true)(size_t n)
	{
		auto bytes = allocBytes(T.sizeof * n);
		auto arr = cast(T[])bytes;
		if (initialize)
			arr[] = T.init;
		else
			debug { (cast(ubyte[])bytes)[] = 0xfc; }
		return arr;
	}

	T* alloc(T)()
	{
		auto bytes = allocBytes(T.sizeof);
		auto p = cast(T*)bytes.ptr;
		*p = T.init;
		return p;
	}

	void[] data() { return start[0 .. next - start]; }
	size_t capacity() { return end - start; }
	size_t usedSize() { return next - start; }
	size_t freeSize() { return end - next; }
}

problem.d

import core.bitop : popcnt;

import std.algorithm.comparison;
import std.algorithm.iteration;
import std.algorithm.searching;
import std.algorithm.setops : cartesianProduct;
import std.array;
import std.format : format;
import std.parallelism;
import std.range : iota;
import std.stdio;

import game;
import search;

Card patch(Card card, Abilities ability) { card.abilities |= ability; return card; }
Card addAttack(Card card, byte amount) { card.attack += amount; return card; }
Card addHealth(Card card, byte amount) { card.health += amount; return card; }
Card addDamage(Card card, byte amount) { card.damage += amount; return card; }
Card sprintLeft(Card card) { card.flags |= CardFlags.sprintLeft; return card; }
Card clearClans(Card card) { card.clans = Clans.none; return card; }
Card clearAbilities(Card card) { card.abilities = Abilities.none; return card; }

void main()
{
	version(none)
	Game game = {
		hand: [
		],
		deck: [
			cards[CardIndex.cagedWolf],
			cards[CardIndex.stinkbug],
			cards[CardIndex.stoat],
			cards[CardIndex.bullfrog],
			cards[CardIndex.wolf],
			cards[CardIndex.second].addAttack(1).patch(Abilities.trinketBearer),
			cards[CardIndex.cockroach].patch(Abilities.beesWithin),
			cards[CardIndex.packRat],
			cards[CardIndex.opossum].addHealth(2),
			cards[CardIndex.urayuli],
			cards[CardIndex.cardTentacle].patch(Abilities.trinketBearer),
			cards[CardIndex.workerAnt].clearAbilities().patch(Abilities.worthySacrifice),
			cards[CardIndex.wolfCub],
			cards[CardIndex.ouroboros],
			cards[CardIndex.cardTentacle],
			cards[CardIndex.packRat],
		],
		board: [[
			noCard,
			noCard,
			noCard,
			noCard,
		], [
			noCard,
			noCard,
			noCard,
			noCard,
		], [
			noCard,
			noCard,
			noCard,
			noCard,
		]],
		draws: 0,
		playerDamage: [0, 0],
		bones: 2,
		totems: [
			{ Clans.squirrel, Abilities.sharpQuills },
			{},
		],
		items: [
			Item.scissors,
			Item.pliers,
			Item.boulderInABottle,
		],
	};

	Game game = {
		hand: [
			cards[CardIndex.cockroach].patch(Abilities.beesWithin),
			cards[CardIndex.packRat],
		],
		deck: [
			cards[CardIndex.cagedWolf],
			cards[CardIndex.stinkbug],
			cards[CardIndex.stoat],
			cards[CardIndex.bullfrog],
			cards[CardIndex.wolf],
			cards[CardIndex.second].addAttack(1).patch(Abilities.trinketBearer),
			cards[CardIndex.packRat],
			cards[CardIndex.opossum].addHealth(2),
			cards[CardIndex.urayuli],
			cards[CardIndex.cardTentacle].patch(Abilities.trinketBearer),
			cards[CardIndex.workerAnt].clearAbilities().patch(Abilities.worthySacrifice),
			cards[CardIndex.wolfCub],
			cards[CardIndex.ouroboros],
		],
		board: [[
			noCard,
			cards[CardIndex.cardTentacle],
			noCard,
			noCard,
		], [
			noCard,
			cards[CardIndex.elkFawn].patch(Abilities.sharpQuills),
			cards[CardIndex.elkFawn].sprintLeft().patch(Abilities.sharpQuills),
			cards[CardIndex.boulder],
		]],
		aiMove: [
			noCard,
			cards[CardIndex.elk],
			noCard,
			noCard,
		],
		draws: 1,
		playerDamage: [2, 2],
		bones: 2,
		totems: [
			{ Clans.squirrel, Abilities.sharpQuills },
			{ Clans.deer, Abilities.sharpQuills },
		],
		items: [
			Item.scissors,
			Item.pliers,
			Item.boulderInABottle,
		],
	};

	findSolution(game);

	// findBestDeckAddition(game, [
	// 	cards[CardIndex.cardTentacle],
	// 	cards[CardIndex.turkeyVulture],
	// 	cards[CardIndex.elk],
	// ]);

	// findBestStatMod(game, (ref card) { card.health += 2; });
	// findBestStatMod(game, (ref card) { if (card.attack > 0) card.attack++; });

	// findBestSacrifice(game);

	// findBestTransfusion(game);

	// findBestTrial(game, [
	// 	trialOfWisdom,
	// 	trialOfPower,
	// 	trialOfBones,
	// ]);
}

void findSolution(Game game)
{
	game.initialize();

	size_t numIters;
	search.search(game, (Node* root) {
		auto game = root.getGame();
		writefln("%2d: %5d - %s", ++numIters, root.score, describeAction(game, root.choices[root.bestChoice][0].action));
		save(root);
		return true;
	});
}

void save(Node* node)
{
	auto f = File("solution.txt.tmp", "wb");
	f.writefln("\t// score: %d", node.score);
	f.writeln(node.getGame().toString());
	while (node.expanded)
	{
		f.writeln("=======================================");
		if (!node.choices.length)
			break;
		auto bestChoice = node.choices[node.bestChoice];
		auto game = node.getGame();
		f.writefln(describeAction(game, bestChoice[0].action));
		f.writeln("=======================================");
		node = bestChoice[0].node;
		f.writefln("\t// score: %d", node.score);
		f.writeln(node.getGame().toString());
	}
	f.writeln("=======================================");
	auto game = node.getGame();
	if (game.isOver)
		f.writeln("Game over");
	else
	if (!node.choices.length)
		f.writeln("Reached dead end");
	else
		f.writeln("Reached unexpanded node");
	f.writeln("Final score: ", node.score);
	f.close();
	rename("solution.txt.tmp", "solution.txt");
}

Game addToDeck(Game game, Card card)
{
	foreach (ref deckCard; game.deck)
		if (!deckCard)
		{
			deckCard = card;
			return game;
		}
	assert(false, "Deck is full");
}

void findBestDeckAddition(Game game, scope Card[] cards)
{
	auto variants = cards
		.map!(card => Variant(game.addToDeck(card), card.toString()))
		.array;
	return findBestVariant(variants);
}

void findBestStatMod(Game game, scope void delegate(ref Card) mod)
{
	auto variants = maxDeckSize.iota
		.filter!(deckIndex => game.deck[deckIndex])
		.map!((deckIndex) {
			auto game2 = game;
			mod(game2.deck[deckIndex]);
			return Variant(game2, game2.deck[deckIndex].toString());
		})
		.array;
	return findBestVariant(variants);
}

void findBestSacrifice(Game game)
{
	auto variants = maxDeckSize.iota
		.filter!(deckIndex => game.deck[deckIndex])
		.filter!(deckIndex => !(game.deck[deckIndex].flags & CardFlags.noSacrifice))  // ? no pelts at least...
		.map!((deckIndex) {
			auto game2 = game;
			game2.deck[deckIndex] = noCard;
			return Variant(game2, game.deck[deckIndex].toString());
		})
		.array;
	return findBestVariant(variants);
}

void findBestTransfusion(Game game)
{
	auto donors = maxDeckSize.iota
		.filter!(deckIndex =>
			game.deck[deckIndex] &&
			game.deck[deckIndex].abilities &&
			game.deck[deckIndex].abilities == cards[game.deck[deckIndex].index].abilities
		)
		.array;
	auto receivers = maxDeckSize.iota
		.filter!(deckIndex =>
			game.deck[deckIndex] &&
			game.deck[deckIndex].abilities == cards[game.deck[deckIndex].index].abilities
		)
		.array;
	auto variants = cartesianProduct(donors, receivers)
		.filter!(pair => pair[0] != pair[1])
		.map!((pair) {
			auto donor = pair[0];
			auto receiver = pair[1];
			auto game2 = game;
			game2.deck[receiver].abilities |= game2.deck[donor].abilities;
			game2.deck[donor] = noCard;
			return Variant(game2,
				format("donor: %s, receiver: %s",
					game.deck[donor].toString(),
					game.deck[receiver].toString(),
				)
			);
		})
		.array;
	return findBestVariant(variants);
}

enum searchDepth = 7;

struct Variant { Game game; string name; }

void findBestVariant(Variant[] variants)
{
	auto wins = new uint[variants.length];

	foreach (seed; size_t.max.iota.parallel(1))
	{
		scope(failure) writefln("%7d: Error!", seed);
		auto scores = new Score[variants.length];

		Score bestScore = Score.min;

		foreach (i, ref variant; variants)
		{
			RNG rng;
			rng.seed(cast(uint)seed);
			auto seedGame = variant.game.randomGame(rng);
			seedGame.initialize();

			int iterations;
			search.search(seedGame, (Node* root) {
				if (++iterations < searchDepth)
					return true;
				scores[i] = root.score;
				return false;
			}, true);
			if (scores[i] > bestScore)
				bestScore = scores[i];
		}

		synchronized
		{
			foreach (i, score; scores)
				if (score == bestScore)
					wins[i]++;

			auto bestWins = wins[].reduce!max;
			auto bestIndex = wins.countUntil(bestWins);
			writefln("%7d: %(%d\t%)    |     Best: #%d (%s) with %d wins",
				seed, wins,
				bestIndex,
				variants[bestIndex].name,
				bestWins,
			);
		}
	}
}

struct Trial { int function(Card card) getter; int threshold; }

immutable trialOfPower  = Trial((Card card) => card.attack   , 4);
immutable trialOfHealth = Trial((Card card) => card.health   , 6);
immutable trialOfWisdom = Trial((Card card) => card.abilities == Abilities.unknown ? 0 : popcnt(card.abilities), 3);
immutable trialOfBlood  = Trial((Card card) => card.bloodCost, 4);
immutable trialOfBones  = Trial((Card card) => card.bonesCost, 5);

immutable trialOfTheFinned  = Trial((Card card) => !!(card.abilities & Abilities.waterborne), 1);
immutable trialOfRarity     = Trial((Card card) => !!(card.flags & CardFlags.rare), 1);
immutable trialOfSkins      = Trial((Card card) => !!card.index.among(CardIndex.rabbitPelt, CardIndex.wolfPelt, CardIndex.goldenPelt), 1);

void findBestTrial(Game game, Trial[] trials)
{
	size_t numCombinations = 0;
	auto wins = new int[trials.length];

	foreach (card1Index; 0              .. maxDeckSize) if (game.deck[card1Index])
	foreach (card2Index; card1Index + 1 .. maxDeckSize) if (game.deck[card2Index])
	foreach (card3Index; card2Index + 1 .. maxDeckSize) if (game.deck[card3Index])
	{
		numCombinations++;
		size_t[3] indices = [card1Index, card2Index, card3Index];
		foreach (trialIndex; 0 .. trials.length)
		{
			int sum;
			foreach (deckIndex; indices)
				sum += max(0, trials[trialIndex].getter(game.deck[deckIndex]));
			if (sum >= trials[trialIndex].threshold)
				wins[trialIndex]++;
		}
	}

	foreach (trialIndex; 0 .. trials.length)
		writefln("%d: %6.2f%% (%d/%d)",
			trialIndex, 100 * double(wins[trialIndex]) / numCombinations,
			wins[trialIndex], numCombinations,
		);
}

search.d

import core.bitop : popcnt;

import std.algorithm.iteration;
import std.algorithm.mutation : swap;
import std.algorithm.searching;
import std.algorithm.setops;
import std.algorithm.sorting;
import std.experimental.allocator.mallocator;
import std.parallelism;
import std.range;
import std.stdio : stderr;

import containers.hashmap;

import ae.utils.array;
import ae.utils.parallelism;

import game;
import memory;

alias Score = int;

struct Node
{
	hash_t gameHash;

	// How did we get here?
	union
	{
		Node* parent;
		const(Game)* rootGame; // when parentAction.type == none
	}
	Action parentAction;

	bool scoreIsFinal;
	Score score;
	size_t bestChoice; // only when expanded

	struct Outcome
	{
		Action action; // includes choice and outcome
		Node* node;
	}
	alias Choice = Outcome[];
	Choice[] choices; // if non-null, then this node is expanded (might still be empty)

	bool expanded() const @nogc { return choices.ptr !is null; }

	Game getGame() const nothrow @trusted
	{
		if (parentAction.type == Action.Type.none)
			return *rootGame;

		assert(parent);
		auto game = parent.getGame();
		game.applyAction(parentAction);
		game.normalize();
		return game;
	}
}

Score getFinalScore(ref const Game game) @nogc
{
	assert(game.isOver);
	Score score;
	bool weWon = game.playerDamage[Player.me] < game.playerDamage[Player.ai];
	if (!weWon)
		score -= 10_000;
	else
	{
		score += 10_000;
		score += (game.playerDamage[Player.ai] - game.playerDamage[Player.me]) * 200;
	}
	score += game.bonusScore();
	return score;
}

// This value is used only for freshly expanded nodes,
// and will be overwritten on the next iteration.
Score getHeuristicScore(ref const Game game)
{
	if (game.isOver)
		return getFinalScore(game);

	Score score;
	score += (game.playerDamage[Player.ai] - game.playerDamage[Player.me]) * 100;
	score += game.bonusScore() / 10;
	foreach (ref card; game.hand)
		if (card)
			score += 25;
	foreach (ref card; game.board[Row.my])
		if (card)
			score += 50;
	foreach (ref card; game.board[Row.ai])
		if (card)
			score -= 50;
	foreach (ref card; game.board[Row.aiNext])
		if (card)
			score -= 25;
	return score;
}

struct GameRef
{
	const(Node)* node;
	hash_t toHash() const nothrow @safe { return node.gameHash; }
	bool opEquals(ref const GameRef b) const nothrow @safe { return node.getGame() == b.node.getGame(); }
}

// Simple stable sort with O(1) space complexity, optimized for
// sorted or almost-sorted (one unsorted item) arrays.
// Similar to Gnome Sort.
void mySort(alias pred, R)(R r)
{
	for (size_t i = 1; i < r.length; i++)
		if (pred(r[i], r[i - 1]))
		{
			auto j = i;
			do
			{
				swap(r[j - 1], r[j]);
				j--;
			}
			while (j > 0 && pred(r[j], r[j - 1]));
		}
	debug assert(r.isSorted!pred());
}

alias wordCompare = (ref a, ref b) => cast(size_t[])(a.bytes) < cast(size_t[])(b.bytes);

void normalize(ref Game game) nothrow @nogc
{
	game.hand[].mySort!wordCompare;
	game.deck[].mySort!wordCompare;
}

bool isNormalized(ref const Game game)
{
	Game normalizedGame = game;
	normalizedGame.normalize();
	return game == normalizedGame;
}

void expandGame(ref const Game game, scope void delegate(scope const Action[] outcomes) handleChoice)
{
	if (game.isOver())
		return; // Terminal state

	if (game.draws)
	{
		if (game.hand[].canFind(noCard))
		{
			bool mustDrawFromDeck = game.deckPicks == 0; // Magpie's abilities force drawing from deck
			if (!mustDrawFromDeck)
			{
				Action action = {
					type: Action.Type.drawSquirrel,
				};
				handleChoice(action.toArray);
			}

			if (game.deckPicks || (game.boons & Boons.magpiesEye))
			{
				foreach (ubyte deckIndex; 0 .. maxDeckSize)
					if (game.deck[deckIndex])
					{
						Action action = {
							type: Action.Type.pickFromDeck,
							deckIndex: deckIndex,
						};
						handleChoice(action.toArray);
					}
			}
			else
			{
				Action[maxDeckSize] actions;
				size_t numActions;
				foreach (ubyte deckIndex; 0 .. maxDeckSize)
					if (game.deck[deckIndex])
					{
						Action action = {
							type: Action.Type.drawFromDeck,
							deckIndex: deckIndex,
						};
						actions[numActions++] = action;
					}
				if (numActions > 0)
					handleChoice(actions[0 .. numActions]);
			}
		}
	}

	if (!game.draws)
	{
		foreach (ubyte handIndex; 0 .. maxHandSize)
			if (game.hand[handIndex])
			{
				Action action = {
					type: Action.Type.playCard,
					handIndex: handIndex,
				};
				assert(game.hand[handIndex].bloodCost >= 0, {
					string s = "Unknown card cost";
					debug s ~= ": " ~ cardNames[game.hand[handIndex].index];
					return s;
				}());

				if (game.hand[handIndex].bonesCost > game.bones)
					continue;

				foreach (ubyte sacrificeOrder; 0 .. sacrificeOrders.length)
				{
					bool ok = {
						byte blood;
						foreach (boardColumn; sacrificeOrders[sacrificeOrder])
						{
							if (blood >= game.hand[handIndex].bloodCost)
								return false; // too many sacrifices
							auto card = &game.board[Row.my][boardColumn];
							if (!*card)
								return false;
							if (card.flags & CardFlags.noSacrifice)
								return false;
							if (card.abilities & Abilities.worthySacrifice)
								blood += 3;
							else
								blood++;
						}
						return blood >= game.hand[handIndex].bloodCost;
					}();
					if (!ok)
						continue;

					action.sacrificeOrder = sacrificeOrder;

					foreach (ubyte boardColumn; 0 .. boardWidth)
					{
						bool canMoveHere = {
							if (!game.board[Row.my][boardColumn])
								return true; // empty slot, can move here
							if (sacrificeOrders[sacrificeOrder].canFind(boardColumn))
							{
								if (game.board[Row.my][boardColumn].abilities & Abilities.manyLives)
									return false; // card will remain
								return true; // card will be sacrificed, can move here
							}
							return false; // occupied slot, can't move here
						}();
						if (canMoveHere)
						{
							action.boardColumn = boardColumn;
							handleChoice(action.toArray);
						}
					}
				}
			}

		foreach (ubyte itemIndex; 0 .. maxItems)
			if (game.items[itemIndex])
			{
				foreach (byte boardColumn; -1 .. boardWidth)
				{
					bool canMoveHere = {
						switch (game.items[itemIndex])
						{
							case Item.placeholder:
								return false;
							case Item.fishHook:
								return boardColumn >= 0 && game.board[Row.ai][boardColumn] && !game.board[Row.my][boardColumn];
							case Item.scissors:
								return boardColumn >= 0 && game.board[Row.ai][boardColumn];
							default:
								return boardColumn == -1; // Does not target a board cell
						}
					}();
					if (!canMoveHere)
						continue;

					Action action = {
						type: Action.Type.useItem,
						itemIndex: itemIndex,
						boardColumn: boardColumn,
					};
					handleChoice(action.toArray);
				}
			}

		{
			Action action = {
				type: Action.Type.endTurn,
			};
			handleChoice(action.toArray);
		}
	}
}

void search(bool verbose = false)(ref const Game initGame, scope bool delegate(Node* root) iterCallback, bool singleThreaded = false)
{
	auto numThreads = singleThreaded ? 1 : totalCPUs;

	// Dedicated arena for Nodes, to allow iterating over all nodes
	auto nodeArena = Arena("nodes", 24UL * 1024 * 1024 * 1024 / totalCPUs * numThreads);
	scope(exit) static if (verbose) stderr.writefln("nodeArena: %d / %d", nodeArena.usedSize, nodeArena.capacity);

	struct ThreadData
	{
		Arena arena;
		size_t numExpansions;
		size_t expandExploreHead, expandCommitHead;
	}
	auto threadData = new ThreadData[numThreads];
	scope (exit)
		foreach (threadIndex; 0 .. numThreads)
			threadData[threadIndex].arena = Arena.init;
	foreach (threadIndex; 0 .. numThreads)
		threadData[threadIndex].arena = Arena("thread", 32UL * 1024 * 1024 * 1024 / totalCPUs);
	scope(exit) static if (verbose) stderr.writefln("thread arenas: %d / %d",
		numThreads.iota.map!(threadIndex => threadData[threadIndex].arena.usedSize).sum,
		numThreads.iota.map!(threadIndex => threadData[threadIndex].arena.capacity).sum,
	);

	HashMap!(GameRef, Node*, Mallocator, hashOf, /*supportGC:*/false, /*storeHash:*/false) hashTable;

	Node* getNodeForGame(ref const Game game, hash_t gameHash)
	{
		assert(game.isNormalized());

		Node dummyNode;
		dummyNode.rootGame = &game;
		dummyNode.gameHash = gameHash;

		if (auto p = GameRef(&dummyNode) in hashTable)
			return *p;

		return null;
	}

	auto root = nodeArena.alloc!Node;
	Game rootGame = initGame;
	rootGame.normalize();
	root.rootGame = &rootGame;
	root.gameHash = hashOf(rootGame);
	root.score = getHeuristicScore(rootGame);

	void updateScore(ref Node node) @nogc
	{
		assert(node.expanded);
		if (node.scoreIsFinal)
			return;

		if (!node.choices.length)
		{
			// if (node.game.isOver())
			// 	// reuse heuristic score, which is final in a game-over state
			// 	assert(node.score == getFinalScore(node.game));
			// else
			// 	node.score = -10_000; // dead end?
			node.scoreIsFinal = true;
			return;
		}

		size_t bestChoice = 0;
		Score bestScore = Score.min;
		bool scoreIsFinal = true;
		foreach (i, choice; node.choices)
		{
			Score avgScore;
			auto outcomes = choice;
			{
				Score sum;
				foreach (outcome; outcomes)
				{
					sum += outcome.node.score;
					scoreIsFinal = scoreIsFinal && outcome.node.scoreIsFinal;
				}
				if (outcomes.length == 1) // single outcome - most common case
					avgScore = sum;
				else
					avgScore = sum / cast(Score)outcomes.length;
				assert(avgScore < 50_000);
			}
			if (avgScore > bestScore)
			{
				bestScore = avgScore;
				bestChoice = i;
			}
		}

		bestScore -= 1; // distance malus

		node.score = bestScore;
		node.bestChoice = bestChoice;
		node.scoreIsFinal = scoreIsFinal;
	}

	// --- Expansion storage

	struct Expansion
	{
		Node* parentNode;
		Action parentAction;

		hash_t gameHash;
		// TODO: maybe keep a Game copy here (check what's faster)
		Game game;

		Score heuristicScore;

		// After sorting, is this the first distinct item
		// (i.e. it is different from the previous item)?
		bool unique;
	}

	alias expansionCompare = (ref a, ref b)
	{
		if (a.gameHash != b.gameHash)
			return a.gameHash < b.gameHash;
		return cast(size_t[])(a.game.bytes) < cast(size_t[])(b.game.bytes);
	};

	auto expansionsArena = Arena("expansions", 2UL * 1024 * 1024 * 1024 / totalCPUs * numThreads);
	auto maxExpansionsPerThread = (expansionsArena.end - expansionsArena.start) / 2 / Expansion.sizeof / numThreads;
	auto maxExpansions = maxExpansionsPerThread * numThreads;
	auto expansionsBuffer = expansionsArena.alloc!Expansion(maxExpansions);
	auto uniqueExpansionsBuffer = expansionsArena.alloc!(Expansion, false)(maxExpansions);

	auto threadExpansionsBuffers = numThreads
		.iota
		.map!(threadIndex => expansionsBuffer[threadIndex * maxExpansionsPerThread .. (threadIndex + 1) * maxExpansionsPerThread])
		.array;

	// --- Main loop

	do
	{
		auto allNodes = cast(Node[])nodeArena.data;

		// Expansion loop
		bool keepExpanding = true;

		auto thread0Start = threadData[0].expandCommitHead;

		while (keepExpanding)
		{
			static if (verbose) stderr.writefln("- Expanding");

			// Exploratory step - expand unexpanded states and put all new games in a buffer

			static if (verbose) stderr.writefln("  - Exploring");
			foreach (threadIndex; numThreads.iota.parallel(1))
			{
				auto threadExpansionsBuffer = threadExpansionsBuffers[threadIndex];
				size_t numThreadExpansions;

				ref size_t nodeIndex() { return threadData[threadIndex].expandExploreHead; }
				for (; nodeIndex < allNodes.length; nodeIndex++)
				{
					auto node = &allNodes[nodeIndex];
					if (nodeIndex % numThreads == threadIndex && !node.expanded)
					{
						const Game game = node.getGame();

						void choiceHandler(scope const Action[] actions)
						{
							assert(actions.length, "Zero outcomes");

							foreach (ref action; actions)
							{
								if (numThreadExpansions == maxExpansionsPerThread)
									return; // Out of space

								Game nextGame = game;
								nextGame.applyAction(action);

								nextGame.normalize();
								auto gameHash = hashOf(nextGame);

								if (getNodeForGame(nextGame, gameHash))
									continue; // already visited

								Expansion expansion;
								expansion.parentNode = node;
								expansion.parentAction = action;
								expansion.game = nextGame;
								expansion.gameHash = gameHash;
								threadExpansionsBuffer[numThreadExpansions++] = expansion;
							}
						}

						expandGame(game, &choiceHandler);

						if (numThreadExpansions == maxExpansionsPerThread)
							break; // Out of space
					}
				}

				threadData[threadIndex].numExpansions = numThreadExpansions;

				// Sort it (in preparation of full sort/deduplicate).
				threadExpansionsBuffer[0 .. numThreadExpansions].sort!expansionCompare();
			}

			static if (verbose) stderr.writefln("    - %d/%d expansions",
				numThreads.iota.map!(threadIndex => threadData[threadIndex].numExpansions).sum,
				maxExpansions,
			);

			// We will need to retry the loop if any of the thread buffers got full.
			keepExpanding = numThreads.iota.any!(
				threadIndex => threadData[threadIndex].numExpansions == maxExpansionsPerThread
			);

			// Deduplicate and count

			static if (verbose) stderr.writefln("  - Deduplicating");
			size_t numUniqueExpansions = 0;
			auto threadExpansions = numThreads.iota.map!(threadIndex =>
				threadExpansionsBuffers[threadIndex][0 .. threadData[threadIndex].numExpansions]
			).array;
			foreach (ref expansion; threadExpansions.multiwayUnion!expansionCompare)
				uniqueExpansionsBuffer[numUniqueExpansions++] = expansion;

			static if (verbose) stderr.writefln("    - %d/%d unique expansions", numUniqueExpansions, maxExpansions);

			// Allocate nodes

			auto numNewNodes = numUniqueExpansions;
			auto newNodes = nodeArena.alloc!Node(numNewNodes);

			// Populate nodes

			static if (verbose) stderr.writefln("  - Populating");
			foreach (threadIndex; numThreads.iota.parallel(1))
			{
				foreach (expansionIndex, ref expansion; uniqueExpansionsBuffer[0 .. numUniqueExpansions])
					if (expansionIndex % numThreads == threadIndex)
					{
						Node node;
						node.parent = expansion.parentNode;
						node.parentAction = expansion.parentAction;
						node.gameHash = expansion.gameHash;
						node.score = getHeuristicScore(expansion.game);

						newNodes[expansionIndex] = node;
					}
			}

			// Register in hash table

			static if (verbose) stderr.writefln("  - Registering");
			foreach (ref node; newNodes)
				hashTable[GameRef(&node)] = &node;

			// Final expansion - save pointers

			static if (verbose) stderr.writefln("  - Saving expansion results");
			foreach (threadIndex; numThreads.iota.parallel(1))
			{
				ref size_t nodeIndex() { return threadData[threadIndex].expandCommitHead; }
				for (; nodeIndex < allNodes.length; nodeIndex++)
				{
					auto node = &allNodes[nodeIndex];
					if (nodeIndex % numThreads == threadIndex && !node.expanded)
					{
						enum maxChoices = maxHandSize * boardWidth * (1 << boardWidth);
						Node.Choice[maxChoices] choices = void;
						size_t numChoices = 0;

						bool stop = false;

						const Game game = node.getGame();

						Node.Outcome runAction(Action action) /*@nogc*/
						{
							Node.Outcome outcome;
							outcome.action = action;

							Game nextGame = game;
							nextGame.applyAction(action);

							nextGame.normalize();
							auto gameHash = hashOf(nextGame);

							auto nextNode = getNodeForGame(nextGame, gameHash);
							if (!nextNode)
								stop = true;

							outcome.node = nextNode;
							return outcome;
						}

						void choiceHandler(scope const Action[] actions)
						{
							assert(actions.length, "Zero outcomes");

							auto outcomes = threadData[threadIndex].arena.alloc!(Node.Outcome)(actions.length);
							foreach (i; 0 .. actions.length)
								outcomes[i] = runAction(actions[i]);
							choices[numChoices++] = outcomes;
						}

						expandGame(game, &choiceHandler);

						if (stop)
							break; // Ran into unregistered node - exploratory step ran out of space here

						assert(numChoices <= maxChoices);
						node.choices = threadData[threadIndex].arena.alloc!(Node.Choice)(numChoices);
						node.choices[] = choices[0 .. numChoices];
						assert(node.expanded);
					}
				}

				assert(threadData[threadIndex].expandExploreHead <= threadData[threadIndex].expandCommitHead);
			}

			if (!singleThreaded && allNodes.length != thread0Start) stderr.writef("[%d%%]\r", 100 * (threadData[0].expandCommitHead - thread0Start) / (allNodes.length - thread0Start)); stderr.flush();
		}

		// Score propagation step

		static if (verbose) stderr.writefln("- Propagating scores");
		foreach_reverse (ref node; allNodes)
			updateScore(node);

		static if (verbose) stderr.writefln("- Iteration done");
	}
	while (iterCallback(root));
}

unittest
{
	Game game;
	if (false) search(game, null);
}