A Competitive Markov Approach to the Optimal Combat Strategies of On-Line Action Role-Playing Game Using Evolutionary Algorithms
- 1 Graduate School of Advanced Integration Science, Chiba University, Chiba, Japan.
- 2 Graduate School of Advanced Integration Science, Chiba University, Chiba, Japan.
- 3 Graduate School of Advanced Integration Science, Chiba University, Chiba, Japan.
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.
- 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
- 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.
- 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.
- J. Filar and K. Vrieze, “Competitive Markov Decision Processes,” Springer-Verlag, New York, 1996. doi:10.1007/978-1-4612-4054-9
- 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.
- M. Potter, “The Design and Analysis of a Computational Model of Cooperative Coevolution,” Ph.D. Dissertation, 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 (ICGA), 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-10 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. 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
- 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.