Effect of look-ahead depth in evolutionary checkers. (English) Zbl 1279.68300
Summary: 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.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68T05 | Learning and adaptive systems in artificial intelligence |
References:
| [1] | Turing A M. Computing machinery and intelligence. Mind, 1950, 59: 433–460. · doi:10.1093/mind/LIX.236.433 |
| [2] | Samuel A L. Some studies in machine learning using the game of checkers. IBM Journal on Research and Development, 1959, 3(3): 210–229. · doi:10.1147/rd.33.0210 |
| [3] | Newborn M. Kasparov versus Deep Blue. Computer Chess Comes of Age. New York: Springer-Verlag, 1996. |
| [4] | Campbell M, Hoane Jr. A J, Hsu F H. Deep blue. Artificial Intelligence, 2002, 134(1-2): 57–83. · Zbl 0982.68122 · doi:10.1016/S0004-3702(01)00129-1 |
| [5] | Schaeffer J. One Jump Ahead: Computer Perfection at Checkers (2nd edition). New York: Springer, 2009. · Zbl 1156.68049 |
| [6] | Sastry K, Goldberg D, Kendall G. Chapter 4: Genetic algorithms. In Search Methodologies: Introductory Tutorials in Optimization 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 Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Burke E K, Kendall G (eds.), Springer, 2005, pp.127–164. |
| [8] | Fausett L V. Fundamentals of Neural Networks: Architectures, Algorithms and Applications, Prentice Hall, 1993. · Zbl 0828.68107 |
| [9] | Yao X. Evolving artificial neural networks. Proc. the IEEE, 1999, 87(9): 1423–1447. · doi:10.1109/5.784219 |
| [10] | Jong K A D. Evolutionary Computation: A Unified Approach. Cambridge, USA: MIT Press, 2006. · Zbl 1106.68093 |
| [11] | Eiben A E, Smith J E. Introduction to Evolutionary Computing (1st edition). Springer, 2003. · Zbl 1028.68022 |
| [12] | Fogel D B. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (3rd edition). Piscataway, USA: IEEE Press, 1995. · Zbl 0926.68052 |
| [13] | Michalewicz Z, Fogel D. How to Solve It: Modern Heuristics. Springer-Verlag, 2000. · Zbl 0943.90002 |
| [14] | Fogel D B. Blondie24: Playing at the Edge of AI. San Francisco, USA: Morgan Kaufmann Publishers, 2002. |
| [15] | Fogel D B, Hays T J, Hahn S L, Quon J. A self-learning evolutionary chess program. Proceeding of the IEEE, 2004, 92(12): 1947–1954. · doi:10.1109/JPROC.2004.837633 |
| [16] | Fogel D B, Hays T J, Hahn S L, Quon J. Further evolution of a self-learning chess program. In Proc. the IEEE 2005 Symposium on Computational Intelligence & Games, April 2005, pp.73–77. |
| [17] | Fogel D B, Hays T J, Hahn S L, Quon J. The Blondie25 chess program competes against Fritz 8.0 and a human chess master. In Proc. the IEEE 2006 Symposium on Computational Intelligence and Games, May 2006, pp.230–235. |
| [18] | Al-Khateeb B, Kendall G. The importance of look-ahead depth in evolutionary checkers. In Proc. the 2011 IEEE Congress on Evolutionary Computation, June 2011, pp.2252–2258. |
| [19] | Chellapilla K, Fogel D B. Anaconda defeats Hoyle 6-0: A case study competing an evolved checkers program against commercially available software. In Proc. the 2000 Congress on 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. · doi:10.1109/5.784222 |
| [21] | Chellapilla K, Fogel D B. Evolving an expert checkers playing program without using human expertise. IEEE Transactions on Evolutionary Computation, 2001, 5(4): 422–428. · doi:10.1109/4235.942536 |
| [22] | Chellapilla K, Fogel D B. Evolving neural networks to play checkers without relying on expert knowledge. IEEE Transactions on Neural Networks, 1999, 10(6): 1382–1391. · doi:10.1109/72.809083 |
| [23] | Kendal G, Shaw S. Investigation of an adaptive cribbage player. In Proc. the 3rd International Conference on Computers and Games, July 2002, pp.29–41. |
| [24] | Cai X, Venayagamoorthy G K, Wunsch D C II. Evolutionary swarm neural network game engine for capture go. Neural Networks, 2010, 23(2): 295–305. · doi:10.1016/j.neunet.2009.11.001 |
| [25] | Binner J M, Gazely A M, Kendall G. An evaluation of UK risky money: An artificial intelligence approach. Global Business and Economics Review, 2009, 11(1): 1–18. · doi:10.1504/GBER.2009.025378 |
| [26] | Kendall G, Su Y. Imperfect evolutionary systems. IEEE Transactions on Evolutionary computation, 2007, 11 (3): 294–307. · doi:10.1109/TEVC.2006.887348 |
| [27] | Cameron B B, Powley E, Whitehouse D, Lucas S M, Cowling P I, Rohlfshagen P, Tavener S, Perez D, Samothrakis S, Colton S. A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(1): 1–43. · doi:10.1109/TCIAIG.2012.2186810 |
| [28] | Samuel A L. Some studies in machine learning using the game of checkers II: Recent progress. IBM Journal on Research and Development, 1967, 11(6): 601–617. · doi:10.1147/rd.116.0601 |
| [29] | Kaelbling L P, Littman M L, Moore A W. Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 1996, 4: 237–285. |
| [30] | Sutton R S, Barto A G. Reinforcement Learning: An Introduction. Cambridge, USA: MIT Press, 1998. |
| [31] | Vrakas D, Vlahavas I P L. Artificial Intelligence for Advanced Problem Solving Techniques. Hershey, USA: Information Science 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. · JFM 54.0543.02 · doi:10.1007/BF01448847 |
| [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 world man-machine checkers champion. AI Magazine, 1996, 17(1): 21–30. |
| [36] | Russell S, Norvig P. Artificial Intelligence: A Modern Approach (3rd edition). Prentice Hall, 2009. · Zbl 0835.68093 |
| [37] | Schaeffer J, Culberson J C, Treloar N, Knight B, Lu P, Szafron D. A world championship caliber checkers program. Artificial Intelligence, 1992, 53(2/3): 273–289. · doi:10.1016/0004-3702(92)90074-8 |
| [38] | Fogel D B. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (2nd edition). USA: Wiley-IEEE Press, 2000. · Zbl 0926.68052 |
| [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. · Zbl 1226.00005 |
| [40] | Fogel D B, Chellapilla K. Verifying anaconda’s expert rating by competing against Chinook: Experiments in co-evolving a neural checkers player. Neurocomputing, 2002, 42(1-4): 69–86. · Zbl 1002.68709 · doi:10.1016/S0925-2312(01)00594-X |
| [41] | Al-Khateeb B, Kendall G. Introducing a round robin tournament into Blondie24. In Proc. the IEEE 2009 Symposium on Computational Intelligence and Games, Sept. 2009, pp.112–116. |
| [42] | Levene M, Fenner T I. The effect of mobility on minimaxing of game trees with random leaf values. Artificial Intelligence, 2001, 130(1): 1–26. · Zbl 0992.68165 · doi:10.1016/S0004-3702(01)00072-8 |
| [43] | Nau D S, Luštrek M, Parker A, Bratko I, Gams M. When is it better not to look ahead?. Artificial Intelligence, 2010, 174(16-17): 1323–1338. · Zbl 1237.91047 · doi:10.1016/j.artint.2010.08.002 |
| [44] | Smet P, Calbert G, Scholz J, Gossink D, Kwok H-W,Webb M. The effects of material, tempo and search depth on win-loss ratios in chess. In Proc. the 16th Australian Conf. Artificial Intelligence, Dec. 2003, pp.501–510. · Zbl 1205.91047 |
| [45] | Bettadapur P, Marsland T A. Accuracy and savings in depth-limited capture search. International Journal of Man-Machine Studies, 1988, 29(5): 497–502. · doi:10.1016/S0020-7373(88)80008-7 |
| [46] | Runarsson T P, Jonsson E O. Effect of look-ahead search depth in learning position evaluation functions for Othello using {\(\epsilon\)}-greedy exploration. In Proc. the IEEE 2007 Symposium 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 difference feature to Blondie24. In Proc. the 10th Annual Workshop on Computational Intelligence, Sept. 2010, pp.1–6. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
