Analyzing Computer Game Narratives

Key insights

6 takeaways

01
The optimized search reduced average branching factor sharply on most benchmarks, from 122 to 10 on RTZ Chapter 2 and from 62 to 5 on MCHEVA.See it on page 7
02
DPRYKH was the hardest benchmark for the optimized search because many player commands remained even after optimization.See it on page 7
03
The authors observed that search time often decreased as maximum search depth increased, which runs counter to their initial expectation.See it on page 7
04
The authors report that a prior SAT-based solver could not complete RTZ Chapter 1 after several days of execution time, which the new approach improves on by orders of magnitude.See it on page 6
05
Pre- and post-condition dataflow analysis lets the search skip action pairs whose conditions are incompatible, reducing the branching factor.See it on page 4
06
Measuring time to the first winning solution, rather than enumerating all solutions, was chosen because complete enumeration is dominated by reporting time.See it on page 6

Summary

The paper by Clark Verbrugge and Peng Zhang of McGill University presents a formal reachability analysis system for interactive fiction (IF) game narratives, written in the PNFG language. The method is an exhaustive, depth-first search of narrative states, optimized with dataflow techniques borrowed from compiler optimization. The authors focus on winnability, meaning the path to win the game, and benchmark the system on six narratives: two chapters of the commercial game Return to Zork, and four amateur narratives written by students as a course assignment. The benchmarks range from 387 to 1,472 lines of code, with 8 to 22 rooms each.

The optimized search was measured by timing how long it took to find the first winning solution, averaged over 10 attempts per depth, with a 5-minute limit per search (6 minutes for DPRYKH). The authors report that the approach finds solutions within these bounds for all benchmarks at most search depths. The DPRYKH benchmark was the most challenging because of its many global commands and resulting large branching factor. Average branching factor dropped from 69 to 44 for DPRYKH, and from 122 to 10 for RTZ Chapter 2.

An unexpected result was that search times often decreased as maximum search depth increased. The authors attribute this partly to minimum-length solutions being rare.