Killer moves with null move pruning

[rbarreira]

Hi,

I was thinking of implementing the killer heuristic, but I thought of a potential problem which may affect the implementation.

To store the killer moves, usually people talk about an array indexed by search depth. But when doing null-move searches, a given depth may belong to the opposite player compared to regular searches. This means the null searches will be reading and writing from/to the killer moves for the opponent, which means bugs or at least performance problems.

How do people fix this? Just disable the killer heuristic in null move searches, or maybe have another index in the array for the side? (i.e. killer_moves[max_depth][2][n_killers])

Thanks in advance,
RB

[bob]

Hi,

I was thinking of implementing the killer heuristic, but I thought of a potential problem which may affect the implementation.

To store the killer moves, usually people talk about an array indexed by search depth. But when doing null-move searches, a given depth may belong to the opposite player compared to regular searches. This means the null searches will be reading and writing from/to the killer moves for the opponent, which means bugs or at least performance problems.

How do people fix this? Just disable the killer heuristic in null move searches, or maybe have another index in the array for the side? (i.e. killer_moves[max_depth][2][n_killers])

Thanks in advance,
RB

Don't index by depth. Index by ply. That should start at 0/1 and go up one every time you make a move, whether it is a null-move or not.

[mjlef]

Hi,

I was thinking of implementing the killer heuristic, but I thought of a potential problem which may affect the implementation.

To store the killer moves, usually people talk about an array indexed by search depth. But when doing null-move searches, a given depth may belong to the opposite player compared to regular searches. This means the null searches will be reading and writing from/to the killer moves for the opponent, which means bugs or at least performance problems.

How do people fix this? Just disable the killer heuristic in null move searches, or maybe have another index in the array for the side? (i.e. killer_moves[max_depth][2][n_killers])

Thanks in advance,
RB

Don't index by depth. Index by ply. That should start at 0/1 and go up one every time you make a move, whether it is a null-move or not.

Just a reminder that you need to increment the ply for null moves, otherwise you would end up trying killers for the wrong side.

[hgm]

usually people talk about an array indexed by search depth.

No.

[rbarreira]

Thanks a lot guys. That does sound more reasonable...

[vladstamate]

Heh,

I realized I was doing this very mistake in Plisk. Once I fixed it, the new version scores 53.1% over the non-corrected version (not incrementing ply in makeNullMove) after 417 games played.

Regards,
Vlad.