AEL PRUNING¹

Article type: Research Article

Authors: Heinz, Ernst A.^{; 2}

Affiliations: Cambridge, USA

Note: [1] This article is an extended version of the identically titled Chapter 3 from our book “Scalable Search in Computer Chess” (Heinz, 2000). We thank the publisher Vieweg Verlag for their kind permission to reprint large parts of the chapter herein.

Note: [2] M.I.T. Laboratory for Computer Science (Room NE 43 - 228), Massachussetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, USA. Email: heinz@mit.edu. WWW = http://supertech.lcs.mit.edu/~heinz/

Abstract: In the past, we introduced the new forward-pruning techniques adaptive null-move pruning (A), extended futility pruning (E), and limited razoring (L). Since they differ substantially in nature, it remained unclear how well they combine and which level of effectiveness their combination achieves. Based on the names of the three building blocks, we call the combined scheme AEL pruning. As it turns out, AEL pruning clearly belongs to the collection of practically successful forward-pruning techniques in computer chess. AEL pruning is easy and efficient to implement. Extensive experiments with 2180 test positions from well-known tactical test suites show that AEL pruning fully preserves the tactical strength of our chess program DARKTHOUGHT while reducing its search effort by 20 to 50 percent on average at fixed iteration depths of 8 to 12 plies. The reduction in search effort scales as well with search depth as that for any of the three techniques alone. The positive results of 580 test games (self-play and versus other strong chess programs) provide further empirical evidence for the practical usefulness of AEL pruning

DOI: 10.3233/ICG-2000-23104

Journal: ICGA Journal, vol. 23, no. 1, pp. 21-32, 2000