Computer Games Fourth Workshop on Computer Games CGW 2015 and the Fourth Workshop on General Intelligence in Game Playing Agents GIGA 2015 Held in Computer and Information Science 1st ed 2016 Edition

by 2016

Computer Games Fourth Workshop on Computer Games CGW 2015 and the Fourth Workshop on General Intelligence in Game Playing Agents GIGA 2015 Held in Computer and Information Science 1st ed 2016 Edition This book constitutes the refereed proceedings of the Fourth Computer Games Workshop CGW 2015 and the Fourth Workshop on General Intelligence in Game Playing Agents GIGA 2015 held in conjunction with the 24th International Conference on Artificial Intelligence IJCAI 2015 Buenos Aires Argentina in July 2015 The 12 revised full papers presented were carefully reviewed and selected from 27 submissions The papers address all aspects of artificial intelligence and computer game playing They

Publisher :

Author : 2016

ISBN : 9783319394015

Year : 179

Language: en

File Size : 10.87 MB

Category : Computers Technology

Tristan Cazenave · Mark H.M. Winands
Stefan Edelkamp · Stephan Schiffel
Michael Thielscher · Julian Togelius (Eds.)

Communications in Computer and Information Science

614

Computer Games
Fourth Workshop on Computer Games, CGW 2015
and the Fourth Workshop on General Intelligence
in Game-Playing Agents, GIGA 2015
Held in Conjunction with the 24th International Conference
on Artificial Intelligence, IJCAI 2015
Buenos Aires, Argentina, July 26–27, 2015, Revised Selected Papers

123

Communications
in Computer and Information Science

614

Commenced Publication in 2007
Founding and Former Series Editors:
Alfredo Cuzzocrea, Dominik Ślęzak, and Xiaokang Yang

Editorial Board
Simone Diniz Junqueira Barbosa
Pontifical Catholic University of Rio de Janeiro (PUC-Rio),
Rio de Janeiro, Brazil
Phoebe Chen
La Trobe University, Melbourne, Australia
Xiaoyong Du
Renmin University of China, Beijing, China
Joaquim Filipe
Polytechnic Institute of Setúbal, Setúbal, Portugal
Orhun Kara
TÜBİTAK BİLGEM and Middle East Technical University, Ankara, Turkey
Igor Kotenko
St. Petersburg Institute for Informatics and Automation of the Russian
Academy of Sciences, St. Petersburg, Russia
Ting Liu
Harbin Institute of Technology (HIT), Harbin, China
Krishna M. Sivalingam
Indian Institute of Technology Madras, Chennai, India
Takashi Washio
Osaka University, Osaka, Japan

More information about this series at http://www.springer.com/series/7899

Tristan Cazenave Mark H.M. Winands
Stefan Edelkamp Stephan Schiffel
Michael Thielscher Julian Togelius (Eds.)






Computer Games
Fourth Workshop on Computer Games, CGW 2015
and the Fourth Workshop on General Intelligence
in Game-Playing Agents, GIGA 2015
Held in Conjunction with the 24th International Conference
on Artificial Intelligence, IJCAI 2015
Buenos Aires, Argentina, July 26–27, 2015
Revised Selected Papers

123

Editors
Tristan Cazenave
Université Paris-Dauphine
Paris
France

Stephan Schiffel
Reykjavik University
Reykjavik
Iceland

Mark H.M. Winands
Maastricht University
Maastricht
The Netherlands

Michael Thielscher
The University of New South Wales
Sydney, NSW
Australia

Stefan Edelkamp
Universität Bremen
Bremen
Germany

Julian Togelius
New York University
Brooklyn, NY
USA

ISSN 1865-0929
ISSN 1865-0937 (electronic)
Communications in Computer and Information Science
ISBN 978-3-319-39401-5
ISBN 978-3-319-39402-2 (eBook)
DOI 10.1007/978-3-319-39402-2
Library of Congress Control Number: 2016939911
© Springer International Publishing Switzerland 2016
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the
material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,
broadcasting, reproduction on microfilms or in any other physical way, and transmission or information
storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now
known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication
does not imply, even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in this book are
believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors
give a warranty, express or implied, with respect to the material contained herein or for any errors or
omissions that may have been made.
Printed on acid-free paper
This Springer imprint is published by Springer Nature
The registered company is Springer International Publishing AG Switzerland

Preface

These joint proceedings contain the papers of the Computer Games Workshop (CGW
2015) and the General Intelligence in Game-Playing Agents (GIGA 2015) workshop,
which were both held in Buenos Aires, Argentina. These workshops took place on July
26 and 27, 2015, respectively, in conjunction with the 24th International Conference on
Artificial Intelligence (IJCAI 2015). These two workshops reflect the large interest in
AI research for games.
The Computer and Games Workshop series is an international forum for researchers
interested in all aspects of artificial intelligence (AI) and computer game playing.
Earlier workshops took place in Montpellier, France (2012), Beijing, China (2013), and
Prague, Czech Republic (2014). For the fourth edition of the Computer Games
Workshop, 16 submissions were received in 2015. Each paper was sent to two
reviewers. In the end, 10 papers were accepted for presentation at the workshop, of
which eight made it into these proceedings. The published papers cover a wide range of
topics related to computer games. They collectively discuss eight abstract games:
Chinese checkers, Go Fish, Lost Cities, Morpion Solitaire, Phantom Domineering,
Phantom Go, Settlers of Catan, and Surakarta. Additionally, one paper is on a roguelike
game and one paper is on the Pancake Problem.
The GIGA workshop series has been established to become the major forum for
discussing, presenting, and promoting research on general game playing (GGP). It aims
at building intelligent software agents that can, given the rules of any game, automatically learn a strategy for playing that game at an expert level without any human
intervention. The workshop intends to bring together researchers from subfields of AI
to discuss how best to address the challenges and further advance the state of the art of
general game-playing systems and generic artificial intelligence. Following the inaugural GIGA Workshop at IJCAI 2009 in Pasadena (USA), follow-up events took place
at IJCAI 2011 in Barcelona (Spain) and IJCAI 2013 in Beijing (China). This fourth
workshop on General Intelligence in Game-Playing Agents received 11 submissions.
Each paper was sent to two reviewers. In the end, 10 papers were accepted for presentation at the workshop, of which four made it into these proceedings. The accepted
papers cover topics such as general video game playing, advanced simulation-based
methods, heuristics, and learning.
In all, 44 % of the submitted papers for both workshops were selected for these
proceedings. Here we provide a brief outline of the 12 contributions, in the order in
which they appear in the proceedings. They are divided into two parts: the first eight
belong to the Computer Games Workshop and the last four to the GIGA Workshop.

VI

Preface

Computer Games Workshop
“Challenges and Progress on Using Large Lossy Endgame Databases in Chinese
checkers,” written by Nathan Sturtevant, discusses using large endgame databases to
improve the performance of minimax and Monte Carlo tree search (MCTS)-based
agents in Chinese checkers. Several challenges are faced in how to properly integrate
the endgame databases and how to correct errors that occur because of the compression
that is used when storing the endgame data. Experimental results suggest that minimaxbased approaches are able to do a better job of using the endgame data than MCTS
approaches.
“Sequential Halving for Partially Observable Games,” authored by Tom Pepels,
Tristan Cazenave, and Mark Winands, investigates sequential halving as a selection
policy in the following four partially observable games: Go Fish, Lost Cities, Phantom
Domineering, and Phantom Go. Additionally, H-MCTS is studied, which uses
sequential halving at the root of the search tree, and UCB elsewhere. Experimental
results reveal that H-MCTS performs the best in Go Fish, whereas its performance is on
par in Lost Cities and Phantom Domineering. Sequential halving as a flat Monte Carlo
search appears to be the stronger technique in Phantom Go.
“An Experimental Investigation on the Pancake Problem,” by Bruno Bouzy, discusses the pancake problem. It is an NP-hard problem and linked to the genome
rearrangement problem also called sorting by reversals (SBR). To date, the best theoretical R-approximation was 2 with an algorithm, which gives a 1.22 experimental
R-approximation on stacks with a size smaller than 70. In this paper a Monte Carlo
search (MCS) approach with nested levels and specific domain-dependent simulations
is used. The paper shows that MCS is an alternative to iterative deepening depth first
search for sorting large stacks of pancakes. At a given level and with a given number of
polynomial-time domain-dependent simulations, MCS is a polynomial-time algorithm
as well. MCS at level 3 gives a 1.04 experimental R-approximation, which is a
breakthrough. At level 1, MCS solves stacks of size 512 with an experimental
R-approximation value of 1.20.
“485 – A New Upper Bound for Morpion Solitaire,” a joint collaboration by Henryk
Michalewski, Andrzej Nagórko, and Jakub Pawlewicz, shows a new upper bound of
485 moves for the 5T variant of the Morpion Solitaire game. This is achieved by
encoding Morpion 5T rules as a linear program and solving 126,912 instances of this
program on special octagonal boards. To show the correctness of this method, the rules
of the game have been analyzed and the potential of a given position has been used. By
solving continuous-valued relaxations of linear programs on these boards, an upper
bound of 586 moves is obtained. Further analysis of original, not relaxed, mixedinteger programs leads to an improvement of this bound to 485 moves. However, this is
achieved at a significantly higher computational cost.
“Multi-Agent Retrograde Analysis,” by Tristan Cazenave, proposes a new predator–
prey game. This domain is modeled as a board game where three predators are trying to
capture a prey. Each agent has five possible moves: going up, down, left, right, or
staying in the same location. The game terminates if the prey is on the same location as
a predator or if the prey cannot move to an empty location. Small boards up to 99

Preface

VII

have been solved using retrograde analysis. The outcome is that the predator–prey
game is always lost for the prey when there are at least three predators.
“The Surakarta Bot Revealed,” by Mark Winands, presents the ideas behind the
agent SIA, which won the Surakarta tournament at the ICGA Computer Olympiad five
times. The paper first describes SIA’s ab-based variable-depth search mechanism.
Enhancements such as multi-cut forward pruning and realization probability search
improve the agent considerably. Next, features of the static evaluation function are
discussed as well. Experimental results indicate that features, which reward distribution
of the pieces and penalize pieces that clutter together, give a genuine improvement in
the playing strength.
“Learning to Trade in Strategic Board Games,” written by Heriberto Cuayáhuitl,
Simon Keizer, and Oliver Lemon, describes a data-driven approach for automatic
trading in the game of Settlers of Catan. Their experiments are based on data collected
from human players trading in text-based natural language. The performance of
Bayesian networks, conditional random fields, and random forests have been compared
in the task of ranking trading offers, and are evaluated both in an offline setting and
online while playing the game against a rule-based baseline. Experimental results show
that agents trained from data from average human players can outperform rule-based
trading behavior, and that the random forest model achieves the best results.
“Argumentative AI Director Using Defeasible Logic Programming,” a joint effort by
Ramiro Agis, Andrea Cohen, and Diego Martínez, presents a novel implementation of
an AI director that uses argumentation techniques to decide dynamic adaptations in the
level generation of a roguelike game called HermitArg. The architecture of the game
introduces smart items with defeasible information to be analyzed in a dialectical
process.

GIGA Workshop
“On the Cross-Domain Reusability of Neural Modules for General Video Game
Playing,” written by Alex Braylan, Mark Hollenbeck, Elliot Meyerson, and Risto
Miikkulainen, considers a general approach to knowledge transfer in which an agent
learning with a neural network adapts how it reuses existing networks as it learns in a
new domain. This approach is domain-agnostic and requires no prior assumptions
about the nature of task relatedness or mappings. The method’s performance and
applicability are analyzed in high-dimensional Atari 2600 general video game playing.
“The GRL System: Learning Board Game Rules with Piece-Move Interactions,”
written by Peter Gregory, Henrique Coli Schumann, Yngvi Björnsson, and Stephan
Schiffel, studies the problem of learning formal models of the rules of board games,
using as input only example sequences of the moves made in playing those games. This
work is distinguished from previous work in this area in that the interactions are learned
between the pieces in the games. A previous game rule acquisition system is supplemented by allowing pieces to be added and removed from the board during play, and
using a planning domain model acquisition system to encode the relationships between
the pieces that interact during a move.

VIII

Preface

“Creating Action Heuristics for General Game Playing Agents,” authored by Michal
Trutman and Stephan Schiffel, investigates an approach that learns online heuristics
that guide the simulations of MCTS in GGP. This approach generates heuristics that
estimate the usefulness of actions by analyzing the game rules as opposed to the
simulation results. Experimental results show the potential of this approach.
“Space-Consistent Game Equivalence Detection in General Game Playing,” by
Haifeng Zhang, Dangyi Liu, and Wenxin Li, discusses that GGP agents can efficiently
enhance their intelligence by taking advantage of experience from past games. The
authors argue that it is necessary for agents to detect equivalence between games. This
paper defines game equivalence formally and concentrates on a specific scale, spaceconsistent game equivalence (SCGE). To detect SCGE, an approach is proposed
mainly reducing the complex problem to some well-studied problems. An evaluation
of the approach is performed at the end.
These proceedings would not have been produced without the help of many persons.
In particular, we would like to mention the authors and reviewers for their
help. Moreover, the organizers of IJCAI 2015 contributed substantially by bringing the
researchers together.
March 2016

Tristan Cazenave
Mark H.M. Winands
Stefan Edelkamp
Stephan Schiffel
Michael Thielscher
Julian Togelius

Organization

Program Chairs
Tristan Cazenave
Mark Winands
Stefan Edelkamp
Stephan Schiffel
Michael Thielscher
Julian Togelius

Université Paris–Dauphine, France
Maastricht University, The Netherlands
University of Bremen, Germany
Reykjavik University, Iceland
University of New South Wales, Australia
New York University, USA

Program Committee
Yngvi Björnsson
Bruno Bouzy
Tristan Cazenave
Stefan Edelkamp
Michael Genesereth
Hiroyuki Iida
Nicolas Jouandeau
Lukasz Kaiser
Sylvain Lagrue
Marc Lanctot
Simon Lucas
Jacek Mańdziuk
Jean Méhat
Martin Müller
Diego Perez
Thomas Philip
Runarsson
Arpad Rimmel
Ji Ruan
Abdallah Saffidine
Spyridon
Samothrakis
Tom Schaul
Stephan Schiffel
Sam Schreiber
Nathan Sturtevant
Fabien Teytaud
Michael Thielscher

Reykjavik University, Iceland
Université Paris–Descartes, France
Université Paris–Dauphine, France
University of Bremen, Germany
Stanford University, USA
Japan Advanced Institute of Science and Technology, Japan
Université Paris 8, France
Université Paris–Diderot, France
Université d’Artois, France
Google DeepMind, UK
University of Essex, UK
Warsaw University of Technology, Poland
Université Paris 8, France
University of Alberta, Canada
University of Essex, UK
University of Iceland, Iceland
Supelec, France
Auckland University of Technology, New Zealand
University of New South Wales, Australia
University of Essex, UK
Google DeepMind, UK
Reykjavik University, Iceland
Google Inc., USA
University of Denver, USA
Université du Littoral Côte d’Opale, France
University of New South Wales, Australia

X

Organization

Julian Togelius
Mark Winands
Shi-Jim Yen

New York University, USA
Maastricht University, The Netherlands
National Dong Hwa University, Taiwan

Additional Reviewers
Sumedh Ghaisas
Chiara Sironi
Maciej Świechowski

Contents

Computer Games Workshop 2015
Challenges and Progress on Using Large Lossy Endgame Databases
in Chinese Checkers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nathan R. Sturtevant

3

Sequential Halving for Partially Observable Games . . . . . . . . . . . . . . . . . . .
Tom Pepels, Tristan Cazenave, and Mark H.M. Winands

16

An Experimental Investigation on the Pancake Problem . . . . . . . . . . . . . . . .
Bruno Bouzy

30

485 – A New Upper Bound for Morpion Solitaire. . . . . . . . . . . . . . . . . . . .
Henryk Michalewski, Andrzej Nagórko, and Jakub Pawlewicz

44

Multi-agent Retrograde Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tristan Cazenave

60

The Surakarta Bot Revealed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Mark H.M. Winands

71

Learning to Trade in Strategic Board Games . . . . . . . . . . . . . . . . . . . . . . .
Heriberto Cuayáhuitl, Simon Keizer, and Oliver Lemon

83

Argumentative AI Director Using Defeasible Logic Programming . . . . . . . . .
Ramiro A. Agis, Andrea Cohen, and Diego C. Martínez

96

General Intelligence in Game-Playing Agents 2015
On the Cross-Domain Reusability of Neural Modules for General Video
Game Playing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Alex Braylan, Mark Hollenbeck, Elliot Meyerson,
and Risto Miikkulainen
The GRL System: Learning Board Game Rules with Piece-Move
Interactions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Peter Gregory, Henrique Coli Schumann, Yngvi Björnsson,
and Stephan Schiffel

115

130

XII

Contents

Creating Action Heuristics for General Game Playing Agents . . . . . . . . . . . .
Michal Trutman and Stephan Schiffel

149

Space-Consistent Game Equivalence Detection in General Game Playing . . . .
Haifeng Zhang, Dangyi Liu, and Wenxin Li

165

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

179

Computer Games Workshop 2015

Challenges and Progress on Using Large Lossy
Endgame Databases in Chinese Checkers
Nathan R. Sturtevant(B)
Department of Computer Science, University of Denver, Denver, CO, USA
[email protected]

Abstract. A common evaluation function for playing Chinese Checkers
with two or more players has been the single-agent distance across the
board. This is an abstraction of a perfect heuristic, because it ignores the
interactions between the players in the game. Previous work has studied
these heuristics for smaller versions of the game, including 6-piece data
for a board with 49 locations and 81 locations which have 13.98 million
and 324.5 million combinations respectively. The single-agent solution
to the full game of Chinese Checkers has 81 locations and 10 pieces per
player. This results in 1.88 trillion possible positions and is stored using
500 GB of disk space. In this paper we report results from a preliminary
study on how to best use the data to improve the play of a Chinese
Checkers program.

1

Introduction

Endgame databases have been a key component of game-playing programs in
games like Checkers [23] and Chess [15], where they contain precise information
that is easier to pre-compute than it is to summarize in heuristics or machinetuned evaluation functions. Endgame databases are most useful when a game
converges to simpler positions that may take a long time to resolve. In this case,
the size of the endgame databases are small relative to the size of the game, and
the computation associated with the endgame database would be non-trivial to
reproduce at runtime. For instance, work on 7-piece chess endgame databases
has discovered a position where 549 moves are required for mate [1]. These lines
of play would not be discovered by programs that just attempt to find the best
move from the same position, as the depth of search required is far beyond what
could be found by normal time controls during a competitive game. Similarly,
work on Checkers databases helped prove that a well-studied position from 1800,
once assumed to be a win, was actually a draw [22]. Databases have also been
successfully built for games like Chinese Chess [7].
Endgame databases are not universally useful, however, particularly when
there are many possible endgame positions and when the resolution of each position is simple. In games such as card games, for example, endgame databases are
52!
essentially useless. There are 44!2
4 = 1.9 trillion combinations of two cards that
4 players can have at the end of a trick-based card game (assuming a standard
52 card deck), but there are at most 16 ways to play out each possible hand.
c Springer International Publishing Switzerland 2016

T. Cazenave et al. (Eds.): CGW 2015/GIGA 2015, CCIS 614, pp. 3–15, 2016.
DOI: 10.1007/978-3-319-39402-2 1

© 2018-2019 uberlabel.com. All rights reserved