Monday, August 3, 2015

Finishing my disseration; new draft on Ceptre!

This blog has been silent for some time now due to me putting all of my writing energy into a draft of my dissertation! It has now been sent to my committee, and I defend on August 31st. For now, the draft is in private circulation, but I'm not being picky about who reads it: if you're interested in looking at a copy, let me know. I'll be sure to post a link here once the defense draft is ready.

Meanwhile, a new paper on my game modeling language Ceptre (a fundamental piece of my thesis) has been accepted to AIIDE 2015! Here's a recent draft.

In the next few weeks, I'm going to try to get Ceptre into shape with enough documentation that brave-enough souls can experiment on their own. Meanwhile, the GitHub repo is available, and I'm happy to assist anyone who's interested in playing with what's there.

Tuesday, May 5, 2015

Linear logic proof sets as split-screen hypertext

There is often some confusion when I discuss using linear logic to capture narrative structure. There are two interesting kinds of branching in linear logic, but we usually only talking about branching structure in narrative if it's interactive narrative, i.e. if the branches represent choices or alternatives between outcomes in a story scene. But there is also branching structure in many non-participatory narratives: there is a causal order of events, which is usually not a strictly total ordering. For example, scenes with different sets of characters, whose proceedings don't depend on one another's outcome, may be told in arbitrary order and still be coherent (though of course coherence isn't necessarily a narrative's goal, or its only goal).

The latter kind of branching can be thought of as spatial branching (for a sufficiently metaphorical notion of space), in the sense that different components of the narrative universe can evolve independently, then join together when they need to interact.

Spatial branching contrasts with temporal branching, which is the sort you get from hypertext and other narrative forms typically described as "branching." Choices are made, which determines one linear path through the narrative. Typically the experience of traversing such a path is oblivious to the alternative paths, just as real temporal experiences are oblivious to timelines in which we'd made different choices -- although a great deal of hypertext is designed with the intent of multiple traversals, which imparts a sort of metaexperience evocative of time travel.

In standard logical terms, spatial branching is conjunctive while temporal branching is disjunctive. Multiple independent events can happen "at once" -- "Lola asks her father for money and Manni asks his friend for money" -- but only one event from a set of alternatives can apply to a given piece of narrative state: "Lola dodges the dog on the stairs or she trips on the dog and injures her leg."

In linear logical terms, the more relevant distinction is additive vs. multiplicative branching: additive branching maps to sets of alternative routes from a single narrative state, where multiplicative branching refers to partitions of the state evolving independently.

The distinction also comes up in discussions of nondeterminism and concurrency: a program which asks for a random coin flip and says "heads" or "tails" depending on the answer can be seen as nondeterministic in a different way from a program with two threads, one of which prints "heads" and the other "tails."

Linear logic programs can have both kinds of nondeterminism/branching, but what's interesting is that after you run them -- i.e. after you create a proof a given linear logic formula -- you've selected a choice for all of the temporal branching points, but the resulting proof can still be seen as containing conjunctive, or spatial, branching structure. (I've elaborated previously on the idea of linear logic proofs' concurrent structure.)

One way of connecting linear logic to branching stories, then, is to take the one kind of branching that's left in proofs and map it to the one kind of branching in hypertext stories, which is exactly what we did for Quiescent Theater. The odd thing about this project is that there's a mismatch: we generated disjunctively branching stories from the conjunctively structured proofs. This has the kind of interesting effect that choices in the resulting stories act like "following" particular characters through their experience of the events of the story, with the ability to jump to new characters when the one you're currently following interacts with them. This is also the mechanic in the participatory theater experience Tamara, which partly inspired the experiment -- in fact, when Rob initially proposed the concept, I didn't understand it precisely because of the mismatch between types of branching; only after attending a performance of Tamara did I see the potential for that mismatch to make a kind of sense.

But I've recently been thinking about how to make a more precise correspondence between both kinds of branching structure present in branching + multi-agent narratives, and both kinds of concurrency in linear logic. I think I figured out how today. It requires that we extend traditional hypertext with a notion of compositional components that can be rendered simultaneously -- e.g. by splitting the screen. I've experimented with split-screen hypertext before, but this would require something quite a bit more sophisticated: any click in any panel of the screen could introduce new splits, merge arbitrary panels together, and depend on the state of other panels (in addition to its own state).

With that interpretation, a forward-chaining linear logic program -- or perhaps more precisely, a set of proofs generated from such a logic program -- can be rendered as follows: initialize the page with as many panels as there are atomic resources in the initial context. Provide an interface for selecting any subset of panels. For each selected subset, display a (possibly empty) set of clickable links corresponding to the set of transitions that apply to that resource set. (I originally imagined those links appearing in every relevant panel, but they could equally well appear in a completely separate global panel, modulo UX concerns.) For example, a par of rules [ r1 : a * b -o c ] and [ r2 : a * b -o d ] would render as 2 links when the [ a ] and [ b ] panels are both selected. Then a link click on [ r1 ] would merge [ a ] and [ b ] into a single panel with contents [ c ]. For first-order logic programs (i.e. ones with logic variables), we would need to disjunctively-nondeterministically generate several alternative structures and do a similar transformation on proof steps rather than on whole programs.

I think this idea has been explored in academic study of hypertext from a literary point of view before: this paper on conjunctive hypertext seems relevant, though I'm not entirely sure the structural observations I'm describing are as deep as whatever narratological points they are making.

P.S. If anyone wants to help me build the target interface I described, please let me know. My skills at making visual interfaces look the way I want are... probably not as good as someone else's reading this. ;)

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?