Introduction

I'm a big fan of videogames. I like small, well defined boxes where I can get
better at some task. I like measuring myself against my peers. As such, it's
probably no great surprise that I like speedrunning and randomizers.

For the unititiated, speedrunning is trying to beat some game as quickly as
possible. It's a popular way to play games with a thriving community. You can
see that in the fracturing of the community into niche genres. These people
don't use exploits, these people use exploits, but not exploits that allow them
to jump to a specific memory address, and so on.

My favorite flavor of speedrun is the randomizer. Speedrunning breaks down into
two major skills: memorization and execution. Execution is how well you can
drive the game, in terms of input timing, combat strategy, and so on.
Memorization is how much you know about the layout of the game. When should you
go to this location, what does it net you when you go there. As more people
speedrun a game, the number of competitive ways to complete the game dwindles
until there is only one acceptable route, and everything is execution.

Randomizers turn this on its head. They take the standard locations and enemies
of the game and mix them all up at random. In Legend of Zelda: A Link to the
Past randomizer, you might not get the sword as the first item. You might not
get it for tens of minutes.

This is neat, because it diminshes some of the power of memorization. It's also
neat because players expect to be able to complete the game independent of the
randomization. The ability to win any instance is something every randomizer
guarantees.It turns out that checking if a given instance of a randomizer is
winnable, or feasible, is an example of a classic problem in artificial
intelligence: planning.

Propositional Planning for Randomizers

We'll use Final Fantasy IV: Free Enterprise (FF4:FE) as our concrete example. In
FF4:FE, the goal is to find the crystal and defeat the final boss of the game,
Zeromus. In FF4:FE, all generated instances are technically winable. They may be
extremely difficult, but it is technically possible to win. There are two ways
to generate a winnable instance: guarantee that the instances you generate are
all winnable by construction, or generate a random instance and verify that at
least one solution to it exists. We're going to examine the latter approach.

The following is the simplest configuration of the randomizer:

  • 17 Key Items
  • 17 Locations Where They Appear
  • Initially start with two party members and one item

So, there are 17! possible configurations, or roughly 3.5 x 10^14 playable
configurations of the items in the game. It would be impossible to check each
instance individually, either by hand or with a program. Instead, we need a
method for solving an arbitrary instance of the game. This way we can generate a
configuration and check to see if it is winnable. Then we just iterate through
random instances until a solvable example is found to give to the player.

The most direct way to prove that an instance can be won is to find a sequence
of actions for winning the randomizer. I don't mean the actual controll inputs,
but rather a solution to a simplified representation of the randomized instance.
The ideal representaiton has a parsimonious way of representing the current
state of play of the game, a way of deducing the impact of actions on the state
of play, and a fast way of checking to see if the player has won the
abstraction. In short, planning with propositional logic is the perfect formalism.

Informally, a propositional planning problem is defined by the following:

  • A set of propositions describing all aspects of the world
    • For example, HaveCrystal, HaveHook, HaveTail
  • A set of states representing the configurations of the world
    • States are members of the powerset of propositions
    • Less formally, they represent any possible configuration of propositions
  • A set of actions describing what we can do
    • Formally, an action is a function from state to state
  • A set of goals describing when the game is won

Formally, a propositional planning problem is defined by the tuple < S, i, A, G > where:

  • The states S = ScriptP(P), where P is all propositions describing the world
  • The initial state i in S
  • A set of actions A s.t. each member of A is a function from s in S onto s' in S
  • G subset of S, the set of all states satisfying the goal

Formally, the we would like to find a sequence of actions in A which, starting
with i, produces some state g in G. Informally, we're looking for a plan that
carries us from the start of the game to a win. To see how we can do this, we'll

  • Look at the predicates needed to describe FF4:FE
  • Look at a generic description of the actions in the game
  • Solve a concrete instance to prove it is winable

Propositions

Starting with the predicates, there are 17 key items in the game. There are 17
corresponding locations where they can be found. We'll take a straightforward
approach and represent each of these as a boolean. Concretely, let's consider
the return to Castle Baron. To visit the Castle, the player must have found a
key to the baron sewers. The formalism we've chosen suggests two predicates
here, one for the key and one for having visited the castle to complete the boss
fight:

  • BaronKey
  • BaronFight

State Representation

Remember that states are elements of the powerset of all propositions. Reducing
the state of FF4:FE to propositional logic gives us some convenient
representational power. Specifically, we'll make a closed-world assumption:
everything not known to be true is false. We'll represent the states of play
according to their propositions in conjunctive normal form. Let's imagine a pair
of simple states.

The start of the game having received the Baron Key as our free item:

/\ BaronKey

The state of the game after beating the Baron Castle and winning the hook:

/\ BaronFight
/\ Hook

Actions

Actions are what let us move between states like the previous two. Actions are
defined by:

  • Preconditions - Those things which must be true for the action to happen
  • Add Effects - Things that the action makes true
  • Delete Effects - Things that the action makes false.

Again, consider storming the Baron castle. It's precondition is that we have the
key for the sewers leading from the city to the castle. It removes possession of
the key from our inventory. Finally, it marks that we've visited the location
and gives us some key item. More explicitly:

BaronFight Example

Preconditions

{ BaronKey, -BaronFight }

DeleteEffects

{ BaronKey }

AddEffects

{ BaronFight, Hook }

Combining Actions and States

Let's combine the two, the initial game state and the action, to see how we
arrive at the second fight. Our initial state is simply having the BaronKey,
since it was handed to us during the intor cut scene:

/\ BaronKey

We begin by considering whether or not the action is applicable. This is done by
looking to see if the preconditions of the action are consistent with the
current state. It turns out they are: We possess the Baron Key (BaronKey is
true), and we have not yet done the Baron castle fight (BaronFight is not true).

Now that we know the action is applicable, we apply it. That means removing the
delete effects, then adding the add effects. The progression looks like this:

/\ BaronKey

Nothing is true

/\ BaronFight
/\ Hook

The empty state in the middle represents the point between removing the delete
effects and adding the add effects. This isn't meaningful in this example, but
it is sometimes useful to have an action both delete and add a thing. Although
we write the states down in conjunctive normal form, sometimes it is useful to
think of them as sets of things which are known to be true. The equivalent
progression is:

{ BaronKey }
{}
{ BaronFight, Hook }

Goals

The goal of the game is to fight the final boss, Zeromus. They're far away on
the moon, and can only be defeated if the party has the crystal in their
possession. We can state the goal in one of two equivalent ways: either the goal
is a test, or predicate, that a state must satisfy or being a goal means that
the state must belong to a subset of all states defined by some test or
predicate. In our case, the following is true of all goal states: The party has
the crystal, and the party has either the pass or the dark crystal.

From a predicate view, Goal(s) is true if the proposition Crystal and one of DarkCrystal or Pass is present in s, formally:

goal_predicate

Why the Rigor?

The formality of these statements is confusing for many. Boolean algebra isn't
the first approach most of us take when writing a problem statement out.
However, that's because we're clever and can fill in gaps in a reasonable
problem statement. Computers aren't clever, nor are they reasonable. Computers
are the very embodiment of malicious compliance. If you want them to solve a
problem, you have to be very careful as to how you ask the question.

We've stated the problem of deciding the winability of a randomized RPG as an
enumeration over sets driven by set operations:

  • The initial state is a set.
  • The actions are functions from sets to sets
  • The goal test is set membership test

Computers are pretty great at set math. By performing the translation, we've
enabled the computer to help us answer a difficult problem. The real trick was
for a human to come in and recognize that the problem of deciding winability of
a randomized RPG could be restated as a propositional logic problem.

Forming the whole plan

Imagine we had the following instance, mapping the key events on the left with the key items rewarded on the right:

  • InitialItem -> BaronKey
  • AntlionFight -> LucaKey
  • FabulFight -> RatTail
  • OrdealFight -> Pan
  • BaronInnFight -> MagmaKey
  • BaronCastleFight -> Hook
  • EdwardTroia -> Spoon
  • MagneticCaveFight -> EarthCrystal
  • ZotFight -> Pass
  • DrLugae -> Pan
  • Bab-ilFight -> TowerKey
  • LucaFight -> LucaKey
  • SealedCaveFight -> DarkCrystal
  • SummonTownChest -> Crystal
  • YangsWife -> TwinHarp
  • YangsWifesPan -> SandRuby
  • RatTailTrade -> Package

There are a large number of plans that allow us to get all the way to a Zeromus
fight, which is enabled by having the crystal and one of the pass or the dark
crystal. Here are four:

  • BaronFight -> SummonTownChest -> LucaFight -> SealedCaveFight -> ZeromusFight
  • BaronInnFight -> SummonTownChest -> LucaFight -> SealedCaveFight -> ZeromusFight
  • BaronFight -> SummonTownChest -> YangsWife -> MagneticCaveFight -> ZotFight -> ZeromusFight
  • BaronInnFight -> SummonTownChest -> YangsWife -> MagneticCaveFight -> ZotFight -> ZeromusFight

Let's consider the first example, and look at how it progresses the states:

/\ BaronKey

/\ BaronFight
/\ Hook

/\ BaronFight
/\ SummonTownChest
/\ Hook
/\ Crystal

/\ BaronFight
/\ SummonTownChest
/\ LucaFight
/\ Hook
/\ Crystal
/\ LucaKey

/\ BaronFight
/\ SummonTownChest
/\ LucaFight
/\ SealedCaveFight
/\ Hook
/\ Crystal
/\ DarkCrystal

And in this final state, we have both the crystal and the dark crystal. Zeromus is reachable and the instance of the randomizer can be won.

Building the Action from a Template

Note that, up until now, we've talked about how to prove a specific instance of
the randomizer is solvable. That's not quite what we want to do. We want to be
able to prove an arbitrary instance of the randomizer is solvable, for any given instance.

To do that, we need to talk about how the actions for the planning problem are
generated. In the example we've been using, we know that we get the hook when
completing the baron fight. We know that for some specific instance. For all
instances, we know that a key item is awarded when the Baron fight is completed.
This suggests a template action that we fill in for a specific instance of the
randomizer, as follows

BaronFight Example

Preconditions

{ BaronKey, -BaronFight }

DeleteEffects

{ BaronKey }

AddEffects

{ BaronFight, SOME_ITEM }

If we define all of the possible actions in the game as templates, we can fill
in the correct values for the awarded item when we get ready to prove a given
instance is solvable.

Wrapping Up

Randomizers breathe a bunch of new life into decades old games. They're
challenging to play, and they're fun to race. One thing that every randomizer
has to do is provide winnable instances to players. There are a couple of ways
of guaranteeing that any given instance is solvable, and we've just looked at
one.

There are two particularly interesting threads to pull at from this interseciton
of randomizers and artificial intelligence: We could examine techniques for
guiding the player of the randomizer to the most effective routes. We could look
at a more formal model of randomizer domains and how they behave in open source
solvers.

We'll eventually consider both. For now, I hope you've found this installment of
"AI In The Wild" edifying. I hope you'll join me for the next installment, where
we will continue to investigate classic AI problems that crop up in our daily
lives.