The ACG 2019 Conference

Cooperation

The first paper is “Advice is useful for Game AI: Experiments with Alpha-Beta Search Players in Shogi” by Shogo Takeuchi. It presents methods to strengthen a game AI using advice from other game AIs during game play. Advice is a list of moves selected by an advise. Propose is a mechanism that makes a player search again when the player’s move is different from advice. Experiments are made for the game of Shogi.

The second paper by Eisuke Sato and Hirotaka Osawa is “Reducing Partner’s Cognitive Load by Estimating the Level of Understanding in the Cooperative Game Hanabi”. Hanabi is a cooperative game for ordering cards through information exchange. Cooperation is achieved in terms of increased scores, as well as a reduced cognitive load for the players. The thinking time is used as an indicator of cognitive load. The results showed that the thinking time is inversely proportional to the confidence of choice. When the agent uses the thinking time of the player, the mean thinking time of the human player is shortened. It suggests that cooperation could reduce the cognitive load of the players without influencing performance.

The third paper by Gregory Schmidt and Philip Shoptaugh is “Making a Better Game: The History of Cluster”. The authors present a case study. They investigate the initial inspiration process and design process. Their combination led to successfully optimized versions of the game Cluster.

Single player games

The fourth paper by Taishi Oikawa, Chu-Hsuan Hsueh and Kokolo Ikeda is “Enhancing Human Players’ T-Spin Technique in Tetris with Procedural Problem Generation”. The authors are interested in programs that can entertain or teach human players. The programs automatically generate puzzles so that human players improve at playing the game of Tetris. A technique hard to learn for beginners is T-spin. Therefore, automatically generated two-step T-spin problems are given to human players to solve, which improved their skills at Tetris.

The fifth paper by Kiminori Matsuzaki is “A Further Investigation of Neural Network Players for Game 2048”. Game 2048 is a stochastic single-player game. Strong 2048 computer players use N-tuple networks trained by reinforcement learning. The paper investigates neural-network players for Game 2048 and improve their layers and their inputs and outputs. The best neural-network player achieved an average score of 215 803 without search techniques. This result is comparable to N-tuple-network players.

Mathematical approaches

The sixth paper by Michael Hartisch and Ulf Lorenz is “A Novel Application for Game Tree Search – Exploiting Pruning Mechanisms for Quantified Integer Programs”. The authors investigate pruning in search trees of so-called quantified integer (linear) programs (QIPs). QIPs consist of a set of linear inequalities and a minimax objective function, where some variables are existentially quantified and others are universally quantified. They develop and theoretically substantiate tree pruning techniques based upon algebraic properties. The implementation of their findings can massively speed up the search process.

The seventh paper by Nicolas Fabiano and Ryan Hayward is “New Hex Patterns for Fill and Prune”. A fill pattern in the game of Hex is a subposition with one or more empty cells that can be filled without changing the position’s minimax value. Some cells can be pruned and ignored when searching for a winning move. The authors introduce (1) two new kinds of Hex fill – mutual and near-dead – and thereafter (2) some resulting fill patterns. Moreover, they show four new permanently-inferior fill patterns. Finally, they present three new prune results, based on strong-reversing, reversing, and game-history, respectively.

The eighth paper by Jos Uiterwijk is “Solving Cram using Combinatorial Game Theory”. He investigates the board game Cram, which is an impartial combinatorial game. He uses (1) an αβ solver and (2) knowledge obtained from Combinatorial Game Theory (CGT). Moreover, the author exploits endgame databases pre-filled with CGT values (nimbers) for all positions fitting on boards with at most 30 squares together with two efficient move-ordering heuristics. The combination gives a large improvement of solving power. Jos also defines five more heuristics based on CGT that further reduce the sizes of the solution trees considerably. He was able to solve all odd by odd Cram boards for which results were available from the literature (even by even and odd by even boards are trivially solved). On top of that, he proves new results for two boards, viz. the 3×21 board, is a first-player win, and the 5×11 board, is a second-player win.

Nonogram: General and specific approaches

The ninth paper by Aline Hufschmitt, Jean-Noel Vittaut and Nicolas Jouandeau is “Exploiting Game Decompositions in Monte Carlo Tree Search”. They propose the Multiple Tree MCTS (MT-MCTS) approach, which simultaneously builds multiple MCTS trees that correspond to different sub-games. The authors apply MT-MCTS to single player games from General Game Playing. Complex compound games are solved faster, namely from 2 times faster (Incredible) up to 25 times faster (Nonogram).

The tenth paper by Yan-Rong Guo, Wei-Chiao Huang, Jia-Jun Yeh, Hsi-Ya Chang, Lung-Pin Chen and Kuo-Chan Huang is “On Efficiency of Fully Probing Mechanisms in Nonogram Solving Algorithm”. Fully probing plays are important for Nonogram. The authors address three critical factors influencing fully probing efficiency: re-probing policy, probing sequence, and computational overhead. Taking into account these factors they improve the speed of solving Nonogram puzzles significantly.

Deep learning

The eleventh paper by Hsiao-Chung Hsieh, Ti-Rong Wu, Ting Han Wei and I-Chen Wu is “Net2Net Extension for the AlphaGo Zero Algorithm”. The number of residual blocks of a neural network that learns to play the game of Go following the AlphaGo Zero approach is important for the strength of the program, but it also takes more time for self-play. The authors propose a method to deepen the residual network without reducing performance. The deepening process is performed by inserting new layers into the original network. Three insertion schemes are presented. For 9×9 Go, they obtain a 61.69% win rate against the unextended player, while greatly saving time for self-play.

The twelfth paper by Tomihiro Kimura and Kokolo Ikeda is “Designing Policy Network with Deep Learning in Turn-Based Strategy Games”. The authors apply deep learning to turn-based strategy games. A recurrent policy network is developed learning from game records. The game data are generated using Monte Carlo Tree Search. The resulting policy network outperforms MCTS.

Invited papers

The first invited paper by Nathan Sturtevant is “Steps towards Strongly Solving 7×7 Chinese Checkers”. Chinese Checkers is a game for 2-6 players that has been used as a testbed for game AI in the past. Nathan provided an overview of what is required to strongly solve versions of the game. He also included a complete set of rules needed to solve the game. Finally, he provided results on smaller boards where the results showed that these games are all a first-player win.

The second invited paper by Cameron Browne, Matthew Stephenson, Éric Piette and Dennis J.N.J. Soemers is “The Ludii General Game System: Interactive Demonstration”. Ludii is a new general game system, currently under development. Their aims are to support a wider range of games than existing systems and approaches. Ludii is being developed primarily for the task of game design, but it offers also a number of other potential benefits for many people, such as game and AI researchers, professionals and hobbyists. The paper describes (1) the approach behind Ludii, (2) how it works, (3) how it is used, and (4) what it can potentially do.

Jonathan Schaeffer gave a third invited talk. It was on the history of computer chess.