Planning for Randomizers

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 diminishes 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 representation 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:

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 intersection 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.

You Might Also Like

• Identifying AI Opportunities: A Hypothetical Case Study
• (Machine) Learning By Doing
• A Brief Evaluation of Cloud ML Tools