AggressiveFutilityPruning

When I implemented multithreading, I was finally able to increase the default search depth of Project Invincible to five plies. I know that it's not great, there is still a lot of room for improvements, but I'm going to leave these improvements for a future release.

However, increasing the search depth actually made the AI weaker. I studied the games and found out that the AI was sacrificing pieces which it expected to get back at leaf nodes. However, often it wasn't able to get the pieces back. For example, in an exceptionally bad test game it sacrificed a knight and predicted that it will be able to take a rook with its queen. The rook was protected by a queen, but the queen was pinned and couldn't protect the rook - except that the pinning piece was the AI's queen, and if it would have taken the rook, the opponent's queen would have become unpinned.

These issues are normally found with Quiescent Search, but I don't have it implemented due to the bad performance of the AI. In addition, my implementation of Static Exchange Evaluation makes some assumptions (such as that the pins won't change) for performance reasons.

I decided to not improve SEE or implement QS. Instead I decided to somehow keep the AI from sacrificing pieces which it expects to get back at leaf nodes, because it often won't get these pieces back if the opponent is strong. (On the other hand, if he/she/it is very weak, PI will win the game anyway.) That leads to a careful playing style.

So, how do I detect a situation where the AI considers sacrificing material and expects to get it back at a leaf node? Quite easily. First, the entire problem can occur only if it is the AI's turn at frontier nodes, i.e. if the number of plies is odd. When the problem occurs, the evaluation score will be bad (for the AI) at a frontier node and good at one of the leaf nodes. Therefore it can be detected like this:

1. At a frontier node, call the evaluation function.
2. If the evaluation function returns a good score, we're done - we haven't sacrificed a piece or we have already got it back.
3. Otherwise, continue searching normally.
4. If any of the leaf nodes is good (has a good score), we have detected the problem. The score mustn't be trusted.

But think about it. If all leaf nodes are bad, we can prune the entire subtree because we know that the move we tried two plies back isn't good. Here we have decided that if the frontier node is bad, we have to assume that all leaf nodes are bad too (otherwise we will sacrifice material that we won't get back). Therefore we can prune immediately if the frontier node turns out to be bad.

Aggressive Futility Pruning (AFP) is very similar with Futility Pruning, but with two significant differences:

• It is only attempted if it's the computer's turn.
• The margin is very low. In Project Invincible, it is 100 points which is equal to half a pawn.

Like normal Futility Pruning, AFP is not tried if the last move was a capture because the taken piece is often protected.

In my tests, AFP made Project Invincible significantly stronger with a fixed depth. Of course it improves performance as well. :)