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
SHRDLU, Eliza

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

Evaluation
– 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