Robustness to distribution shift has become a growing concern for text and image models as they transition from research subjects to deployment in the real world. However, high-quality benchmarks for distribution shift in tabular machine learning tasks are still lacking despite the widespread real-world use of tabular data and differences in the models used for tabular data in comparison to text and images. As a consequence, the robustness of tabular models to distribution shift is poorly understood. To address this issue, we introduce TableShift, a distribution shift benchmark for tabular data. TableShift contains 15 binary classification tasks in total, each with an associated shift, and includes a diverse set of data sources, prediction targets, and distribution shifts. The benchmark covers domains including finance, education, public policy, healthcare, and civic participation, and is accessible using only a few lines of Python code via the TableShift API. We conduct a large-scale study comparing several state-of-the-art tabular data models alongside robust learning and domain generalization methods on the benchmark tasks. Our study demonstrates (1) a linear trend between in-distribution (ID) and out-of-distribution (OOD) accuracy; (2) domain robustness methods can reduce shift gaps but at the cost of reduced ID accuracy; (3) a strong relationship between shift gap (difference between ID and OOD performance) and shifts in the label distribution. The benchmark data, Python package, model implementations, and more information about TableShift are available at https://github.com/mlfoundations/tableshift and https://tableshift.org .

Researchers have proposed many methods for fair and robust machine learning, but comprehensive empirical evaluation of their subgroup robustness is lacking. In this work, we address this gap in the context of tabular data, where sensitive subgroups are clearly-defined, real-world fairness problems abound, and prior works often do not compare to state-of-the-art tree-based models as baselines. We conduct an empirical comparison of several previously-proposed methods for fair and robust learning alongside state-of-the-art tree-based methods and other baselines. Via experiments with more than $340{,}000$ model configurations on eight datasets, we show that tree-based methods have strong subgroup robustness, even when compared to robustness- and fairness-enhancing methods. Moreover, the best tree-based models tend to show good performance over a range of metrics, while robust or group-fair models can show brittleness, with significant performance differences across different metrics for a fixed model. We also demonstrate that tree-based models show less sensitivity to hyperparameter configurations, and are less costly to train. Our work suggests that tree-based ensemble models make an effective baseline for tabular data, and are a sensible default when subgroup robustness is desired. See https://github.com/jpgard/subgroup-robustness-grows-on-trees for code to reproduce our experiments and detailed experimental results.

Research suggests that parental engagement through Joint Media Engagement (JME) is an important factor in children's learning for coding and programming. Unfortunately, parents with limited technology background may have difficulty supporting their children's access to programming. English-language learning (ELL) families from marginalized communities face particular challenges in understanding and supporting programming, as code is primarily authored using English text. We present BlockStudio, a programming tool for empowering ELL families to jointly engage in introductory coding, using an environment embodying two design principles, text-free and visually concrete. We share a case study involving three community centers serving immigrant and refugee populations. Our findings show ELL families can jointly engage in programming without text, via co-creation and flexible roles, and can create a range of artifacts, indicating understanding of aspects of programming within this environment. We conclude with implications for coding together in ELL families and design ideas for text-free programming research.

K-8 mathematics students must learn many procedures, such as addition and subtraction. Students frequently learn "buggy' variations of these procedures, which we ideally could identify automatically. This is challenging because there are many possible variations that reflect deep compositions of procedural thought. Existing approaches for K-8 math use manually specified variations which do not scale to new math algorithms or previously unseen misconceptions. Our system examines students' answers and infers how they incorrectly combine basic skills into complex procedures. We evaluate this approach on data from approximately 300 students. Our system replicates 86% of the answers that contain clear systematic mistakes (13%). Investigating further, we found 77% at least partially replicate a known misconception, with 53% matching exactly. We also present data from 29 participants showing that our system can demonstrate inferred incorrect procedures to an educator as successfully as a human expert.

In order for reinforcement learning systems to learn quickly in vast action spaces such as the space of all possible pieces of text or the space of all images, leveraging human intuition and creativity is key. However, a human-designed action space is likely to be initially imperfect and limited; furthermore, humans may improve at creating useful actions with practice or new information. Therefore, we propose a framework in which a human adds actions to a reinforcement learning system over time to boost performance. In this setting, however, it is key that we use human effort as efficiently as possible, and one significant danger is that humans waste effort adding actions at places (states) that aren't very important. Therefore, we propose Expected Local Improvement (ELI), an automated method which selects states at which to query humans for a new action. We evaluate ELI on a variety of simulated domains adapted from the literature, including domains with over a million actions and domains where the simulated experts change over time. We find ELI demonstrates excellent empirical performance, even in settings where the synthetic "experts" are quite poor.

Educational games have a potentially significant role to play in the increasing efforts to expand access to computer science education. Computational thinking is an area of particular interest, including the development of problem-solving strategies like divide and conquer. Existing games designed to teach computational thinking generally consist of either open-ended exploration with little direct guidance or a linear series of puzzles with lots of direct guidance, but little exploration. Educational research indicates that the most effective approach may be a hybrid of these two structures. We present Dragon Architect, an educational computational thinking game, and use it as context for a discussion of key open problems in the design of games to teach computational thinking. These problems include how to directly teach computational thinking strategies, how to achieve a balance between exploration and direct guidance, and how to incorporate engaging social features. We also discuss several important design challenges we have encountered during the design of Dragon Architect. We contend the problems we describe are relevant to anyone making educational games or systems that need to teach complex concepts and skills.

Understanding how players interact with games is an important challenge for designers. When playing games centered around problem solving, such as logic puzzles like Sudoku or Nonograms, people employ a rich structure of domain-specific knowledge and strategies that are not obvious from the description of a game's rules. This paper explores automatic discovery of player-oriented knowledge and strategies, with the goal of enabling applications ranging from difficulty estimation to puzzle generation to game progression analysis. Using the popular puzzle game Nonograms as our target domain, we present a new system for learning human-interpretable rules for solving these puzzles. The system uses program synthesis, powered by an SMT solver, as the primary learning mechanism. The learned rules are represented as programs in a domain-specific language for condition-action rules. Given game mechanics and a training set of small Nonograms puzzles, our system is able to learn sound, concise rules that generalize to a test set of large real-world puzzles. We show that the learned rules outperform documented strategies for Nonograms drawn from tutorials and guides, both in terms of coverage and quality.

Countless human pursuits depend upon collaborative problem solving, especially in complex, open-ended domains. As part of the growing technological support for such collaboration, an opportunity exists to design systems that actively guide and facilitate collaborative problem solving toward the most productive outcomes. A better understanding of the dynamics of open-ended collaboration on complex problems is needed to realize this opportunity. Motivated by this need for better understanding, we investigate the collaborative problem solving ecosystem of the scientific-discovery game Foldit. Our investigation is guided by two primary questions: how do the social aspects of Foldit impact an individual's behavior? and what factors have significant impact on group success? We find that collaboration and competition are associated with increased participation and that collaboration increases individual performance. We also find that measures of group skill, individual skill, and participation correlate with better group performance.

In many real-world reinforcement learning problems, we have access to an existing dataset and would like to use it to evaluate various learning approaches. Typically, one would prefer not to deploy a fixed policy, but rather an algorithm that learns to improve its behavior as it gains more experience. Therefore, we seek to evaluate how a proposed algorithm learns in our environment, meaning we need to evaluate how an algorithm would have gathered experience if it were run online. In this work, we develop three new evaluation approaches which guarantee that, given some history, algorithms are fed samples from the distribution that they would have encountered if they were run online. Additionally, we are the first to propose an approach that is provably unbiased given finite data, eliminating bias due to the length of the evaluation. Finally, we compare the sample-efficiency of these approaches on multiple datasets, including one from a real-world deployment of an educational game.

Prior research has established that long-term interests in programming are often shaped by formative computing experiences, especially those involving programming and graphics. Existing authoring environments for children (ages 9-14) to make 2D games and animations require them to: (a) create programs, (b) customize templates, or (c) combine rewrite rules with programs. One way to support early experiences in computing for a more diverse set of learners is to simplify such authoring systems, by removing text heavy code and minimizing cognitive load, which can allow separation of coding concepts from writing code. In this paper, we describe an exploratory system we are designing to test this idea, called BlockStudio. Using a Programming By Example paradigm, children manipulate colored blocks on the screen to specify desired behavior via concrete changes. Based on these inputs, our system synthesizes generalized rules based on color. We give a brief overview of our current prototype, then share insights gleaned from two intergenerational co-design sessions with children and discuss implications for designers of similar systems.

We propose a novel sensing technique called proactive sensing. Proactive sensing continually repositions a camera-based sensor as a way to improve hand pose estimation. Our core contribution is a scheme that effectively learns how to move the sensor to improve pose estimation confidence while requiring no ground truth hand poses. We demonstrate this concept using a low-cost rapid swing arm system built around the state-of-the-art commercial sensing system Leap Motion. The results from our user study show that proactive sensing helps estimate users' hand poses with higher confidence compared to both static and random sensing. We further present an online model update to improve performance for each user.

The current state-of-the-art method for generating educational content, such as math word problems and hints, is manual authoring by domain experts. Unfortunately, this is costly, time consuming, and produces content that lacks diversity. Attempts to automatically address the time and diversity issues through natural language generation still do not produce content that is sufficiently creative and varied. Crowdsourcing is a viable alternative - there has been a great deal of research on leveraging human creativity to solve complex problems, such as user interface design. However, these systems typically decompose complex tasks into subtasks. Writing a single word problem or hint is a small enough problem that it is unclear how to further break it down, but also far more complex than typical microtasks like image labeling. Therefore, it is not obvious how to apply these worker improvement methods or which ones are most effective (if at all). We build upon successful task design factors in prior work and run a series of iterative studies, incrementally adding different worker-support elements. Our results show that successive task designs improved accuracy and creativity.

Student retention is a central challenge in systems for learning at scale. It has been argued that educational video games could improve student retention by providing engaging experiences and informing the design of other online learning environments. However, educational games are not uniformly effective. Our recent research shows that player retention can be increased by using a brain points incentive structure that rewards behaviors associated with growth mindset, or the belief that intelligence can grow. In this paper, we expand on our prior work by providing new insights into how growth mindset behaviors can be effectively promoted in the educational game Refraction. We present results from an online study of 25,000 children who were exposed to five different versions of the brain points intervention. We find that growth mindset animations cause a large number of players to quit, while brain points encourage persistence. Most importantly, we find that awarding brain points randomly is ineffective; the incentive structure is successful specifically because it rewards desirable growth mindset behaviors. These findings have important implications that can support the future generalization of the brain points intervention to new educational contexts.

Current algorithms for the standard multi-armed bandit problem have good empirical performance and optimal regret bounds. However, real-world problems often differ from the standard formulation in several ways. First, feedback may be delayed instead of arriving immediately. Second, the real world often contains structure which suggests heuristics, which we wish to incorporate while retaining the best-known theoretical guarantees. Third, we may wish to make use of an arbitrary prior dataset without negatively impacting performance. Fourth, we may wish to efficiently evaluate algorithms using a previously collected dataset. Surprisingly, these seemingly-disparate problems can be addressed using algorithms inspired by a recently-developed queueing technique. We present the Stochastic Delayed Bandits (SDB) algorithm as a solution to these four problems, which takes black-box bandit algorithms (including heuristic approaches) as input while achieving good theoretical guarantees. We present empirical results from both synthetic simulations and real-world data drawn from an educational game. Our results show that SDB outperforms state-of-the-art approaches to handling delay, heuristics, prior data, and evaluation.

A long-term goal of game design research is to achieve end-to-end automation of much of the design process, one aspect of which is creating effective level progressions. A key difficulty is getting the player to practice with interesting combinations of learned skills while maintaining their engagement. Although recent work in task generation and sequencing has reduced this effort, we still lack end-to-end automation of the entire content design process. We approach this goal by incorporating ideas from intelligent tutoring systems and proposing progression strategies that seek to achieve mastery of not only base concepts but arbitrary combinations of these concepts. The input to our system is a model of what the player needs to do to complete each level, expressed as either an imperative procedure for producing solutions or a representation of features common to all solutions. The output is a progression of levels that can be adjusted by changing high-level parameters. We apply our framework to a popular math puzzle game and present results from 2,377 players showing that our automatic level progression is comparable to expert-crafted progression after a few design iterations based on a key engagement metric.

Interactive learning environments such as intelligent tutoring systems and software tutorials often teach procedures with step-by-step demonstrations. This instructional scaffolding is typically authored by hand, and little can be reused across problem domains. In this work, we present a framework for generating interactive tutorials from an algorithmic representation of the problem-solving thought process. Given a set of mappings between programming language constructs and user interface elements, we step through this algorithm line-by-line to trigger visual explanations of each step. This approach allows us to automatically generate tutorials for any example problem that can be solved with this algorithm. We describe two prototype implementations in the domains of K-12 mathematics and educational games, and present results from two user studies showing that educational technologists can author thought-process procedures and that generated tutorials can effectively teach a new procedure to students.

Video games have great potential to motivate students in environments for learning at scale. However, little is known about how to design in-game incentive structures to maximize learning and engagement. In this work, we expand on our previous research that introduced a new "brain points" incentive structure designed to promote the growth mindset, or the belief that intelligence is malleable. We replicate our original findings, showing that brain points increase student persistence and use of strategy. We also explore how brain points impact students from different demographic groups. We find that brain points are less engaging for low-income students, and discuss methods of improving our design in the future.

Most of the current research on improving learning outcomes focuses on a small subset of variables of an immensely multi-dimensional space of the learning ecosystem. Most digital learning tools primarily focus on individual students, other research focuses only on teacher professional development, or only on curriculum improvement. In this talk I will describe our efforts on how to discover optimal parameters of the entire ecosystem that considers student factors (engagement and mastery), classroom factors (blended learning variations and group learning variations), curriculum factors (multidimensional variation of existing curricula), and teacher factors (in-class tools that mitigate weaknesses, and promote teacher development). I will describe our work on algorithms to discover optimal learning pathways in this high-dimensional space. I will conclude with the outcomes of deploying a portion of our platform on algebra challenges conducted on two US states and the country of Norway.

We present a method for training recurrent neural networks to act as near-optimal feedback controllers. It is able to generate stable and realistic behaviors for a range of dynamical systems and tasks -- swimming, flying, biped and quadruped walking with different body morphologies. It does not require motion capture or task-specific features or state machines. The controller is a neural network, having a large number of feed-forward units that learn elaborate state-action mappings, and a small number of recurrent units that implement memory states beyond the physical system state. The action generated by the network is defined as velocity. Thus the network is not learning a control policy, but rather the dynamics under an implicit policy. Essential features of the method include interleaving supervised learning with trajectory optimization, injecting noise during training, training for unexpected changes in the task specification, and using the trajectory optimizer to obtain optimal feedback gains in addition to optimal actions.

Educational technology requires a delivery mechanism to scale. One method that has not yet seen widespread use is the educational campaign: large-scale, short-term events focused on a specific educational topic, such as the Hour of Code campaign. These are designed to generate media coverage and lend themselves nicely to collaborative or competitive goals, thus potentially leveraging social effects and community excitement to increase engagement and reach students who otherwise would not participate. In this article, we present a case study of three such campaigns that we ran to encourage students to play an algebra game—DragonBox Adaptive: the Washington, Norway, and Minnesota Algebra Challenges. We provide several design recommendations for future campaigns based on our experience, including the effects of different incentive schemes, the insertion of “tests” to fast-forward students to levels of appropriate difficulty, and the strengths and weaknesses of campaigns as a method of collecting experimental data.

We present a general automatic experimentation and hypothesis generation framework that utilizes a large set of users to explore the effects of different parts of an intervention parameter space on any objective function. We also incorporate importance sampling, allowing us to run these automatic experiments even if we cannot give out the exact intervention distributions that we want. To show the utility of this framework, we present an implementation in the domain of fractions and numberlines, using an online educational game as the source of players. Our system is able to automatically explore the parameter space and generate hypotheses about what types of numberlines lead to maximal short-term transfer; testing on a separate dataset shows the most promising hypotheses are valid. We briefly discuss our results in the context of the wider educational literature, showing that one of our results is not explained by current research on multiple fraction representations, thus proving our ability to generate potentially interesting hypotheses to test.

There is great interest in leveraging video games to improve student engagement and motivation. However, educational games are not uniformly effective, and little is known about how in-game rewards affect children's learning-related behavior. In this work, we argue that educational games can be improved by fundamentally changing their incentive structures to promote the growth mindset, or the belief that intelligence is malleable. We present "brain points," a system that encourages the development of growth mindset behaviors by directly incentivizing effort, use of strategy, and incremental progress. Through a study of 15,000 children, we show that the "brain points" system encourages more low-performing students to persist in the educational game Refraction when compared to a control, and increases overall time played, strategy use, and perseverance after challenge. We believe that this growth mindset incentive structure has great potential in many educational environments.

Video games are increasingly recognized as a compelling platform for instruction that could be leveraged to teach students at scale. Hint systems that provide personalized feedback to students in real time are a central component of many effective interactive learning environments, however little is known about how hints impact player behavior and motivation in educational games. In this work, we study the effectiveness of hints by comparing four designs based on successful hint systems in intelligent tutoring systems and commercial games. We present results from a study of 50,000 students showing that all four hint systems negatively impacted performance compared to a baseline condition with no hints. These results suggest that traditional hint systems may not translate well into the educational game environment, highlighting the importance of studying student behavior to understand the impact of new interactive learning technologies.

We present a technique for analyzing a set of animal gaits to predict the gait of a new animal from its shape alone. This method works on a wide range of bipeds and quadrupeds, and adapts the motion style to the size and shape of the animal. We achieve this by combining inverse optimization with sparse data interpolation. Starting with a set of reference walking gaits extracted from sagittal plane video footage, we first use inverse optimization to learn physically motivated parameters describing the style of each of these gaits. Given a new animal, we estimate the parameters describing its gait with sparse data interpolation, then solve a forward optimization problem to synthesize the final gait. To improve the realism of the results, we introduce a novel algorithm called joint inverse optimization which learns coherent patterns in motion style from a database of example animal-gait pairs. We quantify the predictive performance of our model by comparing its synthesized gaits to ground truth walking motions for a range of different animals. We also apply our method to the prediction of gaits for dinosaurs and other extinct creatures.

A key challenge in teaching a procedural skill is finding an effective progression of example problems that the learner can solve in order to internalize the procedure. In many learning domains, generation of such problems is typically done by hand and there are few tools to help automate this process. We reduce this effort by borrowing ideas from test input generation in software engineering. We show how we can use execution traces as a framework for abstracting the characteristics of a given procedure and defining a partial ordering that reflects the relative difficulty of two traces. We also show how we can use this framework to analyze the completeness of expert-designed progressions and fill in holes. Furthermore, we demonstrate how our framework can automatically synthesize new problems by generating large sets of problems for elementary and middle school mathematics and synthesizing hundreds of levels for a popular algebra-learning game. We present the results of a user study with this game confirming that our partial ordering can predict user evaluation of procedural difficulty better than baseline methods.

Creating game content requires balancing design considerations at multiple scales: each level requires effort and iteration to produce, and broad-scale constraints such as the order in which game concepts are introduced must be respected. Game designers currently create informal plans for how the game's levels will fit together, but they rarely keep these plans up-to-date when levels change during iteration and testing. This leads to violations of constraints and makes changing the high-level plans expensive. To address these problems, we explore the creation of mixed-initiative game progression authoring tools which explicitly model broad-scale design considerations. These tools let the designer specify constraints on progressions, and keep the plan synchronized when levels are edited. This enables the designer to move between broad and narrow-scale editing and allows for automatic detection of problems caused by edits to levels. We further leverage advances in procedural content generation to help the designer rapidly explore and test game progressions. We present a prototype implementation of such a tool for our actively-developed educational game, Refraction. We also describe how this system could be extended for use in other games and domains, specifically for the domains of math problem sets and interactive programming tutorials.

Abstract There exists a large body of research devoted to creating real time interactive locomotion controllers which are targeted at some specific class of character, most often humanoid bipeds. Relatively little work, however, has been done on approaches which are applicable to creatures with a wide range of different forms – partially due to the lack of easily obtainable motion‐capture data for animals and fictional creatures. We show how a locomotion controller can be created despite this dearth of data by synthesizing it from scratch. Our method only requires as input a description of the shape of the animal, the gaits which it can perform, and a model of the task or tasks for which the controller will be used. From this a sequence of motion clips are automatically synthesized and assembled into a motion graph which defines a physically realistic controller capable of performing the specified tasks. The method attempts to minimize the computational time required to generate this controller and we show its effectiveness at creating interactive controllers for a range of tasks for bipeds, tripeds, and quadrupeds.

One of the key challenges of video game design is teaching new players how to play. Although game developers frequently use tutorials to teach game mechanics, little is known about how tutorials affect game learnability and player engagement. Seeking to estimate this value, we implemented eight tutorial designs in three video games of varying complexity and evaluated their effects on player engagement and retention. The results of our multivariate study of over 45,000 players show that the usefulness of tutorials depends greatly on game complexity. Although tutorials increased play time by as much as 29% in the most complex game, they did not significantly improve player engagement in the two simpler games. Our results suggest that investment in tutorials may not be justified for games with mechanics that can be discovered through experimentation.

Program verification is the only way to be certain that a given piece of software is free of (certain types of) errors --- errors that could otherwise disrupt operations in the field. To date, formal verification has been done by specially-trained engineers. Labor costs have heretofore made formal verification too costly to apply beyond small, critical software components.

Some problems in procedural content generation for games involve hard constraints (e.g. that a generated puzzle is necessarily solvable). Common techniques for generator design lack a way to specify crisp (yes/no) constraints on what counts as a valid content artifact and guarantee these constraints are satisfied in the generator's output. In this paper we present two independent implementations of three diverse level design automation tools for the popular online educational game Refraction. All of the systems guarantee key properties of their output. Applying a constraint-focused generator design perspective in depth, we found that even emergent aesthetic style properties were straightforward to directly control. Our results with Refraction provide further concrete evidence for the claim that the expressive power of constraints and the ease with which they can be incorporated into suitably designed generative processes makes them a powerful tool for producing reliably-controllable generators for game content.

Interactive, task-guided character controllers must be agile and responsive to user input, while retaining the flexibility to be readily authored and modified by the designer. Central to a method's ease of use is its capacity to synthesize character motion for novel situations without requiring excessive data or programming effort. In this work, we present a technique that animates characters performing user-specified tasks by using a probabilistic motion model, which is trained on a small number of artist-provided animation clips. The method uses a low-dimensional space learned from the example motions to continuously control the character's pose to accomplish the desired task. By controlling the character through a reduced space, our method can discover new transitions, tractably precompute a control policy, and avoid low quality poses.

We present a motion synthesis framework capable of producing a wide variety of important human behaviors that have rarely been studied, including getting up from the ground, crawling, climbing, moving heavy objects, acrobatics (hand-stands in particular), and various cooperative actions involving two characters and their manipulation of the environment. Our framework is not specific to humans, but applies to characters of arbitrary morphology and limb configuration. The approach is fully automatic and does not require domain knowledge specific to each behavior. It also does not require pre-existing examples or motion capture data. At the core of our framework is the contact-invariant optimization (CIO) method we introduce here. It enables simultaneous optimization of contact and behavior. This is done by augmenting the search space with scalar variables that indicate whether a potential contact should be active in a given phase of the movement. These auxiliary variables affect not only the cost function but also the dynamics (by enabling and disabling contact forces), and are optimized together with the movement trajectory. Additional innovations include a continuation scheme allowing helper forces at the potential contacts rather than the torso, as well as a feature-based model of physics which is particularly well-suited to the CIO framework. We expect that CIO can also be used with a full physics model, but leave that extension for future work.

Game designers frequently invest in aesthetic improvements such as music, sound effects, and animations. However, their exact value for attracting and retaining players remains unclear. Seeking to estimate this value in two popular Flash games, we conducted a series of large-scale A/B tests in which we selectively removed aesthetic improvements and examined the effect of each component on play time, progress, and return rate. We found that music and sound effects had little or no effect on player retention in either game, while animations caused users to play more. We also found, counterintuitively, that optional rewards caused players to play less in both games. In one game, this gameplay modification affected play time three times as much as the largest aesthetic variation. Our methodology provides a way to determine where resources may be best spent during the game design and development process.

Large-scale, ground-level urban imagery has recently developed as an important element of online mapping tools such as Google's Street View. Such imagery is extremely valuable in a number of potential applications, ranging from augmented reality to 3D modeling, and from urban planning to monitoring city infrastructure. While such imagery is already available from many sources, including Street View and tourist photos on photo-sharing sites, these collections have drawbacks related to high cost, incompleteness, and accuracy. A potential solution is to leverage the community of photographers around the world to collaboratively acquire large-scale image collections. This work explores this approach through PhotoCity, an online game that trains its players to become "experts" at taking photos at targeted locations and in great density, for the purposes of creating 3D building models. To evaluate our approach, we ran a competition between two universities that resulted in the submission of over 100,000 photos, many of which were highly relevant for the 3D modeling task at hand. Although the number of players was small, we found that this was compensated for by incentives that drove players to become experts at photo collection, often capturing thousands of useful photos each.

Secondary game objectives, optional challenges that players can choose to pursue or ignore, are a fundamental element of game design. Still, little is known about how secondary objectives affect player behavior. It is commonly believed that secondary objectives such as coins or collectible items can increase a game's flexibility, replayability, and depth. In contrast, we present results from analysis of two popular online Flash games showing that secondary objectives can easily harm the retention of many players. We support our findings with data collected from over 27,000 players through large-scale A/B tests in which we measured play time, progress, and return rate. We show that while secondary objectives can encourage long-term players to extend their playtime, they can also cause many players to play for less time. By modifying secondary objectives so that they reinforce the primary goal of the game instead of distracting from it, we are able to avoid negative consequences and still maintain the retention of long-term players. Our results suggest that secondary objectives that support the primary goal of the game are consistently useful, while secondary objectives that do not support the main goal require extensive testing to avoid negative consequences.

As games grow in complexity, gameplay needs to provide players with powerful means of managing this complexity. One approach is to give automation tools to players. In this paper, we analyze an in-game automation tool, the Foldit cookbook, for the scientific discovery game Foldit. The cookbook allows players to write recipes that can automate their strategies. Through analysis of cookbook usage, we observe that players take advantage of social mechanisms in the game to share, run, and modify recipes. Further, players take advantage of both a simplified visual programming interface and a text-based scripting interface for creating recipes. This indicates that there is potential for using automation tools to disseminate expert knowledge, and that it is useful to provide support for multiple authoring styles, especially for games where the final game goal is unbounded or hard to attain.

Visual data mining is a powerful technique allowing game designers to analyze player behavior. Playtracer, a new method for visually analyzing play traces, is a generalized heatmap that applies to any game with discrete state spaces. Unfortunately, due to its low discriminative power, Playtracer's usefulness is significantly decreased for games of even medium complexity, and is unusable on games with continuous state spaces. Here we show how the use of state features can remove both of these weaknesses. These state features collapse larger state spaces without losing salient information, resulting in visualizations that are significantly easier to interpret. We evaluate our work by analyzing player data gathered from three complex games in order to understand player behavior in the presence of optional rewards, identify key moments when players figure out the solution to the puzzle, and analyze why players give up and quit. Based on our experiences with these games, we suggest general principles for designers to identify useful features of game states that lead to effective play analyses.

We present a probabilistic algorithm for nonlinear inverse reinforcement learning. The goal of inverse reinforcement learning is to learn the reward function in a Markov decision process from expert demonstrations. While most prior inverse reinforcement learning algorithms represent the reward as a linear combination of a set of features, we use Gaussian processes to learn the reward as a nonlinear function, while also determining the relevance of each feature to the expert's policy. Our probabilistic algorithm allows complex behaviors to be captured from suboptimal stochastic demonstrations, while automatically balancing the simplicity of the learned reward structure against its consistency with the observed actions.

We present a technique for efficiently synthesizing animations for characters traversing complex dynamic environments. Our method uses parameterized locomotion controllers that correspond to specific motion skills, such as jumping or obstacle avoidance. The controllers are created from motion capture data with reinforcement learning. A space-time planner determines the sequence in which controllers must be executed to reach a goal location, and admits a variety of cost functions to produce paths that exhibit different behaviors. By planning in space and time, the planner can discover paths through dynamically changing environments, even if no path exists in any static snapshot. By using parameterized controllers able to handle navigational tasks, the planner can operate efficiently at a high level, leading to interactive replanning rates.

A physics-based control system that tracks a single motion trajectory produces high-quality animations, but does not recover from large disturbances that require deviating from this tracked trajectory. In order to enhance the responsiveness of physically simulated characters, we introduce algorithms that construct composite controllers that track multiple trajectories in parallel instead of sequentially switching from one control to the other. The composite controllers can blend or transition between different path controllers at arbitrary times according to the current system state. As a result, a composite control system generates both high-quality animations and natural responses to certain disturbances. We demonstrate its potential for improving robustness in performing several locomotion tasks. Then we consolidate these controllers into graphs that allow us to direct the character in real time.

Analysis of gameplay data is crucial for evaluating design decisions and refining a game experience. However, identifying player strategies and finding areas of confusion is difficult because a designer may not know what queries to ask or what patterns to look for in the data. To make this task easier, we present Playtracer, a method for visually analyzing play traces that is independent of a specific game's structure. Playtracer applies multidimensional scaling to cluster players and game states, providing a detailed visual representation of the paths the players take through a game. We evaluate our method by analyzing an educational puzzle game and highlighting common hypotheses, pitfalls, confusing elements, and anomalies. Our results suggest that Playtracer can be an effective tool for game analysis and improvement.

Incorporating the individual and collective problem solving skills of non-experts into the scientific discovery process could potentially accelerate the advancement of science. This paper discusses the design process used for Foldit, a multiplayer online biochemistry game that presents players with computationally difficult protein folding problems in the form of puzzles, allowing ordinary players to gain expertise and help solve these problems. The principle challenge of designing such scientific discovery games is harnessing the enormous collective problem-solving potential of the game playing population, who have not been previously introduced to the specific problem, or, often, the entire scientific discipline. To address this challenge, we took an iterative approach to designing the game, incorporating feedback from players and biochemical experts alike. Feedback was gathered both before and after releasing the game, to create the rules, interactions, and visualizations in Foldit that maximize contributions from game players. We present several examples of how this approach guided the game's design, and allowed us to improve both the quality of the gameplay and the application of player problem-solving.

We are interested in reconstructing real world locations as detailed 3D models, but to achieve this goal, we require a large quantity of photographic data. We designed a game to employ the efforts and digital cameras of everyday people to not only collect this data, but to do so in a fun and effective way. The result is PhotoCity, a game played outdoors with a camera, in which players take photos to capture flags and take over virtual models of real buildings. The game falls into the genres of both games with a purpose (GWAPs) and alternate reality games (ARGs). Each type of game comes with its own inherent challenges, but as a hybrid of both, PhotoCity presented us with a unique combination of obstacles. This paper describes the design decisions made to address these obstacles, and seeks to answer the question: Can games be used to achieve massive data-acquisition tasks when played in the real world, away from standard game consoles? We conclude with a report on player experiences and showcase some 3D reconstructions built by players during gameplay.

The goal of inverse reinforcement learning is to find a reward function for a Markov decision process, given example traces from its optimal policy. Current IRL techniques generally rely on user-supplied features that form a concise basis for the reward. We present an algorithm that instead constructs reward features from a large collection of component features, by building logical conjunctions of those component features that are relevant to the example policy. Given example traces, the algorithm returns a reward function as well as the constructed features. The reward function can be used to recover a full, deterministic, stationary policy, and the features can be used to transplant the reward function into any novel environment on which the component features are well defined.

We present a method for inferring the behavior styles of character controllers from a small set of examples. We show that a rich set of behavior variations can be captured by determining the appropriate reward function in the reinforcement learning framework, and show that the discovered reward function can be applied to different environments and scenarios. We also introduce a new algorithm to recover the unknown reward function that improves over the original apprenticeship learning algorithm. We show that the reward function representing a behavior style can be applied to a variety of different tasks, while still preserving the key features of the style present in the given examples. We describe an adaptive process where an author can, with just a few additional examples, refine the behavior so that it has better generalization properties.

We propose a novel representation of motion data and control that enables characters with both highly agile responses to user input and natural handling of arbitrary external disturbances. The representation organizes motion data as samples in a high dimensional generalization of a vector field we call a 'motion field'. Our runtime motion synthesis mechanism freely 'flows' in the motion field and is capable of creating novel and natural motions that are highly-responsive to the real time user input, and generally not explicitly specified in the data.

The incorporation of randomness is critical for the believability and effectiveness of controllers for characters in competitive games. We present a fully automatic method for generating intelligent real-time controllers for characters in such a game. Our approach uses game theory to deal with the ramifications of the characters acting simultaneously, and generates controllers which employ both long-term planning and an intelligent use of randomness. Our results exhibit nuanced strategies based on unpredictability, such as feints and misdirection moves, which take into account and exploit the possible strategies of an adversary. The controllers are generated by examining the interaction between the rules of the game and the motions generated from a parametric motion graph. This involves solving a large-scale planning problem, so we also describe a new technique for scaling this process to higher dimensions.

We describe a framework for the automatic synthesis of biped locomotion controllers that adapt to uneven terrain at run-time. The framework consists of two components: a per-footstep end-effector path planner and a per-timestep generalized-force solver. At the start of each footstep, the planner performs short-term planning in the space of end-effector trajectories. These trajectories adapt to the interactive task goals and the features of the surrounding uneven terrain at run-time. We solve for the parameters of the planner for different tasks in offline optimizations. Using the per-footstep plan, the generalized-force solver takes ground contacts into consideration and solves a quadratic program at each simulation timestep to obtain joint torques that drive the biped. We demonstrate the capabilities of the controllers in complex navigation tasks where they perform gradual or sharp turns and transition between moving forwards, backwards, and sideways on uneven terrain (including hurdles and stairs) according to the interactive task goals. We also show that the resulting controllers are capable of handling morphology changes to the character.

We present methods for creating compact and efficient data-driven character controllers. Our first method identifies the essential motion data examples tailored for a given task. It enables complex yet efficient high-dimensional controllers, as well as automatically generated connecting controllers that merge a set of independent controllers into a much larger aggregate one without modifying existing ones. Our second method iteratively refines basis functions to enable highly complex value functions. We show that our methods dramatically reduce the computation and storage requirement of controllers and enable very complex behaviors.

Dynamically simulated characters are difficult to control because they are underactuated---they have no direct control over their global position and orientation. In order to succeed, control policies must look ahead to determine stabilizing actions, but such planning is complicated by frequent ground contacts that produce a discontinuous search space. This paper introduces a locomotion system that generates high-quality animation of agile movements using nonlinear controllers that plan through such contact changes. We demonstrate the general applicability of this approach by emulating walking and running motions in rigid-body simulations. Then we consolidate these controllers under a higher-level planner that interactively controls the character's direction.

We present a fully automatic method for generating gaits and morphologies for legged animal locomotion. Given a specific animal's shape we can determine an efficient gait with which it can move. Similarly, we can also adapt the animal's morphology to be optimal for a specific locomotion task. We show that determining such gaits is possible without the need to specify a good initial motion, and without manually restricting the allowed gaits of each animal. Our approach is based on a hybrid optimization method which combines an efficient derivative-aware spacetime constraints optimization with a derivative-free approach able to find non-local solutions in high-dimensional discontinuous spaces. We demonstrate the effectiveness of this approach by synthesizing dynamic locomotions of bipeds, a quadruped, and an imaginary five-legged creature.

Summary form only given. We argue that real-time domain of interactive games requires completely new approach to algorithms for most problems in computer graphics. To illustrate this point, we describe our recent work on two very different phenomena, human locomotion and fluid simulations, and show how the requirements of high-fidelity, realtime performance and unconditional stability resulted in some very unusual algorithms to these well studied problems.

This paper describes an approach to building real-time highly-controllable characters. A kinematic character controller is built on-the-fly during a capture session, and updated after each new motion clip is acquired. Active learning is used to identify which motion sequence the user should perform next, in order to improve the quality and responsiveness of the controller. Because motion clips are selected adaptively, we avoid the difficulty of manually determining which ones to capture, and can build complex controllers from scratch while significantly reducing the number of necessary motion samples.

We present a new approach to realtime character animation with interactive control. Given a corpus of motion capture data and a desired task, we automatically compute near-optimal controllers using a low-dimensional basis representation. We show that these controllers produce motion that fluidly responds to several dimensions of user control and environmental constraints in realtime. Our results indicate that very few basis functions are required to create high-fidelity character controllers which permit complex user navigation and obstacle-avoidance tasks.

We present a real-time crowd model based on continuum dynamics. In our model, a dynamic potential field simultaneously integrates global navigation with moving obstacles such as other people, efficiently solving for the motion of large crowds without the need for explicit collision avoidance. Simulations created with our system run at interactive rates, demonstrate smooth flow under a variety of conditions, and naturally exhibit emergent phenomena that have been observed in real crowds.

We present a new model reduction approach to fluid simulation, enabling large, real-time, detailed flows with continuous user interaction. Our reduced model can also handle moving obstacles immersed in the flow. We create separate models for the velocity field and for each moving boundary, and show that the coupling forces may be reduced as well. Our results indicate that surprisingly few basis functions are needed to resolve small but visually important features such as spinning vortices.

This paper presents a novel physics-based representation of realistic character motion. The dynamical model incorporates several factors of locomotion derived from the biomechanical literature, including relative preferences for using some muscles more than others. elastic mechanisms at joints due to the mechanical properties of tendons, ligaments, and muscles, and variable stiffness at joints depending on the task. When used in a spacetime optimization framework, the parameters of this model define a wide range of styles of natural human movement.Due to the complexity of biological motion, these style parameters are too difficult to design by hand. To address this, we introduce Nonlinear Inverse Optimization, a novel algorithm for estimating optimization parameters from motion capture data. Our method can extract the physical parameters from a single short motion sequence. Once captured, this representation of style is extremely flexible: motions can be generated in the same style but performing different tasks, and styles may be edited to change the physical properties of the body.

This paper presents an inverse kinematics system based on a learned model of human poses. Given a set of constraints, our system can produce the most likely pose satisfying those constraints, in real-time. Training the model on different input data leads to different styles of IK. The model is represented as a probability distribution over the space of all possible poses. This means that our IK system can generate any pose, but prefers poses that are most similar to the space of poses in the training data. We represent the probability with a novel model called a Scaled Gaussian Process Latent Variable Model. The parameters of the model are all learned automatically; no manual tuning is required for the learning component of the system. We additionally describe a novel procedure for interpolating between styles.Our style-based IK can replace conventional IK, wherever it is used in computer animation and computer vision. We demonstrate our system in the context of a number of applications: interactive character posing, trajectory keyframing, real-time motion capture with missing markers, and posing from a 2D image.

We describe a novel method for controlling physics-based fluid simulations through gradient-based nonlinear optimization. Using a technique known as the adjoint method , derivatives can be computed efficiently, even for large 3D simulations with millions of control parameters. In addition, we introduce the first method for the full control of free-surface liquids. We show how to compute adjoint derivatives through each step of the simulation, including the fast marching algorithm, and describe a new set of control parameters specifically designed for liquids.

We develop a novel method for fitting high-resolution template meshes to detailed human body range scans with sparse 3D markers. We formulate an optimization problem in which the degrees of freedom are an affine transformation at each template vertex. The objective function is a weighted combination of three measures: proximity of transformed vertices to the range data, similarity between neighboring transformations, and proximity of sparse markers at corresponding locations on the template and target surface. We solve for the transformations with a non-linear optimizer, run at two resolutions to speed convergence. We demonstrate reconstruction and consistent parameterization of 250 human body models. With this parameterized set, we explore a variety of applications for human body modeling, including: morphing, texture transfer, statistical analysis of shape, model fitting from sparse markers, feature analysis to modify multiple correlated parameters (such as the weight and height of an individual), and transfer of surface detail and animation controls from a template to fitted models.

We introduce an acting-based animation system for creating and editing character animation at interactive speeds. Our system requires minimal training, typically under an hour, and is well suited for rapidly prototyping and creating expressive motion. A real-time motion-capture framework records the user's motions for simultaneous analysis and playback on a large screen. The animator's real-world, expressive motions are mapped into the character's virtual world. Visual feedback maintains a tight coupling between the animator and character. Complex motion is created by layering multiple passes of acting. We also introduce a novel motion-editing technique, which derives implicit relationships between the animator and character. The animator mimics some aspect of the character motion, and the system infers the association between features of the animator's motion and those of the character. The animator modifies the mimic by acting again, and the system maps the changes onto the character. We demonstrate our system with several examples and present the results from informal user studies with expert and novice animators.

We describe a method for controlling smoke simulations through user-specified keyframes. To achieve the desired behavior, a continuous quasi-Newton optimization solves for appropriate "wind" forces to be applied to the underlying velocity field throughout the simulation. The cornerstone of our approach is a method to efficiently compute exact derivatives through the steps of a fluid simulation. We formulate an objective function corresponding to how well a simulation matches the user's keyframes, and use the derivatives to solve for force parameters that minimize this function. For animations with several keyframes, we present a novel multiple-shooting approach. By splitting large problems into smaller overlapping subproblems, we greatly speed up the optimization process while avoiding certain local minima.

In this paper we describe a physics-based method for synthesis of bird flight animations. Our method computes a realistic set of wingbeats that enables a bird to follow the specified trajectory. We model the bird as an articulated skeleton with elastically deformable feathers. The bird motion is created by applying joint torques and aerodynamic forces over time in a forward dynamics simulation. We solve for each wingbeat motion separately by optimizing for wingbeat parameters that create the most natural motion. The final animation is constructed by concatenating a series of optimal wingbeats. This detailed bird flight model enables us to produce flight motions of different birds performing a variety of maneuvers including taking off, cruising, rapidly descending, turning, and landing.

This paper presents an example-based method for calculating skeleton-driven body deformations. Our example data consists of range scans of a human body in a variety of poses. Using markers captured during range scanning, we construct a kinematic skeleton and identify the pose of each scan. We then construct a mutually consistent parameterization of all the scans using a posable subdivision surface template. The detail deformations are represented as displacements from this surface, and holes are filled smoothly within the displacement maps. Finally, we combine the range scans using k -nearest neighbor interpolation in pose space. We demonstrate results for a human upper body with controllable pose, kinematics, and underlying surface shape.

This paper presents a framework for the skeleton-driven animation of elastically deformable characters. A character is embedded in a coarse volumetric control lattice, which provides the structure needed to apply the finite element method. To incorporate skeletal controls, we introduce line constraints along the bones of simple skeletons. The bones are made to coincide with edges of the control lattice, which enables us to apply the constraints efficiently using algebraic methods. To accelerate computation, we associate regions of the volumetric mesh with particular bones and perform locally linearized simulations, which are blended at each time step. We define a hierarchical basis on the control lattice, so for detailed interactions the simulation can adapt the level of detail. We demonstrate the ability to animate complex models using simple skeletons and coarse volumetric meshes in a manner that simulates secondary motions at interactive rates.

In this paper we present a general method for rapid prototyping of realistic character motion. We solve for the natural motion from a simple animation provided by the animator. Our framework can be used to produce relatively complex realistic motion with little user effort.We describe a novel constraint detection method that automatically determines different constraints on the character by analyzing the input motion. We show that realistic motion can be achieved by enforcing a small set of linear and angular momentum constraints. This simplified approach helps us avoid the complexities of computing muscle forces. Simpler dynamic constraints also allow us to generate animations of models with greater complexity, performing more intricate motions. Finally, we show that by learning a small set of key parameters that describe a character pose we can help a non-skilled animator rapidly create realistic character motion.

In contrast to most physically based animation techniques that synthesize human motion from scratch, we take the approach of motion transformation as the underlying paradigm for generating computer animation. In doing so we combine the expressive richness of an input animation sequence with the controllability of space-time optimization to create a wide range of realistic character animation. The space-time dynamics formulation also allows editing of intuitive, high-level motion concepts such as the time and placement of footprints, length and mass of various extremities number of body joints and gravity. Our algorithm is well suited for the reuse of highly-detailed captured motion animation. We report application of our algorithm on two such sequences: human run and human jump. As a result, both of these sequences produced a wide range of realistic motions. We show by DOF comparison how closely the resulting motion matches the reality.

Physical simulation of dynamic objects has become commonplace in computer graphics because it produces highly realistic animations. In this paradigm the animator provides few physical parameters such as the objects' initial positions and velocities, and the simulator automatically generates realistic motions. The resulting motion, however, is difficult to control because even a small adjustment of the input parameters can drastically affect the subsequent motion. Furthermore, the animator often wishes to change the end-result of the motion instead of the initial physical parameters.

We introduce a novel algorithm for transforming character anima-tion sequences that preserves essential physical properties of the motion. By using the spacetime constraints dynamics formulation our algorithm maintains realism of the original motion sequence without sacrificing full user control of the editing process. In contrast to most physically based animation techniques that synthesize motion from scratch, we take the approach of motion transformation as the underlying paradigm for generating computer animations. In doing so, we combine the expressive richness of an input animation sequence with the controllability of spacetime op-timization to create a wide range of realistic character animations. The spacetime dynamics formulation also allows editing of intu-itive, high-level motion concepts such as the time and placement of footprints, length and mass of various extremities, number of body joints and gravity. Our algorithm is well suited for the reuse of highly-detailed cap-tured motion animations. In addition, we describe a new methodol-ogy for mapping a motion between characters with drastically dif-ferent numbers of degrees of freedom. We use this method to re-duce the complexity of the spacetime optimization problems. Fur-thermore, our approach provides a paradigm for controlling com-plex dynamic and kinematic systems with simpler ones.

We describe a simple technique for editing captured or keyframed animation based on warping of the motion parameter curves.The animator interactively defines a set of keyframe-like constraints which are used to derive a smooth deformation that preserves the fine structure of the original motion.Motion clips are combined by overlapping and blending of the parameter curves.We show that whole families of realistic motions can be derived from a single captured motion sequence using only a few keyframes to specify the motion warp.Our technique makes it feasible to create libraries of reusable "clip motion."