Jason Gauci
ABSTRACT
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.
- P. J. Bentley and S. Kumar. Three ways to grow designs: A comparison of embryogenies for an evolutionary design problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), pages 35--43, 1999.Google Scholar
- J. C. Bongard. Evolving modular genetic regulatory networks. In Proceedings of the 2002 Congress on Evolutionary Computation, 2002. Google ScholarDigital Library
- J. Burmeister and J. Wiles. The challenge of Go as a domain for AI research: A comparison between go and chess. In Proceedings of the Third Australian and New Zealand Conference on Intelligent Information Systems. IEEE Western Australia Section, pages 181--186, 1995.Google ScholarCross Ref
- D. D'Ambrosio and K. O. Stanley. A novel generative encoding for exploiting neural network sensor and output geometry. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007), New York, NY, 2007. ACM Press. Google ScholarDigital Library
- D. B. D'Ambrosio and K. O. Stanley. Generative encoding for multiagent learning. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008), New York, NY, 2008. ACM Press. Google ScholarDigital Library
- A. Dewdney. New Turing Omnibus. WH Freeman & Co. New York, NY, USA, 1993. Google ScholarDigital Library
- M. Fierz. Simplech. http://arton.cunst.net/xcheckers/, 2002.Google Scholar
- M. Fierz. Cake checkers engine. http://www.fierz.ch/cake.php, 2008.Google Scholar
- D. B. Fogel. Blondie24: Playing at the Edge of AI. 2002. Google ScholarDigital Library
- J. Gauci and K. O. Stanley. Generating large-scale neural networks through discovering geometric regularities. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007), New York, NY, 2007. ACM Press. Google ScholarDigital Library
- J. Gauci and K. O. Stanley. A case study on the critical role of geometric regularity in machine learning. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-2008), Menlo Park, CA, 2008. AAAI Press. Google ScholarDigital Library
- J. Gauci and K. O. Stanley. Autonomous evolution of topographic regularities in artificial neural networks. Neural Computation, 22(7):1860--1898, 2010. To appear. Google ScholarDigital Library
- J. Gauci and K. O. Stanley. Indirect Encoding of Neural Networks for Scalable Go. pages 354--363, 2010. Google ScholarDigital Library
- S. Gelly and D. Silver. Combining online and offline learning in UCT. In 17th International Conference on Machine Learning, pages 273--280, 2007. Google ScholarDigital Library
- S. Gelly and D. Silver. Achieving master level play in 9 x 9 computer go. In D. Fox and C. P. Gomes, editors, AAAI, pages 1537--1540. AAAI Press, 2008. Google ScholarDigital Library
- G. S. Hornby and J. B. Pollack. Creating high-level components with a generative representation for body-brain evolution. Artificial Life, 8(3), 2002. Google ScholarDigital Library
- D. Knuth and R. Moore. An analysis of alpha-beta pruning. Artificial Intelligence, 6(4):293--326, 1975.Google ScholarCross Ref
- C.-P. P. Lu. Parallel search of narrow game trees. PhD thesis, 1993.Google Scholar
- S. Russell, P. Norvig, J. Canny, J. Malik, and D. Edwards. Artificial intelligence: a modern approach. Prentice hall Englewood Cliffs, NJ, 1995. Google ScholarDigital Library
- K. O. Stanley. Compositional pattern producing networks: A novel abstraction of development. Genetic Programming and Evolvable Machines Special Issue on Developmental Systems, 8(2):131--162, 2007. Google ScholarDigital Library
- K. O. Stanley, D. B. D'Ambrosio, and J. Gauci. A hypercube-based indirect encoding for evolving large-scale neural networks. Artificial Life, 15(2):185--212, 2009. Google ScholarDigital Library
- K. O. Stanley and R. Miikkulainen. Continual coevolution through complexification. In Genetic and Evolutionary Computation Conference, 2002. Google ScholarDigital Library
- K. O. Stanley and R. Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10:99--127, 2002. Google ScholarDigital Library
- K. O. Stanley and R. Miikkulainen. A taxonomy for artificial embryogeny. Artificial Life, 9(2):93--130, 2003. Google ScholarDigital Library
- K. O. Stanley and R. Miikkulainen. Evolving a roving eye for Go. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), Berlin, 2004. Springer Verlag.Google ScholarCross Ref
- X. Yao. Evolving artificial neural networks. Proceedings of the IEEE, 87(9):1423--1447, 1999.Google ScholarCross Ref
Index Terms
- Evolving neural networks for geometric game-tree pruning
Recommendations
Evolving Game NPCs Based on Concurrent Evolutionary Neural Networks
Edutainment '08: Proceedings of the 3rd international conference on Technologies for E-Learning and Digital EntertainmentEvolutionary Artificial Neural Networks (EANNs) has been highly effective in Artificial Intelligence (AI) and in training Non-Player-Characters (NPCs) in video games. An important question in training NPCs in games is how we can choose the appropriate ...
Evolving explicit opponent models in game playing
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computationOpponent models are necessary in games where the game state is only partially known to the player, since the player must infer the state of the game based on the opponents actions. This paper presents an architecture and a process for developing neural ...
A Draughts Learning System Based on Neural Networks and Temporal Differences: The Impact of an Efficient Tree-Search Algorithm
SBIA '08: Proceedings of the 19th Brazilian Symposium on Artificial Intelligence: Advances in Artificial IntelligenceThe NeuroDraughts is a good automatic draughts player which uses temporal difference learning to adjust the weights of an artificial neural network whose role is to estimate how much the board state represented in its input layer by NET-FEATUREMAP is ...
Comments