[Guide] Futile attempts with futility pruning

In short futility pruning prunes nodes that are so bad that they most likely can not compete with the principal variation.

Names of the depths

Firstly lets get a few terms clear. These are names of different depths in the search.

Root: This is where the first moves for the side to move are generated and searched one by one. If we do a 5 ply search, this will be called depth=5 (since that is what we call alpha-beta with).

Horizon: This is when the depth is reached and we call quiescent search. So we call it depth=0, since that is what we have when quiescent search is called.

Frontier: This is the depth before the horizon. Depth=1.

Futility pruning

Futility pruning is done at the frontier nodes (depth=1). If we are at a frontier node first we call the static evaluation and if that evaluation + a margin (usually the value of a minor piece) is not better than alpha. We know that this node has no chance of beating the alpha even if we search one ply more.

So we return the evaluation (or call quiescent search) and skip the last ply.

We do not want to do this if the last move was a capture or if we are in check or if the next move is a checking move. If any of these cases are true the position is too dynamic to be pruned and we risk missing something important.

Extended futility pruning

Works exactly like futility pruning but is done at pre-frontier nodes (depth=2) and the margin is bigger (atleast the value of a rook).

The margin needs to be bigger since we are pruning 2 plies here and the risk of missing something is much greater.

Razoring

Pretty much like futility pruning, but is done at pre-pre-frontier nodes (depth=3). The margin needs to be about the value of a queen here. And instead of returning the evaluation or calling quiescent search we reduce the search depth with 1 ply.

So we actually do not prune the entire branch but only shorten it a bit.

Problems in Mediocre

I have tried implementing this for hours but I am apparently doing something wrong. The theory is so simple that it should not really be a problem.

I am getting weird results. With some settings I get a decrease in performance, that is the engine takes longer time to reach the search depth. This should not be possible since all we do is remove searches from the tree and I can not see how that would slow down the calculation.

With other settings I get a massive performance improvement, but get extremely weird principal variations. Sometimes the engine does not return a full principal variation line, and sometimes it returns a line with black moves where it should be white.

When trying to play games with these settings the engine blends perfectly good moves with horrible mistakes. So horrible that it can not possibly be the result of a cut ply.

It can take a protected pawn with the queen and in the principal variation expect the queen to be taken, but still evaluate the position as equal.

I am leaning towards letting this go at the moment and start with the hash tables.

But since I am too stubborn for my own good I have a feeling I will keep working on this until I get it to run.