A Competitive Markov Approach to the Optimal Combat Strategies of On-Line Action Role-Playing Game Using Evolutionary Algorithms

Haoyang Chen, Yasukuni Mori, Ikuo Matsuba

Graduate School of Advanced Integration Science, Chiba University, Chiba, Japan..

DOI: 10.4236/jilsa.2012.43018                

Abstract

In the case of on-line action role-playing game, the combat strategies can be divided into three distinct classes, Strategy of Motion(SM), Strategy of Attacking Occasion (SAO) and Strategy of Using Skill (SUS). In this paper, we analyze such strategies of a basic game model in which the combat is modeled by the discrete competitive Markov decision process. By introducing the chase model and the combat assistant technology, we identify the optimal SM and the optimal SAO, successfully. Also, we propose an evolutionary framework, including integration with competitive coevolution and cooperative coevolution, to search the optimal SUS pair which is regarded as the Nash equilibrium point of the strategy space. Moreover, some experiments are made to demonstrate that the proposed framework has the ability to find the optimal SUS pair. Furthermore, from the results, it is shown that using cooperative coevolutionary algorithm is much more efficient than using simple evolutionary algorithm.

Keywords

Game Design; Game Balance; Competitive Markov Decision Process; Cooperative Coevolutionary Algorithm; Competitive Coevolution

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	H. Y. Chen, Y. Mori and I. Matsuba, “Design Method for Game Balance with Evolutionary Algorithms Using Stochastic Model,” Proceedings of International Conference on Computer Science and Engineering, Shanghai, 28-31 October 2011, Vol. 7, pp. 1-4.
[3]	H. Y. Chen, Y. Mori and I. Matsuba, “Evolutionary Approach to the Balance Problem of On-line Action RolePlaying Game,” Proceedings of the 3rd International Conference on Computational Intelligence and Software Engineering, Wuhan, 9-11 November 2011, pp. 1039-1042.
[4]	J. Filar and K. Vrieze, “Competitive Markov Decision Processes,” Springer-Verlag, New York, 1996. doi:10.1007/978-1-4612-4054-9
[5]	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, July 1991, pp. 264-270.
[6]	M. Potter, “The Design and Analysis of a Computational Model of Cooperative Coevolution,” Ph.D. Dissertation, George Mason University, Fairfax, 1997.
[7]	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 (ICGA), Pittsburgh, 15-19 July 1995, pp. 382-388.
[8]	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-10 August 2001, pp. 1337-1343.
[9]	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
[10]	M. Potter and K. D. Jong, “The Coevolution of Antibodies for Concept Learning,” Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, Amsterdam, 27-30 September 1998, pp. 530-539. doi:10.1007/BFb0056895
[11]	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.
[12]	A. Carlos and S. Moshe, “Fuzzy CoCo: A CooperativeCoevolutionary Approach to Fuzzy Modeling,” IEEE Transactions on Fuzzy Systems, Vol. 9, No. 5, 2001, pp. 727-737. doi:10.1109/91.963759
[13]	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
[14]	M. Potter and K. D. 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, Vol. 866, pp. 249-257. doi:10.1007/3-540-58484-6_269
[15]	M. Potter and K. D. Jong, “Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents,” Evolutionary Computation, Vol. 8, No. 1, 2000, pp. 1-29. doi:10.1162/106365600568086
[16]	R. P. Wiegand, W. Liles and K. D. Jong, “An Empirical Analysis of Collaboration Methods in Cooperative Coevolutionary Algorithms,” Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, 7-11 July 2001, pp. 1235-1242.
[17]	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.
[18]	R. P. Wiegand, “An Analysis of Cooperative Coevolutionary Algorithms,” Ph.D. Dissertation, George Mason University, Fairfax, 2004.
[19]	C. Reeves and J. Rowe, “Genetic Algorithms Principles and Perspectives: A Guide to GA Theory,” Kluwer Academic Publishers, Norwell, 2002.
[20]	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
[21]	M. Vose, “The Simple Genetic Algorithm,” MIT Press, Cambridge, 1999.
[22]	P. Liviu, “Theoretical Convergence Guarantees for Cooperative Coevolutionary Algorithms,” Evolution Computation, Vol. 18, No. 4, 2010, pp. 581-615. doi:10.1162/EVCO_a_00004