Automatic Story Generation

Discussions on everything related to the software, electronic, and mechanical components of information systems and instruments.

Automatic Story Generation

Postby bloaf on April 4th, 2016, 12:53 pm 

I've been thinking about automatic story writing lately. I know that there are some fields that research things like making up a story from scratch, or generating text from some abstract representation. But what I'm most interested in is the problem of:

Given some collection of actors, events, and relationships between the events, how do you select the sequence of events that makes for the best story?

The closest thing I'm aware of is automatic news story generation

The specific context is that I am thinking about creating a videogame that records the game's events & player actions, then generates an actual story (i.e. not just a news report) based on what happened. The story does not necessarily feature the player/player's character as the protagonist. The reason videogames are nice for story generation is the same reason they are nice for economics, we have access to a complete data set with everything that happened. However, its clear that simply re-telling every game event does not make for a good story. To do the conversion from event-list to story, I've thought of three steps that seem necessary:
  • Pick the elements from the big list of everything that could form the "backbone" of the story.
  • Take the "backbone" of the story and decide the order in which to present the events. (e.g. decide to keep something a secret for a dramatic reveal, or bounce back and forth between two parallel narratives that will eventually converge.)
  • Embellish the elements from the backbone so that we get an actual story instead of a "plot summary." This includes things like using repetition, poetic meter, or introducing morals to the story.

In this thread, I'd like to focus on the first things first: picking out the story backbone. My current thoughts on how to approach the problem go like this:

  • Give every event in the big list a base "dramaticity" value. Things like eating lunch would get a low base dramaticity score, but a betrayal would get a high base dramaticity score.
  • Establish "causality" or "explainability." In other words, we start describing certain events as causes or explainers of other events. For example, "starvation" is a good explainer of "decided to steal food," which is a good explainer of "food stolen." We can also have bad explainers, e.g. "negligable status ailment" is a bad explainer of "crushing defeat."
  • Choose a candidate "explanatory path" (e.g. hungry -> decide to steal -> steal -> detected -> caught -> imprisoned). Create a modified dramaticity of each event based on the dramaticity of the prior and subsequent event. For example, being hungry is not a very dramatic event by itself, but since it led to the more dramatic event of deciding to steal, the hunger's dramaticity gets increased. On the other hand, since the decision to steal was triggered by a mundane cause (i.e. hunger, instead of some tragic obsession) its dramaticity gets lowered. How much the dramaticity changes depends on how good the explanatory link is, and the base dramaticity values of the two events.
  • Look for patterns in the modified dramaticity. We want to pick a story that has a high overall dramaticity score, but we might also want one that has something of an arc, with the classic buildup/conflict/resolution features.
  • If the "explanatory path" chosen has a high overall dramaticity, and a good dramaticity pattern, then accept it as the story backbone, otherwise go back to 3 and pick a new path.

There are a few issues with these steps.

First off, we need to precisely define what we mean by "explainability." I think this would not be too difficult to code, we would just need some code that explores counterfactuals (e.g. status.hungry is a good explainer of deciding to steal iff when we re-run that decision with status.notHungry we get a completely different outcome.)

Second, to really do this well, I think we should have some insight into the game character's intent when making a decision. In other words, when a character makes a decision to do something, they should have some expected outcome. Then we could suspect, without even needing to do the counterfactual analysis, that a decision to steal was driven by hunger. We would do so by looking at the differences between their current state and their expected outcome, and see that the biggest difference is the original state had status.hungry, while the expected outcome had status.nothungry.
bloaf
Forum Neophyte
 
Posts: 9
Joined: 13 Jan 2016
Natural ChemE liked this post


Re: Automatic Story Generation

Postby Natural ChemE on April 4th, 2016, 6:07 pm 

Folks,

bloaf was telling me about this idea outside the forum. I suggested that he post it here because it's such a cool topic and this forum should provide a decent medium for discussing it.

I saw his idea as something like:
  1. Let's create a Dwarf Fortress-like universe.
  2. Let's fill that universe with characters, some intelligent.
  3. Someone watching this universe should be able to tell good stories based on its events.
  4. Let's make computer programs that watch the universe and generate stories for us.
bloaf made a really neat distinction between dramaticity and explanatory power. Personally I thought of the current US election process as a good example of this distinction:
  • dramaticity: How compelling a reporter in the media feels the story is; entertainment.
  • explanatory power: How useful a data scientist expects the information to be for predicting the outcome of the election; physics.

As bloaf explained in the OP, one route to making a story could be:
  1. Simulate the universe.
  2. Have an algorithm find the most dramatic events in the history of that universe.
  3. Select an extremely dramatic event to be the theme of the story.
  4. Construct a narrative web around the core event by:
    1. adding events that causally explain events already in the web;
    2. adding related events that are themselves dramatic/interesting.

Tangential thoughts (tl;dr):
  1. The Worldbuilding StackExchange has a lot of neat discussion from folks discussing hypothetical worlds.
  2. Basically by definition, drama is the set of events that human brains focus on. The more focus-worthy an event is, the more dramatic it is. I suspect that a sufficiently well-developed model for drama should provide insight into how human minds operate, in particular how human minds pick out what to focus on from the vast wealth of data that they receive from their senses. This insight could be very useful in creating efficient implementations of AI.
Natural ChemE
Forum Moderator
 
Posts: 2754
Joined: 28 Dec 2009


Re: Automatic Story Generation

Postby Natural ChemE on April 4th, 2016, 6:33 pm 

bloaf,

I was thinking about ways to define the universe. I think that emergent gameplay'll pop out of some basic physics in a sufficiently large world.

To reason this out like in research notebook, I figure:
  1. Grid-based universe in three spatial dimensions and one temporal dimension.
    1. How fine-grained?
      1. Not too fine, or it'll be too expensive to simulate.
      2. Not coarser than characters, or else characters can't be clever in exploiting physics (engineering).
      3. Dwarf Fortress seems to have one-character-per-grid-space. Finer would be more interesting but more costly.
    2. No time-travel, at least for now.
      1. We could simulate a universe with time-travel, but we'd either have to:
        1. converge the universe rather than just run it (for retro-active time-travel); or
        2. add another temporal dimension, kinda making the universe's complexity with the number of time steps.
        Technically the first approach is just the second approach after the second temporal dimension's run to equilibrium, so the second approach would be more rigorous but crazy costly.
  2. We employ mind-body dualism, having creatures' minds existing outside the physics of the game as opposed to their thoughts effected by in-game physics.
    1. Less interesting, but required to keep computational costs practical.
  3. Thermodynamics:
    1. Grid slots store:
      1. their internal energy, ;
      2. their heat capacity, ;
      3. their thermal conductivity, .
    2. Grid slots have a temperature calculated from internal values as .
    3. Grid slots update their internal energy based on heat fluxes from surrounding grid slots on each time frame.
      1. Heat flux is based on an effective heat transfer coefficient between the two grid slots, combined inversely, such that .
      2. Heat flux is proportional to the temperature gradient.
      3. A grid slot's total change in internal energy due to heat flux is
          .
    4. So, on each time step, a grid slot updates its internal energy by using fluxes calculated from it and its neighbors prior values. The grid slot now has a temperature based on this new internal energy, .
    5. Temperature is controlled at the boundaries.
      1. At the most subterranean level, grid spaces have a set temperature equal to the planet's internal core temperature, .
        1. This temperature is set and cannot be changed.
        2. Equivalently, the planet's core has infinite heat capacity.
      2. At the upper-most level of the atmosphere, grid spaces have a set temperature equal to absolute zero.
        1. Any heat flux to these upper-most squares is considered to be lost to space.
        2. The upper atmosphere will tend to be very cold due to constant heat loss to space.
    6. Heat can be generated through processes like capturing sunlight, chemical reactions, and mechanical motion.
      1. Too lazy to well-model capturing the heat from light absorption, so for now we can just say that ground-level terrain grids naturally generate heat due to sunlight at some regular rate based on area normal to the atmosphere.
      2. Characters might create energy by setting up fires, but otherwise we can ignore most sources for now.
    7. The main narrative advantages of Thermodynamics are:
      1. Natural system where temperatures can change over seasons and environments to make for a more diverse, dynamic universe.
      2. Allow intelligent characters to attempt to modify their environment by doing stuff like:
        1. setting up camp fires, chimneys, etc. to keep warm;
        2. building walls, homes, and other structures to maintain comfortable temperatures.
After that, I'd like to set up some basic Chemistry for stuff like agriculture, marine life (fresh-water vs. salt-water creatures, oxygen levels, poisons, etc.), etc.. It wouldn't have to be too complete or complex; we could just say stuff like how a grid slot with dirt has certain elements that naturally replenish that allow for certain kinds of plant life to grow in 'em, potentially allowing for stuff like crop rotation later on, along with natural reasons why certain (rare?) crops might grow better in certain regions, motivating trade between societies.

But I'm getting stuck on a silly point: what content should grid slots be allowed to have? Presumably grid slots should be able to contain atmosphere, water, and then... what about solids? Like it's easy enough to reason that we could have "earth", "sand", etc., but what about construction materials like wood, stone, steel, etc.? And then creatures, planets, ... I might have to take a break here and think about it!
Natural ChemE
Forum Moderator
 
Posts: 2754
Joined: 28 Dec 2009


Re: Automatic Story Generation

Postby Natural ChemE on April 4th, 2016, 8:40 pm 

Quick start in a C# WPF project called "Story", for MainWindow.xaml.cs:
Code: Select all
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace Story
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();

            (new System.Threading.Thread(() => { DoSomething.Work(); })).Start();
        }
    }

    public static class DoSomething
    {
        public static void Work()
        {
            var universe = Universe.New(new int[] { 250, 250, 20 });
        }
    }

    public class Universe
    {
        public long TimeIndex { get; protected set; } = 0;
        public int[] Lengths { get; private set; }
        public Slot[,,] Grid { get; private set; }
        public double PlanetCoreTemperature
        {
            get
            {
                //  Will likely depend on how deep we model; Earth gets hotter toward the core at about
                //  25degC per km of depth in the range-of-interest.
                //      https://en.wikipedia.org/wiki/Geothermal_gradient
                //  For now, will assume a shallow maximum depth for computational ease.
                return 30;
            }
        }
        protected Universe() { }
        public static Universe New(int[] lengths)
        {
            var toReturn = new Universe();

            toReturn.Lengths = lengths.Clone() as int[];
            var grid = new Slot[lengths[0], lengths[1], lengths[2]];
            toReturn.Grid = grid;

            for (int i=0; i < lengths[0]; ++i)
            {
                for (int j=0; j < lengths[1]; ++j)
                {
                    for (int k=0; k < lengths[2]; ++k)
                    {
                        //  Arbitrarily for now, top half of the world is air, bottom half is ground.  No water yet.
                        grid[i, j, k] = Slot.New(((double)k) / ((double)lengths[2]) < 0.5 ? Slot.SlotTypes.Ground : Slot.SlotTypes.Air );
                    }
                }
            }

            return toReturn;
        }
    }
    public abstract class Slot
    {
        public double InternalEnergy { get; set; }
        public abstract double HeatCapacity { get; }            //  in J/(kg*K)
        public abstract double ThermalConductivity { get; }     //  in W/(m*K)
        public double Temperature { get { return this.InternalEnergy / this.ThermalConductivity; } }

        public enum SlotTypes
        {
                Ground
            ,   Air
            ,   Water
        }

        public static Slot New(
                SlotTypes slotType
            )
        {
            switch(slotType)
            {
                case SlotTypes.Air:     return AirSlot.New();
                case SlotTypes.Ground:  return GroundSlot.New();
                case SlotTypes.Water:   return WaterSlot.New();
                default:                throw new NotImplementedException("Error:  SlotTypes.\"" + slotType.ToString() + "\" not recognized.");
            }
        }
    }
    public class GroundSlot
        :   Slot
    {
        protected GroundSlot() { }
        public static GroundSlot New()
        {
            var toReturn = new GroundSlot();
            return toReturn;
        }
        public override double HeatCapacity
        {
            get
            {
                //  http://www.engineeringtoolbox.com/specific-heat-capacity-d_391.html
                //  lists:
                //       800 for "soil, dry"
                //      1480 for "soil, wet"
                //  in J/(kg*K) at constant pressure
                return 1000;
            }
        }
        public override double ThermalConductivity
        {
            get
            {
                //  http://www.engineeringtoolbox.com/thermal-conductivity-d_429.html
                //  lists:
                //      0.33 for "Ground or soil, very dry area"
                //      0.5  for "Ground or soil, dry area"
                //      1.0  for "Ground or soil, moist area"
                //      1.4  for "Ground or soil, very moist area"
                //  all at 25degC, in W/(m*K)
                return 1;
            }
        }
    }

    public class AirSlot
        :   Slot
    {
        protected AirSlot() { }
        public static AirSlot New()
        {
            var toReturn = new AirSlot();
            return toReturn;
        }
        public override double HeatCapacity
        {
            get
            {
                //  http://www.engineeringtoolbox.com/specific-heat-capacity-d_391.html
                //  lists:
                //      1005 for "Air, dry (sea level)"
                //  in J/(kg*K) at constant pressure
                return 1005;
            }
        }
        public override double ThermalConductivity
        {
            get
            {
                //  http://www.engineeringtoolbox.com/thermal-conductivity-d_429.html
                //  lists:
                //      0.024 for "Air, atmosphere (gas)"
                //      0.020 for "Air, elevation 10000 m"
                //  all at 25degC, in W/(m*K)
                return 0.024;
            }
        }
    }


    public class WaterSlot
        :   Slot
    {
        protected WaterSlot() { }
        public static WaterSlot New()
        {
            var toReturn = new WaterSlot();
            return toReturn;
        }
        public override double HeatCapacity
        {
            get
            {
                //  http://www.engineeringtoolbox.com/specific-heat-capacity-d_391.html
                //  lists:
                //      4182 for "Water, pure liquuid (20[deg]C)"
                //  in J/(kg*K) at constant pressure
                return 4182;
            }
        }
        public override double ThermalConductivity
        {
            get
            {
                //  http://www.engineeringtoolbox.com/thermal-conductivity-d_429.html
                //  lists:
                //      0.58 for "Water"
                //  all at 25degC, in W/(m*K)
                return 0.58;
            }
        }
    }
}
Next to do:
  1. Add in world-generation code.
    1. Need to generate water spaces.
    2. Need to assign reasonable initial internal heat capacity estimates to each Slot.
      • But these estimates don't need to be perfect, since we can do some fake initialization time steps to let the natural physics assert itself before starting the actual simulation.
  2. Add in a time-step method to iterate Universe.

I haven't done out the math to estimate how much RAM/CPU-work will be required for universes of various sizes. I'd guess that we're probably looking at linear scaling against universe size for both, where each Slot will consume some bytes that's about equal to how many parameters it stores - so so far just InternalEnergy, and kinda the Type of the Slot. But then presumably extra parameters for.. whatever else goes into the universe.

Right now I'm working under the assumption that the AI'll tend to eat a lot more of the CPU time than the basic physics.
Natural ChemE
Forum Moderator
 
Posts: 2754
Joined: 28 Dec 2009



Return to Computers

Who is online

Users browsing this forum: No registered users and 3 guests