TWO LEARNING ALGORITHMS FOR FORWARD PRUNING

Article type: Research Article

Authors: Kocsis, Levente | van den Herik, H. Jaap | Uiterwijk, Jos W.H.M.¹

Affiliations: Maastricht, The Netherlands

Note: [1] Department of Computer Science, Institute for Knowledge and Agent Technology (IKAT), Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands. Email: {l.kocsis,herik,uiterwijk}@cs.unimaas.nl

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.

DOI: 10.3233/ICG-2003-26303

Journal: ICGA Journal, vol. 26, no. 3, pp. 165-181, 2003