The Realization of Genetic Algorithm in Terms of Checkers Evaluation Function

Abstract:

The GA(Genetic Algorithm) is used in this paper to solve the evaluation problem in the checkers game. The evaluation parameter is chosen based on six critical facts, such as the number of black pieces and the number of red pieces. The evaluation function is linear with different weights. Using the weights as the chromosome, along with the local hill-climbing method in GA and the mathematical statistical method to choose child generation, the algorithm realizes evolution automatically. With sufficient evolution times, new chromosome appears, leading to the formation of an optimized evaluation function. Based on the experimental data analysis, the algorithm could enhance the power of checkers program effectively.

• Periodical: Applied Mechanics and Materials (Volumes 411-414)
• Pages: 1979-1985
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.411-414.1979
• Online since: September 2013
• Authors: Zhe Su, Shu Qin Li, Yun Lu Jia, Li Wei Zheng, Si Cong Fan
• Keywords: Checkers, Evaluation Function, Game Theory, Genetic Algorithm (GA)

References

[1] Xiaochun Wang. PC Game Programming [M]. Chongqing: Chongqing University Press. 2002: 1-27. (in Chinese).

[2] George F. Luger. Artificial Intelligence-Structures and Strategies for Complex Problem Solving [M]. The 4 edition. Beijing: Mechanical Industry Press, 2004: 101-131. (in Chinese).

[3] Mitsuo Gen, Runwei Cheng. Genetic Algorithms and Engineering Optimization[M]. Xinjie Yu, Gengui Zhou, translation. Beijing: Tsinghua University Press, 2004: 1-40. (in Chinese).

[4] Holland J H. In Yovirs M.C. Eds. Self-Organizing Systems. 1962: 215—230.

[5] Holland J H. Adaptation in nature and artificial system[M]. Ann Arbor: The University of Michigan Press, (1975).

[6] Yangsen Zhang, Gaijuan Zhang. Artificial Intelligence Course [M]. Beijing: Higher Education Press. 2008: 322-327. (in Chinese).

[7] Lorenz D, Markovitch S. Derivative evaluation function learning using genetic operators. Proc of the AAAI Fall Symposium on Games. New Carolina: AAAI Press, 1993: 106 - 114.

[8] Jiao Wang, Tao Wang, Yanhong Luo, Xinhe Xu. Journal of Northeastern University. 2005, 26(10): 949-951. (in Chinese).

[9] Tom M. Mitchell. Machine learning[M]. USA: The McGraw-Hill Companies. 1997: 1-19.

[10] Yen S J, Chen J C, Yang T N. ICG A Journal, 2004, (3): 3- 18.

[11] Sutton R S. Machine Learning, 1988, 3(1): 9-44.

[12] Guo Li. Journal of Southwestern University. 2007, 29(11): 138-142. (in Chinese).