User-Driven Narrative Variation in Large Story Domains
using Monte Carlo Tree Search

Bilal Kartal, John Koenig, and Stephen J. Guy

Planning-based techniques are powerful tools for automated narrative generation, however, as the planning domain grows in the number of possible actions traditional planning techniques suffer from a combinatorial explosion.  In this work, we apply Monte Carlo Tree Search to goal-driven narrative generation. We demonstrate our approach to have an order of magnitude improvement in performance over traditional search techniques when planning over large story domains. Additionally, we propose a Bayesian story evaluation method to guide the planning towards believable narratives which achieve user-defined goals.  Finally, we present an interactive user interface which enables users of our framework to modify the believability of different actions, resulting in greater narrative variety.




[Narrative Variety]

        Citizen Arrest Configuration

     In this configuration, the believability of citizen arrest
     action is set high, resulting Bob arresting the murderer.

        Officer arrest configuration

     In this configuration, the Inspector Lestrade arrests the
     murder due to low believability of citizen arrest action.

[Comparison to Traditional Search Algorithms]

Our proposed approach using Monte Carlo Tree Search (MCTS) outperforms other search techniques such as Breadth-First Search, Depth-First Search, and Best-First Search. 
(a) Even for a small search budget, MCTS outperforms other methods
(b) The gains improve dramatically for larger budgets.

[Heuristics for Performance Improvement]

(a) For small search budgets (<500K nodes explored) the search heuristics tested had only a moderate effect on performance. 
(b) For large search budgets, the advantage of the rollout biasing heuristic can be clearly seen.  Additionally, while the selection bias heuristic helps with small budgets it tends to get stuck in local minima.