bob wrote: ↑Tue Aug 06, 2019 6:34 am
I remember when Dave Slate wrote the first paper I saw on this topic. He gave a position where black was on move, and white had the move Nxc7+ forking the black king and rook. As black tries different moves, almost ALL are refuted by the same move, Nxc7. Except for say Rac8 and Kd8 or Kd7 or even Kf8 to avoid the check. This is an example where clearing killers at ply+1 actually hurts significantly. And over the years it seems to me that while killers are pretty local, If you clear killers ply+1 before searching at ply, then the above won't happen, but back up two plies where white plays Nb5 and then Nxc7+ Black has to stop either Nb5 or Nxc7. Which are killer moves for most black replies. Zeroing ply+1 would at the very least wipe out the Nxc7+ move over and over whenever white plays Nb5. If he doesn't, that move is not legal and has no negative effect to speak of.
I've tried zeroing them but always found a small cost in tree size. In fact, I even try killers[ply-2] before giving up on trying killer moves, and that tested positive for me.
YMMV of course.
I don't get it. What is the killer here? The King moves avoiding the check? Which moves are they refuting, then, and how are these moves possible from different positions?
No, the killer in the first example is Nxc7, or even Nc7 if there is no pawn there. In the second example, Nb5 is the killer that enables Nc7 to win the exchange. Killers might be a specific escape from check, or a specific piece move to escape some threat, etc. My main point was that at ply N, trying killers from N-2 was a measurable Elo improvement in our testing. In the Nc7+ move, it forks the king and rook. Most moves will not prevent that. You either have to move one of the two pieces, or else defend the checking square or remove the checking piece. All the other pawn pushes, piece moves, don't solve the problem and the check is the first move to try. It will usually be best except when the opponent averts the threat. In the example Slate gave, there were very few moves that avoided the problem, meaning most moves were refuted by the Nc7+ which killers tried first...
In endgames it is often pretty obvious (say a passed pawn push) that might not get ordered first by other approaches. IE always try the pawn push first if there is no hash move and such... I've always thought that rather than being VERY local in nature, they are just sort of local - within a few plies rather than just at one specific ply.
Not saying what I do is the exactly right thing, just that testing proved it worked better in the case of Crafty...
There'd better be no Pawn, because a capture usually would not become a killer. So this had me confused.
I still do not see how this relates to the use of 'cousin killers'. If Nb5 makes Nc7+ possible as a follow-up, then almost all moves would indeed be refuted by Nc7+. But that is just the normal killer heuritic, where the same move works in sibbling nodes. To have a cousin node you would also need the move Nb5 to be different. But then the Knight will almost never be able to reach c7. And the alternative to Nb5 might have attacked something else, in which case you have to rescue that rather than defending against the now non-existing fork. (Or it would have attacked nothing, in which case the null move would already have refuted it, and you never get to trying killers.)
If Nc7+ would already have been possible 2 ply earlier, and if it was any good, then usually it would already have been played there to cause a cutoff, and you would never get to nodes that postpone it.
maybe I misread. IE after Nb5 the opponent gets to move, and at that ply the killers for ply+1 would be zeroed? Which mean Nc7 would not be found as a killer...
The point is that after Nb5, at the moment that you zero the killer at ply+1, Nc7+ cannot yet be a killer. Because that killer slot was filled by a node after ANOTHER move than Nb5, so that the Knight could not possibly go to c7, as it was not on b5. Only after a follow-up move of Nb5 has been searched (most-likely the null move) the ply+1 killer slot first gets to contain Nc7+ for the first time. But then you are already past the clearing. You don't clear the ply+1 killer slot after every move at ply+0. That would indeed completely destroy the killer heuristic. You only clear it at the top of Search().
hgm wrote: ↑Sat Aug 10, 2019 8:24 am
The point is that after Nb5, at the moment that you zero the killer at ply+1, Nc7+ cannot yet be a killer. Because that killer slot was filled by a node after ANOTHER move than Nb5, so that the Knight could not possibly go to c7, as it was not on b5. Only after a follow-up move of Nb5 has been searched (most-likely the null move) the ply+1 killer slot first gets to contain Nc7+ for the first time. But then you are already past the clearing. You don't clear the ply+1 killer slot after every move at ply+0. That would indeed completely destroy the killer heuristic. You only clear it at the top of Search().
That is why Slate suggested TWO killers per ply with a frequency of use count. So that Nc7 will stick around even when Nb5 is not played, which might produce a different killer.
I understood the "start of search" idea. But as I said, this would hide the Nc7 killer at the next ply, for the first move searched... where I hope Nc7 will call an instant cutoff...
No, you are still off by 1 ply. There are two killers because when a different REPLY to Nb5 isn't refuted by Nc7+ (e.g. because Nc7+ only forks a King unprotected Rook, but this particular reply attacked your Queen) but by some other quiet move (like moving that Queen to safety), you will not lose the memory of Nc7+ for the next REPLY to Nb5 (which likely would not attack your Queen, so that it is "business as usual" ).
