Ordered, linear, and other substructural type systems allow us to expose deep properties of programs at the syntactic level of types. In this paper, we develop a family of unary logical relations that allow us to prove consequences of parametricity for a range of substructural type systems. A key idea is to parameterize the relation by an algebra, which we exemplify with a monoid and commutative monoid to interpret ordered and linear type systems, respectively. We prove the fundamental theorem of logical relations and apply it to deduce extensional properties of inhabitants of certain types. Examples include demonstrating that the ordered types for list append and reversal are inhabited by exactly one function, as are types of some tree traversals. Similarly, the linear type of the identity function on lists is inhabited only by permutations of the input. Our most advanced example shows that the ordered type of the list fold function is inhabited only by the fold function.

Logic programming, as exemplified by datalog, defines the meaning of a program as its unique smallest model: the deductive closure of its inference rules. However, many problems call for an enumeration of models that vary along some set of choices while maintaining structural and logical constraints—there is no single canonical model. The notion of stable models for logic programs with negation has successfully captured programmer intuition about the set of valid solutions for such problems, giving rise to a family of programming languages and associated solvers known as answer set programming. Unfortunately, the definition of a stable model is frustratingly indirect, especially in the presence of rules containing free variables. We propose a new formalism, finite-choice logic programming, that uses choice, not negation, to admit multiple solutions. Finite-choice logic programming contains all the expressive power of the stable model semantics, gives meaning to a new and useful class of programs, and enjoys a least-fixed-point interpretation over a novel domain. We present an algorithm for exploring the solution space and prove it correct with respect to our semantics. Our implementation, the Dusa logic programming language, has performance that compares favorably with state-of-the-art answer set solvers and exhibits more predictable scaling with problem size.

Game authoring can be a difficult, technical process; exploring new ways to describe games and game mechanics may help make game authoring more accessible. In this work, we present Tile Rewrite Rule Behavior Trees (TRRBTs): a concept for a domain-specific language for authoring tile-based, turn-based games. The approach combines tile rewrite rules and behavior trees. Using TRRBTs, a game’s state is represented as a grid of tiles, the behavior trees describe the overall flow of the game, and the rewrite rules at leaf nodes describe changes in game state. We include transform nodes, which apply transformations to other nodes in the behavior tree, allowing more complex mechanics to be expressed in a compact way. We demonstrate a text-based approach to using TRRBTs to create several simple games, show how the approach allows re-use of trees to build on existing games, and show how they can provide a unified representation for procedural content generation and enemy AI along with game mechanics.

Free and open source social platform software has dramatically lowered the barrier to entry for anyone to set up and administer their own social network. This new population of social network administrators thus assume data management responsibilities for sociotechnical systems. Administrators have the power to customize this software, including data collection and data retention, potentially leading to radically different privacy policies. To better understand the characteristics — e.g., the variability, prohibitions, and permissions — of privacy policies on these new social networking platforms, we have conducted a case study of Mastodon. We performed a text analysis of 351 privacy policies and a survey of 104 Mastodon administrators. While most administrators used the default policy that ships with the Mastodon software, we observed that approximately ten percent of our sample tailored their privacy policies to their instances and that some administrators conflated codes of conduct with privacy policies. Our findings suggest the existing market-based individualistic frameworks for thinking about privacy policies do not adequately address this emerging community.

Game description languages have a variety of uses, including formal reasoning about the emergent consequences of a game's mechanics, implementation of artificial intelligence decision-making where the game's rules make up the space of possible actions, automated game and level generation, and game prototyping for the sake of low-time-investment design and tinkering. However, in practice, a new game description language has been invented for almost every new use case, without providing formal underpinnings that follow generalizable principles and can be reasoned about separately from the specific software implementation of the language. Ceptre is a language that attempts to break this pattern, based on an old idea known as multiset rewriting. This paper describes the language formally, through example, and in a tutorial style, then demonstrates its use for writing formal specifications of game mechanics so that they may be interactively explored, queried, and analyzed in a computational framework. Ceptre allows designers to step through executions, interact with the mechanics from the standpoint of a player, run random simulated playthroughs, collect and analyze data from said playthroughs, and formally verify mathematical properties of the mechanics, and it has been used in a number of research projects since its inception, for applications such as procedural narrative generation, formal game modeling, and game AI.

Background and Context: Open-ended programming projects encourage novice students to choose and pursue projects based on their own ideas and interests, and are widely used in many introductory programming courses. However, novice programmers encounter challenges exploring and discovering new ideas, implementing their ideas, and applying unfamiliar programming concepts and APIs. Code examples are one of the primary resources students use to apply code usage patterns and learn API knowledge, but little work has investigated the effect of having access to examples on students’ open-ended programming experience.

Many students rely on examples when learning to program, but they often face barriers when incorporating these examples into their own code and learning the concepts they present. As a step towards designing effective example interfaces that can support student learning, we investigate novices' needs and strategies when using examples to write code. We conducted a study with 12 pairs of high school students working on open-ended game design projects, using a system that allows students to browse examples based on their functionality, and to view and copy the example code. We analyzed interviews, screen recordings, and log data, identifying 5 moments when novices request examples, and 4 strategies that arise when students use examples. We synthesize these findings into principles that can inform the design of future example systems to better support students.

Our researchers seek to support students in building block-based programming projects that are motivating and engaging as well as valuable practice in learning to code. A difficult part of the programming process is planning. In this research, we explore how novice programmers used a custom-built planning tool, PlanIT, contrasted against how they used storyboarding when planning games. In a three-part study, we engaged novices in planning and programming three games: a maze game, a break-out game, and a mashup of the two. In a set of five case studies, we show how five pairs of students approached the planning and programming of these three games, illustrating that students felt more creative when storyboarding rather than using PlanIT. We end with a discussion on the implications of this work for designing supports for novices to plan open-ended projects.

Open-ended programming engages students by connecting computing with their real-world experience and personal interest. However, such open-ended programming tasks can be challenging, as they require students to implement features that they may be unfamiliar with. Code examples help students to generate ideas and implement program features, but students also encounter many learning barriers when using them. We explore how to design code examples to support novices' effective example use by presenting our experience of building and deploying Example Helper, a system that supports students with a gallery of code examples during open-ended programming. We deployed Example Helper in an undergraduate CS0 classroom to investigate students' example usage experience, finding that students used different strategies to browse, understand, experiment with, and integrate code examples, and that students who make more sophisticated plans also used more examples in their projects.

Tile maps are useful for a wide variety of games, particularly tabletop role-playing games. However, existing tools for creating them usually either require the map to be created entirely by hand, or procedurally generate the entire map with only a few parameters being controlled by the user. In previous work, we presented a mixed-initiative tool for generating tile maps that gives the user precise control over the generated map while still allowing them to take advantage of procedural generation. In this work, we empirically evaluate this tool by asking five users to complete three thinkaloud tasks and a post-task survey. We found that users found the tool fun to use and that it made map design easier. We discuss takeaways and how this tool and similar tools can be made better.

Block-based programming environments, such as Scratch and Snap!, engage users to create programming artifacts such as games and stories, and share them in an online community. Many Snap! users start programming by reusing and modifying an example project, but encounter many barriers when searching and identifying the relevant parts of the program to learn and reuse. We present Pinpoint, a system that helps Snap! programmers understand and reuse an existing program by isolating the code responsible for specific events during program execution. Specifically, a user can record an execution of the program (including user inputs and graphical output), replay the output, and select a specific time interval where the event of interest occurred, to view code that is relevant to this event. We conducted a small-scale user study to compare users’ program comprehension experience with and without Pinpoint, and found suggestive evidence that Pinpoint helps users understand and reuse a complex program more efficiently.

Open-ended programming increases students' motivation by allowing them to solve authentic problems and connect programming to their own interests. However, such open-ended projects are also challenging, as they often encourage students to explore new programming features and attempt tasks that they have not learned before. Code examples are effective learning materials for students and are well-suited to supporting open-ended programming. However, there is little work to understand how novices learn with examples during open-ended programming, and few real-world deployments of such tools. In this paper, we explore novices' learning barriers when interacting with code examples during open-ended programming. We deployed Example Helper, a tool that offers galleries of code examples to search and use, with 44 novice students in an introductory programming classroom, working on an open-ended project in Snap. We found three high-level barriers that novices encountered when using examples: decision, search, and integration barriers. We discuss how these barriers arise and design opportunities to address them.

Project-based learning can encourage and motivate students to learn through exploring their own interests, but introduces special challenges for novice programmers. Recent research has shown that novice students perceive themselves to be "bad at programming, especially when they do not know how to start writing a program, or need to create a plan before getting started. In this paper, we present PlanIT, a guided planning tool integrated with the Snap! programming environment designed to help novices plan and program their open-ended projects. Within PlanIT, students can add a description for their project, use a to do list to help break down the steps of implementation, plan important elements of their program including actors, variables, and events, and view related example projects. We report findings from a pilot study of high school students using PlanIT, showing that students who used the tool learned to make more specific and actionable plans. Results from student interviews show they appreciate the guidance that PlanIT provides, as well as the affordances it offers to more quickly create program elements.

Villanelle is an interactive fiction authoring tool designed to support autonomous non-player characters, or “char-acter AI.” Character AI is notoriously challenging for interactive fiction authors to develop, especially for authors approaching interactive fiction from a writing rather than programming background. This paper describes a participatory design process in which we assess the author experience with Villanelle and build a new tool iteration to support their needs. The results of our first user study demonstrate the strong potential of Villanelle's incorporation of behavior trees as an easy-to-Learn computational model for character AI, but they also indicate syntax challenges for inexperienced programmers. Consequently, we developed a block-based programming interface for Villanelle and recruited a new set of study participants to evaluate this iteration using the same study instruments. The results indicate improvements in Villanelle's usability and creativity support for inexperienced programmers.

One approach to teaching game design to students with a wide variety of disciplinary backgrounds is through team game projects that span multiple weeks, up to an entire term. However, open-ended, creative projects introduce a gamut of challenges to novice programmers. Our goal is to assist game design students with the planning stage of their projects. This paper describes our data collection process through three course interventions and student interviews, and subsequent analysis in which we learned students had difficulty expressing their creative vision and connecting the game mechanics to the intended player experience. We present these results as a step towards the goal of scaffolding the planning process for student game projects, supporting more creative ideas, clearer communication among team members, and a stronger understanding of human-centered design in software development.

Bolstered by a growing interest in simulating believable non-player characters (NPCs), work on NPC models has spanned topics such as planning, procedural storytelling, decision-making, and social dynamics. However, research groups work in isolation, designing and discussing their character models with disparate approaches, often using project-specific terminology. This makes it challenging to identify, classify, and accumulate existing knowledge. It is our position that since modelling of virtual characters has become an integral part of the scientific practice in our field, we must develop a common taxonomy to discuss these models. With this goal in mind, we conduct an in-depth analysis of a selection of projects, categorizing existing agent social interactions, and comparing results from research-based and commercial social simulation works in the entertainment domain. We conceptualize a taxonomy that classifies agent interactions by their social behaviours, inter-agent communication, knowledge flow, and the change in their relationships. We posit such a taxonomy would allow scientists to reproduce and evaluate existing models, collaborate on standards, share advances with other researchers and practitioners, allow for better communication and methodologies developed for new techniques, and allow for a more rigorous model-to-model analysis.

The cooperative card gameHanabihas become of increasing interest in the community, since it combines partially hidden information with information exchange using restricted communication channels. In this article, we describe artificial intelligence agents that are designed to play the game with human players. Our agents make use of the fact that human players expect other players to act intentionally by formulating goals of their own and planning how to achieve them. They then use the available actions available to communicate their plan to the human player. On the flip side, our agents also interpret the actions performed by the human player as containing information about their plans. We present two different variants of our agent that perform this interpretation in different ways. Additionally, since part of human communication happens in subtle indirect ways, we also demonstrate that our agent can use the timing of the human player’s actions as additional information. In order to validate our agents, we have performed two separate experiments: one was done to validate the intentional component of the agents, while the other focused on the interpretation of received information. In this article, we also present the results obtained from these two experiments.

Extensive research has been conducted on using procedural music generation in real-time applications such as accompaniment to musicians, visual narratives, and games. However, less attention has been paid to the enhancement of textual narratives through music. In this paper, we present Mood Into Note Using Extracted Text (MINUET), a novel system that can procedurally generate music for textual narrative segments using sentiment analysis. Textual analysis of the flow and sentiment derived from the text is used as input to condition accompanying music. Music generation systems have addressed variations through changes in sentiment. By using an ensemble predictor model to classify sentences as belonging to particular emotions, MINUET generates text-accompanying music with the goal of enhancing a reader’s experience beyond the limits of the author’s words. Music is played via the JMusic library and a set of Markov chains specific to each emotion with mood classifications evaluated via stratified 10-fold cross validation. The development of MINUET affords the reflection and analysis of features that affect the quality of generated musical accompaniment for text. It also serves as a sandbox for further evaluating sentiment-based systems on both text and music generation sides in a coherent experience of an implemented and extendable experiential artifact.

Procedural narrative generation systems often focus on autonomous agent based simulations to create emergent interactions, plan-based approaches to provide guarantees for coherence, or using elements of simulation to guide plan-based approaches. These different approaches, with some exceptions, tend to trade off character autonomy in service of more designer controlled experiences or content authoring in service of encoding domain knowledge of possible branches of the narrative and participating characters. We have developed a system, called Stories of the Town, that automatically generates narratives by synthesizing three distinct approaches to traditional narrative generation: context-free grammars, planning, and simulation. More specifically, our system generates narratives via probabilistic context-free grammars applied to state-space planning problem solutions from planning problem formulations of simulated character models. Our system uses character simulations to generate variety in narratives and ensures narrative coherence through authoring probabilistic context-free grammars. By doing so, this system takes advantage of the strengths of each individual approach (e.g. controllability, scalability, intentionality, and variety) to generate narratives that are extensible, expressive, consistent with simulated character personalities and histories, and controllable. We show that this system has strong potential in automatically generating varied, complex, consistent, and goal-oriented narratives. Further development of the system will allow for more efficient utilization of the strengths of each narrative generation approach while also using these strengths to supplement their individual shortcomings.

Systems understanding is a skill required to solve many of the world’s most important problems, from climate change to immunotherapy to social decision-making. However, these problems also require communication among experts with diverse skill sets and academic backgrounds. Our long-term goal is to facilitate systems understanding across a range of disciplines through end-user computational modeling tools. This paper presents the Ceptre Editor, a structure editor for the rule-based programming language Ceptre. The Ceptre Editor runs in the browser and offers a visual interface and integrated development environment for Ceptre, following design recommendations from end-user programming, with the goal of providing discoverable affordances for program construction and maintaining syntactic well-formedness at each edit state. We performed a preliminary evaluation of the tool through a qualitative study, assessing the editors effectiveness at helping users understand and extended a system model, and found promising results regarding learnability and mental model accuracy.

While generative approaches to game design offer great promise, systems can only reliably generate what they can “understand,” which is often represented in a limited, implicit form in hand-crafted evaluation functions or constructive rules. Proceduralist readings, a semiformal approach for interpreting the meaning of a game based on its underlying processes and interactions in conjunction with aesthetic and cultural cues, offer a novel, systematic approach to game understanding. We formalize proceduralist argumentation as a logic program that performs static reasoning over game specifications to derive higher level meanings, as part of Gemini, a bidirectional game analysis and generation system.

Open world games present players with more freedom than games with linear progression structures. However, without clearly-defined objectives, they often leave players without a sense of purpose. Most of the time, quests and objectives are hand-authored and overlaid atop an open world's mechanics. But what if they could be generated organically from the gameplay itself? The goal of our project was to develop a model of the mechanics in Minecraft that could be used to determine the ideal placement of objectives in an open world setting. We formalized the game logic of Minecraft in terms of logical rules that can be manipulated in two ways: they may be executed to generate graphs representative of the player experience when playing an open world game with little developer direction; and they may be statically analyzed to determine dependency orderings, feedback loops, and bottlenecks. These analyses may then be used to place achievements on gameplay actions algorithmically.

Formal models of games help us account for and predict behavior, leading to more robust and innovative designs. While the games research community has proposed many formalisms for both the "game half" (game models, game description languages) and the "human half" (player modeling) of a game experience, little attention has been paid to the interface between the two, particularly where it concerns the player expressing her intent toward the game. We describe an analytical and computational toolbox based on programming language theory to examine the phenomenon sitting between control schemes and game rules, which we identify as a distinct player intent language for each game.

Conversations with non-player characters (NPCs) in games are typically confined to dialogue between a human player and a virtual agent, where the conversation is initiated and controlled by the player. To create richer, more believable environments for players, we need conversational behavior to reflect initiative on the part of the NPCs, including conversations that include multiple NPCs who interact with one another as well as the player.