killer moves and history heuristic table

[smcracraft]

Any conditions under which one would
not want to update these if there were
a beta cutoff?

Any additional conditions under which
one would want to update them?

[PK]

I remember Bob Hyatt advising to update killer moves when there is a best move in the node, even though it does not raise alpha.

Another thing worth thinking about is what to do with the killer moves produced right after a null move. Whereas they are probably quite rare (we need a non-capture refuting a null move), they obviously go to the wrong spot, sometimes being assigned to the wrong color.

[mcostalba]

Another thing worth thinking about is what to do with the killer moves produced right after a null move. Whereas they are probably quite rare (we need a non-capture refuting a null move), they obviously go to the wrong spot, sometimes being assigned to the wrong color.

Are you sure ?

Probably you are right but it is not so _obvious_ why they are bad, at least to me.

Another question, perhaps a bit off topic, why in every engine I have looked I have found always two killer moves's slots ? Never one, never three, never 100 ?

Is it because I have looked to too few engines ?

Thanks
Marco

[hgm]

I remember Bob Hyatt advising to update killer moves when there is a best move in the node, even though it does not raise alpha.

Another thing worth thinking about is what to do with the killer moves produced right after a null move. Whereas they are probably quite rare (we need a non-capture refuting a null move), they obviously go to the wrong spot, sometimes being assigned to the wrong color.

How can you have a best move that does not raise alpha? A hit on an exact hash entry and all other moves failing low with a lower upper-bound? How would the node know that one of its aughter nodes returned an exact score that was below alpha? The bound type is not usually passed towards the root, in search. Most engines do not even propagate the depth towards the root.

The other thing you say suggests that you forget to increase the ply number ('level') when you null move. I would think that refutations of the null move are in fact the most likely refutations of all real moves, as most moves usually resemble the null move in character (being passive and not good for anything). In fact so much that I consider of reserving a special killer slot for null-move refutations, to prevent this killer from being overwritten by refutations that were specific to the preceeding move. E.g. a null move can be refuted by a non-capture if that is a fork or a skewer, and this would be likely to work against most other moves as well. Of course you could have the first real move discover that for itself, and pass it on to its brethren. But that would be quite expensive, as this move will have to discover it in an unreduced search, and the fork or skewer is not likely to be ranked very early in the normal move ordering. It might be hidden randomly between the non-captures.

[bob]

I remember Bob Hyatt advising to update killer moves when there is a best move in the node, even though it does not raise alpha.

Another thing worth thinking about is what to do with the killer moves produced right after a null move. Whereas they are probably quite rare (we need a non-capture refuting a null move), they obviously go to the wrong spot, sometimes being assigned to the wrong color.

1. If you don't "raise alpha" how can there be a "best move"???

2. Captures can easily refute a null-move. It is very common in fact. I move, you pass, I take something. You prefer for the next ply to be an ALL node and fail low, of course, so that the null-move will fail high, but in that case there is no killer anyway. And a killer that refutes a null-move is a good one to try first. Note that I don't allow captures to become killers so the above is moot for my program, since I try captures before killers anyway...

I do not follow the "wrong spot" and "wrong color" issue as I flip STM after making a null-move..

[bob]

Another thing worth thinking about is what to do with the killer moves produced right after a null move. Whereas they are probably quite rare (we need a non-capture refuting a null move), they obviously go to the wrong spot, sometimes being assigned to the wrong color.

Are you sure ?

Probably you are right but it is not so _obvious_ why they are bad, at least to me.

Another question, perhaps a bit off topic, why in every engine I have looked I have found always two killer moves's slots ? Never one, never three, never 100 ?

Is it because I have looked to too few engines ?

Thanks
Marco

The answer is simple. For many positions, there is one continual killer that keeps refuting the opponent's mvoes, until he finds the move that counteracts that killer. But while doing all of that, occasionally a move he makes will lead to a new and even better killer, but it is unique to that move just played. Two killers allows you to have a quick "local move killer" while maintaining the original long-term killer as well.

[PK]

right, I wrote something silly. Instead of "a move that does not raise alpha" I meant "the move that does not cause a beta cutoff" , basically being a pv-move used as a killer.

hgm, as far as the slot thing is concerned, I meant the following:

I make a null move search at depth 6, flipping side to move and calling new search() with depth = 6-R-1, R being 2. so with no special-case code killers are stored at depth 3. I was wrong saying that the color is different, but the killer from another depth might be simply unrelated.

[bob]

right, I wrote something silly. Instead of "a move that does not raise alpha" I meant "the move that does not cause a beta cutoff" , basically being a pv-move used as a killer.

hgm, as far as the slot thing is concerned, I meant the following:

I make a null move search at depth 6, flipping side to move and calling new search() with depth = 6-R-1, R being 2. so with no special-case code killers are stored at depth 3. I was wrong saying that the color is different, but the killer from another depth might be simply unrelated.

I don't store killers by "depth remaining". I store killers in an array indexed by "ply" which is distance from the root... Using depth remaining would be horrible because reductions and null-move reduce the depth significantly...

[AndrewShort]

right, I wrote something silly. Instead of "a move that does not raise alpha" I meant "the move that does not cause a beta cutoff" , basically being a pv-move used as a killer.

hgm, as far as the slot thing is concerned, I meant the following:

I make a null move search at depth 6, flipping side to move and calling new search() with depth = 6-R-1, R being 2. so with no special-case code killers are stored at depth 3. I was wrong saying that the color is different, but the killer from another depth might be simply unrelated.

Like most engines I believe, I have 2 variables: PLY, which is a global variable representing what ply we are building/searching, and I have DEPTH, which search uses as a local variable to represent the depth remaining. Extensions, such as check extensions, can increment the local DEPTH. Or shallow searches, such as null move or IID, can use a reduced local depth. But PLY just plugs onward, always incrementing with MakeMove (and with MakeNullMove) and decrementing with UndoMove (and UndoNullMove).

Killer moves are associated with the PLY, not the DEPTH. In other words, I am on ply 3, and I want to try a killer move that worked before in ply 3 (of course, side to move will be the same). Your way is to say: I have depth 4 remaining, and I want to try a killer move that worked before with depth 4 remaining - but that cannot work, because the side to move could be different, due to depth remaining changing all the time due to extensions/reductions.