Thursday, March 5, 2015

Using Twine for Games Research (Part III)

Where we last left off, I described Twine's basic capabilities and illustrated how to use them in Twine 2 by way of a tiny hack-and-slash RPG mechanic. You can play the result, and you should also be able to download that HTML file and use Twine 2's "import file" mechanism to load the editable source code/passage layout.

Notice that, in terms of game design, it's not much more sophisticated than a slot machine: the only interesting decision we've incorporated is for the player to determine when to stop pushing her luck with repeated adventures and go home with the current spoils.

What makes this type of RPG strategy more interesting to me is the sorts of decisions that can have longer-term effects, the ones where you spend an accumulation of resources on one of several things that might have a substantial payoff down the road. In a more character-based setting, this could be something like increasing skill levels or adding personality traits.

Often, the game-design goals of these features are multi-faceted: consider the shopping mode of Kim Kardashian Hollywood, for a recent and topical example.

(Screenshot via Michelle Dean.)

The clothing the player buys does have mechanical function (in terms of completing projects faster, for example), but it also has the less tangible function of giving a player a sense of control over which combination of in-game artifacts persist with their avatar as they move through the world.* Because these artifacts are subdivided into independent components (like real clothing), the player can combine them in ways that are not pre-anticipated by the game -- no one enumerated every possible combination; components have to systematically make sense in combination. In other words, clothing is a composable mechanism for customizing player experience.

Lest you think that this kind of visual composition wouldn't translate well to a textual medium, I invite you to play a few Twine games like Porpentine's UNTIL OUR ALIEN HEARTS BEAT AS ONE and Whisperbat's Candy Ant Princess.

These examples probably use an old Twine 1 macro called cyclinglink, which doesn't (AFAICT) have a great replacement in Twine 2 -- but aside from the nice in-line interface, all that's really going on is that the text that's shown once the player confirms her choices gets bound to variables that are then rendered later in the game.

Note again that, while each category of item has to be hand-enumerated by the game designer, the combinations do not. For some deeper thoughts related to this idea, take a look at the Icebound team's post on combinatorial narrative and Allison Parrish's work investigating various units of text for which it makes sense to deconstruct and recombine.

In our hack-and-slash game, we'll want to associate certain traits or properties to certain items in the game, such as a numeric damage trait to a weapon. In the rest of this post, I'll walk you through using Twine 2's datamap construct to do so. (Note: I am trying not to assume pre-existing programming experience in this tutorial, but I hope that experienced programmers can gain something from the explanation anyway.)

Monday, February 23, 2015

Paper Draft: "Ceptre: A Language for Executable Game Descriptions"

I briefly interrupt this recent series on Twine to announce that I've recently completed a paper draft on my thesis programming language, Ceptre (pdf, 8 pages):


We present a language called Ceptre in which we unify the concepts underlying several rule-based game design tools, such as Kodu, PuzzleScript, and Inform 7. We illustrate how to capture common mechanical idioms found in these frameworks, such as movement, item acquisition, and agent-based simulation, without specializing anything in Ceptre to those ideas. By distilling the essence of several systems in one using a small, general set of primitives (based on linear logic), we provide a setting in which to recombine fragments of existing world models and to define new ones, freeing designers from genre constraints and assumptions. Our eventual aim is to implement this language as a prototyping tool for game logics and mechanics.
From a PL perspective, this paper introduces the ideas behind forward-chaining linear logic programming, as well as the construct of stages that I extend it with, in order to describe game mechanics.

Using Twine for Games Research (Part II)

This preliminary discussion introduced my thoughts on using Twine as a tool for creating prototypes for games research. I'll start with documenting my first case study: a hack-and-slash RPG-like setting where the player character has a record of attributes ("stats") that evolve through actions that turn certain resources (money, health, items) into others. I've selected this hack-and-slash example because it falls outside the canonical "branching story" domain thought to be Twine's primary use case, but it is not too much trickier to implement. It relies crucially on the management of state in ways that simple branching stories would not, but it does so in a fairly straightforward way.

If all goes well, this post may also serve as a tutorial on the "basics" of Twine (links + variables + expressions). In particular, I'll be using Twine 2/Harlowe, and I haven't seen many tutorials for this new version published yet.

To me, the main "research questions" to ask about this kind of game are:
- What are the feedback loops? When I can do certain groups of actions over and over again, what is their cumulative effect?
- Does play ever stagnate -- i.e. is there a fixed point? Or, what does it mean for a game to stagnate even when I can always increase some stat? ("Click this button to increment a counter" is not very fun if that's all there is to it.)
- Where are the interesting strategic tensions? That is, at which points in the game does the player need to make a difficult decision? What makes it difficult?

All of these questions can be stated in terms of (though not necessarily answered by) a Twine prototype, even if the overall vision for the game involves much more complex rendering and controls. This is the same principle that leads to paper prototyping, but with computational support, which makes things like analysis and playtesting a lot less human-labor-intensive.

Friday, February 20, 2015

Using Twine for Games Research (Part I)

Recently, someone sent a request over the DiGRA list for experiences and information related to academics learning to make games. I replied with a bit of handwavy proselytizing for Twine, copied (and slightly edited) below:
For a surprisingly diverse range of game design logics, Twine makes an excellent prototyping tool for research. Carolyn Vaneseltine writes about using Twine for prototyping here: 
I'd really like to see Twine in use especially for games *research*, for a few reasons:
  • Deployability. It's absolutely the "most time-effective path" from game idea to "an arbitrary person with the internet can play it."
  • Resilience to bitrot. As long as people care about creating backwards-compatible web standards and supporting JavaScript, Twine games will be playable. If we consider our research to be describing "permanent ideas," then people need to be able to play with those ideas decades later!
  • Most people find it quite easy to learn, and it supports quite a range of mechanics, as long as you can conceptualize them in some turn-based way. It's really one of the better settings for thinking about the *systems* in games first without having to muck about with event handling and graphics rendering.
  • Reusability/reproducibility. If the point is to communicate some system of mechanics, then I think Twine works pretty well because the source code is usually readable, easy for the author to release, and easy for outsiders to manipulate. 
Of course, I realize a lot of research goals in games involve aesthetic experiences that Twine won't help at all with creating. But I think it's overlooked as something that would often suffice for the "proof of concept" work we do in research, where instead people sink lots of time into clunky 3D simulations that distract more from the research than they contribute to it.
Afterwards, though, I began to question my own recommendation. I've tried using Twine for research-like ideas (see: numerous attempts at replicating the behavior of Prom Week as a text game) with very limited success, and certainly nothing leading to publication. Nonetheless, it has still been my favorite tool for dabbling in digital game design due to the lack of assumptions it imposes about what kind of game you are making, and I still feel in my soul that it should be possible to communicate this generality in a compelling way to the research community.

So, since the contributors to Twine recently released a new, web-based editor along with a tantalizing new macro and expression language, I decided to launch a period of focused study using Twine to implement some "classic" prototypes and document my roadblocks. I'll use my blog as a "lab notebook" for these experiments, which will incidentally also contain a review/critique of Twine 2.

Before I get into that, though, I want to be more explicit about what I mean by "games research." To be quite honest, the range of research activities discussed on the DiGRA list is quite mystifying to me, and I would love it if someone could write an overview of "things people at universities are doing that they call games research." I have a sense that there are at least the following categories:

  1. Humanities-based scholarship on the cultural context and contents of games, patterned off of "media studies." They ask questions such as how gender and race are represented in the assets and stories of games, as well as how game mechanics reflect cultural values.
  2. Human-Computer Interaction-based study of how humans play digital games, asking questions about what happens to them psychologically under different conditions and whether games can be designed to induce specific experiences (such as education).
  3. AI-based study of how games can simulate more realistic or engaging experiences. A lot of the questions seem to surround programming the behavior of non-player characters, including everything from pathfinding in geometric space to dialogue and storytelling.

My personal studies align most closely with the third category, although because my background is programming languages and not AI, I think of the interesting questions as less about characters and more about representation of game states and behaviors, i.e. "how do we model arbitrary fictional worlds that react to input?" and "how do we reason about the semantics of how these worlds evolve?"

Note that I would also count something like, say, an operating system as a "fictional world," but on the other hand, I'm not as interested in games where the primary and necessary challenges are things like "very quickly calculate the outcome of lots of geometric and physical constraints changing and render them at a certain frames-per-second requirement." So in that sense, what I'm calling "games research" is really a particular intersection of formal system modeling and games, and that's the focus of my current hypothesis under examination (that Twine is a useful tool for stating and answering questions about these systems.)

This post has already exploded in length, so I'm going to save the actual results of experiments so far for the next post. Meanwhile, I'll describe some examples I intend to describe as case studies:

  • Hack-and-slash: player character has a record of attributes like health and inventory and can strategically alternate rest, adventuring, and spending coins (won through adventuring) on more powerful adventuring tools.
  • Dining philosophers: classic problem in synchronizing concurrent systems made interactive by allowing a player to control (all, one, or several?) philosophers: they can pick up a fork on the table, set down a fork they are holding, or eat if they are holding two forks.
  • Social simulation a la Prom Week: multiple characters with sentiments toward one another that can change via player-selected pairwise interactions.
The central questions I'll be asking about these examples are (a) is it easy to encode in Twine, and if so, how is it done? and (b) what do we learn from the encoding? I'll try to pose some example-specific questions before diving into the implementation, as well.

Friday, January 2, 2015

What "safety" means to a PL designer

I just finished reading Justus Robertson & R. Michael Young's INT 2013 paper about their work using the fact that players have incomplete knowledge of a simulation to accommodate incongruous player choices -- those that don't meet the story's goals -- by selectively rewriting the past. I made some sketchnotes summarizing the paper.

Of course, if all one wanted to do were to ensure an authorial goal (e.g. that Batman goes to Harvey's location), one could just simply make all seemingly-significant "choices" lead to the same scene. What I find interesting about this work is that it ensures that any railroading of this form is done in a perceptually consistent way, one that won't leave the player wondering how it was possible for the outcome to occur, because what they saw was consistent with their knowledge. There's a world model that led to Harvey being in one place and Rachel being in another, and that world model can change as long as it goes unobserved. The planner will only create changes that maintain this property.

This guarantee -- that the world model's rearrangements don't disturb perceptual consistency -- is, in a PL designer's terms, a form of safety. It's a property of a planning system that can be modeled in a logical formalism and checked with a computer.

The majority of the time, if you learn about type systems and type safety, you learn that it means preventing program crashes and mundane bugs (like applying a non-function). In sophisticated type systems, it might mean ensuring that you never dereference a null pointer or that your concurrent program is deadlock-free.

Because we talk about safety properties like these the vast majority of the time, I think people understandably get an impression of type- and logic-based programming language design as needlessly uptight for creative, freewheeling endeavors like game creation. Jonathan Blow certainly thinks so. It's as though we're suggesting wearing a lifejacket every time you go swimming, when all you wanna do is splash around in the shallow end.

I think the word "safety" is kind of a PR disaster for PL folks. Yes, sometimes we really do have safety-critical systems that we want to ensure have no bugs whatsoever, because actual human lives are at stake. Sometimes we care about the intersection with security & information flow, which affects people's personal information. And of course no one likes it when things crash or we get our code subtly wrong. But must we sell the Big PL Ideas as being fundamentally about never making mistakes, or preventing as many mistakes as possible, as opposed to actively enabling creative work, empowering people to express their design intent in a way that can, for instance, create more compelling game experiences?

Wednesday, December 31, 2014

Accumulated Braindust

Conor McBride posted a really intriguing list of research problems on his mind at the end of this year, and I thought it was an amazing idea, so I'm copying it. I have little notes I've made to myself in paper notebooks and text files, but rarely do I go through and collect them all in one place.

  • Computer-checking linear logic program invariants (and other, perhaps variant, properties) - what is an appropriate metalogic to reason about linear proof search?
  • Generative invariants: what is their expressive range? Does it have something to do with (co)inductive datatypes or their dependent generalization? Can we extend them to describe general structures such as graphs (with no self-edges or multi-edges), perhaps by allowing quantification over, and introduction to, *sets* of terms rather than types?
  • Ordered logic - are there more connectives? constrained replication and mobility, e.g. a propositional operator *A meaning A can be replicated "in place."
  • What types of bugs exist in sandbox/emergent-behavior games? Could there be a database of these, like a version of "the strange log" w/reference to code or otherwise more concrete structures?
  • Concurrency and multiagent coordination, interactive storytelling, etc - what formal connections can be made? In prior work on validating interactive stories, the types of bugs and properties include things like deadlock and liveness.
  • Concurrency & (epistemic?) modal logic - can a thread/actor/whatever be typed as belief wrt a modal principal?
  • Can one do automatic reasoning about the lifetime of objects in a linear logic program?
  • Chu spaces and n-category models of concurrency - how do they relate to linear logic/CLF?
  • What's a good datatype for hypertext?
  • What's a good notion of subordination for linear logic? should it exist at the atom level or rule level? what does it have to do with causality? 
  • Can one completely unify verbs & nouns in standard parser IF? i.e. reimagine looking, walking, taking etc. as uses of items like sensors, wheels, grabbers that have to be collected + a single "apply" verb (kind of like the Hilbert system of IF games, lots of axioms & modus ponens). are sensors, grabbers, and wheels "canonical" in some necessary sense, or are they just better able to simulate human experience than other interfaces?
  • Is there such a thing as a set of composable macro-building-blocks ("design patterns") for interactive narratives/nonlinear quests? what is a (game) design pattern -- can they be formalized? how are they composed?
  • Can one create a purely-human-mediated decentralized roleplaying system, i.e. one with no GM but still incentives to create interesting scenarios through conflict? Can in-person story games break away from the idea of *role*playing specifically and think about controlling parts of the story which may not encompass or be limited to the actions of a specific character? Does that deprive players of an essential kind of agency?
  • How can I make (or make a tool for making) multipanel hypertext, i.e. so that I can make the thing I wanted Origins to be able to evolve into - multiple loci of control that can sometimes converge and re-diverge?
  • When I design card games, the kind of bug I always have is in failing to create an incentive for a certain action, or making strategy too obvious. Can one model games in a way that allows reasoning about multi-human-player games in terms of incentives, beliefs, partial information, etc, and all of the decision theory/game theory it implies? Maybe using epistemic modal logic (again)?
  • Player-controlled markets: Can we make games where resources actually have to come from somewhere (like other players), and are finite? Like imagine there were no NPC-controlled item shops; the players had to run them. (I know there are games where players control the economy, but usually this is partial; items can still be acquired from quests/NPCs.)
  • Narrative rearrangement: Is there a way to extend the idea of fridge poetry/word rearrangement/replacement mechanics (like in Today I Die) to the narrative level? What's a "unit of narrative" and how does it compose? Would CLF's "natural" answer to this be compelling?

Thursday, December 18, 2014

What do concurrent traces have to say about determinism?

Let's talk about execution traces of concurrent programs, and which ones we consider "the same."

In concurrent programming models, your program constructs allow you to specify computation as indexed by a particular independent execution unit ("thread", "channel", "actor" -- at this level of detail, we can use these terms interchangeably), and to specify how those units communicate or interact. This means you have one artifact, the static program, that gives rise to a set of traces, or possible executions -- records of which parts of the program were evaluated in what order.

We might say that if this set of program traces has only one element, then the program is sequential. But the accuracy of this statement depends on how exactly we represent a program trace! If we are forced to give a total ordering on all computation steps -- unifying a trace with an "interleaving of instructions" -- then yes, the only class of programs for which every trace is "the same" is those that are deterministic and sequential.

But note that this representation precludes deterministic parallel programs, a notable use case for concurrent programming (see Lindsey Kuper's excellent post on the relationship between parallelism and concurrency). You could have two cores simultaneously computing independent things, each of which are totally deterministic -- but you cannot give a total ordering on the steps of execution. You could conceivably do so with respect to a global clock, but such an approach seems uninformative for reasoning about the program you wrote irrespective of the hardware it's running on.

Instead, we can represent an execution trace as a partial ordering of evaluation steps. Or, in other words, we can treat two totally-ordered traces as the same whenever their ordering choices only differ for independent computational components.

This equivalence relation is what literature on CLF refers to as "concurrent equality":

let x1 = e1 in let x2 = e2 in t
is concurrently equivalent to
let x2 = e2 in let x1 = e1 in t

iff e2 doesn't use x1 and e1 doesn't use x2.

Explicating a full trace in terms of its concurrent structure reveals the aforementioned partial order, and means we can visualize the trace as a DAG.

For example, here's a CLF program to sort a list represented as a mapping from locations to elements, by swapping any two adjacent elements that aren't in order, bubble-sort-style:

When we run it on the described 3-element input, a possible trace of the output has the following structure:

There's another possible trace, one that swaps the second and third array positions first, rather than the first and second. Or, viewing the swaps pictorially, there are two orderings for swaps:

We can identify these traces as distinct because of the different dependencies they introduce; each ordering between two swaps is necessary and non-arbitrary. Note: the program is (observably) deterministic; both executions take the same input to the same output.

On the other hand, here are the possible traces for sorting the four-element array [4,3,2,1]:

Again, there are two of them. But that number depends on the syntax I've written them down in. If I required only one swap per line -- one "at a time" -- then I'd have to make an arbitrary choice about which of two independent swaps to do first (e.g. (4,3) or (2,1)?).

In this sense, the 4-element sort traces have concurrent structure where the 3-element traces do not. Remember that both programs are deterministic, and both have multiple possible interleavings of computation units ("scheduler nondeterminism"?). But the difference between these programs is, I think, not well articulated by existing concurrency terminology. Or perhaps it's appropriate to use the term parallelism in this setting? In one set of traces, there is nondeterminism but no parallelism; in the latter set there is both; in Tamara there is parallelism but no (essential) nondeterminism. It still feels like the wrong word, though, because there's nothing inherent about "running computation on different cores simultaneously"; it's just a lack of dependency between actions.

Anyway - what I find so compelling about CLF's notion of concurrency is that it isn't something we talk about as a property of a behavior, it's something we can talk about as a property of a "static artifact" -- the script to a play, or an investigative report of people's independent/interactive behavior. Something to be analyzed after-the-fact of that behavior.

It's my hope that someday we can stop thinking of concurrency as something only related to low-level system processes and instead use it to form compelling mental and programming models of multi-agent behavior.


Edit: Section 7.2 in this ebook about multiagent systems contains a strikingly similar discussion to the one I've laid out here.