Adaptive Null-Move Pruning

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.