Advances in Computer Games

Name: Advances in Computer Games | 13th International Conference, ACG 2011, Tilburg, The Netherlands, November 20-22, 2011, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

13th International Conference, ACG 2011, Tilburg, The Netherlands, November 20-22, 2011, Revised Selected Papers

H. Jaap van den Herik Aske Plaat(Herausgeber*in)

Springer (Verlag)

Erschienen am 18. Juli 2012

XXII, 358 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-31866-5 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title
Preface
Organization
Table of Contents
Accelerated UCT and Its Application to Two-Player Games
Introduction
Drawback of UCT
Related Work
Accelerated UCT
Experiments
Implementation Details
Setup
Performance Comparison of the Plain, Discounted, and Accelerated UCT Algorithms
Performance Comparison with RAVE in Go
Concluding Remarks
References
Revisiting Move Groups in Monte-Carlo Tree Search
Introduction
The Upper Confidence Bounds Algorithm
Research Questions
Experimental Framework
Experiments and Results
Baseline Group Performance
Groups Study in Difficult Move Selection
Grouping in Games with Large Branching Factor
Measuring Group Performance with Regret
Introducing Move Groups and Using Prior Knowledge
Conclusions and Potential Applications
References
PACHI: State of the Art Open Source Go Program
Introduction
Experimental Setup
The Pachi Framework
Monte Carlo Tree Search
Prior Values
Playouts
MCTS Extensions
Time Control
Dynamic Komi
Criticality
Parallelization
Shared Memory Parallelization
Cluster Parallelization
Overall Performance
Conclusion
References
Time Management for Monte-Carlo Tree Search in Go
Introduction
Time Management
Time-Management Strategies
Semi-dynamic Strategies
Dynamic Strategies
Experimental Results
ERICA-BASELINE
Semi-dynamic Strategies
Dynamic Strategies
Strength Comparisons
Conclusion and Future Research
References
An MCTS Program to Play EinStein Würfelt Nicht!
Introduction
ONESTONE, an EWN Playing Program Test Bed
The Road to UCT
MCTS Improvements
EWN Variants
Results
Remarks
References
Monte-Carlo Tree Search Enhancements for Havannah
Introduction
The Rules of Havannah
Havannah and Monte-Carlo Tree Search
MCTS Refinements for Havannah
Enhancing the Play-out Step in MCTS
Enhancing the Selection Step in MCTS
Experiments
Experimental Setup
Last-Good-Reply
N-grams
Initializing Visit and Win Count
Conclusions and Future Research
References
Playout Search for Monte-Carlo Tree Search in Multi-player Games
Introduction
Monte-Carlo Tree Search
Playout Search
Search Techniques
Search Enhancements
Test Domains
Focus
Chinese Checkers
Domain Knowledge
Experiments
Experimental Setup
Results
Conclusions and Future Research
References
Towards a Solution of 7x7 Go with Meta-MCTS
Introduction
Technical Points
Monte-Carlo Tree Search (MCTS)
Meta-MCTS
Scoring Functions Used in Our Meta-MCTS
Existing Handcrafted 7x7 Openings
Experimental Results of Meta-MCTS Before Modifications by Human Expertise
Games against Humans
Introduction of Human Expertise in the Grid-Based Learning
Conclusion
References
MCTS Experiments on the Voronoi Game
Introduction
Voronoi Game
MCTS, UCT, UCB, and RAVE
Light Gaussian Processes
MCTS Experiments without Knowledge
Calibration Experiments
UCT, RAVE, and Light GP Experiments
MCTS Experiments with Knowledge
The Last Move Special Case
Simple Attacks on Unbalanced Cells and the Biggest Cell Attack
Balance
BUCT: A UCT Player Following Balanced VD in the Simulations
aBUCT: A BUCT Player Using Simple Attacks in the Simulations
The One-Round Game and the Second Player Strategy 1R2P
ABUCT: A BUCT Player Using Sophisticated Attacks in the Tree
Against Human Players and against Other Work
Conclusion
References
4*4-Pattern and Bayesian Learning in Monte-Carlo Go*
Introduction
Motivation
The 3*3-Pattern Background
Possibility of 4*4-Patterns
Operations of a 4*4 Pattern
Classification of the 4*4 Patterns
Compression
4*4-Pattern Library
Coding Sequence and Lookup Table
Program Codes for Querying
Bayesian Learning of 4*4-Pattern
Bayesian Pattern Learning Model
The Improvement of Learning Procedure
Experiments
Bayesian 4*4-Pattern Learning Experiments
Effectiveness Experiments
Conclusion and Future Work
References
Temporal Difference Learning for Connect6
Introduction
Connect6 and NCTU6
TD Learning for Connect6
TD Learning
TDLeaf and Bootstrapping
Our TD Learning
Implementation Issues
Feature Selection
Threat Space Search
Learning from the Games Played by Strong Human Players
Experiments
Experimental Environment
Stages
Threat Space Search
Training Games
Discussion
Conclusion
References
Improving Temporal Difference Learning Performance in Backgammon Variants
Introduction
Plakoto
Fevga
Complexity Compared to Standard Backgammon
Updating the Temporal Difference in Games
Determining the Target of the Update
Sequence Creation and How to Update
Experimental Results
Results in the Plakoto and Fevga Variants
Feature Selection
Related Work
Conclusion and Future Work
References
CLOP: Confident Local Optimization for Noisy Black-Box Parameter Tuning
Introduction
Problem Definition
Noisy Optimization
Using Response-Surface Models
Algorithm
Detailed Algorithm Description
Choice of H and Asymptotic Rate of Convergence
Experiments
Effect of Meta-parameter H
Comparison with Other Algorithms
Conclusion
References
Analysis of Evaluation-Function Learning by Comparison of Sibling Nodes
Introduction
Related Work
Learning by Comparison of Moves
Objective Function to Be Minimized
Partial Gradient of the Objective Function
Maximum Change in v(n,) w.r.t. :
Partial Subgradient of v(n,):
Practical Issues:
Experimental Results
Game of Shogi and Shogi Programs
Existence of Partial Derivative
Effectiveness of Gradient Descent
Concluding Remarks
References
Approximating Optimal Dudo Play with Fixed-Strategy Iteration Counterfactual Regret Minimization
Introduction
The Game of Dudo
Imperfect Recall and Counterfactual Regret Minimization
Imperfect Recall of Actions
Counterfactual Regret Minimization
Fixed-Strategy Iteration CFR
Experimental Results
Learning Outperformance
Computational Time Per Training Iteration
Varying Imperfect Action Recall
Conclusion
References
The Global Landscape of Objective Functions for the Optimization of Shogi Piece Values with a Game-Tree Search
Introduction
Two-Dimensional Landscape of the Loss Function
Full Optimization of Shogi Piece Values
Conclusions
References
Solving breakthrough with Race Patterns and Job-Level Proof Number Search
Introduction
Job-Level Proof Number Search
Proof Number Search
Job-Level Parallelization
Parallel PN2
breakthrough and Race Patterns
Rules of breakthrough
Retrograde Analysis for Small Boards
Race Patterns
Experimental Results
Scalability
Partial Results Updates
Patterns
Discussion and Conclusion
References
Infinite Connect-Four Is Solved: Draw
Introduction
Previous Work
Solution of Infinite Connect-Four
Solution of Variants of Infinite Connect-Four
Placing Rules
Height Limit
Width Limit
Conclusion
References
Blunder Cost in Go and Hex
Introduction
A Simple Model of Two-Player No-Draw Games
Blunder Analysis of Fuego
99 Go
Go on Other Board Sizes
Blunder Analysis of MoHex
1111 Hex
77 Hex and Available-Winning-Move Rate
99 Hex and Playing Strength
Conclusions
References
Understanding Distributions of Chess Performances
Introduction
Ratings and Distributions
Population Statistics
Average Error and Results by Tournament Categories
Intrinsic Ratings over Time
Distributions of Performances
Conclusions
References
Position Criticality in Chess Endgames
Introduction
Scenarios and Questions to Be Considered
The Main Scenario: The Win Study
Supplementary Scenarios
The Algorithm: A Generic Response to the Scenarios
Generating Chess(SP) EGTs: Examples and Efficiencies
The First Implementation of the Algorithm: Starchess
Summary
References
On Board-Filling Games with Random-Turn Order and Monte Carlo Perfectness
Introduction
The Basic Result for Board-Filling Games
Examples and Generalisations
The Random-Turn Game OdOku
The Game TOP FOUR
SAT Games with Random Turn Order
Strange Games Related to Mathematical Problems
(p,q,r,s)-Generalisation
Generalisations of the Game Class
Conclusions and Open Questions
References
Modeling Games with the Help of Quantified Integer Linear Programs
Introduction
The Problem Statement: Quantified Linear Programs
Problem Statement
Solutions of QIPs and QLPs: Strategies and Policies
Modeling with QIPs
A Two-Person Zero-Sum Graph Game
Gomoku
Conclusion
References
Computing Strong Game-Theoretic Strategies in Jotto
Introduction
Jotto
A Natural Approach
Game Theory Background
Strategic-Form Games
Extensive-Form Games
Mixed vs. Behavioral Strategies
Nash Equilibria
Smoothed Fictitious Play
Oracular Strategies
Computing Best Responses in Jotto
Computing the Guesser's Greedy Best Response
Computing the Hider's Best Response
Parallelizing the Best Response Calculation
Computing an Approximate Equilibrium in Jotto
Results
Conclusion
References
Online Sparse Bandit for Card Games
Introduction
Algorithms for Sparse Bandits
Matrix Games and Nash Equilibria
EXP3 Algorithm
Sparse EXP3 Bandits
Computational Results
Generated Squared Matrix Games
Generated General Matrix Games
Application to UrbanRivals
Conclusion
References
Game Tree Search with Adaptive Resolution
Introduction
Notations and Algorithm
Theoretical Analysis
Experiments
Experiments
Experimental Settings for Random Trees
Experimental Results and Analysis of Random Trees
Experimental Setting for Real Game Trees
Conclusions
References
Designing Casanova: A Language for Games
Introduction
Background
AModel forGames
The Casanova Language
Design Goals
A Brief Introduction to Casanova
Syntax, Semantics, and Types
Introductory Example
Optimization
A Full Example
Case Study
Rewriting the Game
Resulting Benchmarks
Conclusions
References
Affective Game Dialogues
Introduction
Affect in Game Dialogue Systems
Evaluation
Measurement Tool
Procedure
Results
Discussion and Outlook
References
Generating Believable Virtual Characters Using Behavior Capture and Hidden Markov Models
Introduction
Related Work
Capturing Behaviors
Training in Neverwinter Nights
Behavior Types
Generating Behaviors
Character and Object Generalization
Sequence Generalization
User-Study and Evaluation
User-Study
Preliminary User-Study
Results
Conclusion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken