Final Project: Story Generation

Paper Abstract/Summary

From legends to myths to folklore, stories have always been an integral part of human culture. It is natural for us to be able to draw on prior experiences and convey them in a story format. But if one provides an experience to a computer, how would it translate that into a structured tale? That is what the field of story generation aims to answer. Story generators use algorithms to generate literature that can be considered stories, in that they have some sort of character, premise, or plot. In this field, stories are defined in a functional rather than an aesthetic sense, meaning that generating elegant language is not a core focus. In this post, I propose several solutions of varying complexity for generating such functional stories.

Introduction/Background

There have been attempts to write story generators since the 70’s, and though these generators have grown increasingly more sophisticated, there have been no synthetic Shakespeares or Tolkiens. Early story generators were capable of generating stories with very basic structure; for example, a brief story by TALESPIN [Meehan 1977]:

“John Bear is somewhat hungry. John Bear wants to get some berries. John Bear wants to get near the blueberries. John Bear walks from a cave entrance to the bush by going through a pass through a valley through a meadow. John Bear takes the blueberries. John Bear eats the blueberries. The blueberries are gone. John Bear is not very hungry.”

Later generators like BRUTUS [Bringsjord & Ferruci 1999] are capable of generating short stories with more complex characters that focus on abstract concepts like betrayal. Yet even BRUTUS had some sentences that seemed stilted and unnatural, as well as some odd jumps in the story. In other words, the stories it generated were understandable but not human.

Application

Story generators offer an alternative to the heavily scripted storylines prevalent in video games. Were a computer capable of changing and altering a story with respect to user input, interactive storytelling would be taken to a whole new level. Game playthroughs would be truly unique for each individual player.

Previous Work

As stated previously, story generators have been around since the 70’s. Some well-known story generators would be: Novel Writer [Klein et al. 1973], TALESPIN [Meehan 1977], AUTHOR [Dehn 1981], UNIVERSE [Lebowitz 1983], BRUTUS [Bringsjord & Ferrucci 1999], and more recently FABULIST [Riedl & Young 2010].

Current Problems in the Area

In the field of computer programming, programmers usually give computers very clear instructions detailing what they are supposed to do. A definition of the computer’s goal is given, along with a set of instructions on how to achieve it. For this to be possible, the solution set must be defined in some way, there must be rules for choosing what order to consider each solution, and there must be a way to determine which solutions are actually viable. Each of these requirements appears equally intractable when considering story generation. The first requires one to explain what a story is – already difficult to do, given the broad array of literature the word encompasses, and doubly difficult when communicating with a computer, which only understands ones and zeros. The second and third requirements need some way to rank possible solutions in a way that allows the computer to generate stories with consistent characters, plotline, and even writing style. This requires intimate knowledge of not only plot structures and character building, but also language conventions and word associations.

Since a functional story is the goal, not an elegant one, writing style can be struck off the to-do list. However, this still leaves us with the problem of creating a coherent and believable series of events. Events in a story must follow certain laws; for example, the pigs in Three Little Pigs cannot suddenly sprout wings and fly away from the wolf, because it would make no sense given the laws of the story’s world. This means that the computer also needs to know some pre-defined rules which its story cannot break, and it must be able to identify possible solutions that would break these rules.

Algorithms that attempt to satisfy all these conditions are numerous, but very few, if any, are able to succeed. The sheer complexity and inherent fuzziness of the problem make it near impossible to do.

Proposed Solutions

Before considering solutions for generating actual words and sentences, we must consider how a computer is able to come up with a story. Stories are driven by conflict; conflict is driven by character motivations. Thus, it follows that the first goal a computer should achieve is to create a character who has some motivation – who wants something. From there, the plot will follow.

While the concept of this solution is simple, the implementation is not. A simple way to achieve this is to have a “character” object with attributes describing their motivations, personality, backstory, and relationships with other characters. These attributes would be picked from a pool of pre-determined data. From these characters arises conflicts of interest that then resolve themselves into stories; for instance, if two characters have opposing motivations, they can be selected as protagonist and antagonist.

Image

With the problem of generating characters and plot behind us, we can focus on generating the actual prose. There are several ways to do this.

1. Have pre-written prose that can be mixed and matched each time a story is generated. This approach is highly inflexible and requires a lot of manual work, but in terms of programming, it is the simplest.

2. Use pre-written template sentences that are tagged with categories describing the mood they imply (i.e. scary, angry, sad, happy) and with key words that can be swapped to fit the situation (i.e. if the template is “Bob kicked Alice on the shin”, it could be altered to “Jordan kicked Alyssa on the ankle”).

3. Generate sentences from scratch. This is much more difficult because it would require the computer to understand word associations and how to correctly put together a sentence.

None of these solutions are very optimal, but they serve their purpose.

Conclusion

Quantifying stories is already a difficult task, and instructing a machine to generate them is no simpler. There are countless varied approaches to solving the problem of story generation, but not a one of them is perfect. Like many other givens in human culture, storytelling is a skill that eludes the understanding of machines.

Future Work

As of now, story generators remain firmly entrenched in text-based mediums. However, given creative implementation, such stories could be translated into animations, games, or even short films. A successful story generator would also be a triumph for the ongoing struggle to understand what defines “natural language” – that is, language that appears to have been generated by a human as opposed to a machine. This could in turn elucidate how we interpret words to recognize sarcasm and hidden meanings.

References

Gervás, Pablo. “Story Generator Algorithms.” The Living Handbook of Narratology. N.p., 24 Sep 2012. Web. 26 Jul 2013. < http://wikis.sub.uni-hamburg.de/lhn/index.php/Story_Generator_Algorithms >.

Riedl, Mark. N.p.. Web. 26 Jul 2013. < http://www.cc.gatech.edu/~riedl/pubs/mm.pdf >.

A Book Related to the Project

http://www.amazon.com/Tell-Story-Narrative-Intelligence-Rethinking/dp/0810113139

Advertisements

2 responses to “Final Project: Story Generation

  1. that’s funny, I just emailed Mark Riedl to see if he’d be willing to skype in :)… Cool coincidence. Mark is a nice guy!

  2. Great choice for a book and I love your diagram.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s