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

Socpus ID

84860419133 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84860419133

This document is currently not available here.

Share

COinS