Friday, November 27, 2015

Conference Report: AIIDE 2015

Earlier this month, I traveled to Santa Cruz, CA for two purposes: starting a new postdoc with the Expressive Intelligence Studio (which I'll be working on remotely for the time being) and attending AIIDE, a conference about AI in games, at which I was presenting a paper. I also attended two pre-conference events, the INT workshop on narrative tech, and the EXAG workshop on experimental AI in games.

In this post, I want to mention a few highlights among the many exciting things I learned at the union of these activities, and draw out some common themes.

1. The state of the art in computational narrative is social & emotional believability.

INT this year was joint with SBG, Social Believability in Games, and the themes of the talks blended so seamlessly that it was difficult to remember there were actually two workshops. Iolanda Leite gave the keynote on human-robot interaction; specifically, how to create conversational agents that would maintain children's interest over long-term durations, rather than the usual focus on a single interactive session. Her talk set the stage for other presentations on conversational NPCs, social mediation AI for MMOs and social networks, and the production of socially and culturally appropriate behavior.  I also had several chances to chat with members of the budding research group at American University consisting of UCSC alums Mike Treanor, Josh McCoy, and Anne Sullivan, who organized SBG, and learn about their work on the next generation of Ensemble, a scripting tool for social physics.

The underlying premise of all of this work seems to be that responsive narrative depends on socially believable characters. Meanwhile, social believability is still really hard! There are a lot of pieces to it, like cultural context, social norms within that context, the human interactors' personal/emotional context, the fact that humans remember, forget, and lie (which there was actually an EXAG paper about), and more.

So I'm of two minds about this premise. On the one hand, there are an awful lot of interesting problems in social believability, and I'm really excited to see what comes out of that area in the next few years (especially if epistemic modal logic might be involved). On the other hand, I think it's a mistake to suppose that advances in computational narrative can't be made without it. In some ways, stories are a lot simpler than characters, while it might be tempting to assume that good stories will naturally emerge from any set of sufficiently interesting characters (the premise of reality television), I find myself increasingly intrigued by the possibility of operationalizing approaches like the collaborative storytelling system Microscope, wherein the unit of content isn't a character interaction but an era, epoch, or historical event, each of which may involve characters as instruments, but more fundamentally, must fit together in a global way to meet the demands of narrative structure.

Somewhat tangential, but also related to social and narrative games: at AIIDE proper, Mitu Khandaker-Kokoris gave an amazing keynote (available to watch online) making the point that, often, what makes systems feel social is less about detailed digital realization and more about the gaps that we humans fill in with our willingness to suspend belief and project humanity onto said systems. Katherine Isbister also gave a keynote (unfortunately not recorder), centering on many similar themes, especially the idea that games can be vehicles for emotional and social bonding, providing context for her work in wearable game interfaces. I strongly recommend following Mitu and Katherine's groundbreaking work.

And speaking of social play and storytelling...

2. There's a lot of excitement right now at the intersection of human-driven collaborative storytelling and computer-driven play.

Ian Horswill gave a cool talk at EXAG on generating Fiasco playsets with Prolog, the upshot of which was basically "play Fiasco" (I still haven't), but I'm also enamored of the idea of using computational assistants for primarily human-driven improvy storygames.

Markus Eger spoke at INT about operationalizing PLOTTO, the "master book of all plots," and, at Ian's suggestion, a bunch of grad students and I got together to do a story jam where we semi-democratically made choices about which plot development options to accept until we reached a terminal node. Some notes and sample output here. An interesting thing we learned was that the plot developments don't necessarily come in causal order, but in many cases it is possible to read a development as further elaboration or backstory on a previously-described situation/event. This fact again touches on the idea of iterative and global, rather than linear and simulationist, story generation. (Of course, a downside of PLOTTO is that it's a 1-Markov chain in terms of expressiveness, i.e. it only maintains a history of the previous choice to influence future choices. So there wind up being a lot of loose story threads that never get called upon again later.)

I also spoke at length to various attendees about interactive/immersive/participatory theater. It seems like tons of games people know about, and are intrigued by, Sleep No More, the multi-room concurrent production in New York. (I still need to get my butt on an Amtrak to go see it, but I've heard and read plenty of descriptions at this point.) Pittsburgh's own thriving experimental theater scene has introduced me to Tamara, which I wrote about previously (on this blog and in my thesis), as well as Strata, a gauntlet of immersive/interactive vignettes, and Uncumber's suite of interactive work, including Her Things, a room full of explorable artifacts designed to be pieced together in pursuit of a narrative, held together by improvising actors. These productions serve as interesting points in a design space for collaborative storytelling, in which roleplaying, storygames, and computational fiction all share certain objectives -- blur the line between audience member and story-maker -- but which differ substantially in others (allow participants to alter the story fundamentally, or simply to choose a trajectory through it? allow participants to interact with one another? are participants characters or observers?). I'm very interested in how computational approaches can learn from recent participatory theater experiments and vice-versa.


While I have quite a bit more to say about the conference, I'll curtail the post here in the interest of length and thematic coherence.

Friday, November 6, 2015

How to get a Ph.D. in computer science if you're me

Recently, I've been privy to a lot of advice that people give to beginning and prospective graduate students in computer science. The "grad school survival" talk given to CMU's CS department is one that's been passed down through a few generations; PLMW at SPLASH is a workshop (affiliated with a few different PL conferences, now) with similar aims. At both of these events, I served on panels to answer questions. But by watching the main presenters' talks, I quietly accumulated critiques of the standard advice, and it occurred to me that my experiences might have value to some folks if expressed in longer form.

As the title of this post suggests, all advice is subjective. The reason that I think people give "advice," even knowing this fact, is that otherwise we're telling very personal stories about experiences that might still be raw. Advice is an abstraction over experience. But abstraction yields generalization, and generalizations require care when referring to human lives --- so I'm going to try my hardest to be honest about where serendipity and immutable facts about myself played a role in my experience.

Monday, September 28, 2015

Strange Loop 2015 Highlights

I've returned from Strange Loop in St. Louis, a tech conference whose talks commonly include themes like PL, web dev, distributed systems, functional programming, and tech education. I was giving an invited talk at the Future Programming Workshop (FPW), part of the Strange Loop preconference.

This year, I had to leave early, missing half of Strange Loop proper, but fortunately there are recordings of all the talks up on YouTube! Unfortunately, the hallway track can't be recorded for delayed consumption, and I'm still bummed to've missed out on talking to a bunch of people I either failed to meet or only had one passing conversation with.

That said, even two days was enough time to come away with plenty to write and think about, and I'd like to share some of my personal highlights of the conference with you.

"I See What You Mean" by Peter Alvaro was the first keynote talk, kicking off Strange Loop. In it he tells the story of Dedalus, a temporal logic programming language inspired by Datalog, for declarative distributed programming. While the technical aspects of this talk are very close to my heart, Peter also does a fantastic job of storytelling and pontificating about the pleasures and perils of designing nice languages for messy domains.

"Unconventional Programming with Chemical Computing" by Carin Meier was the next talk I saw after Peter's, and it was rife with connections to declarative distributed computing. Chemical computing is a very linear-logic-like (in fact, multiset-rewriting) abstraction, where programs are sets of "reaction" rules that have molecules consumed and molecules produced. The main interesting difference in the simulator Carin built is that the multisets are visualized as a bunch of molecules bouncing around in 2D space, and rules fire whenever molecules "collide," which may be constrained by some geometric aspects of the simulation (although those features are not included in the semantics of the program, technically). In the video, Carin gives examples that include a (simplified) Dining Philosophers simulation and an email server network simulation.

"Strange Loops: Capturing Knots with Powerful Notations" by Kay Ye was a really delightful romp through knot theory and mathematical philosophy, with equally delightful hand-drawn slides. It tells the story of (primarily) two disparate notations for knots, one of which is significantly more "clever" and elegant, but obtains its expressive power by optimizing for certain knots (rational knots) that happen to be suited for it, yet don't seem to faithfully map onto the concerns of practicing, knot theorists. I thought this talk made an interesting bridge between the kinds of ideas in Peter Alvaro's talk (abstraction boundaries can hinder users) and the ideas in Phil Wadler's talk (which pushed for a preference of "discovered" theories and languages over "invented" ones) -- knots are a domain which seem, like distributed systems, somewhat resistant to the nice discovered interfaces that PL designers crave, and all the challenge lies in negotiating the gulf between the elegant and the useful.

"From Protesting to Programming: Becoming a Tech Activist" by Idalin Bobé was the keynote that solidified to me that Strange Loop is a conference I want to continue attending and endorsing. Idalin tells her personal story of overcoming the obstacles in her life path toward creating lifechanging tech, and even more importantly, she discusses racist police brutality and the events of Ferguson that created critical mass around public awareness of these issues as well as her own will to get involved. My favorite part of this talk was when she stated point-blank that most of the tech coming out of startups is creating bigger gaps of inequality rather than closing those gaps, and how nearly all of the tech thought to enable disempowered activists can be systematically taken away and turned against them.

"A History of Programming Languages for Two Voices" by David Nolen and Michael Bernstein is a "mixtape" of PL history paired with music history. Although I didn't catch this talk in person, I watched it as soon as it popped up online, because I knew this one would be too good to miss. The main thing I love about this talk is the "now start yr own band" attitude of it, the encouragement to the audience to make our own mixtapes celebrating the interdisciplinary connections that excite us. (I know I, for one, want to do a version of this that includes ML and riot grrl.) Also, this talk strongly reminded me of Leigh Alexander's keynote at Different Games 2013 that did a similar mixtape-style history of video games. [I can't find a video, but this article seems to be a close match to the content.]

Finally, here's the video for my FPW talk, which is about Ceptre as a proposal for prototyping language for games:

Here are the slides, too.

Tuesday, September 22, 2015

Upcoming Appearances

I'll be appearing at a few conferences soon:

  • I'm giving the last invited talk at Future Programming Workshop @ Strange Loop this Thursday, September 24th. It's an adaptation of my thesis defense with more focus on the Ceptre programming language itself.
  • I'll be on a panel at PLMW @ SPLASH, an edition of the Programming Languages Mentoring Workshop geared toward undergrads who may be interested in pursuing a Ph.D. in PL. PLMW is on Tuesday, October 27th.
  • I'll be presenting my paper on Ceptre at AIIDE in Santa Cruz, sometime in November 14-18 (the program isn't up yet). 
Say hi if you'll be around!

Wednesday, September 16, 2015

Dissertation and defense slides!

The final draft of my dissertation has been sent to the printers, and you can download the PDF via that link! I'm now on a list of people I've looked up to for a long time as research role models, which is a bit bewildering.

For the short and vague version (I rely a lot on spoken content rather than words-on-slides for talks), check out the slides for my defense talk on SpeakerDeck.

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. ;)