Advances in Computer Games: 17th International Conference, ACG 2021, Virtual Event, November 23–25, 2021, Revised Selected Papers (Lecture Notes in Computer Science, 13262)

This book constitutes the refereed post-conference proceedings of the 17th International Conference on Advances in Computer Games, ACG 2021, which was held as a virtual event during November 23–25, 2021. The 22 full papers included in this book were carefully reviewed and selected from 34 submissions. They were organized in topical sections as follows: learning in games; search in games; solving games; chess patterns; player modelling; and game systems. Preface Organization Contents Learning in Games Improving Counterfactual Regret Minimization Agents Training in Card Game Cheat Using Ordered Abstraction 1 Introduction 2 Background 2.1 Notations and Terminology 2.2 The Game Cheat 2.3 Counterfactual Regret Minimization 3 Related Works 4 Ordered Abstraction and Curriculum Learning 4.1 Application to Cheat 5 Experiments 5.1 Experimental Setups 5.2 Results 6 Conclusion References Deep Reinforcement Learning for Morpion Solitaire 1 Introduction 2 Preliminaries on Monte-Carlo Search for Game Playing 2.1 NMCS and NRPA 2.2 Playing Morpion Solitaire with Monte Carlo Search 3 Imitating NRPA 3.1 Game State Representation 3.2 Neural Network Architecture 3.3 Training Data and Training Procedure 3.4 Model Performance (Without Search) 3.5 Combining MC Search Algorithms with a Neural Based Search Procedure 4 Self Play with Exit 5 Conclusion References Expert Iteration for Risk 1 Introduction 2 Preliminaries 2.1 Monte Carlo Tree Search 2.2 Expert Iteration 3 Previous Work 4 Player Design 4.1 General Player Design and Architecture 4.2 Loss Function and Further Parameters 5 Experiments 5.1 Hexagonal Map 6 Future Work 7 Conclusion References Search in Games Sequential Halving Using Scores 1 Introduction 2 The Sequential Halving Algorithm 2.1 Restart vs Stockpile 2.2 Experiments 3 Scores 3.1 Theoretical Model 3.2 Optimal Combination 3.3 Selection Bias 3.4 Case of AMAF: a Better Formula for ' 3.5 Case of Prior Score: Pruning 3.6 Experiments with AMAF 3.7 Experiments with a Neural Network 4 Conclusion References Cosine Annealing, Mixnet and Swish Activation for Computer Go 1 Introduction 2 Improving Supervised Learning 2.1 Cosine Annealing 2.2 MixNet 2.3 Swish Activation 3 Experimental Results 3.1 Training with Cosine Annealing 3.2 Training Small Networks with Mixnet and Swish Activation 3.3 Training Big Networks with Mixnet and Swish Activation 3.4 Playing 4 Conclusion References A Heuristic Approach to the Game of Sylver Coinage 1 Introduction 2 Bot Strategies for Playing Sylver Coinage 3 Introducing Elo to Keep Track of Bot Success 4 Conclusion References Evaluating Interpretability Methods for DNNs in Game-Playing Agents 1 Introduction 2 Background 2.1 Model Interpretability 2.2 Breakthrough 3 Methods 3.1 The Model 3.2 Evaluation Measures 4 Results 4.1 Experimental Setup 4.2 Saliency Methods: Qualitative Evaluation 4.3 Saliency Methods: Quantitative Evaluation 4.4 Explaining the Explanations 5 Conclusion and Future Work References Solving Games Quixo is Solved 1 Introduction 1.1 Quixo 1.2 Objectives and Challenges 1.3 Results Overview 2 Preliminaries 3 Solving Quixo – Data Structures 3.1 Bitboard State Representation 3.2 Optimized Storage of Results 4 Solving Quixo – Algorithms 4.1 Computing Outcome 4.2 Deriving an Optimal Strategy 4.3 Implementations 5 Results 5.1 55 Quixo 5.2 44 Quixo 6 Conclusions and Open Questions References Solving Bicoloring-Graph Games on Rectangular Boards – Part 1: Partisan Col and Snort 1 Introduction 2 Combinatorial Game Theory for Col and Snort 2.1 Numbers and Star 2.2 Switches 3 Partisan Col on Rectangular Boards 3.1 Col on m n Boards with m and/or n Even 3.2 Col on m n Boards with m and n Odd, with m, n 3 3.3 Linear Col 4 Partisan Snort on Rectangular Boards 4.1 Snort on m n Boards with m and n Even 4.2 Snort on m n Boards with m and/or n Odd 4.3 Linear Snort 5 Conclusions and Future Research References Solving Bicoloring-Graph Games on Rectangular Boards – Part 2: Impartial Col and Snort 1 Introduction 2 Combinatorial Game Theory for iCol and iSnort 2.1 Nimbers 3 Impartial Col and Snort 3.1 iCol on Rectangular Boards 3.2 Linear iCol 3.3 iSnort on Rectangular Boards 3.4 Linear iSnort 4 Conclusions and Future Research References BoxOff is NP-Complete 1 Introduction 2 Reduction Overview 3 4-Color BoxOff is NP-Complete 3.1 Overlay Stones and Gadget Stones 3.2 Signals 3.3 Variable Gadget 3.4 Wiring Gadgets 3.5 Logical Gadgets 3.6 Gadget Interactions 3.7 The Reduction 3.8 Example Transformation 4 Conclusion References Chess Patterns Automatic Recognition of Similar Chess Motifs 1 Introduction 1.1 Related Work 2 Domain Description 3 Similarity Computation 3.1 Static Features 3.2 Dynamic Features 4 Building a Database of Tactical Puzzles 5 Evaluation 5.1 Matching Pairs of Puzzles from a Chess Training Course 5.2 Chess Expert's Explanations of Similarity 5.3 Comparison with a Group of Chess Experts 6 Conclusion References On the Road to Perfection? Evaluating Leela Chess Zero Against Endgame Tablebases 1 Introduction 2 Background 2.1 Chess Endgame Tablebases 2.2 Leela Chess Zero 3 Analyzing Chess Endgames with Leela Zero Chess 3.1 Tablebase Dataset Pre-processing 3.2 Choice of AlphaZero Program and Its Parameters 4 Experiments 4.1 Move Prediction Accuracy for Basic Settings 4.2 Performance at Different Decision Depths 4.3 Case Studies: Interesting Engine Mistakes 5 Summary and Future Work References Chess Endgame Compression via Logic Minimization 1 Introduction 1.1 Game-Theoretic Error-Free Endgame Play 1.2 State-of-the-Art Chess Endgame Data Compression 1.3 Approach 2 Two-Level Logic Minimization 2.1 MINI 2.2 ESPRESSO 2.3 Pupik 2.4 A Simple Position Encoding Scheme 2.5 Method 3 Experimentation 3.1 Two- and Three-Piece Endgame Tables 3.2 Two- Through Four-Piece Results 3.3 Compression Effectiveness 3.4 Query Effectiveness 4 Contributions References Player Modelling Procedural Maze Generation Considering Difficulty from Human Players' Perspectives 1 Introduction 2 Related Work 3 Investigation of Human Players' Tendencies 3.1 Subject Experiments 3.2 Prediction by Supervised Learning 4 Maze Generation and Selection Approach 4.1 Test Player Considering Human-Likeness 4.2 Maze Difficulty Evaluation Using Test Player 5 Subject Experiments on Maze Evaluation 6 Conclusions and Future Work Appendix A Input Features of Prediction Models References Opponent Model Selection Using Deep Learning 1 Introduction 2 Background 2.1 Terminologies 2.2 Chinese Dark Chess 2.3 Game Tournament and Expected Score 2.4 Contempt Factor and Threefold Repetition 2.5 Chinese Dark Chess Programs 3 Method 3.1 Input Data of the ORNN 3.2 Input Planes of the ORNN 3.3 Output of the ORNN 4 Experiments 4.1 Experiment Settings 4.2 The Effect of Using the Contempt Factor 4.3 Experiment Results 5 Conclusions References Using Deep Learning to Detect Facial Markers of Complex Decision Making 1 Introduction and Related Work 1.1 Decision-Making in Video Games 1.2 Facial Expressions and Machine Learning 2 Methods 2.1 Data Collection and Participants 2.2 Decision Selection 3 Data Preparation and Modelling 3.1 Data Extraction 3.2 Data Preprocessing 3.3 Model Description 4 Results 5 Discussion References A Generic Approach for Player Modeling Using Event-Trait Mapping Supported by PCA 1 Introduction 2 Related Works 3 Methodology 4 A Case Study on Wow Data 4.1 Data Collection and Preprocessing 4.2 Trait Selection 4.3 Applying Profiling Steps 4.4 Results and Discussion 5 Conclusion References Game Systems Automatic Generation of Board Game Manuals 1 Introduction 2 Background 2.1 Ludii 2.2 Related Work 3 Ludii Game Description Language 3.1 Translation to English 4 Move Visualisations 4.1 Move Properties 4.2 Identifying Distinct Moves 4.3 Visual Representations 5 Additional Features 5.1 Initial Setup 5.2 Winning/Losing Moves 5.3 Similar Legal Moves 5.4 Strategy Explanation 6 Complete Game Manuals 7 Conclusion 7.1 Limitations 7.2 Future Work A English Translations of Ludii Game Descriptions A.1 Hex A.2 Amazons References Optimised Playout Implementations for the Ludii General Game System 1 Introduction 2 Background 3 Related Work 4 Add-to-Empty Playouts 5 Filter Playouts 6 No-Repetition Playouts 7 Non-uniform Move Distributions 8 Empirical Evaluation 9 Conclusion References General Board Geometry 1 Introduction 2 Game Graphs 2.1 Dimensions: Cells or Vertices 3 Game Board Description 4 Graph Relations 4.1 Directions 4.2 Steps and Walks 4.3 Radials 5 Graph Operators 6 Conclusion References Quantifying the Space of Hearts Variants 1 Introduction 2 Hearts 3 Variants 4 Heuristic Metrics 4.1 Drama 4.2 Security 4.3 Spread 4.4 Order 5 Results 6 Future Work References Author Index