Dynamic Move Chains -- a Forward Pruning Approach to Tree Search in Computer Chess
This addresses the challenge of efficient tree search in computer chess, with potential applications in games with imperfect information, though it appears incremental as it builds on existing pruning techniques.
The paper tackles the problem of pruning search game-trees in computer chess by proposing an algorithm that stores and reuses move sequences from previous searches, which reduces the search space. In tests, it outperformed Transposition Tables in search reduction and gameplay results.
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. This is therefore position independent and so it 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.