Computer Games: Workshop on Computer Games, CGW 2013, Held in Conjunction with the 23rd International Conference on Artificial Intelligence, IJCAI ... Computer and Information Science, Band 408)

Description

This book constitutes the refereed proceedings of the Computer Games Workshop, CGW 2013, held in Beijing, China, in August 2013, in conjunction with the Twenty-third International Conference on Artificial Intelligence, IJCAI 2013. The 9 revised full papers presented were carefully reviewed and selected from 15 submissions. The papers cover a wide range of topics related to computer games. They discuss six games that are played by humans in practice: Chess, Domineering, Chinese Checkers, Go, Goofspiel, and Tzaar. Moreover, there are papers about the Sliding Tile Puzzle, an application, namely, Cooperative Path-Finding Problems, and on general game playing. Preface Organization Contents Monte-Carlo Fork Search for Cooperative Path-Finding 1 Introduction 2 CPF Problem Definition 3 Related Work 3.1 Cooperative Path-Finding 3.2 MCTS 4 MCFS 4.1 Similarities and Differences with MCTS 4.2 MCFS and NMCFS Algorithms 4.3 Basic Simulations 4.4 Pre and Post Processing 5 Experiments 5.1 Set of Problems 5.2 Experimental Settings 5.3 Results 6 Discussion 7 Conclusion References Building Large Compressed PDBs for the Sliding Tile Puzzle 1 Introduction 2 Background 3 Pattern Databases 3.1 Additive Pattern Databases 4 Building Compressed PDBs 4.1 Sequential Algorithm 4.2 Parallel Algorithm 5 Evaluation 5.1 Statistical Evaluation 5.2 Empirical Evaluation 6 Conclusion References Monte Carlo Tree Search in Simultaneous Move Games with Applications to Goofspiel 1 Introduction 1.1 Related Work 2 Simultaneous Move Games 3 Simultaneous Move Monte Carlo Tree Search 3.1 Decoupled UCT 3.2 Exp3 3.3 Regret Matching 3.4 Online Outcome Sampling 4 Empirical Evaluation 4.1 Goofspiel 4.2 Head-to-Head Performance 4.3 Exploitability and Convergence 5 Conclusion and Future Work References Decision Trees for Computer Go Features 1 Introduction 2 Background 2.1 The Game of Go 2.2 Go Features for Monte-Carlo Tree Search 2.3 The Generalized Bradley-Terry Model and Training Weights 2.4 Graphs for Go 2.5 Decision Trees 3 Decision Trees as Features 3.1 Overview 3.2 Structure 3.3 Learning 4 Experiments and Results 4.1 Overview 4.2 Move Prediction 4.3 Playing Strength 5 Conclusions and Future Work A Multiple Decision Tree Descent Paths References UCT Enhancements in Chinese Checkers Using an Endgame Database 1 Introduction 2 Background 2.1 Minimax Algorithm 2.2 UCT Algorithm 2.3 Chinese Checkers 2.4 Endgame Databases 3 Lookup Table 4 Proposed Experiments 4.1 -Players 4.2 UCT Players 5 Experiment Results and Analysis 5.1 Depth-Based Trials 5.2 Sample Based Trials 5.3 Time Based Trials 6 Conclusions and Further Work References Automated Generation of New Concepts from General Game Playing 1 Introduction 2 Method 3 Automated Generation of Heuristic Functions from Simulations 4 Automated Generation of New Concepts for Games from Heuristic Functions 5 Applying Automated Generated Concepts to Games 6 Automated Generation of Ternary Concepts from Binary Concepts 7 Discussion 8 Conclusions References WALTZ: A Strong Tzaar-Playing Program 1 Introduction 1.1 Tzaar Rules 1.2 Strategies 1.3 Game Properties 2 Algorithms for Tzaar 2.1 Evaluation Function 2.2 Heuristic Weak PNS 3 Experiments with Waltz 3.1 DFPN versus Alpha-beta in Endgames 4 Results Against Computer and Human Opponents 5 Further Work References Perfectly Solving Domineering Boards 1 Introduction 2 Characteristics of Domineering 2.1 Move Types 2.2 Board Parameters 2.3 Move-Type Characteristics 3 Perfectly Solving Domineering 3.1 Level-1 Rules 3.2 Level-2 Rules 3.3 Level-3 Rules 3.4 Level-4 Rules 3.5 Level-5 Rules 3.6 Level-6 Rules 4 Results 4.1 Level-1 and Level-2 Results 4.2 Level-3 Results 4.3 Level-4 Results 4.4 Level-5 Results 4.5 Level-6 Results 4.6 Summary of Results up to 10 10 4.7 Summary of Results up to 30 30 5 Discussion 5.1 Discussion of Results 5.2 Correctness of Results 5.3 Winning Strategy 6 Some General Theorems 7 Conclusions 8 Future Research A Appendix References How Relevant Are Chess Composition Conventions? Abstract 1 Introduction 2 Methodology 3 Experimental Setups and Results 3.1 Conventions and Aesthetics 3.2 Human Judge Ratings and Aesthetics 4 Discussion 5 Conclusions Acknowledgement References Author Index http://avaxhm.com/blogs/ChrisRedfield