[Other] Settled for a futility

After some testing I decided which futility pruning I am going to use. These are the highlights:

• 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.), thanks to Mark Lefler for these ideas
• 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

H.G. Muller pointed out to me that if one non-capture is futile, so is the rest so basically that check could be done before even generating the non-captures. However since Mediocre needs the move to be played on the board in order to determine if it is a checking move I can not do that just yet.

This setup is the best I found, but there does not seem to be a big difference between the implementations I tested. I really like the idea of not pruning moves that are likely to change the score however, and the way it is done here is very simple and effective.

Stumbling upon great things

Once I decided on this matter I went on to some other things, mainly bug fixes and such, but there was one thing that I stumbled upon that really seems to pay off. I wanted a pawn hash table since the pawn structure rarely changes and there is a lot of unnescessary work done in the evaluation.

However the implementation would take quite some work since the zobrist key for the pawns would have to be updated every time a pawn is moving and also the current pawn evaluation uses the king positions as well so that would have to be sorted out.

So I decided to try that later and instead I tried implementing a simple evaluation hash table that keeps track of passed evaluations so if we run into the position again that work does not have to be repeated.

This took about 5 lines of code and speeded up the search a huge amount. It almost feels like I did something wrong since I have read so much about how memory lookups are costly and barely worth it. But Mediocre took another little leap in strength with this change.

I will play a test tournament overnight and if the results are good I think it is worth releasing Mediocre v0.32.