Title
Evolving Neural Networks For Geometric Game-Tree Pruning
Keywords
Checkers; Compositional pattern producing networks; Decision-making domains; Game-trees; Hyper-NEAT; NEAT
Abstract
Game-tree search is the engine behind many computer game opponents. Traditional game-tree search algorithms decide which move to make based on simulating actions, evaluating future board states, and then applying the evaluations to estimate optimal play by all players. Yet the limiting factor of such algorithms is that the search space increases exponentially with the number of actions taken (i.e. the depth of the search). More recent research in game-tree search has revealed that even more important than evaluating future board states is effective pruning of the search space. Accordingly, this paper discusses Geometric Game-Tree Pruning (GGTP), a novel evolutionary method that learns to prune game trees based on geometric properties of the game board. The experiment compares Cake, a minimax-based game-tree search algorithm, with HyperNEAT-Cake, the original Cake algorithm combined with an indirectly encoded, evolved GGTP algorithm. The results show that HyperNEAT-Cake wins significantly more games than regular Cake playing against itself. Copyright 2011 ACM.
Publication Date
8-24-2011
Publication Title
Genetic and Evolutionary Computation Conference, GECCO'11
Number of Pages
379-385
Document Type
Article; Proceedings Paper
Personal Identifier
scopus
DOI Link
https://doi.org/10.1145/2001576.2001629
Copyright Status
Unknown
Socpus ID
84860419133 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/84860419133
STARS Citation
Gauci, Jason and Stanley, Kenneth O., "Evolving Neural Networks For Geometric Game-Tree Pruning" (2011). Scopus Export 2010-2014. 2700.
https://stars.library.ucf.edu/scopus2010/2700