=Paper=
{{Paper
|id=Vol-2282/EXAG_113
|storemode=property
|title=Eliminating the Impossible: A Procedurally Generated Murder Mystery
|pdfUrl=https://ceur-ws.org/Vol-2282/EXAG_113.pdf
|volume=Vol-2282
|authors=Henry Mohr,Markus Eger,Chris Martens
|dblpUrl=https://dblp.org/rec/conf/aiide/MohrEM18
}}
==Eliminating the Impossible: A Procedurally Generated Murder Mystery==
https://ceur-ws.org/Vol-2282/EXAG_113.pdf
Eliminating the Impossible: A Procedurally Generated Murder Mystery
Henry Mohr Markus Eger and Chris Martens
hmohr@haverford.edu meger@ncsu.edu, crmarten@ncsu.edu
Principles of Expressive Machines Lab
Haverford College NC State University
Haverford, PA, USA Raleigh, NC, USA
Abstract One approach taken by several video games to improve
variation and replayability is the procedural generation of
Games that involve solving puzzles or mysteries often suffer
from low replayability once the solution is known. Procedu-
content (Hendrikx et al. 2013). This can range from creating
ral content generation has been used to aid with increasing different maps the game is played on, variations of buildings
variance in game play, leading to a higher replay value. How- shown in the game world, or procedurally generated char-
ever, games that feature information that must be obtained acters with their own history (Adams 2017). The challenge
by the player present the additional challenge of tracking the in providing procedurally generated content for a game is to
player’s knowledge and ensuring that it is possible for them generate a wide enough range of outputs to be meaningfully
to finish the game. In this paper we present a detective game different, while preventing undesirable output from occur-
with procedurally generated characters that pursue a range of ring. For example, if a game generates a new maze for play-
goals, including one that commits a murder. The player’s role ers to solve on every play-through, but the mazes are just
is to solve the crime by collecting evidence from the actual minor variations on the same basic layout, they will not pro-
game world as well as by interrogating the characters. Even
though some of the characters might be inclined to hide ev-
vide much of a challenge to the players. On the other hand,
idence, our system guarantees that the player is always able mazes that are literally unsolvable, because there is no path
to solve the murder case. To demonstrate the capabilities of from the start to the goal, must also not be generated.
our system we present a short example game that we have
implemented using our techniques.
The genre of murder mystery stories lends itself nicely to
procedural generation, because it follows a relatively fixed
Introduction general structure, but allows for variety within that structure.
Gregory: “Is there any other point to which you would In 1928 Willard Huntington Wright, using his pen name S.S.
wish to draw my attention?” Van Dine, compiled a list of 20 rules that detective stories
Sherlock Holmes: “To the curious incident of the dog should follow (Van Dine 2015). Most of these rules are dif-
in the night-time.” ferent aspects of the requirement that the murderer has to
Gregory: “The dog did nothing in the night-time.” be found by logical deduction, rather than psychic means,
Sherlock Holmes: “That was the curious incident.” trickery, or by accident. Owing to the time these rules were
From: The Adventure of Silver Blaze written in, the so-called Golden Age of Detective Fiction,
they also recommend to avoid certain topics or techniques
Detective stories in the tradition of Sir Arthur Conan Doyle’s
that were over-used at the time, such as having a dog not
Sherlock Holmes are a cornerstone of today’s entertainment
bark at night-time.
culture, including TV Shows such as Sherlock or Monk,
movies like Murder on the Orient Express or the long run-
ning Nancy Drew series of books. There are also video game In this paper we present a detective game which utilizes
adaption of several of these stories, as well as stand-alone a procedural generation approach to generate a new crime
detective video games, such as L.A. Noire. One limitation on every play through, and uses Dynamic Epistemic Logic
of these games, though, is that they always present the same to represent facts and clues found by the detective. Our ap-
story or a slight variation thereof, making it trivial for a proach provides a range of different experience, by gener-
player to solve the game after the first play-through. For ex- ating a set of different characters with different motivations,
ample, in a faithful video game adaption of the Adventure one of which will commit the murder, but ensures that the re-
of Silver Blaze, the curious incident of the dog in the night- sulting crime is always solvable by the player. We will first
time would be less curious for a player once they learned of discuss some related work, including the underlying logi-
its significance, namely that the dog recognized the culprit cal representation, then present our approach, followed by a
and was therefore silent. brief discussion of an example domain which consists of a
murder on a cruise ship. Finally, we will provide an outlook
on how this work can be expanded upon in the future.
Related Work
Since the basis for detective games lies with detective sto-
ries, much of our work draws from prior work on story
generation. It has been observed that plans and narratives
share several properties, such as consisting of a temporal
and causal ordering of actions, and planning can therefore be
used to generate stories (Young 1999). In such an approach
the author defines a goal for the story, and the planner will
assign actions to characters to achieve this goal. However,
Riedl and Young (2010) have noted that a pure planning ap-
Figure 1: A diagram of the system architecture
proach does not account for the goals the individual char-
acters have, and have presented an alternative planning ap-
proach where each character’s actions have to serve a char-
acter motivation. Note that character motivations typically the appearance of the actual world to each agent. Dynamic
play an important role in detective stories as the motive of Epistemic Logic adds an action language that describes how
the murderer. agents’ beliefs change over time by introducing new worlds
Another important aspect in detective stories is that of that they consider possible or eliminating those that they no
character beliefs. In the beginning of the story, the detec- longer consider possible. There are several differen flavors
tive, like the reader, is unaware of the murderer’s identity, of Dynamic Epistemic Logic, of which we use one devel-
but the murderer often knows that the detective is looking oped by Baltag (2002). It follows what Van Ditmarsch et
for them. Likewise, other characters may actually have ob- al. call the dominant approach, in which actions are repre-
served some aspect of the crime, but may have something sented in a similar way to states, where each action also has
else to hide themselves. Ryan et al. 2015 describe virtual an appearance to the different agents. In this particular fla-
characters that build mental models of the world in a muta- vor it is also possible to have actions that agents only sus-
ble way, i.e. they may misremember or forget parts of what pect to happen, without any action actually occurring. Eger
they know, or they may (intentionally) lie to other agents. and Martens also described a macro system and runtime en-
However, these lies are generated randomly and not in ser- vironment, Ostari, that greatly simplifies writing epistemic
vice of some goal the character may have. actions in Baltag’s logic and is available freely (Eger and
Because of the relatively formulaic structure of murder Martens 2017b). Our game is built on top of this system as
mysteries, the idea of generating them has inspired a num- described in the next section.
ber of previous efforts. Green et al. (?) describe a system that
generated murder mystery adventure games from Wikipedia
articles about historical people. Stockdale (2003) presented Approach
ClueGen, a procedurally generated murder mystery game in
which the player acts as a detective in a murder case. In We have built a system that generates playable murder mys-
this game, the focus lies on characters’ relationships with tery stories based on properties of the different characters
each other, which informs how they share or hide informa- and how the detective can obtain clues to narrow down their
tion with the detective. Due to the uncertainty the player has search. These clues can be found either by examining the
about information provided by the non-player characters, the environment, or by questioning the characters themselves.
game provides the player with audio clues when a character However, some characters may be hiding a secret that they
is lying to enable solvability. In contrast, our approach fo- have committed a different transgression, and will not share
cuses on generating physical clues about the murder, with information that would reveal that transgression to the de-
some of the information related to them truthfully provided tective, unless the detective already knows about it. We track
by non-player characters, guaranteeing the case to be solv- the knowledge of the detective by using Dynamic Epistemic
able. As Eger and Martens (2017a) have described, Dynamic Logic in Ostari, which allows us to determine when the
Epistemic Logic, which we will briefly discuss in the next player has actually collected enough evidence to have a case
section, can be used to keep track of character knowledge in in court.
stories, and what they have deduced about the story world.
In our game, we utilize this approach to track which options The game consists of several parts, shown in Figure 1.
the player has eliminated and to determine whether or not Players interact with the game using a web browser that
they have enough evidence to arrest the murderer. connects to a Python web server that manages the game.
Upon initiating a session, the characters will be generated
by a Python script that generates an Ostari input file as de-
Dynamic Epistemic Logic scribed below. This file is then executed by Ostari, resulting
To formalize the deduction process of the detective, we use in a murder and the corresponding clues, either in physical
Dynamic Epistemic Logic, the logic of changing knowl- form in the game world, or as observed by the characters.
edge and beliefs (Van Ditmarsch, van Der Hoek, and Kooi During game play, Ostari manages the player’s beliefs and is
2007). In Epistemic Logic, beliefs are usually represented as responsible for updating them with the information obtained
sets worlds that the different agents consider possible, called by the investigative actions taken by the player.
Character Generation move between locations. The player can also accuse any sus-
Each game session in our game starts with newly generated pect who has not been ruled out as the murderer, although
characters produced by a Python module. This module uses the accusation will fail unless all other suspects have been
a template file, which contains the Ostari code with the ac- ruled out, i.e. the detective has enough evidence to bring the
tions for the particular game domain, but also has several case to court. Searching a room will always find any clues
placeholder variables that will be filled in with the char- in the room, whether they relate to the murder or to other
acter information. A game domain defines character prop- crimes. Suspects who know properties of the murderer will
erties, each of which has a list of possible values. For ex- tell the inspector upon being questioned, unless they have
ample, a property haircolor may have values blonde, the hidesecret motivation, which in-story signifies that
black and brown. For each character, we randomly draw they a secret, such as being involved in another crime. How-
from these lists of possible property values until we obtain a ever, if the inspector learns their secret (which is represented
unique assignment of property values. This uniqueness con- in the mechanics by believing that the suspect’s secret
straint ensures that the murder is solvable, if each property property has a specific value), and questions them after do-
value can be observed and the detective can determine what ing so, they are willing to admit to their actions and will
value the properties of the murderer have. Once the values share any information they might have. For example, if a
for the properties of the characters are determined, their as- character stole something and saw the murderer in the pro-
signment is converted to Ostari code and the appropriate cess, they will not be forthcoming during questioning be-
placeholder in the template file replaced with that code. cause they want to hide their own crime. However, when the
detective searches the thief’s room they might find the stolen
Generating the Murder and Clues property and be able to confront the thief, who will now
The generation of the murder itself, and therefore the clues cooperate. In epistemic terms, the thief will cooperate once
which the player finds, is handled by Ostari. The generated the detective has knowledge of their crime, which is what is
characters act as players within an Ostari game, with access tracked by Ostari. As the properties of the murderer and of
to domain dependent actions for moving, waiting, murder, the suspects are revealed, the game uses Ostari’s belief sys-
witnessing events, and potential other crimes. These actions tem to track the player’s knowledge of which suspects have
are constrained by their motivation property, so NPC which properties, and who could or could not have commit-
agents will not take significant actions such as murder or ted the murder. The player may accuse a suspect at any point
theft without an in-story reason. Character motivations pro- during the game, but only if they have gathered enough ev-
vide goals for the NPC agents. Currently, agents take ac- idence to eliminate all other suspects, the accusation will
tions randomly until they have achieved their goals, but be- be successful, and the player wins. If the player accuses the
cause actions other than movement are constrained by their wrong suspect, or even if they accuse the actual perpetrator
motivation, they can only take actions that will eventually of the murder but do not have enough evidence to uniquely
lead to their goals being achieved. Actions taken by NPC identify them as the murderer, the game ends with a loss for
agents can generate evidence, either in physical form, by e.g. the player.
leaving a hair behind to indicate their hair color (which sets To prevent the game from devolving into a matter of sim-
the hairclue property of their current location to be their ply gathering as much evidence as possible, there is a limit
haircolor), or by being witnessed by another character. on the number of actions the player can perform. Once the
For example, if an NPC wanders around the game world player runs out of time, the game also ends with a loss for
and observes the murder or parts thereof, they will have ev- the player. Players therefore have to carefully plan where to
idence for the player that will help them determine the mur- go and which information to gather.
derer. However, not all NPCs will be forthcoming with the
information they have, as we will describe in the next sec- User Interface
tion. The game makes sure that the player can always have Our game is presented in the form of a web page. The user
enough evidence to solve the murder by initially creating ev- is first presented with a short back story, and is then redi-
idence in the location of the murder for every property of the rected to the user interface shown in Figure 2. There they can
murderer, then deleting pieces of evidence if a character wit- choose which action to perform by clicking the appropriate
nesses the corresponding properties. This can be seen in the link. Each action has a corresponding effect, such as a move
code for the commitmurder and witnesshair actions, action moving the player character to a different location,
as shown in Figures 3 and 4. This serves the goal of creating or an observational action providing the player with infor-
a satisfying story, by reducing the chance that the evidence mation. This effect is reported to the player, but to simplify
will be trivially gathered into one place while maintaining the process of eliminating the impossible, our user interface
the solvability of the murder. also provides a summary table of the information they have
obtained about the various suspects.
Solving the Murder
To solve the murder, the player investigates the locations
in the game and interviews the suspects to determine who Results
could have committed the crime. The player can search the In this section we will provide a short discussion of an ex-
location they are currently at, question or observe the phys- ample scenario we have developed to demonstrate the ca-
ical properties of a suspect in the same location as them, or pabilities of our approach. A scenario consists of a setting,
Figure 2: A screenshot of the browser-based interface provided by our game. The player can choose between the different
actions on the left, and will be told about the outcomes of these actions below. On the right side the user is presented with a
summary of the facts they have uncovered about the suspects as well as what they know about the murder and murderer.
which is presented in the back story at the beginning of the questioning. However, the thief will cooperate if their theft
game, character properties and motivations, potential goals, is uncovered by the player.
and the corresponding actions the characters can perform.
Currently it is necessary that each property can be observed Action Encoding
in some way by the detective. Additionally, properties that As mentioned above, actions are written in Ostari. Figure
can be observed by NPCs can serve as evidence obtained 3 shows the code for the commitmurder action. The pa-
from questioning them. rameter p1 represents the murderer, whichis only known
to p1 themselves, i.e. all other characters will know that a
Setting and Characters murder occurred, but not who committed it. The action en-
For our example game we chose a cruise ship, the Enchanted sures that the murderer has a grudge against the victim, pre-
Princess of the Horizon, as the setting. As the back story in- vents edge cases such as the murderer killing themselves,
forms the player, one of the passengers on the ship has been or the inspector committing the crime with appropriate pre-
murdered while the ship is at sea and it is now headed for the conditions, performs the actual murder and places the evi-
next harbor. The detective only has limited time (or actions, dence. Additionally, a placeholder character called killer
in game terms) to determine the murderer, until the passen- is set up to have the same properties as the murderer. The
gers are allowed to disembark making it significantly harder public(killer, p1) indicates that this information is
for the authorities to apprehend the culprit. The game is lim- public to these characters only, but hidden from everyone
ited to a small area of the ship, consisting of a deck, a hall- else (by default, properties are not known to any character).
way, and the rooms of a small cast of NPCs, which are the As noted above, each murder places evidence for the mur-
suspects. The NPCs are Sylvia, Valciane, Porter, Dorothy, derer’s height and hair color, but if another character is able
and William. Each character has two physical properties, to observe one of these attributes, and the detective is there-
which are hair color (which can be blonde, black, or brown) fore able to obtain this information by interrogating them,
and height (which can be tall or short). Additionally, one this evidence is removed from the crime scene. Figure 4
character has a valuable gem. shows the action of witnessing a character’s hair color. It has
The initial motivations available in our scenario are hav- preconditions that ensure that there was a murder, the char-
ing a grudge against another NPC, and wanting to steal the acter is alive/active and at the location of the murder and that
gem. Each of these two intentions is assigned to one of they or someone else don’t already know the hair color of the
the characters, who will then set out to perform the murder murderer. It then removes the evidence indicating the hair
and steal the game, respectively. At the conclusion of their color from the murder location, by setting it to unknown
crimes, both of the characters obtain a new motivation of and updates the players belief with the telltruth state-
hiding their secret, which makes them uncooperative during ment.
commitmurder(p1(p1): Suspects, victim: Suspects)
{
precondition (grudge(p1) == victim) or (grudge(p1) == unknown);
precondition eq(p1) != victim;
precondition eq(p1) != inspector;
precondition Forall p in Suspects: murderer(p) == False;
precondition (location(p1) == location(victim) or
(location(p1) == unknown) or (location(victim) == unknown));
precondition active(p1) == True;
precondition active(victim) == True;
murderer(p1) = True;
active(victim) = False;
print("$*$", victim, ":is:deadˆ$ˆ");
public (killer, p1) motivation(killer) = motivation(p1);
public (killer, p1) haircolor(killer) = haircolor(p1);
public (killer, p1) tall(killer) = tall(p1);
public (killer, p1) grudge(killer) = grudge(p1);
hairclue(location(p1)) = haircolor(p1);
heightclue(location(p1)) = tall(p1);
murderlocation(game) = location(p1);
motivation(p1) = hidesecret;
secret(p1) = murder;
...
}
Figure 3: The code for the commitmurder action. The ommitted code only contains output directives for the back story.
witnesshair(p1: Players, c: Colors)
{
precondition active(p1) == True;
precondition location(p1) == murderlocation(game);
precondition Exists p in Suspects: active(p) == False;
precondition murderer(p1) == False;
precondition Forall x in Colors: (eq(x) == unknown) or
(not B (p1): haircolor(killer) == x);
precondition Forall p in Suspects: ((murderer(p) == True) or
(Forall x in Colors: (eq(x) == unknown) or
(not B (p): haircolor(killer) == x)));
hairclue(murderlocation(game)) = unknown;
telltruth (p1): haircolor(killer) == c
}
Figure 4: The code for the witnesshair action.
Example Game evidence to identify a murderer. In addition to physical evi-
For an example play-through, the system generated the fol- dence our system allows other characters to observe the mur-
lowing characters and motivations: der and either share that information or intentionally hide it
to protect another secret they have. This means that solv-
• Sylvia is tall, has black hair, and has a grudge against ing the game once does not trivialize the game in the fu-
Porter. ture. Player knowledge is tracked using Dynamic Epistemic
• William is tall, has brown hair, and has the gem. Logic as implemented by Ostari system to determine when
they have collected enough evidence. We have also shown
• Valciane is short, has black hair, and wants to steal an example game with a small number of properties, that
William’s gem. results in a moderate number of meaningfully distinct de-
• Porter is short, and has blonde hair. tective stories. For future work, we want to build upon this
foundation to create a wider variety of scenarios, by adding
• Dorothy is short, and has brown hair. additional character properties and motivations.
Note that the assignment of properties to characters is While our characters only follow very basic motivations,
unique, i.e. no two characters have the same values for all a possible future extension could give them more complex
properties. This means, if the detective finds evidence for goals, which would result in more variation. For example,
the murderer’s size and hair color, they can uniquely iden- rather than having a grudge as the underlying motivation for
tify the culprit. a murder, wanting the gem could also serve as the impe-
After the characters have been generated, they perform tus. A character with such a motivation would break into the
actions according to their motivations: room in which the gem is held, and if the owner is present
would necessarily have to murder them to obtain the gem.
• Valciane goes to William’s room and steals his gem, and A challenge that needs to be addressed in this case is to en-
her motivation changes to hiding the fact that she stole the sure that exactly one murder happens when multiple char-
gem. acters have motivations that might result in one. Such an
• Sylvia runs into Porter in the hallway, and murders him. extension might also incorporate Ostari’s AI planning sys-
Her motivation changes to hiding the fact that she mur- tem more deeply. Additionally, characters in our game might
dered Porter. Valciane is in the hallway, and witnesses the conceal what they know, but they will never outright lie to
fact that Sylvia has black hair (but not her height!). the player. However, lying of suspects is a staple of detective
fiction, and we are looking at ways to incorporate that into
This is where the player character comes in to investi-
our game. Rather than outright eliminating possibilities, as
gate Porter’s murder. To solve the case, they first observe
the belief system does in the version of Ostari used by the
the body, and deduce that the murderer must be tall from
game, the detective would have to reason about the probabil-
the angle of the wound. They then observe the suspects and
ities of different scenarios. Determining when the detective
can already rule out Valciane and Dorothy, both of whom
has successfully solved a murder in such cases remains a
are short. However, questioning the remaining two suspects
problem for future work.
does not yield any information, because William does not
know anything about the murder and Sylvia wants to hide
her involvement. When questioning the exonerated suspects References
the player is told that Valciane is hiding something, goes to Adams, T. 2017. Secret identities in dwarf fortress. Working
search her room and finds the stolen gem. When the player Notes of the AIIDE 2017 Workshop on Experimental AI in
questions Valciane again, she will tell them what she saw, Games.
since her theft was uncovered and she no longer has any-
Baltag, A. 2002. A logic for suspicious players: Epistemic
thing to hide. With this new information, the player is able
actions and belief–updates in games. Bulletin of Economic
to determine that Sylvia is the murderer and bring her to jus-
Research 54(1):1–45.
tice.
Note that in another play-through of the game, the thief Eger, M., and Martens, C. 2017a. Character beliefs in story
may observe both properties of the murderer, or none at all, generation. Working Notes of the AIIDE 2017 Workshop on
or have another character, who has nothing to hide and is Intelligent Narrative Technologies.
thus more willing to cooperate, observe the murderer, re- Eger, M., and Martens, C. 2017b. Practical specification of
quiring the player to employ different approaches in how to belief manipulation in games. Proceedings of the 13th AAAI
solve the murder. Additionally, while this sample scenario is International Conference on Artificial Intelligence and Inter-
relatively simple, it is possible to add more properties and active Digital Entertainment.
motivations for the characters, resulting in more opportuni- Hendrikx, M.; Meijer, S.; Van Der Velden, J.; and Iosup, A.
ties to hide and find information related to the murder. 2013. Procedural content generation for games: A survey.
ACM Transactions on Multimedia Computing, Communica-
Conclusion and Future Work tions, and Applications (TOMM) 9(1):1.
We have presented our approach to procedurally generated Riedl, M. O., and Young, R. M. 2010. Narrative planning:
murder mystery games, which works by generating char- balancing plot and character. Journal of Artificial Intelli-
acters that are guaranteed to be unique, and the necessary gence Research 39(1):217–268.
Ryan, J. O.; Summerville, A.; Mateas, M.; and Wardrip-
Fruin, N. 2015. Toward characters who observe, tell, misre-
member, and lie. Proc. Experimental AI in Games 2.
Stockdale, A. 2003. Cluegen: An exploration of procedu-
ral storytelling in the format of murder mystery games. In
Proceedings of the AIIDE workshop on Experimental AI in
Games, volume 2.
Van Dine, S. 2015. Twenty rules for writing detective stories.
Booklassic.
Van Ditmarsch, H.; van Der Hoek, W.; and Kooi, B. 2007.
Dynamic epistemic logic, volume 337. Springer Science &
Business Media.
Young, R. M. 1999. Notes on the use of plan structures in
the creation of interactive plot. In AAAI Fall Symposium on
Narrative Intelligence, 164–167.