Playspecs: Regular Expressions for Game Play Traces

Authors

  • Joseph Osborn University of California, Santa Cruz
  • Ben Samuel University of California, Santa Cruz
  • Michael Mateas University of California, Santa Cruz
  • Noah Wardrip-Fruin University of California, Santa Cruz

DOI:

https://doi.org/10.1609/aiide.v11i1.12803

Keywords:

formal modeling, verification, automated testing, automata theory, regular expressions, analytics, telemetry, game dynamics, temporal logic

Abstract

We introduce Playspecs, an application of omega-regular expressions to specifying play traces (sequences of game states or events unfolding over time). This connects the automated analysis and model checking of games to the literature on formal software verification via Bu ̈chi automata. We show how to define desirable or undesirable sequences of game events with Playspecs and how associated algorithms can find examples (or prove the impossibility) of such sequences. Playspecs have two main benefits over existing techniques for specifying the behaviors of a game over time. First, they offer a scalable commitment to formal modeling: the same Playspecs can filter existing traces gathered by telemetry, search for satisfying traces using existing game code, or drive formal verification when paired with a logical model of a game. Second, Playspecs' syntax can be customized for the game engine or game in question so designers may write specifications using their game's native vocabulary. We define Playspecs' syntax and semantics (modulo gamespecific customizations) and outline algorithms for each of the applications mentioned above, providing examples from the social simulation game Prom Week and the puzzle game engine PuzzleScript.

Downloads

Published

2021-06-24

How to Cite

Osborn, J., Samuel, B., Mateas, M., & Wardrip-Fruin, N. (2021). Playspecs: Regular Expressions for Game Play Traces. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 11(1), 170-176. https://doi.org/10.1609/aiide.v11i1.12803