All Title Author
Keywords Abstract

Publish in OALib Journal
ISSN: 2333-9721
APC: Only $99


Relative Articles


Tree Pruning for New Search Techniques in Computer Games

DOI: 10.1155/2013/357068

Full-Text   Cite this paper   Add to My Lib


This paper proposes a new mechanism for pruning a search game tree in computer chess. The algorithm stores and then reuses chains or sequences of moves, built up from previous searches. These move sequences have a built-in forward-pruning mechanism that can radically reduce the search space. A typical search process might retrieve a move from a Transposition Table, where the decision of what move to retrieve would be based on the position itself. This algorithm stores move sequences based on what previous sequences were better, or caused cutoffs. The sequence is then returned based on the current move only. This is therefore position independent and could also be useful in games with imperfect information or uncertainty, where the whole situation is not known at any one time. Over a small set of tests, the algorithm was shown to clearly out perform Transposition Tables, both in terms of search reduction and game-play results. Finally, a completely new search process will be suggested for computer chess or games in general. 1. Introduction This paper describes a new way of dynamically linking moves into sequences that can be used to optimise a search process.The context is to optimise the search process for the game of computer chess. Move sequences are returned during the searching of the chess game tree that cause a cutoff, or determine that certain parts of the tree do not need to be searched further. These move sequences are usually stored in Transposition Tables [1, 2], but instead, they can be stored in a dynamic linking structure and reused in the same way. They can return an already evaluated sequence of moves, which removes the need to search the tree structure that would have resulted in this move sequence. The term “chain” instead of “sequence” will be used to describe the new structure specifically. Move sequence is a more general term that can be used to describe any searched move sequence. This research has been carried out using an existing computer chess game-playing program called Chessmaps. The Chessmaps Heuristic [3] was created as part of a DPhil research project that was completed in 1998. The intention was to try and add some intelligence into a chess game-playing program. If the goal is to build the best possible chess program, then the experience-based approach has probably solved the problem already, as the best programs are now better or at least equal to the best human players. Computer chess can also be used, however, simply as a domain for testing AI-related algorithms. It is still an interesting platform for trying to mimic


[1]  J. Schaeffer, “The history heuristic and alpha-beta search enhancements in practice,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 11, pp. 1203–1212, 1989.
[2]  J. Schaeffer and A. Plaat, “New advances in alpha-beta searching,” in Proceedings of the 25th ACM Computer Science Conference, pp. 124–130, February 1996.
[3]  K. Greer, “Computer chess move-ordering schemes using move influence,” Artificial Intelligence, vol. 120, no. 2, pp. 235–250, 2000.
[4]  A. Fernández and A. Salmerón, “BayesChess: a computer chess program based on Bayesian networks,” Pattern Recognition Letters, vol. 29, no. 8, pp. 1154–1159, 2008.
[5]  A. Iqbal, “What computer chess still has to teach us—the game that will not go,” Electronic Journal of Computer Science and Information Technology, vol. 2, no. 1, pp. 23–29, 2010.
[6]  J. Fürnkranz, “Recent advances in machine learning and game playing,” Oesterreichische Gesellschaft fuer Artificial Intelligence Journal, vol. 26, no. 2, pp. 19–28, 2007.
[7]  J. Baxter, A. Tridgell, and L. Weaver, “KnightCap: a chess program that learns by combining TD(lambda) with gametree search,” in Proceedings of the 15th International Conference on Machine Learning, pp. 28–36, 1998.
[8]  S. Thrun, “Learning to play the game of chess,” in Advances in Neural Information Processing Systems 7, G. Tesauro, D. Touretzky, and T. Leen, Eds., Morgen Kaufmann, San Fransisco, Calif, USA, 1995.
[9]  D. B. Fogel, T. J. Hays, S. L. Hahn, and J. Quon, “A self-learning evolutionary chess program,” Proceedings of the IEEE, vol. 92, no. 12, pp. 1947–1954, 2004.
[10]  B. Bonet and H. Geffner, “Learning depth-first search: a unified approach to heuristic search in deterministic and non-deterministic settings, and its application to MDPs,” in Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS'06), D. Long, S. F. Smith, D. Borrajo, and L. Mc-Cluskey, Eds., pp. 142–151, June 2006.
[11]  S. Gelly and D. Silver, “Combining online and offline knowledge in UCT,” in Proceedings of the 24th International Conference on Machine Learning (ICML'07), pp. 273–280, Corvallis, Ore, USA, June 2007.
[12]  Y. Wang and S. Gelly, “Modifications of UCT and sequence-like simulations for Monte-Carlo Go,” in Proceedings of the IEEE Symposium on Computational Intelligence and Games (CIG'07), pp. 175–182, Honolulu, Hawaii, USA, April 2007.
[13]  J. Fürnkranz, “Machine learning in computer chess: the next generation,” The International Computer-Chess Association Journal, vol. 19, no. 3, pp. 147–161, 1995.


comments powered by Disqus

Contact Us


WhatsApp +8615387084133

WeChat 1538708413