Advances in computer games : 16th international conference, ACG 2019, Macao, China, August 11-13, 2019 : revised selected papers

This book constitutes the refereed post-conference proceedings of the 16th International Conference on Advances in Computer Games, ACG 2019, held in Macao, China, in August 2019. The 12 full papers presented together with 2 invited papers were carefully reviewed and selected from 19 submissions. The selected papers are devoted to topics such as cooperation; single player games; mathematical approaches; nonogram: general and specific approaches; and deep learning. Preface 6 Organization 10 Contents 13 Advice is Useful for Game AI: Experiments with Alpha-Beta Search Players in Shogi 15 1 Introduction 15 2 Related Work 16 2.1 Advice from Game AIs to Human 16 2.2 Majority Voting 17 3 Proposed Method 17 3.1 Options of Searching Moves 18 4 Experiments 18 4.1 Tournament Between Single Engines 19 4.2 Tournaments Among Proposed Methods 20 4.3 Tournament Using Two Advisers 21 4.4 Time Extension 22 4.5 Discussion 22 5 Conclusion 23 References 23 Reducing Partner’s Cognitive Load by Estimating the Level of Understanding in the Cooperative Game Hanabi 25 1 Introduction 25 2 Background of Hanabi 26 2.1 Rules of Hanabi 26 2.2 Works Related to Hanabi 27 3 Agent Algorithm Using Thinking Time 28 3.1 Method 28 3.2 Conventional Self-Estimation Strategy 28 3.3 Self-Estimation Strategy That Changes Estimation Reliability According to Thinking Time 29 4 Thinking-Time Experiment 30 4.1 Interface 30 4.2 Evaluation Method of the Thinking-Time Experiment 30 4.3 Procedure of the Thinking-Time Experiment 31 4.4 Result of the Thinking-Time Experiment 32 5 Cognitive-Load Experiment 33 5.1 Evaluation of the Cognitive-Load Experiment 33 5.2 Procedure of the Cognitive-Load Experiment 33 5.3 Results of the Cognitive-Load Experiment 34 6 Discussion 34 6.1 Discussion of the Thinking-Time Experiment 34 6.2 Discussion of the Cognitive-Load Experiment 35 6.3 Limitations and Future Work 35 7 Conclusion 35 References 36 Making a Better Game: The History of Cluster 38 1 Introduction 38 1.1 Rules of Cluster 39 2 The Genesis of a New Game 39 2.1 Cluster’s Lineage 39 3 From Concept to Realization 41 3.1 Design Considerations 41 3.2 Initial Release 43 4 Cluster-64 44 4.1 Automating the Prototype Generation Process 44 5 Cluster-58 46 5.1 The Refinement Process 46 5.2 The Finalized Design 48 6 Cluster Strategy 49 7 Experimental Game Designs 50 8 Piece to Space Ratio 52 9 Design Heuristic Synopsis 52 10 Game Design Wisdom 53 11 Conclusion 53 References 54 Improving Human Players' T-Spin Skills in Tetris with Procedural Problem Generation 55 1 Introduction 55 2 Background 56 2.1 The Game of Tetris 56 2.2 Related Work on Procedural Problem Generation 57 3 Experiments on Interestingness and Difficulty 58 3.1 Experiment Settings 59 3.2 Features of Two-Step to T-Spin Problems 60 3.3 Results of Predictors 60 4 Experiments on Improving Human Players' Skills 62 4.1 Experiment Settings 62 4.2 Results of Skill Improvement 64 5 Conclusions and Future Work 64 References 65 A Further Investigation of Neural Network Players for Game 2048 67 1 Introduction 67 2 Game 2048 68 3 Related Work: Neural-Network Players for Game 2048 69 4 Experiment 1: Changing Components 70 5 Experiment 2: Changing Input/Output 74 6 Conclusion 77 References 78 A Novel Application for Game Tree Search - Exploiting Pruning Mechanisms for Quantified Integer Programs 80 1 Introduction 80 2 Preliminaries: Basics of Quantified Integer Programming 82 3 Pruning in QIP Search Trees 84 3.1 Theoretical Analysis 84 3.2 SCP Implementation Details 86 3.3 Example 87 4 Solver, Experiments and Results 88 5 Conclusion 90 References 91 New Hex Patterns for Fill and Prune 93 1 Introduction 93 2 General Analysis 94 3 Previous Fill Results 95 4 New Fill Results 96 4.1 Near-Death Patterns 96 4.2 Mutual-Fill Patterns 98 4.3 New X-permanently Inferior Patterns 98 5 New Prune Results 99 5.1 New Theorem Using Reversibility 99 5.2 New Reverse Patterns 100 5.3 Self-reversibility 102 6 Experiments 102 References 103 Solving Cram Using Combinatorial Game Theory 105 1 Introduction 105 2 Combinatorial Game Theory for Cram 106 2.1 Nimbers 107 2.2 Disjunctive Sums of Subgames 109 2.3 Cram Strategies 109 3 Experiments and Discussion 110 3.1 Base Case 110 3.2 Using Endgame Databases 111 3.3 Using CGT Values 113 4 Conclusions and Future Research 117 References 118 Exploiting Game Decompositions in Monte Carlo Tree Search 120 1 Introduction 120 2 MCTS and UCT 121 3 Multiple Tree MCTS (MT-MCTS) 122 4 Experiments 127 5 Discussion 130 6 Conclusion 130 References 131 On Efficiency of Fully Probing Mechanisms in Nonogram Solving Algorithm 133 1 Introduction 133 2 Related Work 135 3 Fully Probing Efficiency from Different Aspects 136 3.1 Re-probing Policy 137 3.2 Probing Sequence 138 3.3 Computational Overhead 140 4 New Fully Probing Methods and Performance Evaluation 141 5 Conclusions and Future Work 143 References 143 Net2Net Extension for the AlphaGo Zero Algorithm 145 1 Introduction 145 2 Background 146 2.1 Residual Networks 146 2.2 AlphaGo Zero 147 2.3 Net2Net 148 3 Our Method 148 3.1 Transfer Method 149 3.2 Training Method 150 4 Experiments 152 4.1 Experimental Setup 152 4.2 Experiment for Shift-Training 152 4.3 Experiment for End-Training 155 5 Conclusion 156 References 156 Designing Policy Network with Deep Learning in Turn-Based Strategy Games 157 1 Introduction 157 2 Turn-Based Strategy Games as an Academic Platform: TUBSTAP 158 2.1 Difficulty of Turn-Based Strategy Games 158 2.2 TUBSTAP Game System 158 2.3 Related Works for TUBSTAP 159 3 Purpose and Procedure 160 3.1 Previous Studies 161 4 Experiments 161 4.1 Game Record Database for Learning 161 4.2 Neural Network Design 163 4.3 Learning Procedure 164 4.4 Result of the Competition Experiment 166 5 Discussion and Conclusion 166 References 167 On Strongly Solving Chinese Checkers 169 1 Introduction 169 2 Background and Related Work 170 2.1 Terminology 171 3 Rules of Chinese Checkers 171 3.1 Movement Rules 172 3.2 Winning Conditions 173 3.3 Illegal States 174 3.4 Draws 176 3.5 Chinese Checkers Symmetry 177 4 Strongly Solving the Chinese Checkers 177 5 Results 178 6 Conclusions and Future Work 179 References 179 A Practical Introduction to the Ludii General Game System 181 1 Introduction 181 1.1 The Digital Ludeme Project 181 2 Ludemic Approach 182 2.1 Ludemes 182 2.2 Ludi 183 3 Class Grammar 183 3.1 Annotations 183 3.2 Game Descriptions 184 3.3 Game Compilation 184 3.4 Advantages and Disadvantages 185 4 Game Representation 185 4.1 Game States 185 4.2 Moves and Actions 185 5 AI Agents 186 5.1 Default AI Agents 186 5.2 Third-Party AI Support 186 6 Ludii Player 186 6.1 Game Playing 187 6.2 Agent Evaluation 188 6.3 Manual Game Creation 188 7 Ludii Portal 189 8 Planned Services 191 8.1 Automated Game Design 191 8.2 Game Optimisation 191 8.3 Historical Game Reconstruction 191 9 Conclusion 192 References 192 Author Index 194 Front Matter ....Pages i-xiii Advice is Useful for Game AI: Experiments with Alpha-Beta Search Players in Shogi (Shogo Takeuchi)....Pages 1-10 Reducing Partner’s Cognitive Load by Estimating the Level of Understanding in the Cooperative Game Hanabi (Eisuke Sato, Hirotaka Osawa)....Pages 11-23 Making a Better Game: The History of Cluster (Gregory Schmidt, Philip Shoptaugh)....Pages 24-40 Improving Human Players’ T-Spin Skills in Tetris with Procedural Problem Generation (Taishi Oikawa, Chu-Hsuan Hsueh, Kokolo Ikeda)....Pages 41-52 A Further Investigation of Neural Network Players for Game 2048 (Kiminori Matsuzaki)....Pages 53-65 A Novel Application for Game Tree Search - Exploiting Pruning Mechanisms for Quantified Integer Programs (Michael Hartisch, Ulf Lorenz)....Pages 66-78 New Hex Patterns for Fill and Prune (Nicolas Fabiano, Ryan Hayward)....Pages 79-90 Solving Cram Using Combinatorial Game Theory (Jos W. H. M. Uiterwijk)....Pages 91-105 Exploiting Game Decompositions in Monte Carlo Tree Search (Aline Hufschmitt, Jean-Noël Vittaut, Nicolas Jouandeau)....Pages 106-118 On Efficiency of Fully Probing Mechanisms in Nonogram Solving Algorithm (Yan-Rong Guo, Wei-Chiao Huang, Jia-Jun Yeh, Hsi-Ya Chang, Lung-Pin Chen, Kuo-Chan Huang)....Pages 119-130 Net2Net Extension for the AlphaGo Zero Algorithm (Hsiao-Chung Hsieh, Ti-Rong Wu, Ting-Han Wei, I-Chen Wu)....Pages 131-142 Designing Policy Network with Deep Learning in Turn-Based Strategy Games (Tomihiro Kimura, Kokolo Ikeda)....Pages 143-154 On Strongly Solving Chinese Checkers (Nathan R. Sturtevant)....Pages 155-166 A Practical Introduction to the Ludii General Game System (Cameron Browne, Matthew Stephenson, Éric Piette, Dennis J. N. J. Soemers)....Pages 167-179 Back Matter ....Pages 181-181