In on-line role-playing games (RPG), each race holds some attributes and skills. Each skill contains several abilities such as physical damage, hit rate, etc. Parts of the attributes and all the abilities are a function of the character’s level, which are called Ability-Increasing Functions (AIFs). A well-balanced on-line RPG is characterized by having a set of well-balanced AIFs. In this paper, we propose an evolutionary design method, including integration with an improved Probabilistic Incremental Program Evolution (PIPE) and a Cooperative Coevolutionary Algorithm (CCEA), for on-line RPGs to maintain the game balance. Moreover, we construct a simplest turn-based game model and perform a series of experiments based on it. The results indicate that the proposed method is able to obtain a set of well-balanced AIFs efficiently. They also show that in this case the CCEA outperforms the simple genetic algorithm, and that the capability of PIPE has been significantly improved through the improvement work.
KeywordsGame DesignGame BalanceCooperative Coevolutionary AlgorithmProbabilistic Incremental Program Evolution
A. Rollings and D. Morris, “Game Architecture and Design: A New Edition,” New Readers, Indianapolis, 2004.
E. Adams, “Fundamentals of Game Design,” 2nd Edition, New Readers, Berkeley, 2009.
R. Leigh, J. Schonfeld and S. Louis, “Using Coevolution to Understand and Validate Game Balance in Continuous Games,” Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, Atlanta, 12-16 July 2008, pp. 1563-1570. doi:10.1145/1389095.1389394
J. M. Olsen, “Game Balance and AI Using Payoff Matrices,” In: B. S. Jones and T. Alexander, Eds., Massively Multiplayer Game Development, Charles River Media Inc., Hingham, 2002, pp. 38-48.
J. H. Holland, “Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology,” Control and Artificial Intelligence, MIT Press, Cambridge, 1975.
D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison Wesley, San Francisco, 1989.
N. L. Cramer, “A Representation for the Adaptive Generation of Simple Sequential Programs,” Proceedings of an International Conference on Genetic Algorithms and Their Applications, Pittsburgh, 24-26 July 1985, pp. 183-187.
J. R. Koza, “Genetic Programming—On the Programming of Computers by Means of Natural Selection,” MIT Press, Cambridge, 1992.
R. Poli, W. B. Langdon and N. F. Mcphee, “A Field Guide to Genetic Programming,” Lulu, Morrisville, 2008.
P. Husbands and F. Mill, “Simulated Coevolution as the Mechanism for Emergent Planning and Scheduling,” Proceedings of the 4th International Conference on Genetic Algorithms, San Diego, 13-16 July 1991, pp. 264-270.
M. Potter, “The Design and Analysis of a Computational Model of Cooperative Coevolution,” Ph.D. Thesis, George Mason University, Fairfax, 1997.
L. Bull, T. C. Fogarty and M. Snaith, “Evolution in Multi-Agent Systems: Evolving Communicating Classifier Systems for Gait in a Quadrupedal Robot,” Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, 15-19 July 1995, pp. 382-388.
M. Potter, L. Meeden and A. Schultz, “Heterogeneity in the Coevolved Behaviors of Mobile Robots: The Emergence of Specialists,” Proceedings of the 17th International Conference on Artificial Intelligence, Seattle, 4 August 2001, pp. 1337-1343.
K. S. Hwang, J. L. Lin and H. L. Huang, “Dynamic Patrol Planning in a Cooperative Multi-Robot System,” Communications in Computer and Information Science, Vol. 212, 2011, pp. 116-123. doi:10.1007/978-3-642-23147-6_14
M. Potter and K. De Jong, “The Coevolution of Antibodies for Concept Learning,” Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, Kraków, 11-15 September 1998, pp. 530-539. doi:10.1007/BFb0056895
Y. Wen and H. Xu, “A Cooperative Coevolution-Based Pittsburgh Learning Classifier System Embedded with Memetic Feature Selection,” Proceedings of IEEE Congress on Evolutionary Computation, New Orleans, 5-8 June 2011, pp. 2415-2422.
A. Carlos and S. Moshe, “Fuzzy CoCo: A Cooperative-Coevolutionary Approach to Fuzzy Modeling,” IEEE Transactions on Fuzzy Systems, Vol. 9, No. 5, 2001, pp. 727-737. doi:10.1109/91.963759
R. Chandra and M. Zhang, “Cooperative Coevolution of Elman Recurrent Neural Networks for Chaotic Time Series Prediction,” Neurocomputing, Vol. 86, 2012, pp. 116-123. doi:10.1016/j.neucom.2012.01.014
M. Potter and K. De Jong, “A Cooperative Coevolutionary Approach to Function Optimization,” Proceedings of the 3rd International Conference on Parallel Problem Solving from Nature, Jerusalem, 9-14 October 1994, pp. 249-257. doi:10.1007/3-540-58484-6_269
M. Potter and K. De Jong, “Cooperative Coevolution: An Architecture for Evolving Co-Adapted Subcomponents,” Evolutionary Computation, Vol. 1, No. 8, 2000, pp. 1-29. doi:10.1162/106365600568086
R. P. Wiegand, W. Liles and K. De Jong, “An Empirical Analysis of Collaboration Methods in Cooperative Coevolutionary Algorithms,” Proceedings of the Genetic and Evolutionary Computation Conference, Dublin, 12-16 July 2001, pp. 1235-1242.
T. Jansen and R. P. Wiegand, “Exploring the Explorative Advantage of the CC (1+1) EA,” Proceedings of the Genetic and Evolutionary Computation Conference, Chicago, 12-16 July 2003, pp. 310-321.
R. P. Wiegand, “An Analysis of Cooperative Coevolutionary Algorithms,” Ph.D. Thesis, George Mason University, Fairfax, 2004.
C. Reeves and J. Rowe, “Genetic Algorithms Principles and Perspectives: A Guide to GA Theory,” Kluwer, New York, 2002.
L. Schmitt, “Theory of Genetic Algorithms,” Theoretical Computer Science, Vol. 259, No. 1-2, 2001, pp. 1-61. doi:10.1016/S0304-3975(00)00406-0
M. Vose, “The Simple Genetic Algorithm,” MIT Press, Cambridge, 1999.
P. Liviu, “Theoretical Convergence Guarantees for Cooperative Coevolutionary Algorithms,” Evolution Computation, Vol. 18, No. 4, 2010, pp. 581-615.
R. P. Salustowicz and J. Schmidhuber, “Probabilistic Incremental Program Evolution,” Evolutionary Computation, Vol. 5, No. 2, 1997, pp. 123-141. doi:10.1162/evco.1997.5.2.123
S. Baluja, “Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning,” Technical Report, CMU-CS-94-163, Carnegie Mellon University, Pittsburgh, 1994.
K. De Jong, “An Analysis of the Behavior of a Class of Genetic Adaptive Systems,” Ph.D. Thesis, University of Michigan, Ann Arbor, 1975.
A. Fujino, T. Tobita, K. Segawa, K. Yoneda and A. Togawa, “An Elevator Group Control System with Floor-Attribute Control Method and System Optimization Using Genetic Algorithms,” IEEE Transactions on Industrial Electronics, Vol. 44, No. 4, 1997, pp. 546-552. doi:10.1109/41.605632
K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II,” Evolutionary Computation, Vol. 6, No. 2, 2002, pp. 182-197. doi:10.1109/4235.996017