TWO LEARNING ALGORITHMS FOR FORWARD PRUNING

Abstract

The article investigates two learning algorithms for forward pruning. The TS-FPV algorithm uses a tabu-search (TS) algorithm to explore the space of the forward-pruning vectors (FPVs). It focuses on critical FPVs. The RL-FPF algorithm is a reinforcement-learning (RL) algorithm for forward-pruning functions (FPFs). It uses a gradient-descent update rule. The two algorithms are tested using the chess program CRAFTY. The criteria used for evaluation are the size of the search tree and the quality of the move. The experimental results show that the two algorithms are able to tune a forward-pruning scheme that has a better overall performance than a comparable full-width search. The main result arrived at is that the FPFs obtained from RL-FPF outperform the best FPVs resulting from TS-FPV.