CFP last date
22 April 2024
Reseach Article

Functional Buildup in Board Game Positional Composition through Evolutionary Genetic Mechanism

Published on February 2012 by Dharm Singh, Chirag S. Thaker, J. S. Shah
Optimization and On-chip Communication
Foundation of Computer Science USA
OOC - Number 1
February 2012
Authors: Dharm Singh, Chirag S. Thaker, J. S. Shah
2614a90e-9e0c-49ee-8e51-762b7ac1d111

Dharm Singh, Chirag S. Thaker, J. S. Shah . Functional Buildup in Board Game Positional Composition through Evolutionary Genetic Mechanism. Optimization and On-chip Communication. OOC, 1 (February 2012), 18-22.

@article{
author = { Dharm Singh, Chirag S. Thaker, J. S. Shah },
title = { Functional Buildup in Board Game Positional Composition through Evolutionary Genetic Mechanism },
journal = { Optimization and On-chip Communication },
issue_date = { February 2012 },
volume = { OOC },
number = { 1 },
month = { February },
year = { 2012 },
issn = 0975-8887,
pages = { 18-22 },
numpages = 5,
url = { /specialissues/ooc/number1/5466-1004/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Special Issue Article
%1 Optimization and On-chip Communication
%A Dharm Singh
%A Chirag S. Thaker
%A J. S. Shah
%T Functional Buildup in Board Game Positional Composition through Evolutionary Genetic Mechanism
%J Optimization and On-chip Communication
%@ 0975-8887
%V OOC
%N 1
%P 18-22
%D 2012
%I International Journal of Computer Applications
Abstract

Board games are very simple games and easy to learn. It has simple rules to move dice or discs. Though they are simple to learn, differences in experiences, skills and strategies make master-level players and naive players. To teach these properties to machine is a daunting task. Researchers attempt to develop evolutionary game player who like humans needs time to start the board game and will improve its performance at each passing game. Evolutionary algorithms simulate this learning procedure and genetic approach helps to find diverse fitter players. With respect to checkers, the evolutionary algorithm was able to discover genetic algorithm that can be used to optimize the move selection in play to near-expert level. Evolutionary approach develops machine player that generates solutions which does not often dominates in the last generation. In real world board game problems, diversity is very useful which can be attained by having a number of machine learning algorithms.This paper highlights, evolutionary genetic algorithm to improve the diversity of a population. From the last generation, representative checkers player fitness values are chosen to carry them to next generation from each species(population member) and combine them in current generation to play the checkers game. There are many high fitness solutions in a search space. Fitness selection techniques can find diverse strategies that survive in genetic search. In this paper, diverse evolutionary checkers players found by such techniques are combined. The evolved move of game player is compared with the fittest player evolved using a simple evolutionary algorithm.

References
  1. D. B. Fogel, “Evolutionary entertainment with intelligent agents,” IEEE Comput., vol. 36, no. 6, pp. 106–108, Jun. 2003.
  2. P. Godefroid and S. Khurshid, “Exploring very large state spaces using genetic algorithms,” Int. J. Softw. Tools Technol. Transf., vol. 6, no. 2, pp. 117–127, 2004.
  3. E. Alba, F. Chicano, M. Ferreira, and J. A. Gmez-Pulido,“Finding deadlocks in large concurrent Java programs using genetic algorithms,” in Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation (GECCO’08). ACM, 2008, pp. 1735–1742.
  4. E. Alba and F. Chicano, “Ant colony optimization for model checking,” in Proceedings of the 11th International Conference
  5. on Computer Aided Systems Theory (EUROCAST 2007), vol. 4739. Springer, 2007, pp. 523–530.
  6. “Genetic programming and model checking: Synthesizing new mutual exclusion algorithms,” in Proceedings of the
  7. 6th International Symposium on Automated Technology for Verification and Analysis (ATVA ’08), vol. 5311. Springer, 2008, pp. 33–47.
  8. C. Johnson, “Genetic programming with fitness based on model checking,” in Proceedings of the 10th European Conference on Genetic Programming (EuroGP 2007), vol. 4445. Springer, 2007, pp. 114–124.
  9. 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.
  10. Barone, L., While, L.: Adaptive learning for poker. In: Proceedings of the Genetic and Evolutionary Computation Conference. (2000) 566{573
  11. Fogel, D., Hays, T., Hahn, S., Quon, J.: A self-learning evolutionary chess program. Proceedings of the IEEE 92 (2004) 1947{1954
  12. P. Aksenov. Genetic algorithms for optimising chess position scoring. Master’s Thesis, University of Joensuu, Finland, 2004.
  13. Y. Bjornsson and T.A. Marsland. Multi-cut alpha-beta-pruning in game-tree search. Theoretical Computer Science, 252(1-2):177–196, 2001.
  14. 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.
  15. R. Gross, K. Albrecht, W. Kantschik, and W.Banzhaf. Evolving chess playing programs. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 740–747. Morgan Kaufmann Publishers, New York, 2002.
  16. Barone, L., While, L.: An adaptive learning model for simpli¯ed poker using evolutionary algorithms. In: Proceedings of the Congress of Evolutionary Computation (GECCO-1999). (1999) 153{160
  17. Chellapilla K. and Fogel D. B.:Evolving an Expert Checkers PlayingProgram without Using Human Expertise.IEEE Trans. Evolutionary Computation,Volume 5, Number 4, 2001, pp. 422-428.
  18. Hauptman and M. Sipper. Using genetic programming to evolve chess endgame players. In Proceedings of the 2005 European Conference on Genetic Programming, pages 120–131. Springer, Lausanne, Switzerland, 2005.
  19. Chellapilla K. and Fogel D. B.:Anaconda Defeats Hoyle 6-0A CaseStudy Competing an Evolved CheckersProgram against Commercially Available Software. Proc. of CEC, 2000, pp. 857-863.
  20. Galuszka A. and Swierniak A.: Game Theoretic Approach to Multi-Robot Planning. WSEAS Transactions onComputers, Issue 3, Volume 3, July 2004, pp. 537-542.
  21. D.N. Allsopp, et al. Coalition agents experiment: multiagent cooperation in international coalitions, IEEE Intell. Syst. 17 (2002) 26–35.
  22. G. Kendall and C. Smith, “The evolution of blackjack strategies,” in Proc. Congr. Evol. Comput., vol. 4, 2003, pp. 2474–2481.
  23. M. Harman, “The current state and future of search based software engineering,” in Proceedings of International Conference on Software Engineering / Future of Software Engineering 2007 (ICSE/FOSE ’07). IEEE Computer Society,2007, pp. 342–357.
  24. Y. Jin, Knowledge Incorporation in Evolutionary Computation. New York: Springer-Verlag, 2004.
  25. K.-J. Kim and S.-B. Cho, “Evolving speciated checkers players with crowding algorithm,” in Proc. Congr. Evol. Comput., vol. 1, 2002, pp.407–412.
  26. Handbook of Evolutionary Computation, Oxford Univ. Press, London, U.K., 1997. C6.1 S. W. Mahfoud Niching methods.
  27. Dharm Singh, Thaker Chirag S and Shah Sanjay M. “Multimedia Game Based Fitness Function Optimization in Evolutionary Search Process” in IJCA Special Issue on IP Multimedia Communication in October 2011 ISBN:978-93-80864-99-3.
  28. “Evolving an expert checkers playing program without using human expertise,” IEEE Trans. Evol. Comput., vol. 5, no. 4, pp. 422–428, Aug. 2001.
  29. D. B. Fogel, “Evolving a checkers player without relying on human experience,” ACM Intell., vol. 11, no. 2, pp. 20–27, 2000.
Index Terms

Computer Science
Information Sciences

Keywords

Board Game Evolutionary Algorithm Game of Checkers Evaluation Function Genetic Algorithm