Call for Paper - July 2022 Edition
IJCA solicits original research papers for the July 2022 Edition. Last date of manuscript submission is June 20, 2022. Read More

Optimization of Fitness Function through Evolutionary Game Learning

Print
PDF
Evolution in Networks and Computer Communications
© 2011 by IJCA Journal
Number 3 - Article 2
Year of Publication: 2011
Authors:
Sanjay M Shah
Dharm Singh
Chirag S Thaker

Abstract

Game playing has been one of the main areas of application of Artificial intelligence and programs are often described as being a combination of search and knowledge. The Board Games are very popular due to their nature provide dynamic environments that make them ideal area of computational intelligence theories, architectures, and algorithms. For almost all the board games building a quality evaluation function is usually a challenging work and requires lot of manual hard work and luck. The quality of the evaluation function is determined by its accuracy, relevance, cost and outcome. Good evaluation function must address all these parameters and then the weighed results are added to an evaluation function experimentally. Almost all board games have very large state space. Due to this nature of board games, evolutionary algorithms such as Genetic algorithm are applied to the game playing. In natural evolution, the fitness of an individual is defined with respect to its competitors and collaborators, as well as to the environment. Evolutionary algorithms follow the same path to evolve game playing programs. Go-moku (Five-in-Line), the board game, is a variant of a Game of GO. This paper mainly highlights application of genetic algorithm to Go-moku and using genetic operators tries to find out fitness values through linear evaluation function applying genetic operators through linear evaluation function.

Reference

  1. Hong, J.-H. and Cho, S.-B. (2004). Evolution of emergent behaviors for shooting game characters in robocode. In Evolutionary Computation, 2004. CEC2004. Congress on Evolutionary Computation, volume 1, pages 634–638, Piscataway, NJ. IEEE.
  2. J. Clune. Heuristic evaluation functions for general game playing. In Proc. of AAAI, 1134–1139, 2007.
  3. Shah Sanjay M , Singh Dharm, Thaker Chirag S. Multimedia Based Fitness Function Optimization Through Evolutionary Game Learning
  4. J¨org Denzinger, Kevin Loose, Darryl Gates, and John Buchanan. Dealing with parameterized actions in behavior testing of commercial computer games. In Proceedings of the IEEE 2005 Symposium on Computational Intelligence and Games (CIG), pages 37–43, 2005.
  5. Matt Gilgenbach. Fun game AI design for beginners. In Steve Rabin, editor, AI Game Programming Wisdom 3, 2006.
  6. S. Schiffel and M. Thielscher. A multiagent semantics for the game description language. In Proc. of the Int.’l Conf. on Agents and Artificial Intelligence, Porto 2009. Springer LNCS.
  7. T. Srinivasan, P.J.S. Srikanth, K. Praveen and L. Harish Subramaniam, “AI Game Playing Approach for Fast Processor Allocation in Hypercube Systems using Veitch diagram (AIPA)”, IADIS International Conference on Applied Computing 2005, vol. 1, Feb. 2005, pp. 65-72.
  8. Thomas P. Runarsson and Simon M. Lucas. Co-evolution versus self-play temporal difference learning for acquiring position evaluation in small-board go. IEEE Transactions on Evolutionary Computation, 9:628 – 640, 2005.
  9. Yannakakis, G., Levine, J., and Hallam, J. (2004). An evolutionary approach for interactive computer games. In Evolutionary Computation, 2004. CEC2004. Congress on Evolutionary Computation, volume 1, pages 986–993, Piscataway, NJ. IEEE.
  10. A. Hauptman and M. Sipper. Evolution of an efficient search algorithm for the Mate-in-N problem in chess. In Proceedings of the 2007 European Conference on Genetic Programming, pages 78–89. Springer, Valencia, Spain, 2007.
  11. P. Aksenov. Genetic algorithms for optimising chess position scoring. Master’s Thesis, University of Joensuu, Finland, 2004. Y. Bjornsson and T.A. Marsland. Multi-cut alpha-beta-pruning in game-tree search. Theoretical Computer Science, 252(1-2):177–196, 2001.
  12. O. David-Tabibi, A. Felner, and N.S. Netanyahu. Blockage detection in pawn endings. Computers and Games CG 2004, eds. H.J. van den Herik, Y. Bjornsson, and N.S. Netanyahu, pages 187–201. Springer-Verlag, 2006.
  13. A. Hauptman and M. Sipper. Using genetic programming to evolve chess endgame players. In Proceedings of the 2005 European Conference onGenetic Programming, pages 120–131. Springer, Lausanne, Switzerland, 2005.
  14. G. Kendall and G. Whitwell. An evolutionary approach for the tuning of a chess evaluation function using population dynamics. In Proceedings of the 2001 Congress on Evolutionary Computation, pages 995–1002. IEEE Press, World Trade Center, Seoul, Korea, 2001.
  15. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. Ann Arbor, MI: University of Michigan Press.
  16. Goldberg, D. E. (1989). Genetic Algorithms in Search,Optimization and and Machine Learning. Reading, MA: Addison-Wesley.
  17. Buckles Bill P. and Petry, Frederick E. Genetic Algorithms. Los Alamitos, CA: The IEEE Computer Society Press. 1992.
  18. Haupt, Randy L, and Haupt, Sue Ellen. (1998). Practical Genetic Algorithms. New York: John wiley & Sons
  19. L.V. Allis,H.J. van den Herik ,M.P.H. Huntjens. Go-Moku and Threat Space Search.
  20. Sanjay Shah, Dharm Singh, Chirag S. Thaker, Multimedia Based Fitness Function Optimization Through Evolutionary Game Learning., 2011 ETNCC, pp 164-168, IEEE Catalog Number CFP1196N-CDR , ISBN 978-1-4577-0238-9 and IEEE Catalog Number CFP1196N-ART , ISBN 978-1-4577-0240-2.