Buckshot Roulette solver

.gitignore

/search_shootself

board.svg

expand.d

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

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

import game;

enum Move : ubyte
{
	shootSelf,
	shootOther,
	useMagnifyingGlass,
	useHandcuffs,
	useBeer,
	useCigarettePack,
	useHandSaw,
}

string[enumLength!Item] itemDescriptions = [
	"a Magnifying Glass",
	"Handcuffs",
	"a Beer",
	"a Cigarette Pack",
	"a Hand Saw",
];

string getMoveDescription(Move move, Character who)
{
	final switch (move)
	{
		case Move.shootSelf       : return who == Character.player ? "Shoot yourself"   : "Shoot themselves";
		case Move.shootOther      : return who == Character.player ? "Shoot the dealer" : "Shoot you";
		case Move.useMagnifyingGlass : return "Use a Magnifying Glass";
		case Move.useHandcuffs    : return "Use Handcuffs";
		case Move.useBeer         : return "Use a Beer";
		case Move.useCigarettePack: return "Use a Cigarette Pack";
		case Move.useHandSaw      : return "Use a Hand Saw";
	}
}

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

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

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

enum Opponent
{
	game,
	perfect,
}

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

	struct State
	{
		Game game;
		alias game this;

		// Things that should be in the state (`Game`) but aren't
		// (because it's relatively inconsequential and will increase the state space too much):

		/// Upper and lower bound, inclusive, of what the initial health is
		/// (which is also the health that a character can heal up to).
		ubyte initialHealthMin = 2, initialHealthMax = 4;
	}

	Score resolveCanHealTo(const ref State state0, ubyte targetHealth, scope Dg!q{Score delegate(State newState, bool result)} handler)
	{
		State state1 = state0;
		state1.initialHealthMin = state1.initialHealthMin.max(state1.health[].fold!max(ubyte(0)));

		if (targetHealth > state1.initialHealthMax)
			return handler(state1, false);
		else
		if (targetHealth <= state1.initialHealthMin)
			return handler(state1, true);
		else
			return driver.choice!(ChoiceMode.unknown, bool)(
				() => "Is it possible to have " ~ targetHealth.to!string ~ " charges?",
				(result) {
					auto state2 = state1;
					if (result)
						state2.initialHealthMin = targetHealth;
					else
						state2.initialHealthMax = cast(ubyte)(targetHealth - 1);
					return handler(state2, result);
				},
				result => result ? "Yes" : "No",
				false, true,
			);
	}

	void switchTurn(ref State state)
	{
		state.currentTurn = state.currentTurn.other;
		driver.log(() => "It is now " ~ (state.currentTurn == Character.player ? "your" : "the dealer's") ~ " turn.");

		if (state.handcuffs[state.currentTurn] == HandcuffState.willSkip)
		{
			driver.log(() => state.currentTurn == Character.player
				? "You are handcuffed and skip your turn."
				: "The dealer is handcuffed and skips their turn."
			);
			if (state.totalShells == 0)
				driver.log(() => "(It doesn't matter, the round is ending.)");
			state.handcuffs[state.currentTurn] = HandcuffState.willBreak;
			return switchTurn(state);
		}

		if (state.handcuffs[state.currentTurn] == HandcuffState.willBreak)
		{
			driver.log(() => (state.currentTurn == Character.player ? "Your" : "The dealer's") ~ " handcuffs break off.");
			state.handcuffs[state.currentTurn] = HandcuffState.none;
		}
	}

	Score resolveRound(const ref State state, scope Dg!q{Score delegate(ShellType shellType, ref State newState)} handler)
	{
		if (!state.nextShell.isNull)
		{
			State newState = state;
			auto shellType = newState.nextShell.get();
			newState.nextShell.nullify();
			return handler(shellType, newState);
		}

		Weighted!ShellType[enumLength!ShellType] options;
		foreach (shellType; ShellType.init .. enumLength!ShellType)
			options[shellType] = Weighted!ShellType(shellType, state.shells[shellType]);

		return driver.choice!(ChoiceMode.randomWeighted, Weighted!ShellType)(
			() => "What shell was in the chamber?",
			(shellType) {
				if (!shellType.weight)
					return Score.nan;
				State newState = state;
				newState.shells[shellType.value]--;
				return handler(shellType.value, newState);
			},
			shellType => ["Blank", "Live"][shellType.value],
			options
		);
	}

	Score shoot(ref const State state, Character whom)
	{
		driver.log(() => 
			state.currentTurn == Character.player
			? whom            == Character.player
			? "You shoot yourself."
			: "You shoot the dealer."
			: whom            == Character.player
			? "The dealer shoots you."
			: "The dealer shoots themselves."
		);
		return resolveRound(state, (ShellType shellType, ref State newState) {
			auto damage = 1;
			if (newState.shotgunSawedOff)
				damage = 2;
			final switch (shellType)
			{
				case ShellType.blank:
					driver.log(() => "Blank. No damage.");
					// If the shotgun was aimed at the other player, switch turns
					if (whom != newState.currentTurn)
						switchTurn(newState);
					break;
				case ShellType.live:
					driver.log(() => (whom == Character.player ? "You take" : "The dealer takes") ~ " " ~ damage.to!string ~ " damage.");
					newState.health[whom] -= damage;
					if (newState.health[whom] <= 0)
						final switch (whom)
						{
							case Character.player:
								driver.log(() => "You are out. You lose!");
								return driver.gameOver(false);
							case Character.dealer:
								driver.log(() => "The dealer is out. You win!");
								return driver.gameOver(true);
						}
					switchTurn(newState);
					break;
			}
			if (newState.shotgunSawedOff)
			{
				driver.log(() => "The shotgun barrel reapparates.");
				newState.shotgunSawedOff = false;
			}
			return driver.recurse(newState);
		});
	}

	Score use(ref const State state0, Item item)
	{
		if (!state0.items[state0.currentTurn][item])
			return Score.nan;
		driver.log(() => (state0.currentTurn == Character.player ? "You use " : "The dealer uses ") ~ itemDescriptions[item] ~ ".");
		State state1 = state0;
		state1.items[state1.currentTurn][item]--;
		final switch (item)
		{
			case Item.handcuffs:
				if (state1.handcuffs[state1.currentTurn.other])
					return Score.nan;
				state1.handcuffs[state1.currentTurn.other] = HandcuffState.willSkip;
				driver.log(() => (state1.currentTurn.other == Character.player ? "You are" : "The dealer is") ~ " now handcuffed.");
				return driver.recurse(state1);
			case Item.magnifyingGlass:
				if (!state1.nextShell.isNull)
					return Score.nan;
				return resolveRound(state1, (ShellType shellType, ref State state2) {
					driver.log(() => (state2.currentTurn == Character.player ? "You now know" : "The dealer now knows") ~ " that the next shell is " ~ shellType.to!string ~ ".");
					state2.nextShell = shellType;
					return driver.recurse(state2);
				});
			case Item.beer:
				return resolveRound(state1, (ShellType shellType, ref State state2) {
					driver.log(() => (state2.currentTurn == Character.player ? "You rack" : "The dealer racks") ~ " the shotgun, and a " ~ shellType.to!string ~ " shell is ejected.");
					return driver.recurse(state2);
				});
			case Item.cigarettePack:
				Score smoke(State state2, bool canHeal)
				{
					if (canHeal)
					{
						driver.log(() => (state2.currentTurn == Character.player ? "You restore" : "The dealer restores") ~ " one charge.");
						state2.health[state2.currentTurn]++;
					}
					else
						driver.log(() => (state2.currentTurn == Character.player ? "You are" : "The dealer is") ~ " already at maximum charges.");
					return driver.recurse(state2);
				}
				return resolveCanHealTo(state1, cast(ubyte)(state1.health[state1.currentTurn] + 1), &smoke);
			case Item.handSaw:
				if (state1.shotgunSawedOff)
					return Score.nan;
				state1.shotgunSawedOff = true;
				driver.log(() => "The shotgun barrel is now sawed off.");
				return driver.recurse(state1);
		}
	}

	Score tryMove(ref const State state, Move move)
	{
		final switch (move)
		{
			case Move.shootSelf : return shoot(state, state.currentTurn);
			case Move.shootOther: return shoot(state, state.currentTurn.other);
			case Move.useMagnifyingGlass: return use(state, Item.magnifyingGlass);
			case Move.useHandcuffs: return use(state, Item.handcuffs);
			case Move.useBeer: return use(state, Item.beer);
			case Move.useCigarettePack: return use(state, Item.cigarettePack);
			case Move.useHandSaw: return use(state, Item.handSaw);
		}
	}

	immutable state0 = State(game);

	if (state0.totalShells == 0)
	{
		// Handcuffs come off. How will you grab the items otherwise?
		foreach (Character character, handcuffState; state0.handcuffs)
			if (handcuffState)
			{
				State state1 = state0;
				state1.handcuffs[character] = HandcuffState.none;
				driver.log(() => "The round is ending; " ~ (character == Character.player ? "your" : "the dealer's") ~ " handcuffs come off.");
				return driver.recurse(state1);
			}

		// It's always the player's turn first.
		if (state0.currentTurn != Character.player)
		{
			State state1 = state0;
			state1.currentTurn = Character.player;
			driver.log(() => "The round is ending; the dealer's turn ends.");
			return driver.recurse(state1);
		}

		// End of round.
		driver.log(() => "Starting new round.");

		State state1 = state0;

		// Use a different flow depending on if the driver is interactive.
		// If yes, use a series of questions suitable for interactive use (humans).
		// If no, use a more efficient flow with fewer questions.
		// The result should be the same.
		if (driver.interactive)
		{
			// Ask questions in the order that the game presents information to players.
			enum Phase
			{
				itemsConfig,
				playerItems,
				charges,
				shells,
				dealerItems,
				end,
			}
			enum minGrantedItems = 1;
			enum maxGrantedItems = 4;
			static struct AskState
			{
				State state;
				alias state this;

				Phase phase;

				// The player gets between 0 and 4 items.  The dealer gets the same amount.
				// We want to ask questions in the order that the game asks them...
				// but it gets complicated because:
				// 1. The item number distribution should be linear,
				//    but the number of granted items can't be known until the end
				// 2. Characters can run out of inventory space
				//    (so the total number of items may not even be knowable...)
				// These track the lower and upper bound (inclusive):
				size_t numItemsLow, numItemsHigh;
				size_t[enumLength!Character] itemIndex;
			}

			scope Dg!(q{Score delegate(ref const Args[0])}, AskState) ask;
			ask = (ref const AskState state2)
			{
				Score nextPhase(ref const AskState state3)
				{
					AskState state4 = state3;
					state4.phase++;
					return ask(state4);
				}

				final switch (state2.phase)
				{
					case Phase.itemsConfig:
						return driver.choice!(ChoiceMode.first, bool)(
							() => "Are items enabled?",
							(itemsEnabled) {
								AskState state3 = state2;
								if (itemsEnabled)
								{
									state3.numItemsLow = minGrantedItems;
									state3.numItemsHigh = maxGrantedItems;
								}
								else
								{
									state3.numItemsLow = 0;
									state3.numItemsHigh = 0;
								}
								return nextPhase(state3);
							},
							(itemsEnabled) => itemsEnabled ? "Yes" : "No (first act of story mode)",
							true, false,
						);

					case Phase.playerItems:
					case Phase.dealerItems:
						auto character = state2.phase == Phase.playerItems ? Character.player : Character.dealer;
						auto itemsSoFar = state2.itemIndex[character];

						if (itemsSoFar == state2.numItemsHigh)
							return nextPhase(state2);

						// Some slightly hairy math, in order to fairly represent the linear
						// distribution of number of granted items without asking additional questions:
						size_t noItemChanceNumerator, noItemChanceDenominator;
						if (itemsSoFar < state2.numItemsLow)
						{
							// We *know* an item will be granted.
							noItemChanceNumerator = 0;
							noItemChanceDenominator = 1;
						}
						else
						{
							noItemChanceNumerator = 1;
							noItemChanceDenominator = maxGrantedItems + 1 - itemsSoFar;
						}
						auto itemNotGrantedWeight =                           noItemChanceNumerator;
						auto itemGrantedWeight    = noItemChanceDenominator - noItemChanceNumerator;

						if (state2.totalItems(character) == maxItems)
						{
							if (character == Character.player)
							{
								// Same as below, except "false" instead of null and "true" instead of non-null.
								Weighted!bool[2] options = [
									{ false, itemNotGrantedWeight },
									{ true , itemGrantedWeight    },
								];

								return driver.choice!(ChoiceMode.randomWeighted, Weighted!bool)(
									() => "No more room, but did " ~ (character == Character.player ? "you" : "the dealer") ~ " get " ~ ["an", "a second", "a third", "a fourth"][itemsSoFar] ~ " item?",
									(gotItem) {
										if (!gotItem.weight)
											return Score.nan;
										AskState state3 = state2;
										if (!gotItem.value)
										{
											if (state3.numItemsHigh > itemsSoFar)
												state3.numItemsHigh = itemsSoFar;
										}
										else
										{
											if (state3.numItemsLow < itemsSoFar + 1)
												state3.numItemsLow = itemsSoFar + 1;
										}
										return nextPhase(state3);
									},
									(gotItem) => gotItem.value ? "Yes" : "No",
									options[],
								);
							}
							else
							{
								// I guess we'll never know.
								return nextPhase(state2);
							}
						}

						Weighted!(Nullable!Item)[enumLength!Item + 1] options;

						foreach (item; Item.init .. enumLength!Item)
							options[item].value = item.nullable;
						options[enumLength!Item].value = Nullable!Item.init;

						foreach (item; Item.init .. enumLength!Item)
						{
							bool canAdd = {
								switch (item)
								{
									case Item.cigarettePack:
										return state2.items[character][Item.cigarettePack] < 2;
									default:
										return true;
								}
							}();
							if (!canAdd)
								continue;

							options[item           ].weight += itemGrantedWeight;
							options[enumLength!Item].weight += itemNotGrantedWeight;
						}

						return driver.choice!(ChoiceMode.randomWeighted, Weighted!(Nullable!Item))(
							() => "What is the" ~ (state2.numItemsHigh == 1 ? "" : [" first", " second", " third", " fourth"][itemsSoFar]) ~ " item that " ~ (character == Character.player ? "you get" : "the dealer gets") ~ "?",
							(item) {
								if (!item.weight)
									return Score.nan;
								AskState state3 = state2;
								if (item.value.isNull)
								{
									if (state3.numItemsHigh > itemsSoFar)
										state3.numItemsHigh = itemsSoFar;
									return nextPhase(state3);
								}
								else
								{
									if (state3.numItemsLow < itemsSoFar + 1)
										state3.numItemsLow = itemsSoFar + 1;
									state3.items[character][item.value.get()]++;
									state3.itemIndex[character]++;
									return ask(state3);
								}
							},
							(item) => item.value.isNull
								? "Nothing (no " ~ (itemsSoFar == 0 ? "" : "more ") ~ "items)"
								: capitalize(itemDescriptions[item.value.get()]),
							options[]
						);

					// Note, this could also be done by making 0 HP representable...
					case Phase.charges:
						return driver.choice!(ChoiceMode.first, ubyte)(
							() => "Reset charges?",
							(charges) {
								AskState state3 = state2;
								if (charges)
								{
									state3.health[] = charges;
									driver.log(() => "Both characters now have " ~ charges.to!string ~ " charges.");
								}
								return nextPhase(state3);
							},
							charges => charges ? "Yes, " ~ charges.to!string ~ " charges" : "No",
							0, 2, 3, 4
						);

					case Phase.shells:
						return driver.choice!(ChoiceMode.random, ubyte)(
							() => "How many shells are loaded?",
							(totalShells) {
								AskState state3 = state2;
								auto liveShells = cast(ubyte)(totalShells / 2); // rounding down
								auto blankShells = cast(ubyte)(totalShells - liveShells);
								driver.log(() => blankShells.to!string ~ " blank, " ~ liveShells.to!string ~ " live.");
								state3.shells[ShellType.blank] = blankShells;
								state3.shells[ShellType.live] = liveShells;
								return nextPhase(state3);
							},
							totalShells => totalShells.to!string,
							2, 3, 4, 5, 6, 7, 8
						);

					case Phase.end:
						driver.log(() => "Round begins.");
						return driver.recurse(state2);
				}
			};
			auto askState = AskState(state1);
			return ask(askState);
		}
		else
			// Refill magazine.
			return driver.choice!(ChoiceMode.random, ubyte)(
				() => "How many shells are loaded?",
				(totalShells) {
					State state2 = state1;
					auto liveShells = cast(ubyte)(totalShells / 2); // rounding down
					auto blankShells = cast(ubyte)(totalShells - liveShells);
					driver.log(() => blankShells.to!string ~ " blank, " ~ liveShells.to!string ~ " live.");
					state2.shells[ShellType.blank] = blankShells;
					state2.shells[ShellType.live] = liveShells;

					// Grant items
					return driver.choice!(ChoiceMode.random, ubyte)(
						() => "How many items are granted?",
						(numItems) {
							scope Dg!q{Score delegate(ref const State, Character)} grantItems;
							grantItems = (ref const State state3, Character character)
							{
								if (character == enumLength!Character)
								{
									// Done granting items.

									driver.log(() => "Round begins.");
									return driver.recurse(state3);
								}

								auto remainingRoom = maxItems - state3.totalItems(character);
								if (remainingRoom < numItems)
									driver.log(() => (character == Character.player ? "You don't" : "The dealer doesn't") ~ " have room to receive " ~ numItems.to!string ~ " item" ~ (numItems == 1 ? "" : "s") ~ ".");

								auto grantedItems = min(numItems, remainingRoom);
								if (grantedItems == 0)
								{
									driver.log(() => (character == Character.player ? "You don't" : "The dealer doesn't") ~ " receive any items.");
									character++;
									return grantItems(state3, character);
								}

								driver.log(() => (character == Character.player ? "You receive" : "The dealer receives") ~ " " ~ grantedItems.to!string ~ " item" ~ (grantedItems == 1 ? "" : "s") ~ ".");

								static foreach (grantedItemsCT; 1 .. 4 + 1)
									if (grantedItemsCT == grantedItems)
										static foreach (numCigarettePacksCT; 0 .. 2 + 1)
											if (numCigarettePacksCT == state3.items[character][Item.cigarettePack])
											{
												alias PackedItems = ubyte;
												alias ItemCNS = CNS!(/*PackedItems*/uint, /*Item*/ubyte, grantedItemsCT, enumLength!Item, true, true);
												static assert(ItemCNS.packedCard <= PackedItems.max);

												Weighted!PackedItems[ItemCNS.packedCard] genItemChoiceTable()
												{
													Weighted!PackedItems[ItemCNS.packedCard] result;
													foreach (PackedItems packedItems, ref option; result)
														option.value = packedItems;

													/*Item*/ubyte[grantedItemsCT] items;
													void iterate(size_t itemIndex, int remainingCigarettePacks)
													{
														if (itemIndex == grantedItemsCT)
														{
															// `dup` for https://issues.dlang.org/show_bug.cgi?id=24354
															/*Item*/ubyte[grantedItemsCT] sortedItems = items.dup;
															sortedItems[].sort();
															auto packedItems = cast(PackedItems)ItemCNS.pack(sortedItems);
															result[packedItems].weight++;
														}
														else
															foreach (item; Item.init .. enumLength!Item)
															{
																if (item == Item.cigarettePack && !remainingCigarettePacks)
																	continue;
																items[itemIndex] = item;
																iterate(itemIndex + 1, remainingCigarettePacks - (item == Item.cigarettePack ? 1 : 0));
															}
													}
													iterate(0, 2 - numCigarettePacksCT);
													return result;
												}

												static immutable choiceTable = genItemChoiceTable();

												return driver.choice!(ChoiceMode.randomWeighted, Weighted!PackedItems)(
													() => "What items did " ~ (character == Character.player ? "you" : "the dealer") ~ " get?",
													(packedItems) {
														if (!packedItems.weight)
															return Score.nan;
														auto items = ItemCNS.unpack(packedItems.value);
														State state4 = state3;
														foreach (item; items)
															state4.items[character][item]++;
														assert(state4.totalItems(character) <= maxItems);
														auto nextCharacter = character; nextCharacter++;
														return grantItems(state4, nextCharacter);
													},
													(packedItems) {
														auto items = ItemCNS.unpack(packedItems.value);
														return items[].map!(item => itemDescriptions[item]).join(", ").capitalize;
													},
													choiceTable[]
												);
											}

								driver.log(() => "Impossible combination of granted items / cigarette packs.");
								return Score.nan;
							};
							return grantItems(state2, Character.init);
						},
						numItems => numItems.to!string,
						1, 2, 3, 4
					);
				},
				totalShells => totalShells.to!string,
				2, 3, 4, 5, 6, 7, 8
			);
	}

	assert(!state0.handcuffs[state0.currentTurn]);

	final switch (state0.currentTurn)
	{
		case Character.player:
			// Assume that the player will proceed according to what's best for them.
			return driver.choice!(ChoiceMode.best, Move)(
				() => "What will you do?",
				move => tryMove(state0, move),
				move => getMoveDescription(move, Character.player),
				EnumMembers!Move,
			);

		case Character.dealer:
			final switch (opponent)
			{
				case Opponent.perfect:
					return driver.choice!(ChoiceMode.worst, Move)(
						() => "What does the dealer do?",
						move => tryMove(state0, move),
						move => getMoveDescription(move, Character.dealer),
						EnumMembers!Move,
					);
				case Opponent.game:
					Score dealerAI(ref const State state1, bool dealerCanHeal)
					{
						Score coinFlip(T)(
							scope Dg!(q{Score delegate(Args[0])}, T) getScore,
							scope string delegate(T) getDescription,
							scope T[] items...
						)
						{
							assert(items.length == 2);
							return driver.choice!(ChoiceMode.random, T)(
								() => "The dealer flips a coin...",
								getScore,
								item => (item == items[0] ? "Heads" : "Tails") ~ ": " ~ getDescription(item),
								items
							);
						}


						// Simulate game AI
						Nullable!Character dealerTarget;
						Nullable!ShellType knownShell;
						bool dealerKnowsShell;

						if (!state1.nextShell.isNull)
						{
							// If it's resolved, it's guaranteed that the current character knows it
							knownShell = state1.nextShell;
							dealerTarget = knownShell.get() == ShellType.live
								? Character.player
								: Character.dealer;
							dealerKnowsShell = true;
						}

						if (state1.totalShells == 1)
						{
							knownShell = state1.shells[ShellType.live]
								? ShellType.live
								: ShellType.blank;
							dealerTarget = knownShell.get() == ShellType.live
								? Character.player
								: Character.dealer;
							dealerKnowsShell = true;
						}

						// The real AI actually iterates over items using a hidden internal order
						// (order that items were acquired).
						// To be safe, assume an order which is most inconvenient for us.
						Move[enumLength!Item] itemOptions; size_t numItemOptions;
						if (state1.items[state1.currentTurn][Item.magnifyingGlass] && !dealerKnowsShell && state1.totalShells != 1)
							itemOptions[numItemOptions++] = Move.useMagnifyingGlass;
						if (state1.items[state1.currentTurn][Item.cigarettePack] && dealerCanHeal)
							itemOptions[numItemOptions++] = Move.useCigarettePack;
						if (state1.items[state1.currentTurn][Item.beer] && knownShell != ShellType.live.nullable && state1.totalShells != 1)
							itemOptions[numItemOptions++] = Move.useBeer;
						if (state1.items[state1.currentTurn][Item.handcuffs] && state1.handcuffs[state1.currentTurn.other] == HandcuffState.none && state1.totalShells != 1)
							itemOptions[numItemOptions++] = Move.useHandcuffs;
						if (state1.items[state1.currentTurn][Item.handSaw] && !state1.shotgunSawedOff && knownShell == ShellType.live.nullable)
							itemOptions[numItemOptions++] = Move.useHandSaw;
						if (numItemOptions)
							return driver.choice!(ChoiceMode.unknown, Move)(
								() => "The dealer will use an item...",
								move => tryMove(state1, move),
								move => getMoveDescription(move, Character.dealer),
								itemOptions[0 .. numItemOptions]
							);

						if (state1.items[state1.currentTurn][Item.handSaw] && !state1.shotgunSawedOff && knownShell != nullable(ShellType.blank))
							return coinFlip!Move(
								move => tryMove(state1, move),
								move => getMoveDescription(move, Character.dealer),
								Move.shootSelf, Move.useHandSaw,
							);

						if (state1.shotgunSawedOff)
							dealerTarget = Character.player;

						if (dealerTarget.isNull)
							return coinFlip!Move(
								move => tryMove(state1, move),
								move => getMoveDescription(move, Character.dealer),
								Move.shootSelf, Move.shootOther,
							);
						else
						{
							auto move = dealerTarget.get() == Character.dealer ? Move.shootSelf : Move.shootOther;
							return tryMove(state1, move);
						}
					}

					// Resolve if dealer can heal here
					if (state0.items[state0.currentTurn][Item.cigarettePack])
						return resolveCanHealTo(state0, cast(ubyte)(state0.health[state0.currentTurn] + 1), (State state1, bool result) { return dealerAI(state1, result); });
					else
						return dealerAI(state0, false);
			}
	}
}

nothrow @nogc
unittest
{
	static struct TestDriver
	{
		enum interactive = false;

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

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

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

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

	Game game;
	TestDriver driver;
	if (false)
		expand(game, driver, Opponent.game);
}

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

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

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

unittest
{
	struct Driver
	{
		enum interactive = false;
		void log(scope string delegate() message) nothrow @nogc {}
		Score recurse(const ref Game game) nothrow @nogc { return 0; }
		alias GetScore(T) = Score delegate(T) nothrow @nogc;
		alias choice = graphChoice!GetScore;
		alias gameOver = graphGameOver;
	}

	Game game;
	Driver driver;
	expand(game, driver, Opponent.game);
}

game.d

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

import ae.utils.meta;

enum Character : ubyte
{
	player,
	dealer,
}

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

enum ShellType : ubyte
{
	blank,
	live,
}

enum Item : ubyte
{
	magnifyingGlass,
	handcuffs,
	beer,
	cigarettePack,
	handSaw,
}

enum maxShells = 8;
enum maxItems = 8;

enum HandcuffState
{
	none,
	willBreak,
	willSkip,
}

struct Game
{
	Character currentTurn;
	byte[enumLength!ShellType] shells;
	@property uint totalShells() const nothrow @nogc { return shells[].sum + (nextShell.isNull ? 0 : 1); }
	byte[enumLength!Item][enumLength!Character] items;
	uint totalItems(Character character) const nothrow @nogc { return items[character][].sum; }
	byte[enumLength!Character] health;
	HandcuffState[enumLength!Character] handcuffs;
	Nullable!ShellType nextShell;
	bool shotgunSawedOff;
}

graph.d

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

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

import game;
import expand;
import packing;

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

PackedScore packScore(Score score) nothrow @nogc
in(0 <= score && score <= 1)
{
	return PackedScore(cast(PackedScore.Value)round(score * PackedScore.Value.max));
}

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

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

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

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

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

		Score recurse(const ref Game game) nothrow @nogc
		{
			return source[game.packGame()].unpackScore;
		}

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

	{
		PackedGame numDone;
		foreach (packedGame; packedGameCard.iota.parallel(packedGameCard / totalCPUs / 128))
		{
			auto game = packedGame.unpackGame();
			auto score = expand.expand(game, &driver, opponent);
			target[packedGame] = score.packScore;
			enum progressPeriod = 0x1000000;
			if (packedGame % progressPeriod == 0)
				synchronized
				{
					numDone += progressPeriod;
					stderr.write(100 * numDone / packedGameCard, "%\r"); stderr.flush();
				}
		}
	}
}

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

	stderr.writeln("=== Generating scores for ", opponent);

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

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

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

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

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

			propagateScores(current, next, opponent);

			auto totalChange = zip(current, next).map!(pair => abs(long(pair[0].value) - pair[1].value)).sum;
			auto maxChange = zip(current, next).map!(pair => abs(int(pair[0].value) - pair[1].value)).reduce!max;
			auto numChanged = zip(current, next).map!(pair => pair[0] == pair[1] ? 0L : 1L).sum;
			// auto crc = crc32Of(table);
			auto changeLimit = 1;
			writeln(" > Change: num=", numChanged, " / ", packedGameCard,
				", total=", totalChange,
				", avg=", (double(totalChange) / packedGameCard).fpToString,
				", max=", maxChange, " / ", changeLimit,
				// ", CRC=", crc[].format!"%(%02x%)",
			);

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

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

unittest
{
	if (false) generateScoreFile(Opponent.init);
}

version (main_graph)
void main()
{
	foreach (opponent; Opponent.init .. enumLength!Opponent)
		generateScoreFile(opponent);
}

index.php

<!doctype html>
<head>
	<meta charset="UTF-8">
	<meta name="darkreader-lock"> <!-- SVG rendering in backgrounds is broken in Dark Reader -->
	<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">

	<title>Buckshot Roulette solver</title>
</head>

<div id="page">
	<!-- <object id="game" data="board.svg?<?php echo(filemtime("board.svg")) ?>"></object> -->
	<?php readfile('board.svg'); ?>
	<div id="packed-game"></div>
	<div id="explorer-page">
		<table>
			<tr>
				<td id="summary">Loading...</td>
			</tr>
		</table>

		<table id="explorer">
			<tr id="explorer-header">
				<th></th>
				<th>Analysis</th>
				<th>Win %</th>
			</tr>
		</table>
	</div>
	<div id="help-page">
		<div>
			<h3>Buckshot Roulette solver</h1>
			<p>Usage:</p>

			<ol>
				<li>
					<p>Input the game you want to get a solution for by clicking/tapping on the slots.</p>
					<p>Right click / long tap a slot to clear it.</p>
					<p>You can also use the mouse wheel to quickly cycle through options.</p>
					<p>Drag items to swap their location.</p>
					<p>Click the stock to change whose turn it is.</p>
				</li>
				<li>
					<p>The summary on the top right will give you a simple explanation of the situation.</p>
				</li>
				<li>
					<p>The outcome explorer on the right will display an analysis of the game.</p>

					<p>
						The <b>Win %</b> column will show the likelihood of the game ending with you winning,
						assuming perfect play on your behalf (i.e. using this solver for all decisions).
						100% means that a win is guaranteed, and 0% means that a loss is inevitable.
					</p>

					<p>
						The explorer simulates the game, playing forward starting from the entered game, based on the selected and implied decisions and outcomes.
						For decisions and random events, the analysis will show how each outcome affects the <b>Win %</b>.
						You can select or change which outcome happens by selecting the corresponding option.
					</p>

					<p>
						Checkpoints are game states that can be loaded into the game editor.
						Click the "Game #" link to do so.
					</p>
				</li>
			</ol>

			<p>You can change the simulated opponent at the top:</p>
			<ul>
				<li><b>Game Dealer AI</b> is the AI that the game uses.</li>
				<li>
					<b>Perfect opponent</b> is a hypothetical opponent who plays perfectly,
					and makes decisions which are most likely to lead them to win.
					However, you can override the opponent's decisions in the explorer.
				</li>
			</ul>

			<p>Click <span class="emoji">🧹</span> to reset the board to a new game. You can use your web browser's back and forward buttons to undo / redo.</p>

			<p>Click <span class="emoji">🔄</span> to flip the board around, if you want to examine your opponent's options.</p>

			<p>Click <span class="emoji">❌</span> to close this help page.</p>

			<p>Links:</p>
			<ul>
				<li><a href="https://gist.github.com/CyberShadow/87d403bb29fa3047f2182c41f74e286e">Source code</a></li>
				<li><a href="https://itch.io/post/9255122">itch.io thread</a></li>
			</ul>
		</div>
	</div>
	<select id="opponent">
		<option value="game">Game dealer AI</option>
		<option value="perfect">Perfect opponent</option>
	</select>
</div>

<!--
<div id="game">
	<div id="flip" title="Click here to flip the board">⇕</div>
	<div id="reset" title="Click here to reset the board">↻</div>
	<div id="status-badinput">Please fix&nbsp;<span class="error">errors</span></div>
	<div id="status-loading">Loading...</div>
	<div id="status-error">Error</div>
	<div id="help"><div>?</div></div>
</div>
-->

<link rel="stylesheet" href="style.css?<?php echo(filemtime("style.css")) ?>">
<script src="script.js?<?php echo(filemtime("script.js")) ?>"></script>

packing.d

import std.algorithm.searching;
import std.algorithm.sorting;
import std.file;
import std.parallelism;
import std.range;
import std.typecons;

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

import game;

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

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

alias PackedShellCount = WithMax!(ubyte, 4);

alias PackedItem = ubyte;
enum packedItemCard = 1 + enumLength!Item; // add 1 for "empty"
alias PackedItemsBase = ushort;
static immutable itemBinomials = BinomialCoefficientTable!(PackedItemsBase, packedItemCard + maxItems, maxItems).generate();
alias ItemCNS = CNS!(PackedItemsBase, PackedItem, maxItems, packedItemCard, /*lexicographic:*/false, /*multiset:*/true, itemBinomials);
enum packedItemsCard = 1287; // == multisetCoefficient(packedItemCard, maxItems) == ItemCNS.packedCard
alias PackedItems = WithMax!(PackedItemsBase, packedItemsCard - 1);

alias PackedHealth = WithMax!(ubyte, 3); // min == 1 !

enum PackedHandcuffState : ubyte { none, otherWillSkip, otherWillBreak }
immutable HandcuffState[2][enumLength!PackedHandcuffState] packedHandcuffStates = [
	/* [current, other] */
	[HandcuffState.none, HandcuffState.none],
	[HandcuffState.none, HandcuffState.willSkip],
	[HandcuffState.none, HandcuffState.willBreak],
];

enum PackedNextShell : ubyte { unknown, blank, live }
immutable Nullable!ShellType[enumLength!PackedNextShell] packedNextShell = [
	Nullable!ShellType.init,
	ShellType.blank.nullable,
	ShellType.live.nullable,
];

struct PrePackedGame
{
	Character currentTurn;
	PackedShellCount[enumLength!ShellType] shells;

	// (we could save 226491/1679616 (~13%) if we make >2 cigarette packs unrepresentable...)
	PackedItems[enumLength!Character] items;
	PackedHealth[enumLength!Character] health;
	PackedHandcuffState handcuffs;
	PackedNextShell nextShell;
	bool shotgunSawedOff;

	static PackedItems packItems(byte[enumLength!Item] items) nothrow @nogc
	{
		PackedItem[maxItems] packedItems;
		size_t i = maxItems;
		foreach_reverse (Item itemType; Item.init .. enumLength!Item)
			foreach (j; 0 .. items[itemType])
				packedItems[--i] = cast(ubyte)(1 + itemType);
		packedItems[0 .. i] = 0;
		PackedItems result = ItemCNS.pack(packedItems);
		return result;
	}

	static byte[enumLength!Item] unpackItems(PackedItems p) nothrow @nogc
	in (p < packedItemsCard)
	{
		PackedItem[maxItems] packedItems = ItemCNS.unpack(p);
		byte[enumLength!Item] result;
		foreach (packedItem; packedItems)
			if (packedItem > 0)
				result[cast(Item)(packedItem - 1)]++;
		return result;
	}

	this(Game game) nothrow @nogc
	{
		this.currentTurn = game.currentTurn;
		foreach (i, value; game.shells) this.shells[i] = value;
		foreach (i, value; game.items) this.items[i] = packItems(value);
		foreach (i, value; game.health) this.health[i] = cast(ubyte)(value - 1);
		this.handcuffs = cast(PackedHandcuffState)packedHandcuffStates.indexOf([
			game.handcuffs[game.currentTurn      ],
			game.handcuffs[game.currentTurn.other]
		].staticArray);
		this.nextShell = cast(PackedNextShell)packedNextShell.indexOf(game.nextShell);
		this.shotgunSawedOff = game.shotgunSawedOff;
	}

	Game unpack() nothrow @nogc
	{
		Game game;
		game.currentTurn = this.currentTurn;
		foreach (i, value; this.shells) game.shells[i] = value;
		foreach (i, value; this.items) game.items[i] = unpackItems(value);
		foreach (i, value; this.health) game.health[i] = cast(ubyte)(value + 1);
		game.handcuffs[game.currentTurn      ] = packedHandcuffStates[this.handcuffs][0];
		game.handcuffs[game.currentTurn.other] = packedHandcuffStates[this.handcuffs][1];
		game.nextShell = packedNextShell[this.nextShell];
		game.shotgunSawedOff = this.shotgunSawedOff;
		return game;
	}
}

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

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

static assert(GameSerializer.minValue == 0);
immutable PackedGame packedGameCard = GameSerializer.cardinality;

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


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

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

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

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

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

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

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

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

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

remotegraph.d

import std.algorithm.sorting;
import std.conv;
import std.exception;
import std.file;
import std.path;

import ae.net.asockets;
import ae.net.http.client;
import ae.utils.aa;
import ae.utils.array;
import ae.sys.dataset;

import expand : Opponent, scoreIndeterminate;
import graph : scoreFileName, PackedScore, packScore;
import packing : PackedGame;

final class RemoteScores
{
private:
	PackedScore[PackedGame] resolved;
	HashSet!PackedGame todo;
	string url;

public:
	this(Opponent opponent)
	{
		url = "~/.config/buckshot-roulette-data".expandTilde().readText()
			~ scoreFileName(opponent).baseName;
	}

	PackedScore opIndex(PackedGame game)
	{
		if (auto p_score = game in resolved)
			return *p_score;
		todo.add(game);
		return scoreIndeterminate.packScore; // placeholder value
	}

	// Returns true if resolution succeeded entirely;
	// false, if a rerun is needed.
	bool resolve()
	{
		if (todo.empty)
			return true;

		auto games = todo.keys.sort.release;
		todo = null;

		auto client = new HttpsClient;
		client.keepAlive = true;
		client.pipelining = true;
		client.agent = null;
		client.handleResponse = (HttpResponse response, string disconnectReason) {
			enforce(response, disconnectReason);
			enforce(response.data.bytes.length == PackedScore.sizeof, "Bad payload size");
			PackedScore score;
			response.data.copyTo(score.asSlice.asBytes);
			resolved.addNew(games.shift(), score).enforce();
			if (!games.length)
				client.disconnect();
		};
		foreach (game; games)
		{
			auto request = new HttpRequest(url);
			request.headers["Range"] = "bytes=" ~ text(game * PackedScore.sizeof) ~ "-" ~ text(game * PackedScore.sizeof + PackedScore.sizeof - 1);
			client.request(request);
		}

		socketManager.loop();

		assert(!games.length);

		return false;
	}
}

// Debug helper (assert/invariant guard)
bool scoresAreFinal(Scores)(Scores scores)
{
	static if (is(Scores == RemoteScores))
		return scores.todo.byKey.empty;
	else
		return true;
}

script.js

const defaultGame = {
	currentTurn: 'player',
	shells: ['live', 'live', 'blank', null, null, null, null, null],
	items: [
		[null, null, null, null, null, null, null, null],
		[null, null, null, null, null, null, null, null]
	],
	nextShell: null,
	health: [2, 2],
	handcuffs: [null, null],
	shotgunSawedOff: false,
};

let currentGame = copyGame(defaultGame);
let showGameFuncs = [];
let resetGameFuncs = [];

function showGame(game) {
	document.querySelectorAll('.value').forEach(e => e.remove());
	document.querySelectorAll('.error').forEach(e => e.style.removeProperty('fill'));
	document.body.classList.toggle('packed-game', typeof game === 'string');
	if (typeof game === 'string')
		document.getElementById('packed-game').textContent = 'Game #' + game;
	else
		for (let func of showGameFuncs)
			func(game);
}

function copyGame(game) { return JSON.parse(JSON.stringify(game)); }

function flipBoard() {
	let game = copyGame(currentGame);
	game.currentTurn = game.currentTurn == 'player' ? 'dealer' : 'player';
	game.items.reverse();
	game.items[0].reverse();
	game.items[1].reverse();
	game.health.reverse();
	game.handcuffs.reverse();
	currentGame = game;
}

function resetBoard() {
	for (let func of resetGameFuncs)
		func(currentGame);
}

const winPercentFormatter = new Intl.NumberFormat('en-US', {
  minimumFractionDigits: 2,
  maximumFractionDigits: 2,
  style: 'percent'
});
const choiceProbabilityFormatter = new Intl.NumberFormat('en-US', {
  maximumFractionDigits: 0,
  style: 'percent'
});

var choiceCounter = 0;

function node(tagName, attributes, children) {
	let e = document.createElement(tagName);
	if (typeof attributes !== 'undefined')
		for (let name in attributes)
			e.setAttribute(name, attributes[name]);
	if (typeof children !== 'undefined') {
		if (typeof children === 'string')
			e.textContent = children;
		else {
			if (!Array.isArray(children))
				children = [children];
			for (let child of children) {
				if (typeof child === 'string')
					child = document.createTextNode(child);
				e.appendChild(child);
			}
		}
	}
	return e;
}

function addAnalysis(problem, data) {
	const origProblem = problem;
	const explorerHeader = document.getElementById('explorer-header');
	while (explorerHeader.nextSibling)
		explorerHeader.nextSibling.remove();

	function addEvent(icon, text, winPercent) {
		const tr = node('TR', {}, [
			node('TD', {}, icon),
			node('TD', {}, text),
			node('TD', {}, winPercent === undefined || winPercent === null
				 ? undefined
				 : winPercentFormatter.format(winPercent)
			)
		]);
		explorerHeader.parentElement.appendChild(tr);
		return tr;
	}

	function gameLink(o) {
		const link = node('A', {href: '#' + o.packedGame + '/' + problem.opponent}, 'Game #' + o.packedGame);
		link.addEventListener('click', function(e) {
			e.preventDefault();
			document.getElementById('explorer-page').scrollTo({ top: 0, behavior: 'smooth' });

			currentGame = copyGame(o.game);
			handleGameEdit(true);
		});
		return link;
	}

	if ('error' in data) {
		addEvent('💥', 'Fatal error: ' + data.error);
		document.getElementById('summary').replaceChildren(node('DIV', {}, [node('B', {}, 'Summary:'), ' ', 'Error, please see below.']));
		return;
	}
	if ('validationError' in data) {
		addEvent('💥', 'Invalid game: ' + data.validationError.message);
		for (let id of data.validationError.ids) {
			let e = document.getElementById('slot-' + id);
			e.classList.add('error');
			e.style.fill = '#faa';
		}
		document.getElementById('summary').replaceChildren(node('DIV', {}, [node('B', {}, 'Summary:'), ' ', 'Error, please see below.']));
		return;
	}

	for (let event of data.events) {
		if ('message' in event)
			addEvent('ℹ️', event.message);
		else
		if ('start' in event)
			addEvent('🚀', ['Analyzing ', gameLink(data), '.'], event.start);
		else
		if ('choice' in event) {
			choiceCounter++;
			let icon =
				event.choice.mode == 'best' ? '🤔' :
				event.choice.mode == 'worst' ? '🖥️' :
				event.choice.mode == 'random' ? '🎲' :
				event.choice.mode == 'randomWithDuplicates' ? '🎲' :
				event.choice.mode == 'unknown' ? '❓' :
				event.choice.mode == 'first' ? '❓' :
				'';
			addEvent(icon,
					 event.choice.description,
					 event.choice.score);
			for (let i = 0; i < event.choice.options.length; i++) {
				let option = event.choice.options[i];
				let description = option.description;
				if ('probability' in option)
					description = '[' + choiceProbabilityFormatter.format(option.probability) + '] ' + description;
				let radio = node('INPUT', {
					type: 'radio',
					name: 'choice-' + choiceCounter,
					id: 'choice-' + choiceCounter + '-' + i,
					value: i
				});
				if ('selectedOptionIndex' in event.choice && i == event.choice.selectedOptionIndex)
					radio.checked = 'checked';
				let label = node('LABEL', { for: radio.id }, [
					radio,
					description,
				]);
				radio.addEventListener('change', function() {
					const problem = {
						opponent: origProblem.opponent,
						game: data.game,
						decisions: option.decisions,
					};
					queryProblem(problem);
				});
				addEvent('➡️', label, option.outcome);
			}
		}
		else
		if ('recursion' in event) {
			addEvent('📍', ['Checkpoint: ', gameLink(event.recursion), '.'], event.recursion.score);
		}
		else
		if ('gameOver' in event) {
			addEvent(event.gameOver ? '✌️' : '💀', 'Game over.', event.gameOver ? 1 : 0);
		}
	}

	document.getElementById('summary').replaceChildren(node(
		'DIV', {}, [
			node('B', {}, 'Summary:'),
			' ',
		].concat((function() {
			if (data.events.length < 2 || !('start' in data.events[0]))
				return ['Failed to summarize results (unrecognized events).'];
			if ('choice' in data.events[1] && data.events[1].choice.mode === 'best') {
				let bestScore = data.events[1].choice.score;
				let bestOptions = [];
				for (let option of data.events[1].choice.options)
					if (option.outcome === bestScore)
						bestOptions.push(option);
				if (!bestOptions.length)
					return ['Failed to summarize results (no options).'];
				if (bestOptions.length == data.events[1].choice.options.length)
					return [
						"It's your turn, however, at this point, your choice ", node('B', {}, "does not matter"), ". ",
						"No matter what you do now, you have a ", node('B', {}, winPercentFormatter.format(bestScore)), " chance to win."
					];
				else {
					const interleave = (arr, thing) => [].concat(...arr.map(n => [n, thing])).slice(0, -1);
					return [
						"It's your turn. For the best outcome (", node('B', {}, winPercentFormatter.format(bestScore)), "), you should ",
					].concat(interleave(bestOptions.map(option => node('B', {}, option.description)), ' or ')).concat(["."]);
				}
			} else {
				return ["It is currently not your turn, but in this situation, you have a ", node('B', {}, winPercentFormatter.format(data.events[0].start)), " chance to win."];
			}
		})()),
	));
}

let stateVersion = 0;

function queryProblem(problem, delay, noSave) {
	let requestVersion = ++stateVersion;

	if (delay === undefined)
		delay = 0;
	
	currentGame = 'game' in problem ? copyGame(problem.game) : problem.packedGame;
	showGame(currentGame);

	document.getElementById('opponent').value = 'opponent' in problem ? problem.opponent : 'game';

	setTimeout(function() {
		if (requestVersion != stateVersion)
			return; // outdated
		if (dragging)
			return;

		// const state = save();
		// const hash = '#' + state;
		// if (hash != window.location.hash)
		// 	window.location = hash;  // Push state

		document.body.classList.toggle('loading', true);

		const url = window.location.hostname == 'cy.md'
			  ? 'https://home.cy.md/jsonapi/backshot-roulette-solver'
			  : 'websolver.php';
		fetch(url, {
			method: 'POST',
			headers: {
				'Content-Type': 'application/json',
			},
			body: JSON.stringify(problem),
		})
		.then((response) => response.ok ? response.json() : { error: "HTTP " + response.status })
		.then((data) => {
			if (requestVersion != stateVersion)
				return; // outdated
			if (dragging)
				return;
			if ('game' in data) {
				currentGame = copyGame(data.game);
				showGame(currentGame);
			}
			addAnalysis(problem, data);
			if ('game' in data && 'packedGame' in data) {
				problem.game = data.game;
				problem.packedGame = data.packedGame;
				if (noSave)
					window.history.replaceState(problem, '', '#' + serialize(problem));
				else
					window.history.pushState(problem, '', '#' + serialize(problem));
			}
			document.body.classList.toggle('loading', false);
		})
		.catch((error) => {
			if (requestVersion != stateVersion)
				return; // outdated
			console.log(error);
			document.body.classList.toggle('loading', false);
			// document.getElementById('status-error').style.display = 'flex';
			document.getElementById('summary').textContent = 'Error: ' + error;
		});
	}, delay);
}

function serialize(problem) {
	let result = problem.packedGame + '/' + problem.opponent;
	if ('decisions' in problem)
		result += '/' + problem.decisions.map(n => n.toString()).join(',');
	return result;
}

function deserialize(hash) {
	let parts = hash.split('/');
	let result = {};
	if (parts.length > 0)
		result.packedGame = parts[0];
	if (parts.length > 1)
		result.opponent = parts[1];
	else
		result.opponent = 'game';
	if (parts.length > 2)
		result.decisions = parts[2].split(',').map(n => parseInt(n));
	return result;
}

window.addEventListener('popstate', function(e) {
	let problem;
	if (e.state !== null)
		problem = e.state;
	else if (window.location.hash.length > 1)
		problem = deserialize(window.location.hash.substr(1));
	else
		return;
	loadProblem(problem);
});

// Replaces the current history state. Use after navigation.
function loadProblem(problem) {
	queryProblem(problem, 0, true);
}

// Use this for interactive edits. It creates a new problem, with no decisions.
function handleGameEdit(now) {
	// for (const id of ['status-badinput', 'status-loading', 'status-nodie', 'status-error', 'result-0', 'result-1', 'result-2', 'opp-move-0', 'opp-move-1', 'opp-move-2'])
	// 	document.getElementById(id).style.display = 'none';

	const problem = {
		opponent: document.getElementById('opponent').value,
		[typeof currentGame === 'string' ? 'packedGame' : 'game']: currentGame
	};
	queryProblem(problem, now ? 0 : 500);
}


// Note: The HTML drag and drop API (dragstart / dragover / drop) does not work on SVG elements.

var dragging = false;
var lastDropTarget = null;

function makeDraggable(node, data, handleFeedback) {
	function getDropTarget(e) {
		for (let target of document.elementsFromPoint(e.clientX, e.clientY)) {
			// console.log('CHECKING IF CAN DROP OVER ', target);

			if ('myIsDroppable' in target && target.myIsDroppable(data))
				return target;
		}
		// console.log('CANNOT DROP OVER ANYTHING');
		return null;
	}

	let primed = false; // per-node
	node.addEventListener('pointerdown', e => {
		e.preventDefault();
		primed = true;
	});
	node.addEventListener('pointermove', e => {
		e.preventDefault();
		if (primed && !dragging && e.buttons == 1) {
			// console.log('DRAG START');
			primed = false;
			dragging = true;
			node.setPointerCapture(e.pointerId);
			handleFeedback(true);
		}
		if (dragging) {
			// console.log('DRAGGING OVER ', document.elementsFromPoint(e.clientX, e.clientY));
			let target = getDropTarget(e);
			if (target !== lastDropTarget) {
				if (lastDropTarget)
					lastDropTarget.myHandleFeedback(false);
				if (target)
					target.myHandleFeedback(true);
				lastDropTarget = target;
			}
		}
	});
	node.addEventListener('pointerup', e => {
		e.preventDefault();
		primed = false;
		if (dragging) {
			// console.log('DRAGGING END');
			node.releasePointerCapture(e.pointerId);
			e.stopImmediatePropagation();
			if (lastDropTarget)
				lastDropTarget.myHandleFeedback(false);
			handleFeedback(false);
			setTimeout(() => {
				dragging = false;
			}, 0);

			let target = getDropTarget(e);
			if (target)
				target.myHandleDropped(data);
		}
	});
}

function makeDropTarget(slotNode, isDroppable, handleDropped, handleFeedback) {
	slotNode.myIsDroppable = isDroppable;
	slotNode.myHandleDropped = handleDropped;
	slotNode.myHandleFeedback = handleFeedback;
}


document.addEventListener('DOMContentLoaded', function() {
	let dragged = null;

	function addControl(type, slot, path, values, valueIDs) {
		let slotID = 'slot-' + type + (slot !== null ? '-' + slot : '');
		let slotNode = document.getElementById(slotID);
		slotNode.style.cursor = 'pointer';

		function getValue(game) {
			let v = game;
			for (let step of path)
				v = v[step];
			return v;
		}
		function setValue(game, value) {
			let v = game;
			for (let step of path.slice(0, -1))
				v = v[step];
			v[path[path.length-1]] = value;
		}

		function cycleValue(game, indexUpdateFun) {
			let oldValue = getValue(game);
			let oldValueIndex = values.indexOf(oldValue);
			let newValueIndex = indexUpdateFun(oldValueIndex);
			newValueIndex = (newValueIndex + values.length) % values.length;
			let newValue = values[newValueIndex];
			setValue(game, newValue);

			handleGameEdit();
		}

		slotNode.addEventListener('click', function(event) {
			if (!dragging && event.button == 0) {
				cycleValue(currentGame, index => index + 1);
				event.preventDefault();
			}
		});
		slotNode.addEventListener('wheel', function(event) {
			cycleValue(currentGame, index => index + Math.sign(event.deltaX + event.deltaY));
			event.preventDefault();
		});
		slotNode.addEventListener('contextmenu', function(event) {
			cycleValue(currentGame, index => 0);
			event.preventDefault();
		});

		const bg = slotNode.querySelector('.bg');
		makeDropTarget(
			bg,
			dragged => dragged.type === type && dragged.slot !== slot,
			dragged => {
				let v0 = getValue(currentGame);
				let v1 = dragged.getValue(currentGame);

				setValue(currentGame, v1);
				dragged.setValue(currentGame, v0);

				handleGameEdit();
			},
			isTarget => bg.classList.toggle('drop-target', isTarget),
		);

		showGameFuncs.push((game) => {
			let value = getValue(game);
			let valueIndex = values.indexOf(value);
			if (typeof valueIDs === 'function')
				valueIDs(value);
			else {
				let valueID = valueIDs[valueIndex];
				if (valueID !== null) {
					valueID = type + '-' + valueID;

					let valueNode = document.createElementNS("http://www.w3.org/2000/svg", 'use');
					valueNode.classList.add('value');
					valueNode.setAttributeNS("http://www.w3.org/1999/xlink", 'href', '#' + valueID);
					slotNode.appendChild(valueNode);

					makeDraggable(
						valueNode,
						{type, slot, getValue, setValue},
						isDragged => {
							valueNode.classList.toggle('dragged', isDragged);
							// console.log(isDragged, valueNode);
						},
					);
				}
			}
		});

		resetGameFuncs.push((game) => {
			cycleValue(game, index => 0);
		});
	}
	addControl('handle', null, ['currentTurn'], ['player', 'dealer'], (currentTurn) => {
		let e = document.getElementById('board');
		e.classList.toggle('dealer-turn', currentTurn === 'dealer');
	});
	for (let i = 0; i < defaultGame.shells.length; i++)
		addControl('shell', i, ['shells', i], [null, 'blank', 'live'], [null, 'blank', 'live']);
	addControl('shell', 'next', ['nextShell'], [null, 'blank', 'live'], ['unknown', 'blank', 'live']);
	for (let c = 0; c < defaultGame.items.length; c++)
		for (let i = 0; i < defaultGame.items[c].length; i++)
			addControl('item', c + '-' + i, ['items', c, i],
					   [null, 'magnifyingGlass', 'handcuffs', 'beer', 'cigarettePack', 'handSaw'],
					   [null, 'magnifyingGlass', 'handcuffs', 'beer', 'cigarettePack', 'handSaw']);
	for (let c = 0; c < defaultGame.health.length; c++)
		addControl('health', c, ['health', c], [4, 3, 2, 1], ['4', '3', '2', '1']);
	for (let c = 0; c < defaultGame.handcuffs.length; c++)
		addControl('handcuffs', c, ['handcuffs', c],
				   [null, 'willSkip', 'willBreak'],
				   [null, 'willSkip', 'willBreak']);
	addControl('barrel', null, ['shotgunSawedOff'], [false, true], [null, 'cutoff']);

	document.getElementById('button-flip').addEventListener('click', function(e) {
		e.preventDefault();
		flipBoard();
		handleGameEdit(true);
	});

	document.getElementById('button-reset').addEventListener('click', function(e) {
		e.preventDefault();
		resetBoard();
		handleGameEdit(true);
	});

	document.getElementById('opponent').addEventListener('change', function(e) {
		e.preventDefault();
		handleGameEdit(true);
	});

	let problem = null;
	if (window.location.hash.length > 1) {
		try {
			problem = deserialize(window.location.hash.substr(1));
		} catch (e) {
			console.log(e);
		}
	}
	if (!problem)
		problem = {
			game: defaultGame,
			opponent: 'game',
		};
	loadProblem(problem);

	const page = document.getElementById('page');
	const pageStyle = window.getComputedStyle(page);
// 	const numUIColumns = pageStyle.gridTemplateColumns.split(' ').length;
// 	const numUIRows = pageStyle.gridTemplateRows.split(' ').length;  // same as aspect-ratio / #page grid-template
	const haveAspectRatio = 'aspectRatio' in pageStyle;

	function updateSize() {
		// // Work around no support of aspect-ratio CSS property
		// // in Steam's in-page browser
		// if (!haveAspectRatio) {
		// 	const unitSize = Math.min(
		// 		document.documentElement.clientWidth / numUIColumns,
		// 		document.documentElement.clientHeight / numUIRows
		// 	);
		// 	page.style.width = (unitSize * numUIColumns) + 'px';
		// 	page.style.height = (unitSize * numUIRows) + 'px';
		// }

		// Make it so that 2em == one grid tile.
		// (Maybe one day this will be doable in CSS...)
		// page.style.fontSize = (page.clientWidth / 2 / numUIRows) + 'px';
		page.style.fontSize = (page.clientWidth / 48) + 'px';

		window.requestAnimationFrame(updateSize);
	}
	updateSize();

	var helpVisible = false;
	document.getElementById('button-help').addEventListener('click', function(e) {
		e.preventDefault();
		helpVisible = !helpVisible;
		document.body.classList.toggle('help-visible', helpVisible);
		document.querySelector('#button-help text').textContent = helpVisible ? '❌' : 'ℹ️';
		document.getElementById('board').classList.remove('help-nag');
		window.localStorage.setItem('buckshot-roulette-seen-help', '');
	});
	if (window.localStorage.getItem('buckshot-roulette-seen-help') === null)
		document.getElementById('board').classList.add('help-nag');
});

search_shootself.d

import std.parallelism;
import std.range;
import std.stdio;

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

import expand;
import graph;
import game;
import packing;

enum opponent = Opponent.game;

void main()
{
	auto scoreData = mapFile(scoreFileName(opponent), MmMode.read);
	auto scores = scoreData.asDataOf!PackedScore.unsafeContents;

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

		Score recurse(const ref Game game) nothrow @nogc
		{
			auto packedGame = game.packGame();
			return scores[packedGame].unpackScore;
		}

		alias gameOver = graphGameOver;

		bool topLevel = true;
		Score[enumLength!Move] moveScores;

		alias GetScore(T) = Score delegate(T) nothrow @nogc;
		Score choice(ChoiceMode mode, T)(
			scope string delegate() description,
			scope GetScore!T getScore,
			scope string delegate(T) getDescription,
			scope const(T)[] items...
		) {
			if (topLevel)
			{
				static if (mode == ChoiceMode.best && is(T == Move))
				{
					assert(items.length == enumLength!Move);

					{
						topLevel = false; scope(exit) topLevel = true;
						foreach (move; items)
							moveScores[move] = getScore(move);
					}

					return 0; // Result unused
				}
				else
					assert(false, "Expected the first choice to be a move choice");
			}
			else
			{
				alias gc = graphChoice!GetScore;
				return gc!(mode, T)(
					description,
					getScore,
					getDescription,
					items,
				);
			}
		}
	}

	PackedGame numDone;
	Score bestDelta = 0;
	foreach (packedGame; packedGameCard.iota.parallel)
	{
		enum progressPeriod = 0x1000000;
		if (packedGame % progressPeriod == 0)
			synchronized
			{
				numDone += progressPeriod;
				stderr.write(100 * numDone / packedGameCard, "%\r"); stderr.flush();
			}

		auto game = packedGame.unpackGame();
		if (game.currentTurn != Character.player)
			continue;
		if (game.totalShells == 0)
			continue;
		if (game.items[Character.dealer][Item.cigarettePack] > 2)
			continue;

		// Filter:
		if (game.totalItems(Character.player))
			continue;
		if (!game.nextShell.isNull)
			continue;

		auto driver = Driver();
		expand.expand(game, &driver, opponent);
		auto delta = driver.moveScores[Move.shootSelf] - driver.moveScores[Move.shootOther];
		if (delta > 0)
		{
			synchronized
			{
				if (delta >= bestDelta)
				{
					writefln("Game #%d: Shooting self is better than shooting opponent by %f%%",
						packedGame, (driver.moveScores[Move.shootSelf] - driver.moveScores[Move.shootOther]) * 100);
					bestDelta = delta;
				}
			}
		}
	}
}

style.css

@import url('https://fonts.googleapis.com/css2?family=Noto+Color+Emoji&display=swap');

* {
	box-sizing: border-box;
}

body {
	margin: 0;
	padding: 0;

	width: 100vw;
	height: 100vh;
	position: relative;
	font-family: sans-serif;

	background-color: #444;
	color: #fff;
}

#page {
	max-width: 100vw;
	max-height: 100vh;
	aspect-ratio: 30/18;
	margin: 0 auto;

	display: grid;
	grid-template: 1fr / 1fr 1fr;
}

#page > * {
	max-height: 100vh;
}

#board {
	align-self: center;
	justify-self: end;
	grid-row: 1;
	grid-column: 1;
}
#packed-game {
	align-self: center;
	justify-self: center;
	grid-row: 1;
	grid-column: 1;
	display: none;
}
body.packed-game #board { display: none; }
body.packed-game #packed-game { display: block; }

#explorer-page {
	grid-row: 1;
	grid-column: 2;
	align-self: start;
	overflow-y: auto;
}

#explorer-page > table {
	margin: 1em 0;
	background-color: white;
	color: black;
	border-collapse: collapse;
	table-layout: fixed;
	width: 100%;
}
#explorer-page > table,
#explorer-page > table > tbody > tr > th,
#explorer-page > table > tbody > tr > td {
	border: 0.21em solid black;
}
#explorer > tbody > tr > th,
#explorer > tbody > tr > td {
	min-width: 2em;
	height: 2em;
	padding: 0.25em;
}
#explorer > tbody > tr > th:nth-child(1) { width: 2em; }
#explorer > tbody > tr > th:nth-child(3) { width: 4.5em; }
#explorer > tbody > tr > td:nth-child(1) { text-align: center; font-family: "Noto Color Emoji"; }
#explorer > tbody > tr > td:nth-child(3) { text-align: right; }

#summary {
	padding: 0.75em 1em;
}

#opponent {
	grid-row: 1;
	grid-column: 1;
	align-self: start;
	position: relative;
	left: 13em;
	top: 0.8em;
	width: 9em;
	border: 0.21em solid black;
}

input, select {
	font-size: inherit;
}

input[type="radio"] {
	margin: 0 0.5em;
    width: 0.9em;
    height: 0.9em;
}

#help-page {
	grid-row: 1;
	grid-column: 2;

	display: none;
	position: relative;
}
.help-visible #help-page { display: block; }
.help-visible #explorer-page { display: none; }
#help-page > div {
	color: black;
	background-color: white;
	border: 0.21em solid black;
	padding: 1em 2em;
	font-size: 75%;
	text-align: justify;

	/* margin: 1em; */
	position: absolute;
	top: 1em; left: 0; bottom: 1em; right: 0;
	overflow: auto;
}
.emoji { font-family: "Noto Color Emoji"; }

ul, ol {
	/* default is 40px which is not responsive: */
	padding-inline-start: 2em;
}
h3 { text-align: center; }

websolver.d

import std.algorithm.comparison;
import std.algorithm.iteration;
import std.algorithm.mutation;
import std.algorithm.searching;
import std.conv;
import std.exception;
import std.file;
import std.math.algebraic;
import std.math.traits;
import std.path;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

import ae.net.ssl.openssl;
import ae.sys.datamm;
import ae.sys.file;
import ae.utils.array;
import ae.utils.json;
import ae.utils.meta;
import ae.utils.text;

import game;
import expand;
import graph;
import packing;
import remotegraph;

mixin SSLUseLib;

class JSGameError : Exception
{
	string[] badIDs;
	this(string msg, string[] badIDs)
	{
		this.badIDs = badIDs;
		super(msg);
	}
}

struct JSGame
{
	Character currentTurn;
	Nullable!ShellType[maxShells] shells;
	Nullable!ShellType nextShell; // includes a shell from `shells`, unlike `Game`
	Nullable!Item[maxItems][enumLength!Character] items;
	ubyte[enumLength!Character] health = [1, 1];
	Nullable!HandcuffState[enumLength!Character] handcuffs; // `null` <=> `HandcuffState.none`
	bool shotgunSawedOff;

	/// Convert `Game` to `JSGame`, trying to not move
	/// things around too much (compared to `reference`).
	this(const Game game, JSGame reference)
	{
		this = reference;

		this.nextShell = game.nextShell;
		foreach (shellType; ShellType.init .. enumLength!ShellType)
			while (this.toGame(false).shells[shellType] > game.shells[shellType])
				this.shells[this.shells[].lastIndexOf(shellType.nullable)] = Nullable!ShellType.init;
		foreach (shellType; ShellType.init .. enumLength!ShellType)
			while (this.toGame(false).shells[shellType] < game.shells[shellType])
				this.shells[this.shells[].indexOf(Nullable!ShellType.init)] = shellType.nullable;

		foreach (character; Character.init .. enumLength!Character)
		{
			foreach (item; Item.init .. enumLength!Item)
				while (this.toGame(false).items[character][item] > game.items[character][item])
					this.items[character][this.items[character][].lastIndexOf(item.nullable)] = Nullable!Item.init;
			foreach (item; Item.init .. enumLength!Item)
				while (this.toGame(false).items[character][item] < game.items[character][item])
					this.items[character][this.items[character][].indexOf(Nullable!Item.init)] = item.nullable;
		}

		foreach (character; Character.init .. enumLength!Character)
			this.health[character] = game.health[character];

		this.currentTurn = game.currentTurn;
		foreach (character; Character.init .. enumLength!Character)
			if (game.handcuffs[character] == HandcuffState.none)
				this.handcuffs[character] = Nullable!HandcuffState.init;
			else
				this.handcuffs[character] = game.handcuffs[character].HandcuffState.nullable;

		this.shotgunSawedOff = game.shotgunSawedOff;

		assert(this.toGame(false) == game);
	}

	Game toGame(bool strict = true) const
	{
		Game game;

		game.currentTurn = this.currentTurn;

		foreach (shell; this.shells)
			if (!shell.isNull)
				game.shells[shell.get()]++;
		game.nextShell = this.nextShell;
		if (!this.nextShell.isNull)
		{
			auto shellType = this.nextShell.get();
			if (strict && !game.shells[shellType])
				throw new JSGameError("Shells / next shell discrepancy.",
					maxShells.iota
					.map!(shellIndex => "shell-" ~ text(shellIndex))
					.array
					~ ["shell-next"]
				);
			game.shells[shellType]--;
		}
		foreach (shellType; ShellType.init .. enumLength!ShellType)
			if (strict && game.shells[shellType] > maxShells / 2)
				throw new JSGameError("Cannot have that many shells of one type.",
					maxShells.iota
					.filter!(shellIndex => this.shells[shellIndex] == shellType.nullable)
					.map!(shellIndex => "shell-" ~ text(shellIndex))
					.array
				);
		foreach (character; Character.init .. enumLength!Character)
		{
			foreach (item; this.items[character])
				if (!item.isNull)
					game.items[character][item.get()]++;
			if (strict && game.items[character][Item.cigarettePack] > 2)
				throw new JSGameError("Cannot have that many cigarette packs.",
					maxItems.iota
					.filter!(itemIndex => this.items[character][itemIndex] == Item.cigarettePack.nullable)
					.map!(itemIndex => "item-" ~ text(ubyte(character)) ~ "-" ~ text(itemIndex))
					.array
				);
		}
		foreach (character; Character.init .. enumLength!Character)
		{
			enforce(this.health[character] > 0 && this.health[character] <= 4);
			game.health[character] = this.health[character];
		}
		foreach (character; Character.init .. enumLength!Character)
			game.handcuffs[character] = this.handcuffs[character].get(HandcuffState.none);
		if (strict && game.handcuffs[Character.player] && game.handcuffs[Character.dealer])
			throw new JSGameError("Only one character may be handcuffed at a time.",
				["handcuffs-0", "handcuffs-1"]
			);
		if (strict && game.handcuffs[game.currentTurn])
			throw new JSGameError("A handcuffed player cannot have the current turn.",
				["handcuffs-" ~ text(ubyte(game.currentTurn)), "handle"]
			);
		game.shotgunSawedOff = this.shotgunSawedOff;
		return game;
	}
}

/// Index into the `items` array passed to some `Driver.choice` call
alias ItemIndex = size_t;

/// Index into some `JSAnalysis.Event.Choice.options` array.
alias OptionIndex = size_t;

struct JSProblem
{
	Opponent opponent;

	Nullable!JSGame game;
	// -- or --
	string packedGame;

	ItemIndex[] decisions;
}

struct JSAnalysis
{
	JSGame game;
	@JSONOptional string packedGame;

	struct Event
	{
		@JSONOptional string message;

		@JSONOptional Nullable!Score start;

		struct Recursion
		{
			JSGame game;
			string packedGame;
			Score score;
		}
		@JSONOptional Recursion recursion;

		struct Choice
		{
			string description;
			ChoiceMode mode;
			struct Option
			{
				/// All decisions up to this point including this one, starting with `game`.
				/// Put this in `JSProblem.decisions`.
				ItemIndex[] decisions;

				string description;
				Score outcome;

				/// Present only for non-uniform random choice events.
				@JSONOptional Nullable!double probability;
			}
			Option[] options;
			Score score; // According to the algorithm - NOT according to `selectedOptionIndex`.
			// If analysis continues, this shows across which branch it does so.
			@JSONOptional Nullable!OptionIndex selectedOptionIndex; // This one is an index into `options`.
		}
		@JSONOptional Choice choice;

		@JSONOptional Nullable!bool gameOver;
	}
	Event[] events;

	struct ValidationError
	{
		string message;
		string[] ids;
	}
	@JSONOptional ValidationError validationError;
}

struct Driver(Scores)
{
	const(JSProblem)* problem;
	Scores scores;
	JSAnalysis* analysis;

	// When true, we are doing linear descent.
	// When false, we are doing a regular recursive depth-first
	// search in order to calculate a score (win probability).
	bool interactive = true;

	JSGame[] recursedGames;
	ItemIndex[] decisions; // Decisions made since the very start; index into items

	void log(scope string delegate() message)
	{
		if (!interactive)
			return;

		JSAnalysis.Event event;
		event.message = message();
		analysis.events ~= event;
	}

	Score run(const ref Game game)
	{
		auto packedGame = game.packGame();
		auto graphScore = scores[packedGame].unpackScore;
		assert(interactive);

		JSAnalysis.Event event;
		size_t eventIndex = analysis.events.length;
		analysis.events ~= event;

		auto score = expand.expand(game, &this, problem.opponent);
		analysis.events[eventIndex].start = score;

		if (abs(score.packScore.value - graphScore.packScore.value) > 0)
			stderr.writeln("Warning: Game #", packedGame, " recursed ", fpToString(score), " != graph ", fpToString(graphScore));

		return score;
	}

	Score recurse(const ref Game game)
	{
		auto packedGame = game.packGame();
		auto graphScore = scores[packedGame].unpackScore;
		if (!interactive)
			return graphScore;

		auto jsGame = JSGame(game, recursedGames[$-1]);
		recursedGames ~= jsGame;
		scope(exit) recursedGames = recursedGames[0 .. $-1];

		JSAnalysis.Event event;
		event.recursion = JSAnalysis.Event.Recursion(jsGame, game.packGame().to!string);
		size_t eventIndex = analysis.events.length;
		analysis.events ~= event;

		auto score = expand.expand(game, &this, problem.opponent);
		analysis.events[eventIndex].recursion.score = score;

		if (abs(score.packScore.value - graphScore.packScore.value) > 0)
			stderr.writeln("Warning: Game #", packedGame, " recursed ", fpToString(score), " != graph ", fpToString(graphScore));

		return score;
	}

	alias GetScore(T) = Score delegate(T);

	Score choice(ChoiceMode mode, T)(
		scope string delegate() description,
		scope Score delegate(T) getScore,
		scope string delegate(T) getDescription,
		scope const(T)[] items...
	) {
		if (!interactive)
		{
			alias gc = graphChoice!GetScore;
			return gc!(mode, T)(
				description,
				getScore,
				getDescription,
				items,
			);
		}

		// First, record the event.
		JSAnalysis.Event event;
		event.choice.description = description();
		event.choice.mode = mode;

		struct Option
		{
			T item;
			static if (mode == ChoiceMode.randomWeighted)
				@property auto weight() { return item.weight; }
			else
				enum size_t weight = 1;
			ItemIndex itemIndex;
			Score score;
		}

		auto options = new Option[items.length];
		foreach (i; 0 .. items.length)
			options[i] = Option(items[i], i);

		// Get scores
		foreach (ref option; options)
		{
			interactive = false; scope(exit) interactive = true;
			option.score = getScore(option.item);
		}

		// Filter out NaNs
		foreach_reverse (optionIndex, ref option; options)
			if (option.score.isNaN)
				options = options.remove(optionIndex);

		// Get total weight
		alias Weight = typeof(Option.init.weight);
		Weight totalWeight = 0;
		foreach (ref option; options)
			totalWeight += option.weight;

		auto includeProbabilities = mode == ChoiceMode.randomWeighted;

		foreach (ref option; options)
		{
			auto jsOption = JSAnalysis.Event.Choice.Option(
				decisions ~ option.itemIndex,
				getDescription(option.item),
				option.score,
			);
			if (includeProbabilities)
				jsOption.probability = 1.0 * option.weight / totalWeight;
			event.choice.options ~= jsOption;
		}

		// The option that's selected by default, if any.
		Nullable!OptionIndex selectedOptionIndex;
		// The resulting score. If selectedOptionIndex is non-null, it would be that option's score.
		Score score = {
			static if (mode == ChoiceMode.random || mode == ChoiceMode.randomWeighted)
			{
				Score sum = 0;
				foreach (ref option; options)
					sum += option.score * option.weight;
				return sum / totalWeight;
			}
			else static if (mode == ChoiceMode.best)
			{
				Score bestScore = -Score.max;
				foreach (OptionIndex optionIndex, ref option; options)
					if (option.score > bestScore)
					{
						bestScore = option.score;
						selectedOptionIndex = optionIndex;
					}
				assert(bestScore != -Score.max, "All choices are invalid");
				return bestScore;
			}
			else static if (mode == ChoiceMode.worst || mode == ChoiceMode.unknown)
			{
				Score worstScore = Score.max;
				foreach (OptionIndex optionIndex, ref option; options)
					if (option.score < worstScore)
					{
						worstScore = option.score;
						selectedOptionIndex = optionIndex;
					}
				assert(worstScore != Score.max, "All choices are invalid");
				return worstScore;
			}
			else static if (mode == ChoiceMode.first)
			{
				assert(options[0].itemIndex == 0);
				selectedOptionIndex = 0;
				return options[0].score;
			}
			else
				static assert(false);
		}();
		event.choice.score = score;

		if (selectedOptionIndex.isNull && options.length == 1)
			selectedOptionIndex = 0;

		if (decisions.length < problem.decisions.length)
		{
			// User's decision overrides what the algorithm would choose.
			auto itemIndex = problem.decisions[decisions.length];
			enforce(itemIndex < items.length, "Invalid choice index");
			auto optionIndex = options.countUntil!((ref option) => option.itemIndex == itemIndex);
			enforce(optionIndex >= 0, "Item is not an option");
			selectedOptionIndex = optionIndex;
		}

		event.choice.selectedOptionIndex = selectedOptionIndex;
		analysis.events ~= event;

		// Move forward when the graph expansion algorithm does so:
		if (!selectedOptionIndex.isNull)
		{
			auto itemIndex = options[selectedOptionIndex.get()].itemIndex;
			decisions ~= itemIndex; scope(exit) decisions = decisions[0 .. $-1];
			auto userChoiceScore = getScore(items[itemIndex]);
			// Discard user choice score (do not let scores bubble up).
			cast(void) userChoiceScore;
		}

		return score;
	}

	Score gameOver(bool playerWon)
	{
		if (!interactive)
			return graphGameOver(playerWon);

		JSAnalysis.Event event;
		event.gameOver = playerWon;
		analysis.events ~= event;

		return graphGameOver(playerWon);
	}
}

JSAnalysis analyze(Scores)(JSProblem problem, Scores scores)
{
	JSAnalysis analysis;
	try
	{

		JSGame jsGame = {
			if (!problem.game.isNull) return problem.game.get;
			if (problem.packedGame) return problem.packedGame.to!PackedGame.unpackGame().JSGame(JSGame.init);
			throw new Exception("No game");
		}();
		analysis.game = jsGame;

		Game game;
		if (problem.packedGame)
			game = problem.packedGame.to!PackedGame.unpackGame();
		else
			game = problem.game.get().toGame();
		analysis.packedGame = game.packGame().to!string;

		Driver!Scores driver;
		driver.problem = &problem;
		driver.scores = scores;
		driver.analysis = &analysis;
		driver.recursedGames = [jsGame];

		driver.run(game);
	}
	catch (JSGameError e)
		analysis.validationError = JSAnalysis.ValidationError(e.msg, e.badIDs);
	return analysis;
}

void main(string[] args)
{
	bool local = true;

	try
	{
		enforce(args.length == 1, "Bad usage");
		auto problem = readFile(stdin).assumeUTF.jsonParse!JSProblem;

		JSAnalysis analysis;
		if (local)
		{
			chdir(args[0].realPath().dirName());
			auto scoreData = mapFile(scoreFileName(problem.opponent), MmMode.read);
			auto scores = scoreData.asDataOf!PackedScore.unsafeContents;

			analysis = analyze(problem, scores);
		}
		else
		{
			auto scores = new RemoteScores(problem.opponent);
			do
				analysis = analyze(problem, scores);
			while (!scores.resolve());
		}

		stdout.writeln(analysis.toJson.replace("nan", "null"));
	}
	catch (Exception e)
	{
		struct ErrorReply { string error; }
		stdout.writeln(ErrorReply(e.msg).toJson);
		return;
	}
}

websolver.php

<?php

$descriptor_spec = [
    0 => ['pipe', 'r'],
    1 => ['pipe', 'w'],
];

$process = proc_open(array('./websolver'), $descriptor_spec, $pipes);

header('Content-Type: application/json');
if (is_resource($process)) {
    stream_copy_to_stream(fopen('php://input' , 'r'), $pipes[0]); fclose($pipes[0]);
    stream_copy_to_stream($pipes[1], fopen('php://output', 'w')); fclose($pipes[1]);
    proc_close($process);
} else {
    echo '{"error":"Failed to create process."}';
}