Dimensionality reduction methods are very common in the field of high dimensional data analysis. Typically, algorithms for dimensionality reduction are computationally expensive. Therefore, their applications for the analysis of massive amounts of data are impractical. For example, repeated computations due to accumulated data are computationally prohibitive. In this paper, an out-of-sample extension scheme, which is used as a complementary method for dimensionality reduction, is presented. We describe an algorithm which performs an out-of-sample extension to newly-arrived data points. Unlike other extension algorithms such as Nystr\"om algorithm, the proposed algorithm uses the intrinsic geometry of the data and properties for dimensionality reduction map. We prove that the error of the proposed algorithm is bounded. Additionally to the out-of-sample extension, the algorithm provides a degree of the abnormality of any newly-arrived data point.

This article provides the first procedure for computing a fully data-dependent interval that traps the mixing time $t_{\text{mix}}$ of a finite reversible ergodic Markov chain at a prescribed confidence level. The interval is computed from a single finite-length sample path from the Markov chain, and does not require the knowledge of any parameters of the chain. This stands in contrast to previous approaches, which either only provide point estimates, or require a reset mechanism, or additional prior knowledge. The interval is constructed around the relaxation time $t_{\text{relax}}$, which is strongly related to the mixing time, and the width of the interval converges to zero roughly at a $\sqrt{n}$ rate, where $n$ is the length of the sample path. Upper and lower bounds are given on the number of samples required to achieve constant-factor multiplicative accuracy. The lower bounds indicate that, unless further restrictions are placed on the chain, no procedure can achieve this accuracy level before seeing each state at least $\Omega(t_{\text{relax}})$ times on the average. Finally, future directions of research are identified.

In interactive storytelling systems and other story-based computer games, a drama manager is a background agent that aims to bring about an enjoyable and coherent experience for the players. In this paper, we present a personalized drama manager that increases a player's expected enjoyment without removing player agency. Our personalized drama manager models a player's preference using data-driven techniques, predicts the probability the player transitioning to different story experiences, selects an objective experience that can maximize the player's expected enjoyment, and guides the player to the selected story experience. Human study results show that our drama manager can significantly increase players' enjoyment ratings in an interactive storytelling testbed, compared to drama managers in previous research.

We encounter the results of category formation every day, from demographic categories like race and gender, to role-playing-game classes like "fighter" or "mage". Category membership is often not simply based on the possession of discrete properties but instead constructed from and reflect the highly nuanced relationships (gradience) between members and best-example individuals called "prototypes". In this paper, we present The Marginal, an artificial intelligence (AI)-driven game that (1) computationally models the cognitive categories that players develop when customizing videogame avatars and (2) generates challenges for players to use their perception of visual, textual, and numerical data to progress in a game created using these models. We use archetypal analysis, an AI clustering approach for identifying boundary points in data, to generate tasks in The Marginal for its gameplay. It shows how AI can be combined with games to model and evaluate cognitive  categorization phenomena.

There has been much work on player modeling using game behavioral data collected. Many of the previous research projects that targeted this goal used aggregate game statistics as features to develop behavior models using both statistical and machine learning techniques. While existing methods have already led to interesting findings, we suspect that aggregated features discard valuable information such as temporal or sequential patterns, which may be important in deciphering information about decisionmaking, problem solving, or individual differences. Such sequential information is critical to analyze player behaviors especially in role-playing games (RPG) where players can face ample choices, experience different contexts, behave freely with individual propensities but possibly end up with similar aggregated statistics (e.g., levels, time spent). In this paper we intend to develop and apply a modeling technique that takes into consideration sequential patters to decipher individual differences in playing a Role Playing Game (RPG) game. Using an RPG with multiple affordances, we designed an experiment collecting granular in-game behaviors of 64 players. Using closed sequential pattern mining and logistic regression, we developed a model that uses gameplay action sequences to predict the real world characteristics, including gender, game play expertise and five personality traits (as defined by psychology). The results show that game expertise is a dominant factor that impacts in-game behaviors. The contribution of this paper is the algorithms we developed combined with a validation procedure to determine the reliability and validity of the results and the results themselves.

Game designers can use computer-aided game design methods to quantitatively compare player skill levels, different game variants, and learning rates, for the purpose of modeling how players will likely experience a game. We use Monte-Carlo simulation, hazard functions, and survival analysis to show how difficulty will quantitatively change throughout a game level as we vary skill, game parameters, and learning rates. We give a mathematical overview of survival analysis, present empirical data analyses of our player models for each game variant, and provide theoretical probability distributions for each game. This analysis shows the quantitative reasons why balancing a game for a wide range of player skill can be difficult; our player modeling provides tools for tuning this game balance. We also analyze the score distribution of over 175 million play sessions of a popular online Flappy Bird variant to demonstrate how learning effects can impact scores, implying that learning is crucial aspect of player modeling.

Avatar customization systems enable players to represent themselves virtually in many ways. Research has shown that players exhibit different preferences and motivations in how they customize their avatars. In this paper, we present a data-driven analytical approach to modeling player behavioral patterns exhibited during the avatar customization process. We used our data mining tool \textit{AIRvatar} to analyze telemetry data obtained from 190 players using an avatar creator of our own design. Using non-negative matrix factorization (NMF) and N-gram models, we demonstrate how our approach computationally models behavioral patterns exhibited by players such as "regular shopping," "engaged shopping," or "bored browsing". Our models obtained significant effect sizes (0.12 <= R^2 <= 0.54) when validated with multiple linear regressions for players' time spent engaging in activities within the avatar creator. The NMF model had comparably high performance and ease of interpretation compared to control models.

In this paper we describe a hierarchical method for procedurally generating 2D game maps using multi-dimensional Markov chains (MdMCs). Our method takes a collection of 2D game maps, breaks them into small chunks and performs clustering to find a set of chunks that correspond to high-level structures (high-level tiles) in the training maps. This set of high-level tiles is then used to re-represent the training maps, and to fit two sets of MdMC models: a high-level model captures the distribution of high-level tiles in the map, and a set of low-level models capture the internal structure of each high-level tile. These two sets of models can then be used to hierarchically generate new maps. We test our approach using two classic games, Super Mario Bros. and Loderunner, and compare the results against other existing map generators.

Videogame avatars provide an expressive avenue for players to represent themselves virtually. Research has shown that these avatars, while virtual, can reveal aspects of players' identities, along with physical, social, and cultural values of the real-world. In this paper, we present an approach for modeling player values through their avatars using artificial intelligence (AI) clustering techniques. In a study with 191 participants who created avatars using our system, we provide a thorough comparison of the techniques across numerical, textual, and visual data. Our findings showed that these data structures can effectively reveal players' values and preferences, such as conforming to stereotypes of character roles using statistical attributes, modeling nuances in text descriptions of avatars, and identifying "best-example" (prototypical) avatar appearances that players can be quantitatively shown to conform to. Our findings suggest that AI clustering approaches can be used to model players to yield insight into implicitly held values in a data-driven manner through virtual avatars.

Clustering is an essential game analysis tool for understanding There are many clustering procedures that could be used player strengths and preferences. For example, clustering to group players based upon their play styles, with k-means techniques have been used to identify player preferences clustering being the most common method. Our use of for using vehicles over direct combat (Drachen et al. 2012), a model-based semi-parametric Bayesian clustering procedure for taking time to solve puzzles over running through content has two important advantages. First, the number of (Drachen, Canossa, and Yannakakis 2009), for understanding clusters (unique player styles) does not have to be prespecified.