COMP 763: Paper List

Paper Keywords

On the effects of loose causal consistency in mobile multiplayer games
Angie Chandler and Joe Finney. [BibTeX]

Keywords: [Online Gaming], [Mobile Gaming]
Length:Medium
Abstract: It is well understood that distributed multiplayer games, as soft real-time systems, require a degree of support from the underlying network in order to function correctly, in terms of predictable end to end bandwidth, latency and jitter. In a mobile environment, such applications face even greater challenges, as the latency of wireless networks is much higher than their wireline counterparts, jitter is often much higher due to network handoff and bandwidth is at a premium. In fact, the latency of many wide area wireless networks is beyond the tolerance of most multiplayer games, rendering such applications unusable. This paper presents the design and experimental evaluation of Rendezvous, a novel decentralized consistency management mechanism that enables the collaboration of multiple players in mobile real-time games, even in a high latency environment. The operation of the mechanism is validated through the analysis of a real world example - a distributed mobile multiplayer soccer game called Knockabout, which is designed to operate on the Smartphone platform. Experimental results are included not only comparing Rendezvous to an existing consistency mechanism, but also measuring the length of network delay tolerated by the platform and its effect on the players.

A Systematic Classification of Cheating in Online Games
Jeff Yan and Brian Randell. [BibTeX]

Keywords: [Online Gaming], [Cheating]
Length: Medium
Abstract: Cheating is rampant in current game play on the Internet. However, it is not as well understood as one might expect. In this paper, we summarize the various known methods of cheating, and we define a taxonomy of online game cheating with respect to the underlying vulnerability (what is exploited?), consequence (what type of failure can be achieved?) and the cheating principal (who is cheating?). This taxonomy provides a systematic introduction to the characteristics of cheats in online games and how they can arise. It is intended to be comprehensible and useful not only to security specialists, but also to game developers, operators and players who are less knowledgeable and experienced in security. One of our findings is that although cheating in online games is largely due to various security failures, the four traditional aspects of security confidentiality, integrity, availability and authenticity are insufficient to explain it. Instead, fairness becomes a vital additional aspect, and its enforcement provides a convincing perspective for understanding the role of security techniques in developing and operating online games.

Versatile Walk Engine
Ronan Boulic, Branislav Ulicny, Daniel Thalmann. [BibTeX]

Keywords: [Game Engine]
Length: Long
Abstract: Walking is one of the most characteristic motions of humans, and the walking animation is indispensable for any game featuring humans or human-like characters. We propose an efficient walk component for the reactive animation of biped characters of any size and proportions. The movement can be controlled by changing independently its style, desired speed, and desired target position. Compared to traditional approaches, our gait style parameterization provides an efficient way to generate a multitude of varied walking animations, as needed, for example, by crowd simulations (as seen in Figure 2.1). One of our key specifications is to allow changes at any time as natural-looking movements tend to fluctuate over time. The resulting challenge we address is to maintain the smoothness of the gait and the coherence of the steps while the speed and style parameters are changing. Combined with the introduction of an angular speed parameter, we show how the walk component deals with speed and position control to ease higher-level behavioral control. Finally, we demonstrate its potential in game-like settings: a group of nonplayer characters is controlled by a rule-based behavioral module, and a player character is interactively controlled by a gamepad

Particle-based communication among game agents
Mike Klaas, Tristram Southey, Warren Cheung. [BibTeX]

Keywords: [Artificial Intelligence]
Length: Short (Prequel to the next paper by Yang)
Abstract: One approach to creating realistic game AI is to create autonomous agents that can perform effectively with no more knowledge than a human player would have in their place. In a multi-agent setting, it is also necessary to devise a means for communicating among agents in collaborative game scenarios (such as a group of controlled agents that are searching for the player), since agents no longer have access to global knowledge. We present a method for communication using particle filters in the setting of game state estimation. Particle filters are an efficient, nonparametric means of performing inference in complex environments. Their use in game AI is particularly compelling, as they provide an easy way to represent nonlinear, non-Gaussian inferences about the state space, while exhibiting computational thrift. We demonstrate that communication among a group of agents using particle filters to reason about the state space can be accomplished in a natural way by sharing particles among the agents filters. We also show how a criterion for deciding when to communicate naturally falls out of this framework. We apply this model in the setting of coordinated target detection, and find that agents of heterogenous types and complexities can nevertheless coordinate effectively.

Particle-based State Estimation and Communication for Game Agents
Suling Yang. [BibTeX]

Keywords: [Artificial Intelligence]
Length: Short (Sequel to the previous paper by Klaas)
Abstract: Artificial intelligence for games is of great interest as video games are more and more popular. Nowadays, people are looking for more realistic game agents that take actions in the same way as intelligent human beings. To estimate the next state of a target, a game agent observes its surrounding and learns from these observations. Several agents can communicate to share information in order to find the target efficiently. Particle filtering has been widely applied in game AI, because it is an e±cient, nonparametric method to learn from observations and is effective even for nonlinear, non-Gaussian state space distribu- tion. In this project, I apply particle filters on state estimation for each individual game agent and on the communication in multi- agent settings. This report shows a few examples that I have tried and the results on how well two game agents can communicate via particle filters.

Story Representation and Interactive Drama
Brian Magerko. [BibTeX]

Keywords: [Game Narratives]
Length: Medium
Abstract: When building a story-intensive game, there is always the question of how much freedom to give the player. Give the player too little, and he may feel constrained and disconnected from the character he is controlling. Give him too much freedom, and the progression of the story may lag or stop altogether. The field of interactive drama attempts to strike a balance between interaction and authorship. The story experienced in an interactive drama is dependent both on the plot content authored as well as the player's choices in the story. Which story representation is appropriate for a particular approach to interactive drama and the relationship between that language and other elements of the architecture is a key factor in design. This paper introduces our interactive drama architecture, IDA, and addresses the requirements it has for a story representation. How those requirements are met by our representational choices is the focus of the rest of the paper.

Approximating Game-Theoretic Optimal Strategies for Full-scale Poker
Darse Billings, N. Burch, Aaron Davidson, Robert Holte, Jonathan Schaeffer, T. Schauenberg and Duane Szafron. [BibTeX]

Keywords: [Artificial Intelligence]
Length: Medium
Abstract: The computation of the first complete approximations of game-theoretic optimal strategies for fullscale poker is addressed. Several abstraction techniques are combined to represent the game of 2- player Texas Hold'em, having size O(10^18), using closely related models each having size O(10^7). Despite the reduction in size by a factor of 100 billion, the resulting models retain the key properties and structure of the real game. Linear programming solutions to the abstracted game are used to create substantially improved poker-playing programs, able to defeat strong human players and be competitive against world-class opponents.

Preventing Bots from Playing Online Games
Philippe Golle and Nicolas Ducheneaut. [BibTeX]

Keywords: [Online Gaming], [Cheating]
Length: Medium
Abstract: As multiplayer online gaming gains in economic and social importance, an increasingly large number of players is beginning to rely on bots (automated player agents) to gain unfair advantages in games. In this article we study the problem of restricting participation in online games to human players so they can enjoy the game without interference from the bots. We propose two broad approaches to prevent bots from playing online games. The first consists of seamlessly integrating software-based tests (known as reverse Turing tests or CAPTCHA tests) into online games to tell humans and computers apart. Our second contribution is to propose hardware instantiations of CAPTCHA tests. Our techniques are applicable in a wide variety of online games, from poker to "shoot'em ups." They are cost-effective, immune to cheating, and preserve the human players' enjoyment of each game. We conclude with a discussion of how approaches to deter the use of bots may complement our techniques to detect bots.

Pervasive games: bringing computer entertainment back to the real world
Carsten Magerkurth, Adrian David Cheok, Regan L. Mandryk and Trond Nilsen. [BibTeX]

Keywords: [Game Genres]
Length: Long
Abstract: This article gives an introduction and overview of the field of pervasive gaming, an emerging genre in which traditional, real-world games are augmented with computing functionality, or, depending on the perspective, purely virtual computer entertainment is brought back to the real world.The field of pervasive games is diverse in the approaches and technologies used to create new and exciting gaming experiences that profit by the blend of real and virtual game elements. We explicitly look at the pervasive gaming sub-genres of smart toys, affective games, tabletop games, location-aware games, and augmented reality games, and discuss them in terms of their benefits and critical issues, as well as the relevant technology base.

Stand up and take your place: identifying narrative elements in narrative adventure and role-play games
Bride Mallon and Brian Webb. [BibTeX]

Keywords: [Game Narratives], [Social Engineering]
Length: Long
Abstract Or Intro: This article reports results from a series of empirical studies exploring narrative dimensions of adventure and role-play in computer-game design. It identifies aspects of narrative employed in such games, considers the significance of narrative structures and devices in increasing user-engagement, and reflects on game-design implications.Because not all approaches identified in traditional narrative theory can be applied to the new, interactive media, a phenomenological, reader-response methodology was used in the studies to identify narrative considerations appropriate to game-players' experiences. In two model focus-group studies, evaluative responses to games played in a controlled environment were analyzed. From the factors identified as affecting engagement, those with narrative aspects were isolated and their significance assessed. Among the factors identified are characterization, identification, agency, motivation, plot, linearity, and authorial control. Also considered is the disruption of primal narrative features of narrative--causality, temporality, and linearity--within a hyper-structure, and a number of design techniques and strategies to resolve such tensions and promote user engagement are suggested.

Solving Checkers
Jonathan Schaeffer, Yngvi Y. Björnsson,, N. Burch, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu and Steve Sutphen. [BibTeX]

Keywords: [Solving Games]
Length: Medium
Abstract: AI has had notable success in building highperformance game-playing programs to compete against the best human players. However, the availability of fast and plentiful machines with large memories and disks creates the possibility of solving a game. This has been done before for simple or relatively small games. In this paper, we present new ideas and algorithms for solving the game of checkers. Checkers is a popular game of skill with a search space of 10^20 possible positions. This paper reports on our first result. One of the most challenging checkers openings has been solved - the White Doctor opening is a draw. Solving roughly 50 more openings will result in the game-theoretic value of checkers being determined.m

GameFlow: a model for evaluating player enjoyment in games
Penelope Sweetser and Peta Wyeth. [BibTeX]

Keywords: [Social Engineering]
Length: Long
Abstract: Although player enjoyment is central to computer games, there is currently no accepted model of player enjoyment in games. There are many heuristics in the literature, based on elements such as the game interface, mechanics, gameplay, and narrative. However, there is a need to integrate these heuristics into a validated model that can be used to design, evaluate, and understand enjoyment in games. We have drawn together the various heuristics into a concise model of enjoyment in games that is structured by flow. Flow, a widely accepted model of enjoyment, includes eight elements that, we found, encompass the various heuristics from the literature. Our new model, GameFlow, consists of eight elements -- concentration, challenge, skills, control, clear goals, feedback, immersion, and social interaction. Each element includes a set of criteria for achieving enjoyment in games. An initial investigation and validation of the GameFlow model was carried out by conducting expert reviews of two real-time strategy games, one high-rating and one low-rating, using the GameFlow criteria. The result was a deeper understanding of enjoyment in real-time strategy games and the identification of the strengths and weaknesses of the GameFlow model as an evaluation tool. The GameFlow criteria were able to successfully distinguish between the high-rated and low-rated games and identify why one succeeded and the other failed. We concluded that the GameFlow model can be used in its current form to review games; further work will provide tools for designing and evaluating enjoyment in games.

The social side of gaming: a study of interaction patterns in a massively multiplayer online game
Nicolas Ducheneaut and Robert J. Moore. [BibTeX]

Keywords: [Social Engineering]
Length: Medium
Abstract: Playing computer games has become a social experience. Hundreds of thousands of players interact in massively multiplayer online games (MMORPGs), a recent and successful genre descending from the pioneering multi-user dungeons (MUDs). These new games are purposefully designed to encourage interactions among players, but little is known about the nature and structure of these interactions. In this paper, we analyze player-to-player interactions in two locations in the game Star Wars Galaxies. We outline different patterns of interactivity, and discuss how they are affected by the structure of the game. We conclude with a series of recommendations for the design and support of social activities within multiplayer games.

Power games just want to have fun?: instrumental play in a MMOG.
T. L. Taylor. [BibTeX]

Keywords: [Social Engineering]
Length: Medium
Abstract: In this paper I explore a particular slice of massive multiplayer participants known as power gamers. Through my ethnography of EverQuest, as well as interviews with players, I analyze the ways these participants, who operate with a highly instrumental game-orientation, actually facilitate their play style through a variety of distinctly social activities. Rather than seeing this segment of the gaming population as "lone ranger" figures or via various other "geek gamer" myths, this work explores the way high-end players are actually embedded in deeply social structures, rituals, and practices.

Is Bayesian Imitation Learning the Route to Believable Gamebots?
C. Thurau, T. Paczian and C. Bauckhage. [BibTeX]

Keywords: [Artificial Intelligence]
Length: Medium
Abstract: As it strives to imitate observably successful actions, imitation learning allows for a quick acquisition of proven behaviors. Recent work from psychology and robotics suggests that Bayesian probability theory provides a mathematical framework for imitation learning. In this paper, we investigate the use of Bayesian imitation learning in realizing more life-like computer game characters. Following our general strategy of analyzing the network traffic of multi-player online games, we will present experiments in automatic imitation of behaviors contained in human generated data. Our results show that the Bayesian framework indeed leads to game agent behavior that appears very much human-like.

An improved safety solver for computer Go
X. Niu and M. Müller. [BibTeX]

Keywords: [Solving Games]
Length: Medium
Abstract: Most Go-playing programs use a combination of search and heuristics based on an inuence function to determine whether territories are safe. However, to assure the correct evaluation of Go positions, the safety of stones and territories must be proved by an exact method. The rst exact algorithm, due to Benson [1], determines the unconditional safety of stones and territories. Müller [3] develops static rules for detecting safety by alternating play, and introduces search-based methods. This paper describes new, stronger search-based techniques including regionmerging and a new method for efciently solving weakly dependent regions. In a typical nal position, more than half the points on the board can be proved safe by our current solver. This almost doubles the number of proven points compared to the 26.4% reported in [3].

ScriptEase - A Demonstration of Ambient Behavior Generation for Computer Role-Playing Games
Maria Cutumisu, Matthew McNaughton, Duane Szafron, Thomas Roy, Curtis Onuczko, Jonathan Schaeffer, Mike Carbonaro. [BibTeX]

Keywords: [Game Development]
Length: Very Small
Abstract: ScriptEase is a publicly-available visual tool that enables game designers to easily create complex interactive stories for computer role-playing games (CRPGs), without programming. In particular, ScriptEase facilitates the automatic generation of scripting code for ambient behaviors of the numerous non-player characters (NPCs) that populate the CRPG world. ScriptEase generates this scripting code using generative design patterns, responding to the challenge of creating entertaining and non-predictable behaviors for NPCs, without the effort of writing custom complex scripts for each NPC. This demonstration describes the steps of generating complex and non-repetitive ambient behavior scripts using generative behavior patterns with ScriptEase, in the context of Neverwinter Nights, a CRPG from BioWare Corp.

ScriptEase: Generative Design Patterns for Computer Role-Playing
Matthew McNaughton, Maria Cutumisu, Duane Szafron, Jonathan Schaeffer, James Redford and Dominique Parker). [BibTeX]

Keywords: [Game Development]
Length: Medium
Abstract: Recently, some researchers have argued that generative design patterns (GDPs) can leverage the obvious design re-use that characterizes traditional design patterns into code re-use. This paper provides additional evidence that GDPs are both useful and productive. Specifically, the current state-of-the-art in the domain of computer games is to script individual game objects to provide the desired interactions for each game adventure. We use BioWare Corp.\u2019s popular Neverwinter Nights computer role-playing game to show how GDPs can be used to generate game scripts. This is a particularly good domain for GDPs, since game designers often have little or no programming skills. We demonstrate our approach using a new GDP tool called ScriptEase.

A Novel Obsolescence-Based Approach to Event Delivery Synchronization in Multiplayer Games
S. Ferretti, M. Roccetti. [BibTeX]

Keywords: [Online Gaming]
Length: Long
Abstract: Revenues generated by video games typically surpass those provided by the cinematography industry. This large and emerging market is driving researchers and practitioners to develop innovative software techniques that allow game players to enjoy exciting and interactive game experiences, even when modern wireless handheld devices are used. In this scenario, there is a growing demand of distributed gaming architectures that are able to provide support to the development of interactive multiplayer networked game applications. To this aim, we have designed and developed an event delivery service for multiplayer networked games that drops obsolete events to guarantee an acceptable interaction degree among remote players, while maintaining the game state consistency. We report important results of an experimental study we have carried out that confirm the viability of our approach.

(P)NFG: A Language and Runtime System for Structured Computer Narratives
Christopher J. F. Pickett and Clark Verbrugge and Félix Martineau. [BibTeX]

Keywords: [Game Narratives]
Length: Medium
Abstract: Complex computer game narratives can suffer from logical consistency and playability problems if not carefully constructed, and current, state of the art design tools do little to help analysis or ensure good narrative properties. A formallygrounded system that allows for relatively easy design and analysis is therefore desireable. We present a language and an environment for expressing game narratives based on a structured form of Petri Net, the Narrative Flow Graph. Our "(P)NFG" system provides a simple, high level view of narrative programming that maps onto a low level representation suitable for expressing and analysing game properties. The (P)NFG framework is demonstrated experimentally by modelling narratives based on non-trivial interactive fiction games, and integrates with the NuSMV model checker. Our system provides a necessary component for systematic analysis of computer game narratives, and lays the foundation for all-around improvements to game quality.