Computers and Games. International Conference, CG 2022 Virtual Event, November 22–24, 2022 Revised Selected Papers

Description

Preface Organization Contents Classic Games FairKalah: Towards Fair Mancala Play 1 Introduction 2 Algorithmic Approach 3 Analysis of Fair Optimal Game Trees 3.1 Features 3.2 Optimal Play Branching Factors and Tension 3.3 Strategic Insights 4 Modeling Optimal Play for Diverse States 4.1 Model Performance Summary 4.2 SHAP Beeswarm Figure Interpretation 5 Future Work 6 Conclusions 7 Appendix: FairKalah Boards 7.1 Moving 1 Piece 7.2 Moving 2 Pieces References Improving Search in Go Using Bounded Static Safety 1 Introduction 2 Related Work 3 Background 3.1 Rules of Go 3.2 Sure Liberty Regions 3.3 Proving the Safety of Regions 4 Improving Lower Bounds for the Number of Safe Points 4.1 Technique 1: Extending Liberties 4.2 Technique 2: Intersecting Play 5 Results 6 Concluding Remarks References An Efficient Chinese Checkers Implementation: Ranking, Bitboards, and BMI2 pext and pdep Instructions 1 Introduction 2 Chinese Checkers Rules 3 Chinese Checkers Bitboard Representation 3.1 Get Winner 3.2 Get, Apply, and Undo Moves 3.3 Ranking and Unranking States 4 Experimental Results 4.1 Solving Time 5 Conclusions References Multi-Player and Multi-Action Games Solving Chainmail Jousting 1 Introduction 2 Rules of the Game 3 Solving the Game 3.1 Preliminary Analysis 3.2 Iterated Elimination of Dominated Strategies 3.3 Finding Nash Equilbria 3.4 Timing and Other Tests 3.5 Comparing the Mixed Strategies 4 Variants 4.1 Maximizing Points 4.2 GaryCon Variant 5 Conclusion References An Algorithm for Multiplayer Games Exploiting Opponents' Interactions with the Player 1 Introduction 2 Background 3 Interaction Tree Search 4 Experiments 5 Discussion References Incentivizing Information Gain in Hidden Information Multi-Action Games 1 Introduction 2 Related Work 2.1 Imperfect Information MCTS Extensions 2.2 Multi-Action Turn MCTS Extensions 3 Information Gain and Risk for MCTS 3.1 Probability Map 3.2 Information Gain Incentive 3.3 Risk Determinization 4 Results 5 Conclusions and Future Work References Solving Games QBF Solving Using Best First Search 1 Introduction 2 Background 2.1 Game Solving with Best First Search Algorithms 2.2 Search Based QBF Solving 2.3 Schloeter's CDCL Based SAT Solver 3 Best-First Search and QBF Solving 3.1 Best-First Search Based QBF Solver with CDCL and SBJ 3.2 Complications with Cube Learning and Pure Literal Elimination 4 Experimental Results and Discussion 5 Conclusion A .26em plus .1em minus .1em Correctness Discussion of the BFS Based CDCL Solver References Oware is Strongly Solved 1 Solution 2 Introduction 2.1 Rules of Oware, Abapa Variant 2.2 History: 30 Years of Research 2.3 Key Milestones 3 Method 3.1 Strategy 3.2 Step 1: Mapping the Legal Positions 3.3 Step 2: Resolving Small State Spaces 3.4 Step 3: Resolving Large State Spaces 4 Validation and Conclusion References Solving Impartial SET Using Knowledge and Combinatorial Game Theory 1 Introduction 2 Impartial SET 3 SET Theory 4 Forward Pruning Using Knowledge and CGT 4.1 Forward Pruning Using Sequence-Based Equivalence 4.2 Forward Pruning Using Symmetry-Based Equivalence 4.3 Forward Pruning Using CGT Subgame Databases 4.4 Forward Pruning Using CGT SubSET Databases 5 Solving Impartial SET Versions 5.1 Solving Using Basic Search Methods 5.2 Solving Using Knowledge-Based Methods 6 Conclusions and Future Research References Measuring Games Which Rules for Mu Torere? 1 Introduction 2 Ruleset A: No Restriction 3 Ruleset B: No Win on First Move 4 Ruleset C: Move If Adjacent to Enemy 5 Ruleset D: No Win on First Two Rounds 6 Ruleset E: Move to Centre If Adjacent to Enemy 7 Which Ruleset: D or E? 7.1 Drawishness 7.2 Playout Behaviour 7.3 Mistake Potential 8 Conclusion References Measuring Board Game Distance 1 Introduction 2 Datasets 2.1 Games 2.2 Concepts 3 Data Visualisation 4 Game Distance 5 Results 5.1 Discussion 6 Conclusion References Decision Making in Games and Puzzles Improving Computer Play in Skat with Hope Cards 1 Introduction 2 Computer Skat 3 Incomplete-Information Search 4 Hope Cards 5 Evaluation 6 Conclusion References Batch Monte Carlo Tree Search 1 Introduction 2 Monte Carlo Tree Search 2.1 Parallelization of MCTS 2.2 The Virtual Loss 2.3 Batched Inferences 2.4 First Play Urgency 3 The Batch MCTS Algorithm 3.1 Trees and Transposition Table 3.2 The Main Algorithm 3.3 Updating the Statistics 3.4 The FPU 3.5 The Virtual Mean 3.6 The Last Iteration 3.7 The Second Move Heuristic 4 Experimental Results 4.1 The FPU 4.2 Trees and Transposition Table 4.3 The Virtual Mean 4.4 The Last Iteration 4.5 The Second Move Heuristic 4.6 Ablation Study 4.7 Inference Speed 5 Conclusion References Towards Transparent Cheat Detection in Online Chess: An Application of Human and Computer Decision-Making Preferences 1 Introduction 1.1 Ethical Considerations 1.2 Related Work 1.3 Contributions 2 Data Sets and Metrics 3 Human Play 3.1 Move Accuracy Plots 3.2 Move Time Plots 4 Computer Play 5 Cheat Detection 5.1 Potential Biases and Limitations 5.2 Distinguishing Between Marked and Non-marked Players 5.3 Implications for Diagnostic Cheat Detection 6 Conclusions References Procedural Generation of Rush Hour Levels 1 Introduction 2 Related Work 2.1 PCG for Puzzles Games 2.2 GAN for PCG 3 Rush Hour Solvers 4 Accelerating the Generation Using Neural Networks 4.1 Architecture Choice 4.2 Database 4.3 Experimental Results 4.4 Discussion 5 Conclusion References Author Index