Computers and Games

Name: Computers and Games | 7th International Conference, CG 2010, Kanazawa, Japan, September 24-26, 2010, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

7th International Conference, CG 2010, Kanazawa, Japan, September 24-26, 2010, Revised Selected Papers

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

Springer (Verlag)

Erschienen am 27. Januar 2011

XVIII, 277 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-17928-0 (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
Solving Hex: Beyond Humans
Introduction
Previous Hex Solving Benchmarks
Current Hex Solving Techniques
Depth-First Proof-Number Search
Improved H-Search
Improved Inferior Cell Analysis
Application of the Strategy-Stealing Argument
Feature Contributions
Hex Solver Scaling
Conclusions
References
Job-Level Proof-Number Search for Connect6
Introduction
Connect6 Applications
Job-Level Proof Number (JL-PN) Search
Proof/Disproof Number Initialization
Node Expansion and Generation
Most Proving Nodes in Parallelism
Experiments
Conclusion
References
Evaluation-Function Based Proof-Number Search
Introduction
Proof-Number Search
PN Search
PN2 Search
Initializing Proof and Disproof Numbers
Alternative Initialization Techniques
Evaluation-Function Based Proof-Number Search
Experiments
Test Environment
Parameter Tuning
Experiments in LOA
Solving 66 LOA
Experiments in Surakarta
Conclusion and Future Research
References
On the Scalability of Parallel UCT
Introduction
Fuego
Methodology
Single-Threaded Scaling
Multi-threaded Scaling
Discussion and Related Work
Conclusion
References
Scalability and Parallelization of Monte-Carlo Tree Search
Introduction
Monte-Carlo Tree Search
Scalability of MCTS
The Limited Scalability by Numbers
Counter-Examples to Scalability
Message-Passing Parallelization
Conclusion
References
Biasing Monte-Carlo Simulations through RAVE Values
Introduction
Monte-Carlo Tree Search
Bandits
Monte-Carlo Tree Search
Rapid Action Value Estimates
PoolRave
Experiments
Havannah
Go
Conclusion
References
Computational Experiments with the RAVE Heuristic
Introduction and Related Work
SOS and the Fuego Framework
Selective False Updates
Lowering Rave Values of Strong Moves
Raising RAVE Values of Weak Moves
RAVE-max: Towards a More Robust RAVE
Results in Go
Joint Distribution and Evolution of Mean and RAVE Values
Conclusion and Future Work
References
Monte-Carlo Simulation Balancing in Practice
Introduction
Description of Algorithms
Softmax Policy
Supervised Learning with MM
Policy-Gradient Simulation Balancing (SB)
Experiments
Erica
Playout Features
Experiment Setting
Influence of Algorithm Meta-parameters
Comparison between MM and SB Feature Weights
Against GNU Go on 99 Board
Playing Strength on 1919 Board
Conclusion
References
Score Bounded Monte-Carlo Tree Search
Introduction
Monte-Carlo Tree Search Solver
Integration of Score Bounds in MCTS
Pessimistic and Optimistic Bounds
Updating the Tree
Pruning Nodes with Alpha-Beta Style Cuts
Bounds Based Node Value Bias
Why Seki and Semeai are Hard for MCTS
Experimental Results
Seki Problems
Connect Four
Conclusion and Future Works
References
Improving Monte-Carlo Tree Search in Havannah
Introduction
WANDERER, an Havannah Playing Program Test Bed
Improving the Basic MCTS Algorithm
Improving the Random Playouts
Recognizing Forced Wins, Losses, and Draws
Initializing Total Playout Count and Win Count
Progressive Widening
The Killer RAVE Heuristic
Results
Remarks
References
Node-Expansion Operators for the UCT Algorithm
Introduction
Monte-Carlo Tree Search and Node Expansion
Expansion Operators
Transition Probability Expansion
Salient Winning Rate Expansion
Visit Count Estimate Expansion
Experiments and Results
Experimental Setup
Results and Discussion
Conclusion and Future Work
References
Monte-Carlo Opening Books for Amazons
Introduction
MCTS Amazons
Monte-Carlo Tree-Search
Specificities of MCTS Amazons
Opening-Books Creation for an MCTS Program
Creating and Using an Opening Book
Best-First
Creating a Best-First Opening Book for an Amazons Program
Using MCTS to Create Opening Books
Creating an Amazons Opening Book with MCTS
Meta Monte-Carlo Tree Search
Adapting Meta-MCTS to Create Opening Books
Experiments and Results
Conclusion and Future Work
References
A Principled Method for Exploiting Opening Books
Introduction
Simple Modifications for ^ V -Algorithms
Mixing Deterministic Opening Books: Fictitious Play and Matrix Games
Experiments
Conclusion
References
A Human-Computer Team Experiment for 9x9 Go
Introduction
The Experiment
Experiment Set-Up
Procedure
Opening Book
The Evolved Experiment
The Current Process
Alternative Approaches
Environment
Time Investment
Results
Examples
Study of a Loss
Komi and Opening Move
Future Research
References
Consultation Algorithm for Computer Shogi: Move Decisions by Majority
Introduction
Creating Two or More Players with Random Numbers
Self-competition with BONANZA
Self-competition with GPS SHOGI
Competition Against Other Programs by Using YSS
Consultation Experiment Using Different Programs
Discussion
Conclusion
References
Optimistic Selection Rule Better Than Majority Voting System
Introduction
Self-play Results of Optimistic and Pessimistic Selections
Optimistic Ensemble System by GPS SHOGI Against BONANZA
Mechanism of Selection in Optimistic Ensemble System
Conclusion
References
Knowledge Abstraction in Chinese Chess Endgame Databases
Introduction
Knowledge in Endgame Databases
The KRKNMM Endgame
Statistical Analysis of the KRKNMM Endgame
Simple Strategies for Reducing the Size of Endgame Databases
Abstracting Knowledge from Endgame Databases
The Scoring Scheme
Goal-Oriented Search Algorithm
Position Induction Algorithm for Winnable Positions
Experiments and Discussions
Definition of Correctness
The Experiment for Drawing Positions
The Experiment for Winnable Positions
Discussions
Conclusions and Future Work
References
Rook Jumping Maze Design Considerations
Introduction
Definitions
History
Generation of Rook Jumping Mazes
Maze Features
Goal Reachability, Reaching States, Reachable States, Black Holes, and White Holes
Start/Goal State Locations
Shortest Solution Uniqueness
Minimum Solution Path Length
Forward/Backward Decisions and Initial Forced Moves
Same Jump Clusters
Example Energy Function
Observations
Algorithm Observations
Diversity of Design
The ``Aha!'' Moment and the Fulfillment of Rule Mastery
Maze Variations
Conclusion
References
A Markovian Process Modeling for Pickomino
Introduction
Game Rules
Markov Modelling
States
Actions
Properties of the Graph
Markovian Decision-Making
Partition of the Space of the Results
Computation of the Families of Probabilities
Decision-Making
Experimental Results
Conclusion and Perspectives
References
New Solutions for Synchronized Domineering
Introduction
Results
Main Theorem
Conclusion
References
The Lattice Structure of Three-Player Games
Introduction
Three-Player Partizan Games
An Example
Relation between G3 and G2
The Lattice Structure of Finite Three-Player Games
References
Enhancements for Multi-Player Monte-Carlo Tree Search
Introduction
Monte-Carlo Tree Search Enhancements
MCTS
Progressive History
Multi-Player MCTS-Solver
Test Domains
Focus
Chinese Checkers
Experiments
Experimental Setup
Progressive History
Multi-Player MCTS-Solver
Conclusions and Future Research
References
Nearly Optimal Computer Play in Multi-player Yahtzee
Introduction
Game Characteristic
Single-player Game
State-Space Analysis
Maximizing Average Score
Maximizing the Probability of Beating a Given Score
Multi-playerGame
Nearly Optimal Multi-player Strategy
Comparison to the Optimal Strategy
Comparison to Other Strategies
Comparison to Human Players
Conclusions and Further Applications
References
Extraversion in Games
Introduction
Methods of Personality Profiling
Motivation
Problem Statement
Outline
Background
The Five Factor Model
The NEO-PI-R
Extraversion
Player Modeling versus Player Profiling
Experimental Setup
In-Game Elements
The Experiment
Results
Extraversion
Control Questions
Conclusions
Future Work
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken