Category Archives: Projects

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

Classifying Data

Image

Pictured above is the result of my attempt to use kNN to classify data. The orange and light blue dots are two different types of data in my “training set”, which is the data set that has already been classified. The red and darker blue dots are the data of my “testing set”, which is the data that I classified using the training set.

The data could also have been classified using a naive Bayes classifier. The placement of orange and light blue dots shows that the position of the dots correlates with their classification. Thus, it is possible to classify the dots according to their positions only; the data on the fringes of the set would be dark blue, and the dots closer to the center would be red. Of course, this approach would likely be less accurate than kNN.

Traveling Salesman Problem

Image

“PathFinder” is a program I wrote that deals with a simple case of the Traveling Salesman Problem. The objective is to visit all points with the shortest path possible. My solution was not optimal, but it was not particularly inefficient either. I used Dijkstra’s algorithm, which finds the shortest path from point to point and then connects the last point to the point where you began. This creates a suboptimal path from the last point to the starting one.

Simple Lisp Program

( defun add (x y)
(+ x y))

( defun subtract (x y)
(- x y))

( defun multiply (x y)
(* x y))

( defun divide (x y)
(/ x y))

( defun factorial (x)
(if (eq x 0)
1
(* x (factorial(- x 1)))))

(print ( add 3 4 ))
(print ( subtract 5 3 ))
(print ( multiply 2 4 ))
(print ( divide 2 5 ))
(print ( factorial 5 ))

This is a program in Lisp that lets you add, subtract, multiply, divide, and find the factorial of a number. Unlike Java, which is imperative, Lisp is a functional programming language, which is why it looks so different. Imperative programming languages tell the computer what to do and how to achieve it. On the other hand, declarative languages (which include functional languages) tell the computer what should be accomplished without describing exactly how to do so.

Lisp was specified in 1958, making it one of the oldest programming languages still being widely used. It originated from Alonzo Church’s lambda calculus and has become the most popular language for AI research.

Final Project Proposal: Story-Telling Chatbot

What is the specific area you are working within?
I am working on a chatbot. That means my project involves word relations, mimicking human behavior, and of course AI.

What is it that you would like to learn about it?
I would like to learn more about conversational patterns and how chatbots like Cleverbot generate the Eliza Effect.

Why is this interesting to you?

I am always looking to expand my knowledge on AI, as well as programming in general. Besides that, I have an interest in the psychology behind the Eliza Effect.

Why should other people care?
Eventually, technology like this could be used to generate games that are a truly interactive experience, telling a story that is not preset but changes on every playthrough.

What are the practical applications of this topic?
See above.

What is the closest example (researched from the web) of what you want to build or investigate?
Two story-telling chatbots that have been built in the past are Tale-Spin and Racter.

What do I want to accomplish? (For example…)
I want to create a chatbot capable of holding conversation and telling a human user about its “experiences” (the stories it generates).

Building a demo/prototype/interactive experience?
Collecting a set of foundational psuedocode/approaches?
Creating a way to teach or explain it to others?
Pooling together a set of current cutting edge research in this area?
Any or all of the above?
etc.

My order set of steps I plan to take to accomplish it?
I plan to first outline the program in pseudocode. Then, I will gather phrases, subjects, places, verbs etc. for the prototype to utilize. After that I will work on actually coding the program, getting user input straight from the command-line to save time on making a frontend.
Foreseeable obstacles?
Generating stories that actually make sense.
What tools am I using?

Java, resources found online.

visualsort

 

Wrote a program that visually represents a bubble sort.

EPGYDraw!

My very basic drawing program.

My very basic drawing program.

Today I wrote a simple program to let you draw and create shapes. It includes:

  • Red, green, blue, or black brush/shapes
  • The ability to click and drag rectangles, rounded rectangles, ellipses, and lines
  • The ability to clear the canvas