MicroTales: Story Planning Benchmark Problems that Scale along Several Dimensions
Version 1.0

Stephen G. Ware and Molly Siler

2026-04-15

Motivation

Story planning is the challenge of generating a narrative that meets certain requirements on its structure and content. It is difficult because a story planner needs to look ahead and consider many possible stories before finding one that satisfies all of the solution criteria.

There has now been several decades of academic research on narrative planning (Young et al. 2013; Kybartas and Bidarra 2016). Each new research project tends to define one or a few new story planning problems, typically ones that highlight the storytelling features being studied by that project. In a previous effort (Ware and Farrell 2023), we collected several of these problems and put them into a common syntax to make it easier to test an algorithm on a variety of “naturally occurring” problems from several authors.

What we feel is missing, and what we are trying to provide with this project, is a single story domain that can generate a wide variety of storytelling problems that vary in size and difficulty. We are inspired by projects like the International Planning Competition (Taitler et al. 2024), AI Gymnasium (Côté et al. 2019), and TextWorld (Côté et al. 2019), but we find many of their problems do not capture the storytelling challenges we are interested in studying. We also hope that this project will help to make story planning problems more accessible to non-academic audiences.

This document describes MicroTales, a single storytelling domain based on very simple fantasy Computer Role Playing Games. Each problem, which we call a scenario, has:

We define each of these parts in detail. MicroTales scenarios are highly modular, with different elements becoming available only when certain extensions are enabled. For example, the Undead extension contains characters, items, locations, and actions related to ghosts. When the Undead extension is enabled, these elements can be used in a scenario.

Our definitions do not assume any particular implementation. We want it to be possible to implement MicroTales in everything from the Planning Domain Definition Language (Ghallab et al. 1998), used to define classical planning problems, to an AI Gymnasium environment (Towers et al. 2024), used to define a Markov Decision Process for reinforcement learning, to even non-digital implementations, like a board game.

Design Goals

Game-Like Storytelling Environment:

MicroTales is designed to imitate a simple game environment where a player controls one character and an experience manager (which might be a human game master or an algorithm) controls the other characters and the environment (Riedl and Bulitko 2013). One of the central challenges in this kind of environment is telling a good story while allowing the player significant agency to make meaningful choices. Problems like this are often solved interactively, meaning that new solutions are generated during play to adapt to unexpected player actions. This does not mean all implementations of MicroTales need to be interactive. You may find it helpful to generate scenarios that are solved only once; our goal is for them to reflect the kinds of problems that an experience manager would need to solve interactively. In other words, if an algorithm can solve a wide variety of MicroTales scenarios, it would probably make a good experience manager if it could be made to run interactively.

Event-Level Storytelling:

Stories can be generated at many levels of granularity. The smallest “atomic unit” of story content in MicroTales is an event, which typically has a subject, verb, and usually one or two objects. An event would correspond to roughly one sentence of a written story. Early storytelling systems like Universe (Lebowitz 1985) and Facade (Mateas and Stern 2005) create stories one scene at a time, and an atomic piece of storytelling content corresponds to roughly one paragraph of a written story. Systems based on text generation, like AI Dungeon (Walton 2019), generate stories one word at a time. Event-level storytelling exists between these two poles.

Scalable along Several Dimensions:

It should be possible to generate a wide variety of scenarios of varying size and difficulty, from trivially easy to nearly impossible. MicroTales can vary in the size of the map, the number of characters, the number of items, the types of actions that are available, and the number and complexity of goals that need to be achieved. The ability to generate a wide variety of scenarios has several advantages. By generating scenarios of different sizes and with different features turned on or off, we can make a controlled study of what makes story planning problems easy or hard to solve. Having many scenarios to train on also encourages learning-based approaches to generalize rather than overfit to a small number of specific problems.

Following Genre Tropes:

While MicroTales is meant to allow a wide variety of scenarios, it is also attempting to follow the genre tropes of simple Medieval computer Role Playing Games. This serves two purposes. First, it allows players of an interactive MicroTales game to leverage existing genre knowledge and minimize the amount of onboarding required to understand the game’s rules. Second, MicroTales is intentionally attempting to represent “naturally occurring” problems. Some things are unlikely or impossible, and some things are over-represented. MicroTales is not meant to represent every conceivable situation or action. It is not meant to be the only type of benchmark problem that storytelling algorithms should be tested on. We are attempting to add to, not restrict, the variety of storytelling problems available for testing.

Active NPCs:

One purpose of MicroTales is to fill a gap we perceive in the kinds of games available to test storytelling algorithms, namely story games with active non-player characters (NPCs). Many story games, like the interactive fiction Zork (Anderson et al. 1980) and similar games available in the TextWorld environment (Côté et al. 2019), rely on the player character to take most of the actions in the story. Actions by others are often short and direct reactions to the player. An ideal MicroTales scenario will feature NPCs taking actions motivated by their own goals, ideally in ways that are predictable or at least believable to the player. Solving a MicroTales scenario should involve the player anticipating the actions of NPCs and creating a situation that encourages NPCs to act in a way that accomplishes the player’s goal.

Wide Variety of Actions:

Many planning and reinforcement learning benchmark problems have a limited variety of action types available. For example, the classic Blocks World planning problem (Slaney and Thiébaux 2001) has only one type of action—moving a block onto another block or onto the table. While it might have a large number of possible actions when we consider all blocks, it has only one type of action. Similarly, the Cart Pole reinforcement learning problem (Towers et al. 2024) has only two actions: push the cart left or right. The action can vary in the force applied, but still there is only one or two types of action. We find that storytelling problems tend to involve a large number of action types. MicroTales has many types of actions with different kinds of preconditions and effects.

Soft Locks are Possible:

A soft lock means a solvable problem has been put into a state from which no solutions are possible. The potential to soft lock a puzzle makes it challenging because solvers must plan ahead. Solvers that rely on performing random actions—like Monte Carlo random rollouts or random exploration in Markov Decision Process solvers—will need to account for soft locks. Many benchmark problems used to test classical planning algorithms (Taitler et al. 2024) do not allow soft locks. Stories often feature irreversible actions that require careful planning, which is why soft locks are allowed, and even encouraged, in MicroTales.

Deterministic Actions:

Actions in MicroTales are deterministic, meaning that when an action occurs we know with 100% certainty what the resulting state will be afterward. Determinism allows a wide variety of search and planning techniques to be applied. Real world problems are not deterministic, but MicroTales is not designed to simulate a real world problem; it is designed to simulate a game in a virtual environment where the experience manager has full control over the virtual world. While a single MicroTales scenario is deterministic, the larger problem of experience management in an interactive MicroTales game is usually viewed as nondeterministic since the player may take unexpected actions.

Complex Multi-Agent Interactions:

Most scenarios will feature more than one character. Many existing AI benchmarks feature only a single agent or assume agents are strictly cooperative or competitive. In MicroTales, each character has their own goals, and they should aid or thwart one another to the extent that their goals align or diverge. One of the central challenges of storytelling is ensuring that each character behaves realistically while maintaining a story’s central structure. MicroTales provides an environment to compare emergent storytelling via multi-agent systems to centralized storytelling via planning.

No Model of Storytelling Enforced:

MicroTales enables the study of what makes a story in a story game believable, interesting, and fun. It tries to avoid enforcing any particular model of storytelling in its rules. Action preconditions are meant to be minimal requirements on when an action would be “physically possible” in the virtual world. For example, one character can only give an item to another if they are in the same location and if the giver has the item. The preconditions do not require that the receiver wants the item; it is up to the algorithm and its model of storytelling to determine whether this action makes sense. To study a model of good storytelling, it must be possible to generate bad stories. Many AI benchmark problems define success as reaching a clear goal via a shortest or lowest cost path, but many MicroTales scenarios will have “solutions” that are bad stories—that is, a sequence of actions that achieves the story goals but is made of actions that are not believable or fun. The quality of a MicroTales solution should not be judged solely on whether it achieves goals or on the number of actions it contains. A solution must be evaluated as a story, but MicroTales does not define what makes a good story. In other words, MicroTales defines a set of objects, actions, and goals so that two researchers can be said to be working in the same domain, but it does not define success in that domain.

Problem Curation Encouraged:

MicroTales defines a scenario’s elements and when they can be used, but it makes no claim that all generated scenarios are interesting. Many MicroTales scenarios will have no way to reach a goal state, and many that have a reachable goal state may not have any interesting or good stories that do so. In other words, generating a uniform sample of MicroTales scenarios is not likely to result in a set of interesting problems. Generators will need to apply further criteria and quality checks to ensure scenarios are interesting. Generating or curating interesting scenario sets by hand is also encouraged.

name: "Robin Hood"
version: 1.0
extensions:
- Crime # Adds jail; allows lawful goal, arrest and release actions
- Marriage # Adds chapel; allows wed goal, marry action
- Monarchy # Adds castle and Crown; allows ruling goal, enthrone action
- Theft # Adds bandit, Coin, and Sword; allows steal action
- Violence # Adds knight and Sword; allows avenged goal, attack action
locations:
- Sherwood : forest # Sherwood forest
- Nottingham : castle # Nottingham Castle
- Jail : jail # The Jail
- Abbey : chapel # Fountains Abbey
paths: # Sherwood Forest connects all locations
- [Sherwood, Nottingham]
- [Sherwood, Jail]
- [Sherwood, Abbey]
characters:
Robin : bandit # Robin Hood is a bandit.
John : noble # Prince John is a noble.
Sheriff : knight # The Sheriff of Nottingham is a knight.
Marian : noble # Maid Marian is a noble.
initial: # Only need to list values if they are not defaults
- [location, Robin, Sherwood] # Robin starts in Sherwood Forest.
- [right, John, Crown] # Prince John starts with a Crown.
goals:
- [Robin, rich, Robin] # Robin wants coins.
- [Robin, wed, Robin, Marian] # Robin wants to marry Marian.
- [John, ruling, John] # John wants to be king.
- [John, wed, John, Marian] # John wants to marry Marian.
- [John, avenged, John] # John wants his enemies dead.
- [Sheriff, ruling, John] # The sheriff wants John to be king.
- [Sheriff, lawful] # The sheriff wants no criminals.
- [Marian, ruling, Marian] # Marian wants to be monarch.
- [wed, Robin, Marian] # Story goal: Robin marries Marian.
An example MicroTales scenario in YAML format.

Example Scenario

Figure 1 gives an example MicroTales scenario that approximates a simple version of the Robin Hood setting. The story goal, given on the last line, is for Robin Hood and Maid Marian to get married. This section describes some example stories that are possible in this scenario and why they might be desirable or undesirable. We assume this scenario is presented as an interactive game where the player controls Robin Hood.

walk(Robin, Nottingham) # Robin goes to Nottingham Castle.
take(Robin, Coin, John) # Robin wants coins to become rich.
attack(Sheriff, Robin) # The Sheriff of Nottingham hurts Robin.
attack(Sheriff, Robin) # The sheriff kills Robin.

This is a simple but unsuccessful story. Robin robs Prince John, but the Sheriff of Nottingham kills Robin for his crimes. This example does not achieve the story goal, but if the scenario is presented as an interactive puzzle it might be a reasonable but unsuccessful attempt by the player to achieve Robin’s goals. Suppose the player tries a different approach.

walk(Robin, Castle) # Robin goes to Nottingham Castle.
take(Robin, Crown, John) # Robins steals John’s crown.
enthrone(Robin) # Robin is crowned king.
arrest(Sheriff, Robin, Jail) # Lawful sheriff throws Robin in jail.
walk(Marian, Sherwood) # Marian on her way to release Robin.
release(Marian, Jail) # Marian unlocks the jail.
walk(Robin, Jail, Sherwood) # Robin on his way to marry Marian.
walk(Robin, Abbey) # Robin goes to the chapel.
walk(Marian, Abbey) # Marian goes to the chapel.
marry(Robin, Marian) # Marian becomes queen by marriage.

This story is more interesting. Robin steals the Crown and becomes the monarch. The storyteller is faced with two possible responses from the sheriff: attack like in the previous story, or arrest Robin and move him to the jail. Killing Robin would end the story before the goal is achieved, but arresting him leaves it open for a happy ending later. Robin can’t do anything from the jail, but Marian comes to free him. Marian’s plan is to marry Robin and satisfy her ruling goal as well as the story goal. We consider this story more interesting because non-player characters take an active role.

While this makes a plausible story, it may not work when presented as a puzzle, since the player might wonder why Robin was allowed to take several actions in a row without any response from the sheriff. Next, we’ll consider a story that enforces strict turn-taking, always allowing one player action after one NPC action.

enthrone(John, Nottingham) # John is crowned king.
# The player chooses to wait, passing their turn.
walk(John, Sherwood) # John on his way to marry.
take(Robin, Coin, John) # Robin steals John’s money.
walk(Marian, Sherwood) # Marian on her way to marry.
take(Robin, Crown, John) # Robin steals John’s crown.
walk(John, Abbey) # John on his way to marry.
walk(Robin, Nottingham) # Robin on his way to be crowned.
walk(Marian, Abbey) # Marian on her way to marry.
enthrone(Robin) # Robin is crowned king.
take(Sheriff, Crown, Robin) # Sheriff steals Robin’s crown.
walk(Robin, Sherwood) # Robin on his way to marry.
walk(Sheriff, Sherwood) # Sheriff on his way to John.
walk(Robin, Abbey) # Robin on his way to marry.
walk(John, Sherwood) # John on his way to the sheriff.
marry(Robin, Marian) # Marian becomes queen by marriage.

John starts by achieving his ruling goal and becoming the monarch. He and Marian then walk in the direction of Fountains Abbey to marry. On the way, John gets robbed by Robin Hood. The player waiting for John to pass by is a prime example of a player anticipating active NPCs. Robin then goes to Nottingham Castle and crowns himself the new monarch before the wedding can take place. The sheriff takes the crown from Robin and goes to Sherwood Forest hoping to give the crown to John. Robin makes his way to Fountains Abbey and marries Marian, achieving the story goal.

In this example, our model of storytelling assumes characters only witness actions that occur in their location (except enthrone, which gets announced to everyone throughout the kingdom). The sheriff is not aware of Robin’s crimes, since he was not in Sherwood Forest during the robbery. This model of limited observability is not required. MicroTales does not model character beliefs; that is left to the storyteller, who is free to use this or any other model. For this scenario, we think it makes the characters seems more realistic, and it adds a new dimension to the puzzle by encouraging Robin to avoid witnesses to his crimes.

Given the sheriff does not know about Robin’s crimes, it may seem odd that he would take the Crown. This theft makes him a criminal and goes against his lawful goal. The sheriff takes the crown because he hopes to return it to John so that John can again take the throne. After returning the crown, the sheriff plans to arrest himself, satisfying all his goals, though the story ends before he can complete his plan. Does it make sense for the sheriff to arrest himself? This is up to the storyteller.

Notice also how the sheriff and John meet in Sherwood Forest. According to our model, the sheriff saw John leave for the forest, but did not see John continue to the Abbey, so the sheriff wrongly believes John is in the forest. John did not see the sheriff go to the forest, so John wrongly believes the sheriff is in the castle. Luckily, these two meet by chance in the forest despite their wrong beliefs thanks to some clever coordination by the storyteller.

Definitions

A MicroTales scenario is defined by several explicit elements which imply the inclusion of other elements. The explicit elements of a scenario are:

Figure 1 shows an example scenario in YAML format.

Many elements of a scenario are not explicitly listed but are implied by what is explicitly listed. For example, each scenario defines variables, and the current state of the scenario is an assignment of a value to each of its variables. Variables are not explicitly listed because they are implied by the extensions, locations, and characters. Similarly, actions are not explicitly listed because which actions are available is implied by the other elements.

A scenario’s elements cannot be created or destroyed. The only thing about a scenario that changes over time is the values assigned to its variables. New locations cannot be added to the map, nor can existing locations be removed. New characters cannot be created or removed (though they can be killed when the relevant extensions are enabled). The items a character is carrying are not first class elements of a scenario, so they do not need to be explicitly defined, and they can be created and destroyed (see the section on Constants for how items work).

The following subsections define MicroTales elements in detail. Rules which must be followed are required. When something is recommended, it means that a scenario generator should try to follow those rules when it can, but it may choose to ignore those rules in service of some other design goal. When a definition says something is a default, it means that a scenario assumes the rule will be followed. If a default is not followed, the scenario must explicitly state some other value. For example, a noble character starts with a Coin in their left hand by default. The scenario does not need to list this under its initial facts because it will be assumed. If the noble should not start with a coin, the scenario should explicitly list their left hand as Null.

Style and Capitalization

Throughout this document, we capitalize specific, individual objects. This includes universal constants like True, False, and Null, the names of all extensions, the names of all constants, and the names given to individual objects defined in example scenarios, like the character name Robin. We use lower case for types, which includes all location types, character types, variable names, goal names, and action names. For example, Robin is the name of a specific character, so we capitalize his name, but his character type, bandit, is a type and is written in lower case. The variable health(Robin) has a lower case name because health is a type of variables, but the value Healthy, which can be assigned to that variable, is a single individual constant and is capitalized.

Extensions

An extension is a group of related elements that become available when an extension is included in a scenario. Extensions are designed to allow additional types of actions in a scenario, but doing so means enabling the locations, characters, and goals that would make those actions possible and relevant.

Figure 1 shows an example list of extensions. In YAML, the list of extensions is simply the key extensions followed by a sequence of strings. The list of extensions is optional and can be omitted, but scenarios with no extensions are likely to be uninteresting.

Some extensions require that other extensions are also enabled. For example, the Undead extension requires some way for characters to die, which is enabled by both the Sickness and Violence extensions. One of these two must be enabled in order to enable Undead. A scenario should explicitly list all extensions that it uses, even those required by other extensions. For example, a scenario that includes Undead should also explicitly list Sickness or Violence or both.

Several scenario elements can be enabled by more than one extension. For example, several extensions enable potions of some sort. All of these extensions enable the sorcerer character type, whose special actions revolve around using potions.

Not all of the elements enabled by an extension need to be used in the scenario, though at least one should be used. We recommend this rule of thumb: if an extension could be removed without modifying the scenario at all, then it is not really enabled and should not be listed as part of the scenario.

Alchemy

Commerce

Crafting

Crime

Enchantment

Forgiveness

Healing

Marriage

Monarchy

Sickness

Stealth

Teleportation

Theft

Undead

Violence

Locations and Paths

MicroTales scenarios take place on a map made of one or more connected locations. A location has a unique name and a type. The type determines what special actions are available in that location. There can be more than one location of the same type on a map as long as they have different names. For example, Sherwood and Mirkwood might both be locations of type forest. We recommend avoiding duplicate locations when possible simply for the sake of variety.

Figure 1 shows an example list of locations. In YAML, the list of locations is the key locations followed by a sequence of one-element maps that each associate one unique string name to a string type, where the type is one of those defined below. A sequence of maps is necessary because the order locations are defined in matters. The list of locations is not optional, because a scenario must define at least one location.

Four location types are always available: the cave, crossroads, forest, and village. These locations are similar in function—characters can drop or pickup an item. The cave and forest have default items waiting to be picked up when some extensions are enabled.

The order that locations are defined in affects the default starting locations of characters. For example, the bandit character type’s default starting location is the first camp or crossroads location that is defined in the scenario. If a scenario contains both a camp and a crossroads, the bandit will start in whichever one is defined first in the list of locations. Similarly, if the scenario has more than one location of type camp, the first one will be used. If there are no locations that a character prefers to start in, they default to starting in the first location in the list. These defaults do not apply if a scenario explicitly states a character’s starting location.

After defining the list of locations, a scenario should define how they are connected via paths. A path is a pair of locations. A path goes in both directions. For example, if Sherwood and Nottingham are connected, then a character can walk from one to the other and back again. When defining a path, the two locations can be given in either order. Each location type defines a minimum and maximum number of paths it should have connecting it to other locations.

As shown in Figure 1, in YAML the list of paths is the key paths followed by a sequence of pairs of strings that match the names of locations. The list of paths is optional if no locations are connected, though only very small scenarios will have no paths.

We recommend that locations be placed on a 2 dimensional grid where each location is of equal size and paths always lead North, South, East or West. This is not required, but it makes it easier to visualize MicroTales scenarios for an audience.

The existence of paths is important for the walk action, but paths are not defined as variables because they do not change (though the jail location type can be locked to restrict movement). We recommend that all locations be accessible to one another. In other words, it should be possible to walk a route from any location to any other.

camp

castle

cave

chapel

crossroads

forest

graveyard

jail

laboratory

market

village

workshop

Characters

Characters are agents who act in the story world. Like locations, each character has a unique name and a type. There can be more than one character of the same type in a scenario as long as they have different names. We recommend avoiding duplicate character types when possible simply for the sake of variety.

Figure 1 shows an example list of characters. In YAML, the list of characters is the key characters followed by a mapping of string names to string types, where the type is one of those defined below. The list of characters is not optional, because a scenario must define at least one character.

Character types define what special actions a character can take. They prohibit some character goals and recommend others. Many character types also define a default starting location and starting items. These defaults do not apply if a scenario explicitly states some other starting location or starting items.

The only character type that is always available is the peasant, which has no special qualities. All other character types are enabled by extensions.

bandit

cleric

knight

merchant

noble

peasant

sorcerer

Variables and Initial Values

Variables are features of a scenario that are assigned one of several possible values. All of a scenario’s variables with their assigned values define a scenario state. Different actions are possible depending on the current state, and actions change the values assigned to variables. Actions are the only way to change variable values.

A scenario does not explicitly define its variables; they are implied by the other elements in the scenario. For example, when the Violence extension is enabled the scenario must have a health variable for every character.

A variable is identified by a name followed by zero to many arguments. In the example above, health is the name of the variable, and it has one argument, the name of the character. If a scenario defines two characters named Robin and Marian, then it will have two health variables, one for each of them. In text, we would write those variables as health(Robin) and health(Marian), though in YAML we use a different style, as discussed below.

Some variables have more than one argument, and the order of arguments matters. For example, every scenario tracks the relationship between each pair of characters, so our example scenario will need the variables relationship(Robin, Marian) and relationship(Marian, Robin). The first variable tracks how Robin regards Marian, and the second tracks how Marian regards Robin. Relationships are not symmetric, so these variables can have different values.

The variable definitions in this section begin with the variable name, followed by one or more parameters in parentheses, followed by a colon and a description of the variable’s possible values. Sometimes a value is simply Boolean, meaning True or False. Sometimes a value is a type, like a location. For example, every character has a location variable, and its possible values are the names of every location defined in the scenario, plus Nullto represent a situation where the character is nowhere on the map. Sometimes a variable’s value is a set of pre-defined constants. For example, a relationship variable can have three possible values: Friend, Null, and Enemy, which mean that the first character considers the second a friend, has no relationship, or considers the second an enemy respectively. Many variables have one of a pre-defined list of constants as their possible values. All constants are defined in the next section.

All variables have a default initial value they will be assigned, but these defaults are ignored if the scenario explicitly defines a variable’s initial value. Figure 1 shows an example list of initial values. In YAML, this list is the key initial followed by a sequence of sequences. Each initial value sequence includes the variable name (defined below), its arguments, and finally the initial value to assign to that variable. For example, if we want Robin to start with a Sword, we would write:

[left, Robin, Sword]

This sequence has three parts: the variable name, the variable’s arguments (in this case, one argument), and finally the value to assign to the variable—i.e. the item to put in Robin’s left hand. In text, we would write this value assignment as:

left(Robin) = Sword

Defining the initial value of a variable with multiple arguments looks like this:

[relationship, John, Robin, Enemy]

Some variables, like the relationship between each character, are counter to MicroTales’s design principle of modeling only necessary physical elements of the world and making no commitments to any particular model of storytelling. These variables exist because they are needed to define some of the goals that characters and stories have. Whenever possible, we try to avoid using them to limit when actions are possible.

criminal ( character ) : Boolean

health ( character ) : {Healthy, Hurt, Dead, Ghost}

item ( location ) : the name of any item or Null

left ( character ) : any item or Null

location ( character ) : the name of any location or Null

locked ( jail ) : Boolean

monarch ( ) : the name of any character or Null

relationship ( character, other ) : {Friend, Null, Enemy}

right ( character ) : any item or Null

spouse ( character ) : the name of any character or Null

visible ( character ) : Boolean

Constants

Constants are special values that can be assigned to some variables. Constants are not explicitly defined; they are implied by which extensions are enabled. For example, the Ghost constant is one possible value for a health variable, and it represents a character who has been raised from the dead. However, if the Undead extension is not enabled, this constant is not available, even if the other constants that can be assigned to health variables are.

One use of constants is the items that characters carry and use in the story. MicroTales elements cannot be created or removed, but items are not first class elements. Each character has a left and right hand variable, and the possible values that can be assigned are the item constants or Nullto represent holding nothing. This means each character can hold up to two items, one in each hand. Consider the sell action, where a character trades an item for a Coin. The action’s precondition requires that the character have the item they are selling in either their left or right hand. The effects of the action replace that hand’s value with a Coin constant, effectively destroying the original item and creating a new Coin item.

BanishPotion

CharmPotion

Coin

Crown

CursePotion

Dead

Enemy

Flower

Friend

Ghost

HealPotion

Healthy

HidePotion

Hurt

Ore

RaisePotion

Sword

TeleportPotion

Goals

Goals are objectives. There are two kinds of goals in MicroTales, character goals and story goals. Character goals are personal objectives that individual characters want to achieve. Story goals are objectives that the storyteller should try to achieve with the story as a whole.

Similar to variables, a goal is one of the names define below followed by zero to many arguments. Figure 1 shows an example list of goals. In YAML, it is the key goals followed by a sequence of sequences. If the sequence is a character goal, the first element is the name of one of the scenario’s characters. If the sequence is a story goal, this name is omitted. The next elements in both types are the goal name (defined below), followed by the goal’s arguments.

For example, this character goal in YAML format says that John wants John to be the monarch:

[John, ruling, John]

The first part, John, specifies which character has this goal. The rest specifies the goal ruling(John), which is the objective that John be the monarch. Characters can also have goals for other characters:

[Sheriff, ruling, John]

The goal of ruling(John) is the same, but it is held by the Sheriff. The Sheriff also wants John to be monarch.

To make this a story goal instead of a character goal, we simply omit the character from the start of the sequence:

[ruling, John]

This means that ruling(John) is a goal for the story as a whole rather than any particular character. The storyteller should try to tell a story where John becomes the monarch.

Two character goals always apply and do not need to be explicitly listed. When Sickness or Violence is enabled, all characters prefer being Healthy over Hurt and prefer Hurt over Dead. Second, if Undead is enabled, all Ghosts have the avenged goal toward themselves. This means they want to kill any character they regard as an Enemy.

Goals are persistent, meaning they do not go away once they are achieved. For example, when a character has the goal to be rich, they want Coins. Once both of their hands are holding Coins, they cannot have more, but they do not stop having the goal to be rich. If they should ever lose one of their coins, they will again want more.

MicroTales does not define the relative importance of one goal to another, and when a goal can be achieved in multiple ways, it only defines ordinal preferences. For example, if a character wants to be both rich and obliged, MicroTales does not specify whether it is more important to that character to have Coins or Friends; this is up to the storyteller. Similarly, a character who wants to be rich would prefer to have 2 Coins over 1 Coin, but it is not necessarily twice as good to have 2 than it is to have 1. Again, this is left up to the storyteller.

MicroTales tries to avoid imposing any particular model of what makes a good story. Some good stories may not achieve goals, and stories that achieve goals are not necessarily good stories. If goals can be ignored, why define them at all? First, MicroTales is meant to study the challenges of story planning. Goals provide constraints that make planning a story challenging because the storyteller needs to look ahead to reason about what is and is not possible when deciding what actions to take. Second, in an interactive setting, goals are what will be communicated to players about what the characters want and what the objectives are for the story. Stories are meant to involve multiple active characters, so anticipating how non-player characters will act requires information about what they want.

at ( character, location )

avenged ( character )

disliked ( character )

harmed ( character )

lawful ( )

lawless ( )

liked ( character )

obliged ( character )

rich ( character )

ruling ( character )

unharmed ( character )

wed ( character, spouse )

Actions

Actions are events that happen in a story. An action has preconditions that limit when it can happen and effects that modify the world state.

A scenario does not explicitly define actions; they are implied by the other elements in the scenario. Any time an action is enabled by a extension it is available in a story. For example, the enthrone action is always available in every story where Monarchy is enabled, though it can only happen when a character is in a castle and holding a Crown.

Like variables and goals, actions are parameterized. The list of parameters are given in parentheses after the name.

An action’s preconditions are meant as minimal restrictions for an action to seem believable based on the world state. Action preconditions do not attempt to restrict when an action makes narrative sense. For example, it probably does not make narrative sense for a character who wants to be rich to give away their Coin, but MicroTales does not prevent this because one purpose of MicroTales is to study different models of when actions make sense. Ideally, a character’s actions are determined by their character goals and the story goals, though this is not required, and it is not enforced by preconditions. To study the generation of good stories, it must be possible to generate bad stories.

Some actions have an active version that is done by a character and a passive version that simply happens. For example, when a character is Hurt, they can be made Healthy again via by the heal action, which is actively done by a character, but they can also simply get better via the recover action. Actions not taken by characters provide flexibility in solving scenarios, but may be perceived as a deus ex machina.

For brevity, we list preconditions and effects on all variables, even if they are not used in a scenario. For example, many actions require that a character not be Dead, but this only applies if health variables exist. If the Sickness or Violence extensions are not enabled, health variables do not exist, so preconditions and effects on those variables are ignored.

We use a few common shorthand phrases in action preconditions:

The only actions that always available in every scenario are basic movement, the walk action, and basic item interactions, the pickup, drop, give, and trade actions.

arrest ( character, target, jail )

Preconditions:

Effects:

attack ( character, target )

Preconditions:

Effects:

banish ( character, target )

Preconditions:

Effects:

brew ( character, potion )

Preconditions:

Effects:

charm ( character, target )

Preconditions:

Effects:

craft ( character, material, item )

Preconditions:

Effects:

curse ( character, target )

Preconditions:

Effects:

die ( character )

Preconditions:

Effects:

drop ( character, item )

Preconditions:

Effects:

enthrone ( character )

Preconditions:

Effects:

forgive ( character, target )

Preconditions:

Effects:

give ( character, item, target )

Preconditions:

Effects:

grow ( forest )

Preconditions:

Effects:

heal ( character, target )

Preconditions:

Effects:

hide ( character )

Preconditions:

Effects:

jailbreak ( jail )

Preconditions:

Effects:

loot ( character, item, target )

Preconditions:

Effects:

marry ( character, spouse )

Preconditions:

Effects:

pickup ( character )

Preconditions:

Effects:

raise ( character, target, graveyard )

Preconditions:

Effects:

recover ( character )

Preconditions:

Effects:

release ( character, jail )

Preconditions:

Effects:

repent ( character )

Preconditions:

Effects:

rise ( character, graveyard )

Preconditions:

Effects:

sell ( character, item )

Preconditions:

Effects:

sicken ( character )

Preconditions:

Effects:

take ( character, item, target )

Preconditions:

Effects:

teleport ( character, location )

Preconditions:

Effects:

trade ( character, price, target, item )

Preconditions:

Effects:

walk ( character, location )

Preconditions:

Effects:

Version History

Version 1.0

License

The first version of this document was written by Stephen G. Ware and Molly Siler of the Narrative Intelligence Lab at the University of Kentucky in September, 2025. The University of Kentucky holds the copyright to this document. It is released under a Creative Commons Attribution-ShareAlike 4.0 International license (CC BY-SA 4.0). In short, this means anyone is free to distribute it and to adapt it, even for commercial purposes, as long as they give appropriate credit to the original authors and release their modifications under the same license. Full details can be found in the license document. The University of Kentucky reserves all rights not explicitly granted by the license.

Acknowledgments

Thank you to Mira Fisher, Lasantha Senanayake, Gage Birchmeier, and other members of the University of Kentucky Narrative Intelligence Lab for their assistance in the design of MicroTales.

This work was supported in part by the U.S. National Science Foundation under Grant No. 2145153 and the U.S. Army Research Office under Grant No. W911NF-24-1-0195. Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation or the Army Research Office.

image
Grant #2145153
image
Grant #W911NF-24-1-0195

Bibliography

Anderson, Tim, Marl Blank, Bruce Daniels, and Dave Lebling. 1980. Zork I: The Great Underground Empire. Infocom.
Côté, Marc-Alexandre, Ákos Kádár, Xingdi Yuan, et al. 2019. TextWorld: A Learning Environment for Text-Based Games.” Computer Games, 41–75.
Ghallab, Malik, Adele Howe, Drew McDermott, et al. 1998. PDDL—the Planning Domain Definition Language. Yale Center for Computational Vision; Control.
Kybartas, Ben, and Rafael Bidarra. 2016. “A Survey on Story Generation Techniques for Authoring Computational Narratives.” IEEE Transactions on Computational Intelligence and Artificial Intelligence in Games 9 (3): 239–53.
Lebowitz, Michael. 1985. “Story-Telling as Planning and Learning.” Poetics 14 (6): 483–502.
Mateas, Michael, and Andrew Stern. 2005. “Structuring Content in the Façade Interactive Drama Architecture.” Proceedings of the 1st AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment.
Riedl, Mark O., and Vadim Bulitko. 2013. “Interactive Narrative: An Intelligent Systems Approach.” AI Magazine 34 (1): 67–77.
Slaney, John, and Sylvie Thiébaux. 2001. Blocks World Revisited.” Artificial Intelligence 125 (1): 119–53.
Taitler, Ayal, Ron Alford, Joan Espasa, et al. 2024. “The 2023 International Planning Competition.” AI Magazine 45 (2): 280–96. https://doi.org/https://doi.org/10.1002/aaai.12169.
Towers, Mark, Ariel Kwiatkowski, Jordan Terry, et al. 2024. Gymnasium: A Standard Interface for Reinforcement Learning Environments. https://arxiv.org/abs/2407.17032.
Walton, Nick. 2019. AI Dungeon. Https://aidungeon.com/.
Ware, Stephen G., and Rachelyn Farrell. 2023. A Collection of Benchmark Problems for the Sabre Narrative Planner. Narrative Intelligence Lab; https://github.com/sgware/sabre-benchmarks/blob/main/report.pdf.
Young, R. Michael, Stephen G. Ware, Bradly A. Cassell, and Justus Robertson. 2013. “Plans and Planning in Narrative Generation: A Review of Plan-Based Approaches to the Generation of Story, Discourse and Interactivity in Narratives.” Sprache Und Datenverarbeitung, Special Issue on Formal and Computational Models of Narrative 37 (1-2): 41–64.