The KIPS Transactions:PartB (정보처리학회논문지B)

Korea Information Processing Society (한국정보처리학회)
권호 표지
DOI QR코드

DOI QR Code

Game Agent Learning with Genetic Programming in Pursuit-Evasion Problem

유전 프로그래밍을 이용한 추격-회피 문제에서의 게임 에이전트 학습

  • 권오광 (성균관대학교 컴퓨터공학부) ;
  • 박종구 (성균관대학교 정보통신공학부)
  • Published : 2008.06.30
Download PDF
⟨ Previous Next ⟩

Abstract

Recently, game players want new game requiring more various tactics and strategies in the complex environment beyond simple and repetitive play. Various artificial intelligence techniques have been suggested to make the game characters learn within this environment, and the recent researches include the neural network and the genetic algorithm. The Genetic programming(GP) has been used in this study for learning strategy of the agent in the pursuit-evasion problem which is used widely in the game theories. The suggested GP algorithm is faster than the existing algorithm such as neural network, it can be understood instinctively, and it has high adaptability since the evolving chromosomes can be transformed to the reasoning rules.

최근의 게임 플레이어들은 단순한 반복적인 조작을 벗어나 복잡한 환경 하에서 다양한 전략과 전술을 구사하여야 하는 게임을 요구하고 있다. 이러한 환경에서 게임 캐릭터를 학습시키기 위해 다양한 인공지능 기법들이 제안되었으며, 최근에는 신경망과 유전 알고리즘을 이용한 학습 방법이 연구되고 있다. 본 논문에서는 게임이론에서 널리 사용되는 추격-회피 전략의 학습을 위해 유전 프로그래밍(GP)을 사용하였다. 제안된 유전 프로그래밍은 신경망과 같은 기존의 방법에 비해 수행 속도가 빠르고, 학습의 결과를 직관적으로 이해할 수 있으며, 진화된 염색체를 추론 규칙으로 변환 가능하므로 호환성이 높다는 장점을 가지고 있다.

Keywords

References

  1. Steve Woodcock, “Game AI: The State of the Industry 2002,” Game Developer Magazine, 2002
  2. Malrey Lee, “Evolution of behaviors in autonomous robot using artificial neural network and genetic algorithm,” Information Sciences, Vol.155, No.1-2, pp.43-60, 2003 https://doi.org/10.1016/S0020-0255(03)00125-7
  3. 조병헌, 정성훈, 성영락, 오하령, “신경망 지능 캐릭터의 게임환경 변화에 대한 적응 방법,” 전자공학회논문지-CI, Vol.42, No.3, pp.17-28, 2005
  4. 박사준, 김성환, 김기태, “인공 유기체의 학습 행동이 게임 캐릭터의 전략에 미치는 영향,” 한국정보과학회 학술발표논문집 2002년도 봄(B), pp.295-297, 2002
  5. 서연규, 조성배, “N명 죄수의 딜레마 게임에서 지역화된 상호작용을 통해 진화된 전략의 일반화 능력,” 한국정보과학회 학술발표논문집 1999년도 봄(B), pp.230-232, 1999
  6. Alireza Soltani, Daeyeol Lee and Xiao-Jing Wang, “Neural mechanism for stochastic behaviour during a competitive game,” Neural Networks, Vol.19, No.8, pp.1075-1090, 2006 https://doi.org/10.1016/j.neunet.2006.05.044
  7. A. L. Nelson, E. Grant and T. C. Henderson, “Evolution of neural controllers for competitive game playing with teams of mobile robots,” Robotics and Autonomous Systems, Vol.46, No.3, pp.135-150, 2004 https://doi.org/10.1016/j.robot.2004.01.001
  8. 황희수, 진화계산 및 진화디자인, 내하출판사, 2002
  9. John R. Koza, Genetic Programming, MIT press, 1992
  10. Geoffrey Miller and Dave Cliff, “Co-evolution of pursuit and evasion I: Biological and game-theoretic foundations,” Technical Report CSRP311, 1994
  11. Stefano Nolfi, Dario Floreano, “Co-evolving predator and prey robots: do 'arm races' arise in artificial evolution,” Artificial Life 4, pp.31-335, 1998 https://doi.org/10.1162/106454698568620
  12. Kam-Chuen Jim, C. Lee Giles, “Talking Helps: Evolving Communicating Agents for the Predator-Prey Pursuit Problem,” Artificial Life 6, pp.237-254, 2000 https://doi.org/10.1162/106454600568861
  13. Hitoshi Iba, “Evolutionary learning of communicating agents,” Information Sciences, Vol.108, No.1-4, pp.181-205, 1997 https://doi.org/10.1016/S0020-0255(97)10055-X
  14. Sreerama K. Murthy, “Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey,” Data Mining and Knowledge Discovery, No 2, pp 345-389, 1997 https://doi.org/10.1023/A:1009744630224
  15. George H. John, Ron Kohavi, Karl Pfleger, “Irrelevant Features and the Subset Selection Problem,” International Conference on Machine Learning, pp.121-129, 1994
  16. John R. Koza, “Concept Formation And Decision Tree Induction Using The Genetic Programming Paradigm,” Parallel Problem Solving from Nature Proceedings of 1st Workshop, PPSN 1, Vol.496, No.1-3, pp.124-128, 1991
  17. Randall S. Sextona, Robert E. Dorseyb and John D. Johnsonb, “Toward global optimization of neural networks: A comparison of the genetic algorithm and backpropagation,” Decision Support Systems, Volume 22, Issue 2, February 1998, pp.171-185 https://doi.org/10.1016/S0167-9236(97)00040-7