====== Chess - Programming - Futility Pruning ======

At a frontier node (one ply away from quiescence), if the static evaluation plus some margin is less than alpha, proceed straight to quiescence or even return an evaluation immediately.

Works best in combination with lazy evaluation.

Lower margins give a faster - but less accurate - search.

If the margin is larger than the maximum possible score improvement, futility pruning is completely theoretically sound but does not prune anywhere near so many nodes.

The idea of not pruning moves that are likely to change the score is very simple and effective.

----

===== What Futility Pruning Options to use =====

Options include:

  * Use full evaluation and margins 125 centipawns for frontier nodes and 500 for pre-frontier nodes, if the evaluation + margin does not reach alpha the move is considered for futility pruning
  * Consider the type of move.  Do not prune moves that:
    * Give check.
    * Move a pawn/queen/rook to the 7th rank.
    * Capture a bishop so the opponent loses the bishop pair.
    * Capture an pawn on the 2nd or 3rd rank.
    * Capture a queen.

The considerations are taken because these moves are likely to change the score more than average (e.g. moving a pawn to 7th rank will always make it a passed pawn, capturing the queen usually alters the king safety quite a bit etc.).

  * If the move is a capture make sure to add the value of the captured piece to the score and see if it still is below alpha minus the margin.
    If the move still is getting pruned after these considerations a final check is made to see if the evaluation is above the best evaluation of the node, if it is that evaluation is recorded so the node does not risk exiting without any evaluation.

If one non-capture is futile, so is the rest so basically that check could be done before even generating the non-captures.

----

It is worth including captures in the futility.

Try not pruning pawns advancing to the seventh rank or similar, since they will most likely increase the score quite a bit.

----

There is the possibility of all moves in a node fitting the requirements for futility pruning.

----

[[Chess:Programming:Futility Pruning|Futility Pruning]]