›› 2012, Vol. 27 ›› Issue (5): 996-1006.doi: 10.1007/s11390-012-1280-6

• Special Issue on Evolutionary Computation • Previous Articles     Next Articles

Effect of Look-Ahead Depth in Evolutionary Checkers

Belal Al-Khateeb1 and Graham Kendall2, Senior Member, IEEE   

  1. 1. College of Computer, Al-Anbar University, Ramadi, Iraq;
    2. School of Computer Science, The University of Nottingham, Nottingham, U.K.
  • Received:2011-08-30 Revised:2012-07-13 Online:2012-09-05 Published:2012-09-05

It is intuitive that allowing a deeper search into a game tree will result in a superior player to one that is restricted in the depth of the search that it is allowed to make. Of course, searching deeper into the tree comes at increased computational cost and this is one of the trade-offs that has to be considered in developing a tree-based search algorithm. There has been some discussion as to whether the evaluation function, or the depth of the search, is the main contributory factor in the performance of an evolved checkers player. Some previous research has investigated this question (on Chess and Othello), with differing conclusions. This suggests that different games have different emphases, with respect to these two factors. This paper provides the evidence for evolutionary checkers, and shows that the look-ahead depth (like Chess, perhaps unsurprisingly) is important. This is the first time that such an intensive study has been carried out for evolutionary checkers and given the evidence provided for Chess and Othello this is an important study that provides the evidence for another game. We arrived at our conclusion by evolving various checkers players at different ply depths and by playing them against one another, again at different ply depths. This was combined with the two-move ballot (enabling more games against the evolved players to take place) which provides strong evidence that depth of the look-ahead is important for evolved checkers players.

[1] Turing A M. Computing machinery and intelligence. Mind,1950, 59: 433-460.
[2] Samuel A L. Some studies in machine learning using the gameof checkers. IBM Journal on Research and Development,1959, 3(3): 210-229.
[3] Newborn M. Kasparov versus Deep Blue. Computer ChessComes of Age. New York: Springer-Verlag, 1996.
[4] Campbell M, Hoane Jr. A J, Hsu F H. Deep blue. ArtificialIntelligence, 2002, 134(1-2): 57-83.
[5] Schaeffer J. One Jump Ahead: Computer Perfection atCheckers (2nd edition). New York: Springer, 2009.
[6] Sastry K, Goldberg D, Kendall G. Chapter 4: Genetic algo-rithms. In Search Methodologies: Introductory Tutorials inOptimization and Decision Support Techniques, Burke E K,Kendall G (eds.), Springer, 2005, pp.97-125.
[7] Koza J, Poli R. Chapter 5: Genetic programming. In SearchMethodologies: Introductory Tutorials in Optimization andDecision Support Techniques, Burke E K, Kendall G (eds.),Springer, 2005, pp.127-164.
[8] Fausett L V. Fundamentals of Neural Networks: Architec-tures, Algorithms and Applications, Prentice Hall, 1993.
[9] Yao X. Evolving artificial neural networks. Proc. the IEEE,1999, 87(9): 1423-1447.
[10] Jong K A D. Evolutionary Computation: A Unified Ap-proach. Cambridge, USA: MIT Press, 2006.
[11] Eiben A E, Smith J E. Introduction to Evolutionary Com-puting (1st edition). Springer, 2003.
[12] Fogel D B. Evolutionary Computation: Toward a New Philos-ophy of Machine Intelligence (3rd edition). Piscataway, USA:IEEE Press, 1995.
[13] Michalewicz Z, Fogel D. How to Solve It: Modern Heuristics.Springer-Verlag, 2000.
[14] Fogel D B. Blondie24: Playing at the Edge of AI. San Fran-cisco, USA: Morgan Kaufmann Publishers, 2002.
[15] Fogel D B, Hays T J, Hahn S L, Quon J. A self-learning evolu-tionary chess program. Proceeding of the IEEE, 2004, 92(12):1947-1954.
[16] Fogel D B, Hays T J, Hahn S L, Quon J. Further evolution ofa self-learning chess program. In Proc. the IEEE 2005 Sym-posium on Computational Intelligence & Games, April 2005,pp.73-77.
[17] Fogel D B, Hays T J, Hahn S L, Quon J. The Blondie25 chessprogram competes against Fritz 8.0 and a human chess mas-ter. In Proc. the IEEE 2006 Symposium on ComputationalIntelligence and Games, May 2006, pp.230-235.
[18] Al-Khateeb B, Kendall G. The importance of look-aheaddepth in evolutionary checkers. In Proc. the 2011 IEEECongress on Evolutionary Computation, June 2011, pp.2252-2258.
[19] Chellapilla K, Fogel D B. Anaconda defeats Hoyle 6-0: Acase study competing an evolved checkers program againstcommercially available software. In Proc. the 2000 Congresson Evolutionary Computation, July 2000, 2: 857-863.
[20] Chellapilla K, Fogel D B. Evolution, neural networks, games,and intelligence. Proceedings of the IEEE, 1999, 87(9): 1471-1496.
[21] Chellapilla K, Fogel D B. Evolving an expert checkers playingprogram without using human expertise. IEEE Transactionson Evolutionary Computation, 2001, 5(4): 422-428.
[22] Chellapilla K, Fogel D B. Evolving neural networks to playcheckers without relying on expert knowledge. IEEE Trans-actions on Neural Networks, 1999, 10(6): 1382-1391.
[23] Kendal G, Shaw S. Investigation of an adaptive cribbageplayer. In Proc. the 3rd International Conference on Com-puters and Games, July 2002, pp.29-41.
[24] Cai X, Venayagamoorthy G K, Wunsch D C II. Evolutionaryswarm neural network game engine for capture go. NeuralNetworks, 2010, 23(2): 295-305.
[25] Binner J M, Gazely A M, Kendall G. An evaluation of UKrisky money: An artificial intelligence approach. Global Busi-ness and Economics Review, 2009, 11(1): 1-18.
[26] Kendall G, Su Y. Imperfect evolutionary systems. IEEETransactions on Evolutionary computation, 2007, 11 (3): 294-307.
[27] Cameron B B, Powley E, Whitehouse D, Lucas S M, Cowl-ing P I, Rohlfshagen P, Tavener S, Perez D, SamothrakisS, Colton S. A survey of Monte Carlo tree search methods.IEEE Transactions on Computational Intelligence and AI inGames, 2012, 4(1): 1-43.
[28] Samuel A L. Some studies in machine learning using the gameof checkers II: Recent progress. IBM Journal on Research andDevelopment, 1967, 11(6): 601-617.
[29] Kaelbling L P, Littman M L, Moore A W. Reinforcementlearning: A survey. Journal of Artificial Intelligence Re-search, 1996, 4: 237-285.
[30] Sutton R S, Barto A G. Reinforcement Learning: An Intro-duction. Cambridge, USA: MIT Press, 1998.
[31] Vrakas D, Vlahavas I P L. Artificial Intelligence for AdvancedProblem Solving Techniques. Hershey, USA: Information Sci-ence Reference, 2008.
[32] Mitchell T M. Machine Learning. McGraw-Hill, 1997.
[33] Von Neumann J. Zur Theorie der Gesellschaftsspiele. Math.Annalen, 1928, 100(1): 295-320.
[34] Edwards D J, Hart T P. The Alpha-Beta Heuristic (AIM-030). Massachusetts Institute of Technology, 1963, http://dspace.mit.edu/handle/1721.1/6098.
[35] Schaeffer J, Lake R, Lu P, Bryant M. Chinook: The worldman-machine checkers champion. AI Magazine, 1996, 17(1):21-30.
[36] Russell S, Norvig P. Artificial Intelligence: A Modern Ap-proach (3rd edition). Prentice Hall, 2009.
[37] Schaeffer J, Culberson J C, Treloar N, Knight B, Lu P, SzafronD. A world championship caliber checkers program. ArtificialIntelligence, 1992, 53(2/3): 273-289.
[38] Fogel D B. Evolutionary Computation: Toward a New Philos-ophy of Machine Intelligence (2nd edition). USA: Wiley-IEEEPress, 2000.
[39] Schaeffer J, Burch N, Björnsson Y, Kishimoto A, Müller M,Lake R, Lu P, Sutphen S. Checkers is solved. Science Express,2007, 317(5844): 1518-1522.
[40] Fogel D B, Chellapilla K. Verifying anaconda's expert ratingby competing against Chinook: Experiments in co-evolving aneural checkers player. Neurocomputing, 2002, 42(1-4): 69-86.
[41] Al-Khateeb B, Kendall G. Introducing a round robin tourna-ment into Blondie24. In Proc. the IEEE 2009 Symposium onComputational Intelligence and Games, Sept. 2009, pp.112-116.
[42] Levene M, Fenner T I. The effect of mobility on minimaxingof game trees with random leaf values. Artificial Intelligence,2001, 130(1): 1-26.
[43] Nau D S, Lu穝trek M, Parker A, Bratko I, Gams M. Whenis it better not to look ahead?. Artificial Intelligence, 2010,174(16-17): 1323-1338.
[44] Smet P, Calbert G, Scholz J, Gossink D, Kwok H-W,Webb M.The effects of material, tempo and search depth on win-lossratios in chess. In Proc. the 16th Australian Conf. ArtificialIntelligence, Dec. 2003, pp.501-510.
[45] Bettadapur P, Marsland T A. Accuracy and savings indepth-limited capture search. International Journal of Man-Machine Studies, 1988, 29(5): 497-502.
[46] Runarsson T P, Jonsson E O. Effect of look-ahead searchdepth in learning position evaluation functions for Othellousing "-greedy exploration. In Proc. the IEEE 2007 Sympo-sium on Computational Intelligence and Games, April 2007,pp.210-215.
[47] Hughes E J. Piece difference: Simple to evolve. In Proc.the 2003 Congress on Evolutionary Computation, Dec. 2003,pp.2470-2473.
[48] Al-Khateeb B, Kendall G. The importance of a piece differ-ence feature to Blondie24. In Proc. the 10th Annual Work-shop on Computational Intelligence, Sept. 2010, pp.1-6.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Wang Hui; Liu Dayou; Wang Yafei;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[2] Peng Chenglian;. Combining Gprof and Event-Driven Monitoring for Analyzing Distributed Programs:A Rough View of NCSA Mosaic[J]. , 1996, 11(4): 427 -432 .
[3] Zhang Chenghong; Hu Yunfa; Shi Baile;. A Reasoning Mechanism for DeductiveObject-Oriented Databases[J]. , 1997, 12(4): 337 -345 .
[4] Ju-Hum Kwon, Chee-Yang Song, Chang-Joo Moon, and Doo-Kwon Baik. Bridging Real World Semantics to Model World Semantics for Taxonomy Based Knowledge Representation System[J]. , 2005, 20(3): 296 -308 .
[5] Bo Yan, You-Xing Qu, Feng-Lou Mao, Victor N. Olman, and Ying Xu. PRIME: A Mass Spectrum Data Mining Tool for De Novo Sequencing and PTMs Identification[J]. , 2005, 20(4): 483 -490 .
[6] Pierre Bourque, Serge Oligny, Alain Abran, and Bertrand Fournier. Developing Project Duration Models in Software Engineering[J]. , 2007, 22(3): 348 -357 .
[7] Li-Guo Yu and Srini Ramaswamy. Component Dependency in Object-Oriented Software[J]. , 2007, 22(3): 379 -386 .
[8] Ji-Gang Wu, Thambipillai Srikanthan, and Guang-Wei Zou. New Model and Algorithm for Hardware/Software Partitioning[J]. , 2008, 23(4 ): 644 -651 .
[9] Hai-Bin Zhang and Zhen-Hua Duan, Senior Member, CCF, IEEE. Symbolic Algorithmic Analysis of Rectangular Hybrid Systems[J]. , 2009, 24(3): 534 -543 .
[10] Wai-Ho Mak (麦伟豪), Yingcai Wu (巫英才), Ming-Yuen Chan (陈明远), and Huamin Qu (屈华民), Member, IEEE. Visibility-Aware Direct Volume Rendering[J]. , 2011, 26(2): 217 -228 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved