Killer Move Heuristic

[lholmes135]

I've implemented the killer move heuristic in my engine. Most searches have fewer nodes now, but there are at least a couple that take more. For example, this FEN takes more nodes with the killer move heuristic than without:
r1b1qrk1/2p1bppp/p1Np1n2/1p6/4P3/1B6/PPP2PPP/RNBQR1K1 w - - 1 11
I have made sure that it is implemented correctly and my move ordering is as intended. I made sure not to store captures or pawn promotions as killer moves, or to have the same move in both the primary/secondary slot. I did notice that the positions that benefit most from the killer moves are quiet positions, such as the opening and endgame. However, I didn't expect that some middlegame positions would actually be slower. Is this normal? Even when it does decrease nodes (most of the time), it isn't the huge performance gain that I was expecting, but typically like 10-20% less time at depth 8.

My move ordering:
1. Anything from the transposition table at the top
2. Pawn promotions next
3. Capturing the last moved piece
4. Any other captures with a positive SEE value, highest SEEs first
5. The primary killer move
6. Secondary killer move
7. Everything else in no particular order


WITH KILLER MOVES:
ucinewgame
go depth 8
info depth 8 score cp 0 nodes 966348 time 3172 nps 304649 pv e2e4 b8c6 g1f3 g8f6 e4e5 f6g4 d2d4 d7d5

position fen r1b1qrk1/2p1bppp/p1Np1n2/1p6/4P3/1B6/PPP2PPP/RNBQR1K1 w - - 1 11
go depth 8
info depth 8 score cp 440 nodes 5630395 time 22953 nps 245301 pv b3d5 c8g4 f2f3 g4e6 c6e7 e8e7 d5a8 f8a8

W/O KILLER MOVES:
ucinewgame
go depth 8
info depth 8 score cp 0 nodes 1414688 time 4000 nps 353672 pv e2e4 b8c6 g1f3 g8f6 e4e5 f6g4 d2d4 d7d5

position fen r1b1qrk1/2p1bppp/p1Np1n2/1p6/4P3/1B6/PPP2PPP/RNBQR1K1 w - - 1 11
go depth 8
info depth 8 score cp 440 nodes 5248141 time 20313 nps 258363 pv b3d5 c8g4 f2f3 g4e6 c6e7 e8e7 d5a8 f8a8

[alvinypeng]

This is normal. Adding the killer move heuristic does not guarantee less nodes will be searched at a given depth for all positions.

[Tearth]

Also an interesting fact, preventing duplicates in killers table is actually weakening my engine - this is completely counterintuitive for me, as in theory you want to have as many good moves as possible there. Not sure if it's due to some bug, but I've tested it a few times and the result was always the same.