Tree Pruning for New Search Techniques in Computer Games

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