Player goals in games are often framed in terms of achieving something in the game world, but this framing can fail to capture goals centered on the player's own mental model, such as seeking the answers to questions about the game world. We use a least-commitment model of interactive narrative to characterize these knowledge goals and the problem of knowledge goal recognition. As a first attempt to solve the knowledge goal recognition problem, we adapt a classical goal recognition paradigm, but in our empirical evaluation the approach sufers from a high rate of incorrectly rejecting a synthetic player's true goals; we discuss how handling of player goals could be made more robust in practice.
tal to a world-state goal: Obtaining the item involves
ifguring out where to find it, and staying alive involves
Goal recognition is the task of inferring the intentions be- figuring out which characters have harmful intent.
hind an agent’s actions. When the agent in question is a In interactive narrative games, the line between
knowlhuman game-player, it can serve as a form of player mod- edge goals and non-knowledge goals is further blurred:
eling [
Goal recognition has been studied extensively in a player’s decisions—the experience manager may have its
games context [
For instance, Ram [
Second, we present a preliminary study of algorithms AIIDE Workshop on Experimental Artificial Intelligence in Games, October 08, 2023, University of Utah, Utah, USA $ cory.siler@uky.edu (C. Siler); sgware@cs.uky.edu (S. G. Ware)
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License
CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org)
Our model of interactive narrative draws from others that
treat the story world as only “existing” as far as the player
is aware of it, rather than simulating the entire world. By
modeling the player’s knowledge of the story so far, an
experience manager can delay decisions about
properties and events outside the player’s perception and use
those decisions as tools to adjust the course of the story
in response to the player’s actions. This idea has been
the basis of approaches to preventing player derailment
of experience manager goals [
Horswill [
Baikadi et al. [
Goal recognition has been explored in a
planningcentric narrative context before, albeit focused on
worldstate models of planning. Farrell and Ware [
Building on the analogy of interactive narrative as a
dialogue between player and game [
Another perspective on explicit question-asking comes from Rothe et al. [27], who ask what humans are likely to ask in the context of the game Battleship. They define a “good” question in terms of maximizing information gain. By studying players empirically, they conclude that people tend to choose the most informative questions when presented with a list of question options, but not when generating their own questions from scratch. Their environment is restricted compared to our interactive narrative focus: They assume that the Battleship players are asking questions solely to optimize their chances of winning the game, and informativeness of questions translates directly to increased ability to win, whereas we consider knowledge goals that sometimes reflect questions asked simply for their own sake.
chosen observation set ∈ (, ). This encompasses
the direct results of the player action as well as anything
In Section 3.1, we propose a representation for how in- else that happens in the story world before the player is
formation is revealed over the progression of interactive able to act next (e.g., NPC actions). The new common
narrative. In Section 3.2, we define a class of knowledge ground then becomes ′ = ( ∪ ).
goals with respect to this framework. As a more specific language for representing the
common ground, we consider the knowledge representation
from QUEST [
The domain is a tuple ⟨, , , , ⟩. is a universe tion and where nodes and arcs each have one of several of propositions. is a universe of proposition sets ⊆ . predefined types; see Graesser et al. [31] for an extended We call the common ground in reference to the discourse account of types and their constraints. We focus on a few model by Stalnaker [26], as it represents the information types: event nodes which correspond to character actions about a story mutually known between the player and or happenings in the world, state nodes which correspond game at a given time during a playthrough. Besides not to something being true in the world, consequence arcs being self-contradictory, we place no general restrictions which express a causal relationship between two nodes, on the contents of a common ground, although we pro- goal nodes which define in-story character goals (distinct pose a more restricted implementation later in this sec- from our model of player goals; we omit these from our tion. A common ground functions like a state, but unlike examples for brevity and clarity), and outcome arcs showa world state which only tracks facts that are true in the ing motivation of event nodes by goal nodes, and reason present moment of the story, a common ground in de- arcs linking goal nodes together as character plans. scribes the story as a whole and will only grow over time; To relate this to the abstract model from above, we can if a propositional representation of world state needs to define the propositions in to indicate the existence of be tracked within the model, the propositions should be QKS nodes and edges, so a common ground in ∈ defined to contain time indices or other ordering con- corresponds to a QKS. When the player takes an action straints that distinguish the past of the story from the in , each observation set in (, ) will include at minipresent in which the player is currently interacting. mum a new event node expressing that took place and is a set of player actions. () is a function mapping consequence arcs to that event node from prior events a common ground ∈ to the set of player actions that or facts that made the player action possible. are legal from that common ground. (, ) is a function We describe an example of how we represent a that maps a common ground ∈ and action ∈ () common-ground change in a hypothetical adventure to a set of possible resultant observation sets, each of game. To start, the player is informed that their characwhich takes the form of a proposition set ⊆ where ter is at their cottage and that a bandit has just broken ( ∪ ) ∈ . into the cottage and left with some stolen money. These
We use this formalism to model the evolution of a facts make up the common ground . We illustrate an player’s knowledge over the course of a playthrough initial QKS representation in Figure 1, including a state of an interactive narrative game. At any given time, node reflecting the player’s location, and a network of the current common ground encompasses all of the state and event nodes reflecting the burglary backstory. facts revealed to the player about the story so far. When (Depending on the architecture, the game may have prethe player chooses an action , they know the result determined where the coin and the bandit went after the will be some observation set in (, ), but they can- burglary, but this information is not yet part of the story not necessarily predict which one. This can model game as far as the player is aware so it is not modeled in the architectures where the actual results of actions are pre- common ground.) determined but depend on information unknown to the The player is presented with a choice of actions to go player (and therefore unmodeled in the common-ground to one of the two other locations in the game world—the representation), but also architectures that use least- or market and the camp. The player chooses to go to the late-commitment experience management or dynamic market (action ). From their perspective, there may be procedural content generation where that information one of multiple outcomes (the full range of possibilities is altogether undecided by the system until it is needed. makes up (, )): They may encounter the bandit there, want (via [goal node]) to do [event linked by outcome arc to the goal node]?” can be specified by following reason arcs forward from the goal node. The QUEST cognitive model predicts that among the neighboring nodes returned this way, humans will rate nearer neighbors as better answers than more distant ones.
In the situation where we ask a QUEST-style question about a common ground that does not yet contain an answer, we can model the question as a goal to reach a common ground where the answer exists. For instance, consider the example from Section 3.1. The player could have the question: “What are the consequences of the bandit having the coin?” The question starts out unanswered in the initial QKS of Figure 1; but by going to Figure 1: Example of a common ground in the QKS represen- the Market, the player may witness the bandit using the tation. coin as in the top-right QKS of Figure 2, in which case a consequence arc from the bandit-has-coin state node now exists and the question is answered. and may or may not witness the bandit spending the Formally, let be the QKS representation of the current stolen money there, or else they may not find the bandit common ground. We define a QUEST question goal as and therefore conclude that the bandit went to the camp a tuple ⟨, , , ⟩, where is an existing node in instead. These map to candidates for how to update the , is an arc direction among incoming or outgoing, common ground, as illustrated in Figure 2. is an arc type, and is a node type. We say that a
The game mechanics resolve what the actual outcome state ′ ⊇ satisfies ⟨, , , ⟩ if the QKS for ′ should be: For instance, the player is informed that they contains an arc of type going direction from see the bandit buying a potion with the money. We up- such that the node on the other end of the arc has type date the QKS to include the corresponding observation . constitutes the subject of the question (e.g., an set to represent the new situation, as with the top-right event/state node in the how case) and the others define QKS in Figure 2. The observation set adds information the form of an answer (e.g., incoming consequence arc both forward in time, such as the event node for the from a state/event node). player’s action of traveling, and backward in time, such as the consequence arc reflecting the past occurrence of the bandit’s arrival at the market. 4. Goal Recognition
3.2. Goals during an interactive narrative. The log may end beAbstractly, we define a player goal as a formula over fore the player has completed any identifiable goals, propositions in . We say that a goal is satisfied in but an observer—e.g., a game designer analyzing the common ground if |= . In the QKS model, this playthrough in hindsight or an experience manager trytranslates to a goal specifying what nodes and arcs can be ing to adapt to the player for later interactions—may added to make the QKS satisfactory. This representation nonetheless need to reason about the player’s intendoes not lose generality over a world-state model since tions. How do we identify possible player goals, including it can specify world-state goals using state nodes for the knowledge goals, motivating the actions? desired facts, but we focus this section on how it can be Our first attempt to solve this problem is a goal recogused to define a certain class of knowledge goals. nition as planning [32] approach: We model the player
An advantage of the QKS representation is that it can with an artificial agent which we call an agent model, hymake direct use of QUEST’s question-answering proce- pothesize that the player has a specific goal, simulate the dures to determine whether the present common ground agent model’s reasoning about how to pursue that goal, answers certain kinds of questions about the story. For and determine whether the agent could have chosen the instance, a question of the form “How did [event/state] same course of action that the player did in the logs; if happen?” can be answered by following consequence so, we conclude the player had that goal. arcs backward from the node; a question of the form However, agent models for existing goal-recognition“What are the consequences of [event/state]?” can be an- as-planning approaches prescribe behavior in a determinswered by following consequence arcs forward from the istic or stochastic environment, whereas our framework node; or a question of the form “Why did the character treats the game as a nondeterministic, nonstochastic environment: players know the range of possible observation acting toward some goal in but has not yet achieved sets that could result from their action but have no reli- it. The solution to a goal recognition problem is the set able way of anticipating which specific observation set ′ ⊆ of candidate goals such that an agent modeled will be chosen. An agent model now needs to account by acting in domain pursuing any goal ∈ ′ for how a player might handle this unpredictability. could produce trajectory .
In our framework, we define a goal recognition prob- Algorithm 1 sketches the goal-recognition-as-planning lem instance as a tuple ⟨, , ⟩. is an interactive process. For each player action so far in , it checks the narrative domain ⟨, , , , , ⟩ as defined in Sec- consistency of that action with each goal; assume the subtion 3.1. is a trajectory consisting of a sequence routine verify is a search process that returns whether 1, 1, 2, 2, · · · , , where ∈ and ∈ for the action could be selected by the agent model. (We = 1 to . This represents (chronologically) the com- check each action individually instead of the whole semon grounds that the player has experienced so far and quence of actions at once because an agent may plan with the actions the player took in response. is a set of the expectation of a certain observation set but receive a candidate goals. is an agent model as elaborated later diferent observation set in actuality and have to revise in this section. its plan.)
Assume comes from a game log, presenting a snap- We spend the rest of this section discussing specific shot of an in-progress playthrough where the player is agent models that the goal recognizer could assume.
Input: Domain , common-ground/player-action tra
jectory , candidate goals , agent model Output: A set of goals ′ ⊆ that an agent modeled by could have been pursuing if it took the action sequence in 1: ′ ← 2: for all ∈ do 3: for all ∈ ′ do 4: if ¬verify(, , , , ) then 5: ′ ← ′ ∖ {} 6: return ′
There are many risks to the robustness of a goal recognition model when applied to real human players: the player acting toward a goal outside of the candidates considered, changing goals, behaving in a non-goal-directed way, missing or misunderstanding information the model assumes is available to them. This preliminary study considers synthetic players that do not yet incorporate these risks, but we acknowledge the importance of human factors for our future work.
There is a wide spectrum of ways even idealized artificial agents can handle the nondeterministic environments of our framework, as shown by the contrast be
First we propose goal recognition using an optimistic tween the highly risk-taking optimistic-planning agent
planning agent model where the agent plans for the best model and the highly risk-averse adversarial-planning
case, hoping that its action will result in a specific ob- agent model described in Section 4. A mismatch between
servation set that gets it closer to the goal. Given a cur- the agent model assumed by the goal recognizer and the
rent common ground , for an optimistic-planning agent decision-making criteria of the actual player can result
with goal , the agent can take an action if there exists in wrong conclusions about the player goals—false
posisome hypothetical plan , +1, +1, · · · , where tives where a candidate goal is wrongly attributed to the
satisfies ; we also require the plan to be nonredun- player, and false negatives where the player’s actual goal
dant in that no strict subsequence of , +1, · · · also is wrongly rejected as a possibility.
satisfies . This definition is based on Sabre’s character Our experiment seeks to quantify the error-proneness
model [
We also propose an adversarial planning agent model the player acts according to another agent model. By usthat plans for the worst case, trying to act according to ing an optimistic planner as the “real” player and trying to a policy that can eventually satisfy the goal even when identify that player’s goals using the opposite extreme of its actions result in the worst-case observation sets. For an adversarial-planning goal recognizer, and the reverse, some goal , define a safe common ground as (base case) we aim to establish upper bounds on goal recognition one that satisfies or (recursively) for which there exists error before human factors are applied. an action ∈ () such that all outcomes in (, ) We generated goal recognition problem instances as result in safe common grounds. Given a current common follows: To derive the domain , we started with depthground , for an adversarial-planning agent with goal limited, tree-structured story graphs [35] from a narra, the agent can take an action if all possible result- tive planning [36] problem, generated using the Sabre ing common grounds are safe. However, because this narrative planner [33]; these graphs consist of nodes repdefinition alone could easily result in situations where resenting world states and edges representing player or the agent would have no valid action choices defined non-player actions, annotated with information such as (because the agent will eventually have to take an ac- whether the player observed a given non-player action. tion where at least one possible outcome could prevent We restructured the story graphs to alternate between the goal), we generalize this definition—we model an branching on a choice of player actions and branching agent who believes the observation sets are chosen uni- on a choice of non-player macro-actions containing any formly at random, and the agent follows an expectimax- number of non-player actions. At each node, we used style [34] policy that it thinks will maximize the worst- previously-proposed mappings [29, 30] to derive a QKS case probability of satisfying the goal. Define the score equivalent of the story so far. We also used an approach expectimax() of a common ground for goal as 1 similar to Robertson and Young [37] and Fisher et al. [38] if satisfies , or 0 if can never be satisfied from to allow uncertainty about which of multiple story-graph (e.g., because is a leaf in a finite tree of possible tra- nodes the player was in, due to possible unobserved past jectories); otherwise, define expectimax() as the aver- events; we derived the final QKS common ground repage score of common grounds reached from choosing resenting the player knowledge by taking the maximal a best action, max∈() ∑︀∈(,|)e(xp,ec)t|imax(∪) . An subTgoraopbhtatihnataistsrhajaercetdorbyy theoofripglianyaelrstaocrtieiosn.s so far, adversarial-planning agent can take an action if we sampled and truncated goal-satisfying playthroughs maximizes the average in this manner. given a goal and agent model . We manually defined the set of candidate goals for the domain.
As a source for our domain, we used the narrative Goal recognizer output planning problem from the Grandma adventure game p n used by Ware et al. [39]. We retained the same characters, actions, locations, and items, but modified the initial sKtnatoewanntdoNthPeCpglaoyaelsr itno tchreeainteittihaleQinKiSti,atlhsreeteuapcatisofnosllhoawvse: d p′ T59rue Pos. 1F1a7lse Neg. already happened in the backstory: The bandit character un th has stolen a sword and a coin from the player character’s roG tru house and left the house. The merchant character is at the bmoatrhkelotcaantdiotnhse rgeuaacrhdabchlearfaroctmeraiscartotshsreobaadnsdriet’ascchaamblpe, n′ 1F2a7lse Pos. T25ru7e Neg. 6S7p%ecificity from the cottage. Unknown to the player and thus not represented in the initial QKS, the bandit intends to use the sword to kill the guard and/or rob the merchant, Figure 3: Adversarial-planning goal recognizer on optimisticand/or use the coin to buy from the merchant. planning player over all goals and trajectories
We defined four possible goals that the synthetic player would try to satisfy and that the goal recognizer would try to distinguish between as the candidate goal set : Goal recognizer output achievement goals to get the stolen coin and to get the p n stolen sword, and knowledge goals in the form of QUEST question goals for “Why did the bandit steal the coin?” aonvedrl“aWp hiny sdoimdethoef bthaendpiltaysteeraal ctthioensswtohradt?c”anThbeesuesgeodailns udn pth′ T59rue Pos. 3F6a0ls1e Neg. Sensitivity 2% the course of satisfying them, e.g., following the bandit ro tru can support any of the goals, but diverge in others, e.g., G killing the bandit enables taking back the stolen items buuntfoelldimainndatleesaronptphoeritruinnitteienstitoonws.atch the bandit’s plans n′ 5F2alse Pos. T15ru56e Neg. 9S7p%ecificity
We generated the narrative planning problem’s story graph to a fixed depth of 6 steps, based on available computation time, and converted it to the graph of QKS com- Figure 4: Optimistic-planning goal recognizer on adversarialmon grounds as described above. We then collected all planning player over all goals and trajectories trajectories for each agent model and each goal and analyzed them in the following process:
Suppose the real player is an optimistic-planning agent reverse. We show standard measures of performance for and the goal recognizer assumes an adversarial-planning a test to distinguish positive from negative cases: sensiagent model, or the reverse. Let be a trajectory; let tivity (how often the recognizer concluded the player had be all the goals, let ′ be the set of goals for which the goal, given that the goal was consistent with the true the player generated and let ′ be the set of player model), and specificity (how often the recognizer goals identified by the goal recognizer for . We counted concluded the player did not have the goal, given that goals in ′ ∩ ′ as true positives for which the the goal was inconsistent with the true player model). goal recognizer would correctly identify a player goal Both of the player-recognizer combinations had worsefor ; ′ ∖ ′ was false negatives for which the than-random sensitivity and better-than-random specirecognizer failed to identify a goal that was consistent ifcity; the recognizers skewed toward correctly rejecting with the true player model; ′ ∖ ′ was false candidate goals when the player did not have those goals, positives for which the recognizer identified a goal that but failing to detect the true goals. The diference was was actually inconsistent with the true player model; especially strongly pronounced in a goal recognizer that and ∖ (′ ∪ ′) was true negatives where the assumed an optimistic-planning agent model when the recognizer correctly did not identify a goal that would actual player used the adversarial-planning agent model; have been inconsistent with the true player model. that is, when considering a goal that the player actually
We show confusion matrices for the results across all had, the optimistic-planning goal recognizer was highly goals and trajectory lengths: Figure 3 shows the per- likely to erroneously reject that goal. These instances formance of a goal recognizer assuming an adversarial- came from the fact that our optimistic-planning agent planning agent model if the actual player acts like an model attempts to be as eficient as possible by avoiding optimistic-planning agent model, and Figure 4 shows the actions that could be redundant to the goal, while the adversarial-planning model accepts longer paths in favor of safety; the simulated adversarial-planning player often This material is based upon work supported by the Natook actions that were unexplainable to the optimistic- tional Science Foundation under Grant No. IIS-2145153. planning recognizer because there was a more direct Any opinions, findings, and conclusions or recommendaroute available. This experiment suggests that strict as- tions expressed in this material are those of the author(s) sumptions about agent eficiency—which are common in and do not necessarily reflect the views of the National existing goal recognition approaches—are too brittle in Science Foundation. practice, and future goal recognition approaches should be designed to handle cautious or meandering players.
This paper highlighted an underexplored class of goals important to interactive narratives—player goals to fill the gaps in their knowledge about the story so far. We extended goal recognition to these goals by defining a planning framework over the space of player mental models rather than over the space of world states, drawing on representations of discourse and question-answering from linguistics and cognitive science.
Accurate algorithms for knowledge goal recognition
are still an open problem. An approach based on
simulating a hypothetical player and comparing its
decisions to the real player’s can easily fail to detect goals
of a player whose playstyle does not match the
algorithm’s assumptions. However, the desiderata for a goal
recognition algorithm depend on how that algorithm
will be used. For instance, high-specificity but
lowsensitivity goal recognition could be acceptable for an
experience manager whose objective is to find a small
handful of the player’s interests and use them to ofer
the player mutually-beneficial opportunities. Conversely,
low-specificity but high-sensitivity goal recognition can
still be useful for a highly-improvisational experience
manager deciding when to fix “plot holes” in its stories
that may be exposed by player knowledge goals [
Reasoning about player goals will ultimately require
considering the context that goals come from. In the case
of knowledge goals, aside from ofering models, the
literature we reference goes on to emphasize that reasoning
efectively about questions requires understanding why
they were asked: Roberts [