Chess Engines : Pruning

Continuing with this series on Modern Chess Engines, after Advanced Evaluation we saw two high-level topics: 'Alpha-beta pruning' and 'Transposition tables'. Both of these concepts reduce the number of positions that an engine must consider in selecting its next move. Taking the second topic first and again relying on chessprogramming.wikispaces.com for a definition:-

Zobrist Hashing • A technique to transform a board position of arbitrary size into a number of a set length, with an equal distribution over all possible numbers. [...] The main purpose of Zobrist hash codes in chess programming is to get an almost unique index number for any chess position, with a very important requirement that two similar positions generate entirely different indices. These index numbers are used for faster and more space efficient hash tables or databases, e.g. transposition tables and opening books.

Pruning has an analogy in human chess, where a master player knows 'intuitively' which moves in a given position need to be considered and which moves are less important.

Pruning • A name for every heuristic that removes completely certain branches of the search tree, assuming they have no bearing to the search result. Alpha-Beta may be considered as backward pruning, because we found a refutation after searching. Forward pruning always involves some risks to overlook something, with influence on the root score.

A number of distinct pruning techniques have been developed.

Futility Pruning • Discards the moves that have no potential of raising alpha, which in turn requires some estimate of a potential value of a move. This is calculated by adding a futility margin (representing the largest conceivable positional gain) to the evaluation of the current position.

At first I didn't understand what this meant, but found a less technical explanation on rec.games.chess: Futility Cut-offs.

If you are so far behind, and the current move is not a tactical move that might win the material back, you can discard this move as a "futile" move and go to the next one. It does introduce errors.

In other words, if you sacrifice your Queen, don't bother with variations that promise no more than to regain a Pawn. Another pruning technique also has practical application.

Null Move Pruning • A method based on the Null Move Observation to reduce the search space by trying a "null" or "passing" move, then seeing if the score of the subtree search is still high enough to cause a beta cutoff. Nodes are saved by reducing the depth of the subtree under the null move.

I frequently use the null move technique in my own engine work. Skip a move, run the engine on the position (now with the other side to play), and look at the top moves. It's a great way to discover the threat(s) in a position.