Multi-Agent Narrative Experience Management as Story Graph Pruning, Stephen Ware, Edward Garcia, Alireza Shirvani and Rachelyn Farrell (2019)

Paper Presentation

​

Management structure

Story graph

Graph pruning

Unexpected player action

This is the end?

Reactive mediation - story reprogramming

Story domain

Options for reaching the end of the game

VS

Action - buy medicine from a tradesman

Action interruption

Character beliefs

The robber holds both coins

All money and medicine from the tradesman

The tradesman and the player are not a criminal scum

Intentionality Pruning

After this pruning, the graph contains 388,318,086 nodes and 1,028,110,791 edges.

Shorter Plan Pruning

After this pruning, the graph has 93,608,267 nodes (76% decrease) and 248,440,557 edges (76% decrease).

Lazy NPC Pruning

After this pruning, the graph has 58,191,971 nodes (38% decrease) and 148,928,950 edges (40% decrease).

Unique Ending Pruning

After this pruning, the graph has 52,262,059 nodes (10% decrease) and 138,072,434 edges (7% decrease).

Goal Priority Pruning

After this pruning, the graph has 30,149,245 nodes (42% decrease) and 76,006,520 edges (45% decrease).

Cycle Pruning

After that, the graph has 23,159,543 nodes (23% decrease) and 56,783,502 edges (25% decrease).

Arbitrary Pruning

After this pruning, the graph has 20,365,197 nodes (12% decrease) and 49,669,363 edges (13% decrease).

Dead End Pruning

After dead ends pruning, the graph has 20 365 187 nodes (5% decrease) and 49 669 351 edges (2% decrease).

Goals

• The story always ends.

​

• The NPC's behavior looks reasonable.

​

• Their methods produce believable NPC’s behavior above what people would naturally perceive in this domain, no matter what policy the experience manager uses.

Experiment design

• 20 participants.
• Preliminary training.
• Two versions of the game - with random pruning and intellectual pruning.
• Random division of participants into two groups, playing versions of the game in a different order.
• The requirement to complete each version at least twice, the chance to play up to ten times.
• A questionnaire with four questions, which asks for the version of the game that is more suitable for the description.

Results

In statistical testing, the p-value is the probability of obtaining test results at least as extreme as the results actually observed, under the assumption that the null hypothesis is correct.

Conclusions

• The story graph will be difficult to shorten for most domains, but the work has been instructive, allowing the long-term implications of each experience manager's decision to be considered.
• These ideas can be applied as heuristics to larger graphs to be generated on demand.
• In areas of storytelling such as this, random action is a surprisingly good base.
• The strongest limiting factor is that the story graph is Markovian, while the stories themselves are inherently non-Markovian.

My review

Pros:

• Very detailed.
• Good described experiment.
• High quality in general.

Cons:

• Sometimes explanations are missing.
• Experiment not well conducted - few questions, few participants.
• It is de facto impossible to repeat.

Credits

• Denis Iudin - Text, graphs
• Daniil Dudkin - Art

Thanks for attention!