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
Killer moves with null move pruning
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Killer moves with null move pruning
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.rbarreira wrote: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
-
- Posts: 1494
- Joined: Thu Mar 30, 2006 2:08 pm
Re: Killer moves with null move pruning
Just a reminder that you need to increment the ply for null moves, otherwise you would end up trying killers for the wrong side.bob wrote: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.rbarreira wrote: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
-
- Posts: 27837
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Killer moves with null move pruning
No.rbarreira wrote: usually people talk about an array indexed by search depth.
-
- Posts: 900
- Joined: Tue Apr 27, 2010 3:48 pm
Re: Killer moves with null move pruning
Thanks a lot guys. That does sound more reasonable...
-
- Posts: 161
- Joined: Thu Jan 08, 2009 9:06 pm
- Location: San Francisco, USA
Re: Killer moves with null move pruning
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.
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.