Best Paper Nominations

The PC Chairs have chosen the following 6 papers as best paper nominees. The award will go to the paper that obtains the most votes from the conference attendees (details to follow):


Knowledge-based Fast Evolutionary MCTS for General Video Game Playing

Diego Perez, Spyridon Samothrakis, Simon Lucas

General Video Game Playing is a game AI domain in which the usage of game-dependent domain knowledge is very limited or even non existent. This imposes obvious difficulties when seeking to create agents able to play sets of different games. Taken more broadly, this issue can be used as an introduction to the field of General Artificial Intelligence. This paper explores the performance of a vanilla Monte Carlo Tree Search algorithm, and analyzes the main difficulties encountered when tackling this kind of scenarios. Modifications are proposed to overcome these issues, strengthening the algorithm’s ability to gather and discover knowledge, and taking advantage of past experiences. Results show that the performance of the algorithm is significantly improved, although there remain unresolved problems that require further research. The framework employed in this research is publicly available and will be used in the General Video Game Playing competition at the IEEE Conference on Computational Intelligence and Games in 2014.


Churn Prediction for High-value Players in Casual Social Games

Julian Runge, Peng Gao, Florent Garcin, Boi Faltings

Predicting when a player will leave a game creates a unique opportunity to increase a player’s lifetime and revenue contribution. The player can be incentivized to stay, strategically cross-linked to other games in the company’s portfolio or in a last step be passed on to competing companies. This paper focuses on predicting churn for high-value players of casual social games and attempts to assess the business impact that can be derived from a predictive churn model. We compare the prediction performance of four common classification algorithms over two casual social games with millions of players each. Further, we implement a hidden Markov model to explicitly address temporal dynamics. We find that a neural network achieves the best prediction performance in terms of area under curve (AUC). To assess the business value of churn prediction, we design and implement an AB test over one of the games. We use free in-game currency as an incentive to retain players. Test results indicate that contacting players short before the churn event based on the model’s predictions improves the effectiveness of communication efforts with players by factor three to four. They further show that giving out free in-game currency is not able to significantly impact churn rate of players. This suggests that players can only be retained by remarkably changing their gameplay experience ahead of the churn event and that cross-linking may be the more effective measure to deal with churning players.


Monte Carlo Tree Search with Heuristic Evaluations using Implicit Minimax Backups

Marc Lanctot, Mark H. M. Winands, Tom Pepels, Nathan R. Sturtevant

Monte Carlo Tree Search (MCTS) has improved the performance of game-playing engines in domains such as Go, Hex, and general-game playing. MCTS has been shown to outperform outperform classic alpha-beta search in games where good heuristic evaluations are difficult to obtain. In recent years, combining ideas from traditional minimax search in MCTS has been shown to be advantageous in some domains, such as Lines of Action, Amazons, and Breakthrough. In this paper, we propose a new way to use heuristic evaluations to guide the MCTS search by storing the two sources of information, estimated win rates and heuristic evaluations, separately. Rather than using the heuristic evaluations to replace the playouts, our technique backs them up implicitly during its MCTS simulations. These learned evaluation values are then used to guide future simulations. Compared to current techniques, we show that using implicit minimax backups leads to stronger play performance in Breakthrough, Lines of Action, and Kalah.


Designer Modeling for Sentient Sketchbook

Antonios Liapis, Georgios Yannakakis, Julian Togelius

This paper documents the challenges in creating a computer-aided level design tool which incorporates computer-generated suggestions which appeal to the human user. Several steps are suggested in order to make the suggestions more appropriate to a specific user's overall style, current focus, and end-goals. Designer style is modeled via choice-based interactive evolution which adapts the impact of different dimensions of quality based on the designer's choice of certain suggestions over others. Modeling process is carried out similarly to style, but adapting to the current focus of the designer's actions. Goals are modeled by estimating the visual patterns of the designer's final artifact and changing the parameters of the algorithm to enforce such patterns on generated suggestions.


Parallel UCT Search on GPUs

Nicolas A. Barriga, Marius Stanescu, Michael Buro

We propose two parallel UCT search (Upper Confidence bounds applied to Trees) algorithms that take advantage of modern GPU hardware. Experiments using the game of Ataxx are conducted, and the algorithm's speed and playing strength is compared to sequential UCT running on the CPU and Block Parallel UCT that runs its simulations on a GPU. Empirical results show that our proposed Multiblock Parallel algorithm outperforms other approaches and can take advantage of the GPU hardware without the added complexity of searching multiple trees.


Searching for Good and Diverse Game Levels

Mike Preuss, Antonios Liapis, Julian Togelius

In procedural content generation, one is often interested in generating a large number of game content artefacts that are not only good but also diverse, in terms of gameplay, visual impression or some other criterion. We investigate several search-based approaches to creating good and diverse game content, in particular approaches based on evolution strategies with or without diversity preservation mechanisms, novelty search and random search. The content domain is game levels, in particular map sketches for strategy games, which are meant to be used as suggestions in the Sentient Sketchbook design tool. Several diversity metrics are possible for this type of content: we investigate tile-based, objective-based and visual impression distance. We find that evolution with diversity preservation mechanisms can produce both good and diverse content, but only when using appropriate distance measures.


[Print Version]