[Other] Improving the speed

I have been a bit worried about the speed of Mediocre for a while. Obviously I did not expect the speed to increase to lightning velocity just because I added a few simple sorting schemes, but I did expect it to make a bigger difference than it did.

So I have been playing around with a few speed improvements. The ones I got implemented successfully are;

• Aspiration Windows
• Principal Variation Search
• Killer moves heuristic

Among the theoretically 'sound' schemes I have yet to implement are history heuristic, and transposition tables.

I will be looking at pruning techniques as well, such as null-move and futility pruning. The problem with these two is if they are done badly we can miss important lines since we do not check everything, but rather assume we can prune something that 'looks' bad and do not look at it at all. This is not the case with the techniques listed above, since neither of them skip any lines.

Anyway, from the three implemented speed improvements I gained a huge boost to calculation times. Here's an example from a particulary complicated position with many captures and pieces on the board:

Without changes

1 -78 109 43 e4
2 -83 422 344 e4 Nc5
3 -76 2969 9274 Bf3 Nc5 Nc6
4 12 21234 49884 Bf3 Kc8 Nc6 Re8
5 12 125406 620494 Bf3 Kc8 Nc6 Re8 Nxa7
Time to search: 2 minutes 5,422 seconds

With changes

1 -78 110 46 e4
2 -83 219 224 e4 Nc5
3 -76 1313 3215 Bf3 Nc5 Bc6
4 12 3641 12188 Bf3 Kc8 d4 Nxd3
5 12 8532 56290 Bf3 Kc8 Nc6 Re8 Nxa7
Time to search: 8,532 seconds

We gained a staggering 2 minutes! :) Notice how the evaluations and expected lines are exactly the same.

Here are a few short notes about the three additions. I will go through these more thouroughly in my next few posts.

Aspiration Windows made the most noticable difference, and is very easy to implement. Instead of calling alphaBeta with a very low alpha value and a very high beta value, we call it with an expected 'window' based on the previous iteration.

Then comes the killer moves which has more to do with move ordering. Moves that cause beta cutoffs are searched earlier in later searches, since these moves will return high values that enables fast cutoffs from less important lines.

And lastly I am not sure how much of a gain the Principal Varion Search is really, it relies heavily on good move ordering which I do not have (killer moves made it better, but not good). Here we assume the first searched move is the best, and with that assumption we call alphaBeta with a very small window (-alpha-1, -alpha). With that small window we are hoping for the rest of the moves to be below alpha, if they are not we have to call the alphaBeta again with a normal window.

Well just updating you a bit. I will be go through all this more thoroughly later.