June 5, 2005

Swig of Gamer-AIIDE

by Andrew Stern · , 8:39 pm

Michael and I had great time last week at the first Artificial Intelligence and Interactive Digital Entertainment conference (AIIDE) in Los Angeles. I’d guess there were around 80 participants, about two-thirds from academia and the rest from the game industry. There were many interesting presentations and a roomful of demos, including our now code-complete Façade, which got an enthusiastic reception. All considered the meeting a success, with plans to hold it again next year.

[Update: here’s a NYTimes article about the conference!]

What follows are raw notes from several of the talks and keynotes, in the order they were presented. Apologies if I missed a few, I occasionally had to take a break to avoid overload, and to tend the demo machine. Talk titles, and particularly prescient quotes, are highlighted in bold.

Doug Church — AI Tools for Generating Player-Driven Emotional Experience in Videogames

currently have a rise of entertainment content in games, beyond just play
not just the challenge of the game, now “entertainment”; big moments, emotional events, open ended worlds
how does AI fit in?

“long tails” — indie products — no infrastructure yet for small niche titles
5-10 years from now, it may be different; for now, the industry is mass-market

now games becoming are content-led, not technology-led
team scale is impacting the development process
Less discipline-based (artist, programmer), more task/feature-oriented
AI programmer is in the trenches with the team

current methods are a dead end street

single player games remain challenge-oriented, or cinematic
mmog’s have more real consequences, in their own way
so the opportunity for AI is more in single player games

risk aversion due to higher budgets
revenue more important than ROI (return on investment)

none of the AI detail gets attention in a 30 second ad or magazine blurb
also, if a character in battle only lives a minute, there’s not much fidelity players can even perceive
industry has been promising good characters for a long time, not delivered —
players are cynical, don’t want to hear it anymore
hard to back out of the fakery

hard to point at what risky AI will do for selling games —
because combat/challenge genre is limited
new features have to be clearly beneficial
hard to make the case to take the risk on ROI
however if succeed and release, it can be a big hit (e.g. Sims)
hard to prove

what’s need to pitch it? have to define:
– player fantasy
– key pillars
– uniqueness

Elixir – Demis Hassabis – Republic – 7-8 years, super ambitious, never quite worked

We’re making a ton of progress just standing still.
that is, we’re increasing the fidelity of existing game genres
it’s a huge amount of work — expression, sensors, traits, etc.

in pure systems (generative), things [player agency] is often flat, muddy
no big events / moments; grinding through low level detail
in games we want more real and more subtle, but without being too fuzzy

AI styles we use a lot:
– opponent
– manage – Sims, B&W creature, RTS troops
Both have clear expression for player in micro-actions or micro-tasks taken

Not much use in:
– negotiate
– converse
– choice & consequence

Design challenges
growing complexity makes clear NPC expression harder
authorial vs. autonomy tension
AI’s need to be robust, contextually aware, and controllable – not an easy balance

again, the game industry is keeping up with the advances in hardware – quite an achievement
complex settings/environments give more options for player expression/scope
but existing trajectory continues to evolve only a small set of games

need AI tools on par with graphics / world fidelity
tools: better blend of AI system behavior nd “script-like” entertainment elements
Risk: managable steps, solid path
(Academic demos need to be strong, immediate demos; already used up some chances)

AI will be necessary to keep costs sane

New styles:
– “real AI” — planning, learning
– entertainment — big moments attached to real choices, take back from cut scenes

Q: small company or big company will do this?

A: either way is possible — a big company with a long term plan, with prototype products along the way
and/or a small company, surviving for 6 years on ramen noodles
or a middleware company who uses their own tools to make a game

Q: what is academics’ role?
A: I want actual concrete things I can look at, the experience it enables, be aware of technology constraints (eg CPU and memory issues)

Will Wright, Maxis — A Design Perspective on AI

this talk will be a design perspective on AI
2001, HAL had big impact on him

observation #1: want to maximize the ratio of internal complexity to perceived intelligence
not just one thing that’s AI – more like a bag of tricks, or a toolset (pliers, wrenches, etc.) – a set of methods, solution sets
controlling the model the player is building in their head

observation #2: player will build a model
if you don’t help, they will build the wrong one

observation #3: flow of information has huge impact on how player perceives intelligence
average person underestimates what it takes
(Will shows video of a “helpless robot” Stupid Fun Club experiment – a fallen broken robot begging for help in an alley in Oakland during the middle of the day)
all single women got spooked; single men stripped the robot for parts; mixed gender couples were the only people who helped

Stupid Fun Club project: conversational action figures that chat with each other – “chatterbots”

observation #4: fine line between complex and random behavior
drama is built on elaborate causal chains
have “kludgey feedback issues” to deal with the non-linear order that things are experienced in

observation #5: minimizing human intelligence and maximizing AI are two different things
human players (eg in MMOGs) offer diversity, not necessarily intelligence

with games and AI, want to go deeper into human psyche, beyond just surface / realism
probably will reach a behavioral uncanny valley at some point
20Q.net — feels like an alien intelligence, the way it asks bizarre questions to come up with the right answer

observation #6: there are many applications of AI that are not opponents or human characters

Will shows a set diagram, with “sub-AI” the inner set, “peer AI” a larger intersecting set, and “meta AI” encompassing all
sub-AI – physics, etc. – we’ve made a lot of progress
peer AI – agents – we’ve made moderate progress
meta AI – experience, info flow – we’ve made little progress

observation #7: system that collects and reflects natural intelligence is easier than replicating that intelligence

observation #8: robust internal model of player can be a huge advantage
interpret style, theme of player; start influencing presentation; story parsing
demo of a social pattern simulation; able to correlate closely to real players’ social behavior

observation #9: static data is a lost opportunity
should automate intelligence that created that data, when feasible

Will is interested in shifting towards AI for developers (“developer AI”)
at Maxis, animators are training programmers how to animate

Bing Gordon, EA: The Turing Test for Game AI

Bing shows some Madden video clips of gameplay, asks audience to guess if the characters are controlled by players or AI. [I guessed right each time :-) ]

Ten predictions:
1. Gaming gets Pixared
2. Living worlds – physics, water, fire, gravity, particles, sound design; heuristics, not algorithms
3. Procedural everything – “engineers’ revenge”
4. Customization and identity
5. Pocket screens – phone is a killer app
6. Social networking – can’t sell a game without a “meta game”
7. Monetization of internet – people will be spending $200/mo on internet 5 yrs from now
8. Chunkable designs
reinvention of game design – pods and cells, code and paper prototyping, microgames not levels
deconstructions – micro-narratives, motivations and rewards
9. Rise of the middle(ware) class – increase reusable code from 10-30%
10. AI matters
don’t be as smart as possible; credible failures
characters: awareness, memory, complex motives, 100x RAM, procedural responses

Jonathan Schaeffer, University of Alberta: Interactive Story Writing Using ScriptEase

academics don’t usually consider “scripting” as AI, but game designers do
need to simplify the cost of scripting
simplifying process of providing content via scripting, to reduce cost, increase quality

games are a new creative expression/writing technology
in Bioware’s Never Winter Nights (NWN), you can create your own story

Obstacle: currently have to program (write) the story; need to bridge the gap for non-programmers
Solution: tool to easily generate a complex roleplaying story
people use NWN to create their own interactive stories

Bioware-supplied foundation:
– NWN engine
– Aurora – game development CAD tools (to make sets)
– NWScript – event-based scripting, procedural language; simple, C++ like, no pointers, but difficult for non-programmers

2M+ users at Bioware website; > 3300 quest stories/games created; lots of interest

ScriptEase – interact with user at their level of abstraction
take user specs and automatically turn them into code
reusable design patterns than encapsulate generic thematic idioms – templates with options
“generative design patterns”

types of patterns:
– encounter – open/close chest, door, barriers
– behavior – guard, customer, server
– dialog – introductory conversations
– plot – eg. assassination; completing sub-tasks before the main task
ScriptEase includes tools for creating and adding new patterns

– team is replacing all existing original NWN scripts (made by the original Bioware team) with ScriptEase patterns; result is less code, fewer errors. Currently working on replacing all NPC behaviors; allows us to trivially replace NPCs with more sophisticated adaptive behaviors
– did some user evaluation with high school students in a creative writing class
Some students with lower academic achievement in creative writing did well with ScriptEase
encouraged a lot more collaboration between students
tough for teacher to grade

Q: (from me, Andrew): I’ve always been bothered by the term “scripting”, it implies a linearity and simplicity which often doesn’t reflect the behavior-ness of today’s “scripts”
But anyhow, are you really able to think of these non-programmer authored quest adventures as “stories”?
A: Agree with the dislike of the term “scripting”; many students attempted somewhat literary-like stories using ScriptEase; they were graded by the teacher on their literary merit

Mark O. Riedl, ICT and R. Michael Young, NC State: From Linear Story Generation to Branching Story Graphs

What does it mean for a story to be branching?
try to understand the relationship between narrative mediation and branching

what is branching? directed graphs

control vs. coherence

narrative mediated

ways to deal with player exceptions
– accomodation — allow player exceptions, re-plan
– intervention — prevent/disallow player exceptions (e.g., make player’s gun malfunction, or artificially miss)

Mimesis system
planner anticipates exceptions, create a mediation policy tree
use heuristics

evaluation: are narrative mediation trees equivalent to branching stories?
narrative mediation path – sequence of character actions and decisions
analysis follows, the answer is yes

[The question I didn’t get a chance to ask: does this approach scale up well or not, when the number of and frequency of player choices gets higher, to match levels of what players will typically want?]

Mark Nelson and Michael Mateas, Ga Tech: Search-Based Drama Management in the Interactive Fiction Anchorhead

types of Drama Manager (DM) actions:
cause, hint, deny, temp_deny, reenable, end_game

Evaluation function – a sum of features:
– location flow
– thought flow
– intensity
– momentum
– choices
– manipulativity
– plot mixing / horning

Peter Weyrauch’s SAS+ from Tea for Three didn’t scale up to work in Anchorhead – it’s a greedy algorithm, need to search too deeply to find best solution
But, we’ve found that SAS+ with reinforcement learning (RL) did work!

Brian Magerko, University of Michigan: Story Representation and Interactive Drama

requirements for story representation

– expressivity
– coherency
– variability
– prediction – example from the movie Sideways – if they were driving along a beachside cliff in danger of crashing and dying, should put a slow truck in front of them, make a cop pull them over, etc.
– fully structured story

plot representation
preconditions, actions
plot points can be active or not
focused on temporal relations between plot points, not causal
two-tiered approach to plot point choice:
– first hope that player choice works out
– if not, do heuristic choice

Michael Mateas, Ga Tech and Andrew Stern, InteractiveStory.net: Structuring Content within the Façade Interactive Drama Architecture

Didn’t take notes, since we gave the talk together; you can find the full paper at interactivestory.net

(later on in conversation, one of the EA developers of The Godfather suggested it would be really helpful to see some sort of visualization of how players traverse the structure of the story space. Good idea – we’ll work on that for a future talk / paper / blog post…)

Marc Cavazza and Fred Charles, University of Teesside: Dialogue Generation in Character-based Interactive Storytelling

dialog in storytelling – hypotheses:
– utterance form is determined by relationship between characters
– utterance content is determined by structure of events (eg, invitation, request…)

witticism-based dialog in storytelling

NLG techniques have evolved over time:
canned -> context-free grammars -> unification grammars -> TAG (+unif)
now circling back around towards canned, with templates

examples: invitation
implicit way to do an invitation – a partial description of a future event
implicit way to refuse – negative judgement on the agent involved
implicit + clarification – actor take-part event:party etc…
implicit acceptance – agent look-forward etc…

unifying various aspects: action, characters, affinities, communication
more believable staged communication based on first principles
next step: unifying agent-to-agent and agent-to-user communication

Chris Crawford: Blending Real Intelligence with Artificial Intelligence

[Update: Chris’ speech, Artists and Technologists, is now online.]

History records a number of golden eras of creativity and innovation, eg the Renaissance; due to convergence of dramatically different things
this period (now) will be looked back on as a computer golden age
but will be perceived differently than we do now
technological and artistic convergence hasn’t happened yet
we do not understand the magnitude of this obstacle

logical, sequential thinking/reasoning is the terribly poweful foundation of our civilization

but humans naturally are pattern-based thinkers
different, but not totally orthogonal, to sequential thinking – one can fake the other
human minds don’t think logically by nature; we fake thinking logically

artists always use pattern based reasoning; technologists use sequential
I will offer advice to technologists on how to cope with this

Negative rules of thumb – these don’t work! –

1) Hubris – roots of this word means overreaching your place in the natural order of things; improper
I offer myself as a warning of the idea of the Renaissance Man
Being a half-assed artist and half-assed programmer doesn’t make me a Renaissance Man, it just makes me a total ass
possible solution: need to train people when they’re young
Europeans are generally ahead of Americans on this, who have a disdain for art
2) Backseat Driver – artist cannot be hands-off, in the back seat
3) Let’s collaborate – doesn’t work well for prima donna artists and programmers

Present a template or model for collaboration between artists and programmers, for least conflict between them

Crawford’s first law of software design: what does the user do?
what are the verbs?
the verb list is the fundamental architectural blueprint; makes whole process easier
Artists should own and write the verb list; they need to be specific, to reduce vagueness
Technologists will be doing technical filtering, implementation plans
Technologists own / create the model. May only humbly suggest new verbs that the artist may not have thought of.
Technologists create authoring / development environment for the model – the artist needs access to play with the model
(with the Erasmatron, I’ve spent 4x the time on the authoring environment than the model)
Artist has to meet technologist halfway in the scripting language, because the essence of computing is the algorithm – it’s not visual (it uses visuals, but that’s not its essence)
Interaction is specified through algorithm; process, not data
the method of merely tweaking parameters sort of barely works… barely plausible, doesn’t really work
Artists will need to write algorithms at the Algebra I level

What should be the characteristics of this scripting language for artists?
– ontology recapitulates phylogeny – scripting isn’t terribly far from writing natural language; will need to learn this new language
– the language should be logographic (one symbol per word), not alphabetic
need interface where all expressions are valid – no syntax errors
– handle/trap and ignore runtime errors – just degrades performance, but never crashes
– small fixed set of datatypes, color-coded
– metaphor for looping – “pick the best”; subsume computer science concepts into ones more natural to the artist; use metaphors like actors, stages, props, roles, rehearsals
– offer statistical analysis of overall performance of system – event X happens 16.9% of time, Y happens 12.4%, etc.

Chris’ pontification of the next 5-10 years – future trends in games
– we’ll see increasing verb counts – currently games have ~12 primary verbs – move left, right, shoot, jump, etc.
– innovation may come from other industries, not the game industry
– interface will move towards language – “Where’s the beef” communicates enormous amounts of information
– But it doesn’t have to be natural language (eg English), that’s too big; we need to design interface languages with ~100 verbs, that are logographic
If Dustin Hoffman in The Graduate was told “Plastics!”, Chris Crawford is telling us, “Linguistics!”

Q: (from me, Andrew) – are players really going to be willing to learn invented languages?
A: Yes – people easily pick up new languages – e.g. visiting a foreign country

Robert Zubek, Northwestern U: Hierarchical Parallel Markov Models of Interaction

His goal: “building an Eliza that doesn’t suck”

[Eds. note – I don’t think Eliza sucks! :-) ]

chatterbots are not quite there – problems maintaining long-term coherence, tracking the topic, dealing with ambiguity
dialog graphs – have coherency, but little support for NL input

Want best of both worlds – power of dialog graphs, plus the NL interface of chatterbots
applying richer interaction representation, to finite state tech

decompose interaction into constituent pieces
track using stochastic models
add hierarchical composition
add parallelism and independence

hidden markov models (HMM’s) – robust in the face of noise
same utterances can yield different responses
graceful performance degradation

does not handle player’s original contributions
danger of verb hunting

[Eds. note – it’s nice to see Rob ending up with an approach similar to what we ended up with in Facade, and to approaches I worked on at Zoesis: in essence, breaking a conversation apart into a collection of small, independent conversation machines, each running in parallel with one another, that have some sort of arbitration to determine which gets to respond to the player’s input at any given time. In Rob’s case, the little conversation machines are simple dialog graphs implemented as finite state machines, and arbitration among them is determined probabilistically. In Facade, each conversation bit is implemented as a simple behavior (each not much more complex than an FSM), and arbitration is done by parallel proposers that fight it out with a set of priorities and heuristics for modifying the priorities. In Zoesis’ case, each bit are also behaviors, who compete via a bidding mechanism.]

Q: (asked by me, Andrew) – to avoid cycles in the conversation, did you consider making dialog graphs unaccessible once they’ve played once? This would mean you’d eventually run out of content, of course.
A: Didn’t get to that, but wanted to.

Damian Isla, Bungie Studios:Spatial Competence

what constitues spatial competence?
In Halo 2, AI’s are given a ‘playground’ within which they are allowed to do whatever they want designer defines the flow of battle by moving the AI from one playground to another

generally speaking, want to automate as much as possible to reduce work for the designer – designer’s time is very precious

problems solved in Halo 2
– environmental representation
– spatial feature extraction
(designers do additional “hints” annotations)
– want representation of ‘place’ – like cognitive maps
not metric, fuzzy, hierarchically organized, discrete, relational
– object representation – 3 ways to see an object – inherent properties, volume, spatial features
Minksy: multiple representations of the same thing is great
like in Sims, objects advertise the things that can be done with it
volume + features: how the AI understands shape
– spatial relations – knowledge-representation-like
e.g. grenade throwing targets, blocked shots, destroy cover (target behind destructable cover), mount-to-uncover
‘behind’ is not a trivial concept
perform dynamic clumping of nearby allies
cognitive efficiency: e.g. consider many as a single group

reference frames – most interesting use: frames of motion, e.g. AI’s running around on top of a tank

spatial behavior – two types: allocentric (fighting, following, searching a room), egocentric (don’t face walls, don’t block player’s line of fire, etc)

these representations are driven by needs of the game, not biologically inspired

Bill Tomlinson, UC Irvine: Negative Behavior Space in the Design of Interactive Agents

when designing engaging AI’s, certain behaviors imply others; can cause unintentional expectation violation

behavior spaces – sets of behaviors
value: repetoire, grouping, agent design, action selection

negative spaces – general meaning – spaces around object being drawn, common in drawing, graphic arts, etc.
value: strong compositional elements, reduce unintentional bias

negative behavior spaces – scoping mechanism for sets of behaviors explicitly not implemented

why? player expectation management, reduce development effort
a character with an awareness of its own negative behavior space can avoid the perimeter

11 Responses to “Swig of Gamer-AIIDE”

  1. andrew Says:

    Robin has written some good commentary on the conference, and some photos from her nifty camera, including several of Michael’s nifty new goatee.

  2. Dirk Scheuring Says:

    Thanks a lot for posting this; very instructive.

    As usual, I like Will Wright’s ideas a lot. “Drama is built on elaborate causal chains” – how very true. As long as “Why?” doesn’t work on everything, there’ll be no drama, IMO. Faking it – for instance, by treating “Why?” as “a provocation” – is not enough. Why? It limits character development tremendously. The result is likely to be a neurotic character. There’s no way to get depth like that.

    observation #6: there are many applications of AI that are not opponents or human characters

    “Right again, Robin.” SciFi, Horror, Fantasy are media genres chock full of non-human intelligent characters. Even cars can be Subjective Characters. Put that in a game and sell it.

    I bet that the “meta AI” is going to be distributed across character AIs. Each character needs a director “built in” (a robot soul ;-); I don’t see a place for an external “manager/director” module. Rather, I see a hierarchy of characters. That, and a simple function at the fixed point. It is a matter of combining and nesting Storyforms.

    Bing Gordon: “Gaming gets Pixared”. Yes, I think this will happen, but (I hope) on various scales. There’ll be smaller and bigger Pixars. Also, the Pixar content creation model might work in a distributed form – are “developer farms” really necessary? If they are, the Big Money guys are really at an advantage. Academics – could you please do some science on that?

    But “engineers’ revenge”? Only if the engineers get really good at using Storyforms, or some other means of formalizing the procedural creation of meaning. Does he expect “engineer’s revenge” to happen at Pixar?

    I wonder whether ScriptEase will be a solution for my authoring problems. It looks like it supports feeding a traditional “n++” content model. I’ll need a model, method, and tool(s) for creating “n^2” type content on a large scale.

    Ah, and Chris Crawford – “we fake thinking logically” – I seem to have observed this, too.

    But: if we succeed in training young people to be both full-assed artists and full-assed programmers, are we in for a world of total double asses?

  3. Dirk Scheuring Says:

    If you have trouble imagining what kind of a fixed point function I’m thinking of – I see it as an equivalent to the use of “The Gutter in comics.

  4. Ian Bogost Says:

    This is great stuff. Of course, it just makes me wish I had more detail. Couple questions.

    (1) About Will’s comment on the future behavioral uncanny valley… what’s the context here? It strikes me that this problem mainly takes form when unbounded… but within a space of defined expressive goals, such as one or three single behaviors, does the same problem persist? Granted, the game’s frame would have to do a damn good job divesting the player of interest in other forms of behavior. Wow, I hope at least some of that made sense.

    (2) I’ve heard most of what Bing had to say before, save the seemingly important “AI matters.” What else did he say about this?

    Incidentally, I used to work two doors down from this British Car Clinic Robin photographed. Tip: don’t buy a British car. This place was always overflowing.

  5. mark Says:

    On Ian’s comments,

    (1) I think it depends on how narrow your world is. If your world in any way includes people, it may be hard to get it just right, I think, because people do all sorts of rather complex things that look weird if almost-but-not-quite right. People-behaviors also seem pretty intertwined with each other, in the sense that if your characters are realistic humans in a few ways, it’ll be weird if other things don’t exist in your world at all. Though perhaps you can coax some apart. A sort of tangential point is that I think there’s a lot of interesting art in the “uncanny valley”. Whether this art takes the form of games people want to play, I don’t know, but I sure like the prospect of being able to unnerve people.

    (2) Frankly, I didn’t think Bing’s talk was that interesting, but that may just be me. I could summarize most of it as “goddamn, Madden NFL sure does sell a lot of copies!” It’s a useful reality check, in that Madden NFL 2005 sells such a sheer number of copies that it explains why companies like EA aren’t that interested in taking a chance on more innovative stuff that, even if it “succeeded” by the standards of an innovative game, would probably still make less money than a month’s worth of Madden sales. The film industry has some similar problems I’d say, but in both industries, simply reminding yourself of the fact that a few blockbusters make a ton of money doesn’t take you much closer towards figuring out how to make something more interesting.

  6. Stephen Says:

    I have a casual interest in AI so my knowledge in this area is quite limited. It does however seem to me that a deeper resevour of scripting reactions is the key. In a day with such high density of hard-drives I would think developers would be putting staff to work doing nothing but generating insidental, non-demanded reaction-of-user dialog and reaction trees for such insidental conversation. Yes the IF AND OR BUT senerios are important but so is end user variety. Take Everquest 2’s use of spoken dialog, this is noticably finite but the user feels gratefull for the increased variety. HL-2 had a few more responces than ussual and this made for a more immersive game. I have written action fiction and as I generate many differant charactors interacting I realize the bredth of possibilities are astounding. But as a game player I feel perfectly happy to purchase more memory and or hard-drive space if the next game is more immersive. This is a envelope that we will gladly help push, as we are all tired of chasing faster better vidio cards that are outdated in months. And games like Guild Wars show that such expensive cards are not even neccasary. Larger HD and MEM are things that benefit the user while not playing games with more media storage and smoother performance.

  7. Stephen Says:

    I forgot to say thank you for posting this very interesting article. Thank you.

  8. andrew Says:

    Interesting to constrast Robin’s evaluation of game AI “in a rut” versus the rosier outlook taken by the NYTimes article.

    I’d suggest game AI is not in a rut, per se – instead it’s standing on a slope, part way up a massive mountain, looking up at the distant peak, gone as far as it can go on foot, and now has to break out the mountain climbing gear and prepare for some very strenous, painful rock climbing. But imagine the views up there!

    Also, a comment on Robin’s point about few women at AIIDE — that’s very true, but let’s not forget two of the primary voices that have had such an influence on framing, guiding and motivating this work for many researchers, particularly for interactive drama – Brenda Laurel and Janet Murray. And Marie-Laure Ryan is a newer voice with lots of new excellent analysis as well.

  9. andrew Says:

    Our AIIDE paper is now online, “Structuring Content within the Façade Interactive Drama Architecture“. Apologies for the delay.

  10. michael Says:

    The AAAI (American Association for Artificial Intelligence) news alert service picked up the NYT article on AIIDE.

  11. togos: Boyce-Codd Sweet Place (664) Says:

    […] f-assed programmer doesn’t make me a Renaissance Man, it just makes me a total ass. From this game AI conference.Post a new comment) […]

Powered by WordPress