[Guide] Trying out advanced killer moves and history heuristic

I have been tweaking my killer moves a bit and tried out the history heuristic.

Advanced Killer Moves

Up until now the killer moves have been replaced every time a new cutoff is done. That is alot of mindless replacing.

I am currently trying out a scheme that keeps track of every move on the board if it causes a cutoff, and increments a count each time it does. If any move were to surpass the current primary and secondary killer moves in number of cutoffs, it takes one of their spots. We keep track of this with a three-dimension array like this:

int[][][] everyKiller = new int[100][120][120]

The first dimension is for what ply the killer move exists on, the second is 'fromIndex' and the third is 'toIndex'. Remember that our 0x88 board has indexes from 0 to 120.

Every time a move causes a cutoff we increment its place in the array. So if the move Ra1xa8 caused a cutoff at ply 5 we increment the spot everyKiller[5][0][112] by one.

Then we check if the move has a higher value than either of the current primary or secondary killer moves, if it does we replace one of them with it.

This makes for a more intelliget selection of killer moves. I can not say I noticed any drastic improvement in performance, but I only tested it on a few positions and it did not cost any extra time either. I do think it is for the better however, especially at higher depths when the statistics get a bit more stable.

History Heuristic

The history heuristic is very simple to implement and works similarly to the advanced killer moves. The difference is we do not keep track of what ply the move exists on, or primary/secondary moves.

This is done by using a two-dimension global array that symbolizes all moves. The first dimension is 'fromIndex' and the second 'toIndex'. Like this:

int[][] historyMoves = [120][120]

When a move causes a cutoff in the alpha-beta search we increment its place in the array like this:

historyMoves[move.fromIndex][move.toIndex]++;

The numbers collected in this array are then used to 'award' ordering points in the move sorting. If a move has a high value in the history array it will be searched earlier than a move with a low value.

I have read about engines keeping primary and secondary history moves, but using the values to order all moves seems more logical.

When trying out the history heuristic I did not notice a big difference on lower plies, of course that is not to be expected since the history array is barely filled and the calculation time is so low that we can not expect any vast improvements.

But when I searched 4 different positions to depth 6 the difference was huge. 1 minute 4 seconds with history heuristics turned on, and 2 minutes 3 seconds with it turned off.

It seems the history heuristic is well worth the small trouble.