Evolving a Ms. PacMan Controller Using Grammatical Evolution
Galvan-Lopez, G., Swafford, J. M., Michael O'Neill and Anthony Brabazon (2010) Evolving a Ms. PacMan Controller Using Grammatical Evolution. 2nd European Workshop on Bio-inspired Algorithms in Games (EvoGames 2010) Istanbul, Turkey, , 07-APR-10 - 09-APR-10
This paper uses genetic programming (GP) to evolve a variety of reactive agents for a simulated version of the classic arcade game Ms. Pac-Man. A diverse set of behaviours were evolved using the same GP setup in three different versions of the game. The results show that GP is able to evolve controllers that are well-matched to the game used for evolution and, in some cases, also generalise well to previously unseen mazes. For comparison purposes, we also designed a controller manually using the same function set as GP. GP was able to significantly outperform this hand-designed controller. The best evolved controllers are competitive with the best reactive controllers reported for this problem.
Lucas, S. and G. Kendall, Evolutionary computation and games. IEEE Computational Intelligence Magazine, 2006. 1(1): p. 10. http://dx.doi.org/10.1109/MCI.2006.1597057
Lucas, S. Evolving a neural network location evaluator to play Ms. Pac-Man. In Proceedings of the IEEE Symposium on Computational Intelligence and Games. 2005. Essex, UK: IEEE.
Cramer, N. A Representation for the adaptive generation of simple sequential programs, Proc. of an Intl. Conf. on Genetic Algorithms and their Applications, Carnegie-Mellon University, July 24-26, 1985.
Koza, J., Genetic programming: on the programming of computers by means of natural selection. 1992, Cambridge, MA: The MIT press.
Gallagher, M. and A. Ryan. Learning to play Pac-Man: An evolutionary, rule-based approach. In The 2003 Congress on Evolutionary Computation. 2003. Piscataway, NJ: IEEE. http://dx.doi.org/10.1109/CEC.2003.1299397
Bonet, J. and C. Stauffer. Learning to play Pac-Man using incremental reinforcement learning. In the Congress on Evolutionary Computation. 1999.
Thompson, J., L. MacMillan, and A. Andrew. An evaluation of the benefits of look-ahead in Ms. Pac-Man. In IEEE Symposium on Computational Intelligence and Games. 2008. Perth, Australia. http://dx.doi.org/10.1109/CIG.2008.5035655
Gallagher, M. and M. Ledwich. Evolving Ms. Pac-Man players: Can we learn from raw input? In IEEE Symposium on Computational Intelligence and Games. 2007: IEEE. http://dx.doi.org/10.1109/CIG.2007.368110
Wirth, N. and M. Gallagher. An influence map model for playing Ms. Pac-Man. In IEEE Symposium on Computational Intelligence and Games (CIG'08). 2008. Perth, Australia: IEEE. http://dx.doi.org/10.1109/CIG.2008.5035644
Robles, D. and S. Lucas. A simple tree search method for playing Ms. Pac-Man. In The IEEE Symposium on Computational Intelligence and Games (cig'09). 2009: IEEE. http://dx.doi.org/10.1109/CIG.2009.5286469
Luke, S. and L. Spector. Evolving teamwork and coordination with genetic programming. In the First Annual Conference on Genetic Programming. 1996: MIT Press.
Wittkamp, M., L. Barone, and P. Hingston. Using NEAT for continuous adaptation and teamwork formation in pacman. In IEEE Symposium on Computational Intelligence and Games. 2008: IEEE. http://dx.doi.org/10.1109/CIG.2008.5035645
Rosca, J. Generality versus size in genetic programming. In the First Annual Conference on Genetic Programming. 1996: MIT Press.
Ohno, T. and H. Ogasawara. Information acquisition model of highly interactive tasks. In ICCS/JCSS. 1999. Charlotte, North Carolina, USA: Association for Information Systems.
DeLooze, L. and W. Viner, Fuzzy q-learning in a nondeterministic environment: eeveloping an intelligent Ms. Pac-Man agent.
Bajurnow, A. and V. Ciesielski. Layered learning for evolving goal scoring behavior in soccer players. In Proceedings of the 2004 Congress on Evolutionary Computation (CEC2004). 2004: IEEE. http://dx.doi.org/10.1109/CEC.2004.1331118
Luke, S., Genetic programming produced competitive soccer softbot teams for RoboCup97. Genetic Programming, 1998: p. 214-222.
Langdon, W. and R. Poli. Evolutionary solo Pong players. In IEEE Congress on Evolutionary Computation. 2005. http://dx.doi.org/10.1109/CEC.2005.1555023
Ebner, M. and T. Tiede. Evolving driving controllers using genetic programming. In IEEE Symposium on Computational Intelligence and Games. 2009: IEEE. http://dx.doi.org/10.1109/CIG.2009.5286465
Montana, D.J., Strongly typed genetic programming, Evolutionary Computation, vol 3, p. 199-230, 1999. http://dx.doi.org/10.1162/evco.19126.96.36.199