Adaptive Null-Move Pruning

Article type: Research Article

Authors: Heinz, E.A.^{; 1}

Affiliations: Karlsruhe, F.R. Germany

Note: [1] Institute for Program Structures and Data Organization (IPD), School of Computer Science, University of Karlsruhe, P.O. Box 6980, D-76128 Karlsruhe, F.R. Germany. Email: heinze@ira.uka.de. WWW=http://wwwipd.ira.uka.de/~heinze/

Abstract: General wisdom deems strong computer-chess programs to be “brute-force searchers” that explore game trees as exhaustively as possible within the given time limits. We review the results of the latest World Computer-Chess Championships and show how grossly wrong this notion actually is. The typical brute-force searchers lost their dominance of the field around 1990 when the null move became popular in microcomputer practice. Today, nearly all world-class chess programs apply various selective forward-pruning schemes with overwhelming success. To this end, we extend standard null-move pruning by a variable depth reduction and introduce what we call adaptive null-move pruning. Quantitative experiments with our chess program DARKTHOUGHT show that adaptive null-move pruning adds a new member to the collection of successful forward-pruning techniques in computer chess. It preserves the tactical strength of DARKTHOUGHT while reducing its search effort by 10 to 30 percent on average in comparison with standard null-move pruning at search depths of 8 to 12 plies. Moreover, adaptive null-move pruning is easy to implement and scales nicely with progressing search depth.

DOI: 10.3233/ICG-1999-22302

Journal: ICGA Journal, vol. 22, no. 3, pp. 123-132, 1999