Guiding Monte Carlo tree searches with neural networks in the game of go

A dissertation submitted in fulfillment of the requirements to the degree of Master in Computer Science and Computer Engineering

Monte Carlo analysis of a puzzle game

When a puzzle game is created, its design parameters must be chosen to allow solvable and interesting challenges to be created for the player. We investigate the use of random sampling as a computationally inexpensive means of automated game analysis, to evaluate the BoxOff family of puzzle games. This analysis reveals useful insights into the game, such as the surprising fact that almost 100% of randomly generated challenges have a solution, but less than 10% will be solved using strictly random play, validating the inventor’s design choices. We show the 1D game to be trivial and the 3D game to be viable.

Generalized correlated equilibrium for two-person games in extensive form with perfect information

A correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is applied for two-person finite games in extensive form with perfect information. Randomization by an umpire takes place over the leaves of the game tree. At every decision point players have the choice either to follow the recommendation of the umpire blindly or freely choose any other action except the one suggested. This scheme can lead to Pareto-improved outcomes of other correlated equilibria. Computational issues of maximizing a linear function over the set of soft correlated equilibria are considered and a linear-time algorithm in terms of the number of edges in the game tree is given for a special procedure called “subgame perfect optimization”.

About tree-depth

In this work I present recent scientific papers related to the concept of tree-depth: different characterizations, a game theoretic approach to it and recently discovered applications. The focus in this work is presenting all the ideas in a self-contained way, such that they can be easily understood with little previous knowledge. Apart from that all the ideas are presented in a homogeneous way with clear examples and all the lemmas, some of which didn’t have proofs in the papers, are presented with rigorous proofs.

A game-theoretic network formation model

We study the dynamics of a game-theoretic network formation model that yields large-scale small-world networks. So far, mostly stochastic frameworks have been utilized to explain the emergence of these networks. On the other hand, it is natural to seek for game-theoretic network formation models in which links are formed due to strategic behaviors of individuals, rather than based on probabilities. Inspired by Even-Dar and Kearns (2007), we consider a more realistic model in which the cost of establishing each link is dynamically determined during the course of the game. Moreover, players are allowed to put transfer payments on the formation of links. Also, they must pay a maintenance cost to sustain their direct links during the game. We show that there is a small diameter of at most 4 in the general set of equilibrium networks in our model. Unlike earlier model, not only the existence of equilibrium networks is guaranteed in our model, but also these networks coincide with the outcomes of pairwise Nash equilibrium in network formation. Furthermore, we provide a network formation simulation that generates small-world networks. We also analyze the impact of locating players in a hierarchical structure by constructing a strategic model, where a complete b-ary tree is the seed network.

General Game Playing: Análisis del problema. Solución basada en un algoritmo hibrido de inteligencia computacional

El objetivo de este trabajo es presentar unas bases de conocimiento sobre el denominado General Game Playing (GGP) analizando los conceptos relacionados con esta área que ha surgido recientemente, de forma que nuestro trabajo pueda ser usado como base en futuras investigaciones y tesis relacionadas con la materia. Para ello, se hará un estudio de los enfoques que se han empleado para abordar el problema y se profundizará en otras técnicas algorítmicas, tales como por ejemplo la de Montecarlo Tree Search y los algoritmos bio-inspirados que no se han empleado (o se han empleado poco) en este contexto. Adicionalmente, se realiza una propuesta de un agente autónomo (es decir, un resolutor del problema), implementando un algoritmo bio-inspirado mixto, dentro de la plataforma para la General Video Game Artificial Intelligence Competition (GVGAI), analizando sus resultados y extrayendo conclusiones.

Meaning in movement : a gestural design game

This paper describes a design game that we called 'Meaning in Movement'. The purpose was to explore notions of professional dental practice with dental practioners in terms of gestures, actions and movements. The game represents a first step towards involving gestures, actions and movements in a design dialog with practioners for the purpose of designing future interactive systems which are more appropriate to the type of skilful actions and richly structured environments of dentists and dental assistants.

Talking about watching : using the video card game and wiki-web technology to engage IT students in developing observational skills.

Designers need to develop good observational skills in order to conduct user studies that reveal the subtleties of human interactions and adequately inform design activity. In this paper we describe a game format that we have used in concert with wiki-web technology, to engage our IT and Information Environments students in developing much sharper observational skills. The Video Card Game is a method of video analysis that is suited to design practitioners as well as to researchers. It uses the familiar format of a card game similar to "Happy Families,, to help students develop themes of interactions from watching video clips. Students then post their interaction themes on wiki-web pages, which allows the teaching team and other students to edit and comment on them. We found that the tangible (cards), game, role playing and sharing aspects of this method led to a much larger amount of interaction and discussion between student groups and between students and the teaching team, than we have achieved using our traditional teaching methods, while taking no more time on the part of the teaching staff. The quality of the resulting interaction themes indicates that this method fosters development of observational skills.In the paper we describe the motivations, method and results in full. We also describe the research context in which we collected the videotape data, and how this method relates to state of the art research methods in interaction design for ubiquitous computing technology.