Killer and History: Increased Node Count

[Cheney]

Hi,

I decided to revisit my move ordering and noticed something interesting. Both the killer history and move history cut many nodes when tested individually but when both heuristics are enabled in the search at the same time, the node count is slightly higher than the history by itself.

I'm not really sure why this happens. I use the standard History[64,64] for history and tested various killer arrays with the current KillerA[MaxPly] and KillerB[MaxPly] and I keep a counter for each to help with ordering and replacement.

I am sorting moves:
1. PV from previous iteration.
2. Position's move from the TT.
3. Captures (MVV/LVA) - no SEE.
4. Killer A or B based on which one has higher count.
5. Moves from the history.

Has anyone else experienced a similar situation?

I can only speculate that a killer move is being played but is not cutting and leading to more nodes tested; however, I would expect it would still decrease node count a bit when coupled with the history heuristic.


Thanks,
Cheney

[Don]

Hi,

I decided to revisit my move ordering and noticed something interesting. Both the killer history and move history cut many nodes when tested individually but when both heuristics are enabled in the search at the same time, the node count is slightly higher than the history by itself.

I'm not really sure why this happens. I use the standard History[64,64] for history and tested various killer arrays with the current KillerA[MaxPly] and KillerB[MaxPly] and I keep a counter for each to help with ordering and replacement.

Your history table is not standard practice. First of all you should have separate arrays by color. And more common these days is something like this:

history[color][piece_type][to_square]

You can also include from_square which I found works just as well, but no better:

history[color][piece_type][from_square][to_square]

In Komodo we keep 2 killers but we have experimented with only using one and using the second only as an LMR veto. It's a very close call. If you don't have good history the second killer is crucial though.

I am sorting moves:
1. PV from previous iteration.
2. Position's move from the TT.
3. Captures (MVV/LVA) - no SEE.
4. Killer A or B based on which one has higher count.
5. Moves from the history.

Has anyone else experienced a similar situation?

The PV from previous iteration should be the same as the hash table move, right?

The count is not a good way to do killers, you should always use the last killer because these tend to be highly local. So if Nf3 works it should be promoted immediately to killer A and the previous killer A should be put in killer B slot. Then you always try killer A first.

I can only speculate that a killer move is being played but is not cutting and leading to more nodes tested; however, I would expect it would still decrease node count a bit when coupled with the history heuristic.

You should definitely get a small benefit from killers on top of history.

Thanks,
Cheney

[bob]

Hi,

I decided to revisit my move ordering and noticed something interesting. Both the killer history and move history cut many nodes when tested individually but when both heuristics are enabled in the search at the same time, the node count is slightly higher than the history by itself.

I'm not really sure why this happens. I use the standard History[64,64] for history and tested various killer arrays with the current KillerA[MaxPly] and KillerB[MaxPly] and I keep a counter for each to help with ordering and replacement.

I am sorting moves:
1. PV from previous iteration.
2. Position's move from the TT.
3. Captures (MVV/LVA) - no SEE.
4. Killer A or B based on which one has higher count.
5. Moves from the history.

Has anyone else experienced a similar situation?

I can only speculate that a killer move is being played but is not cutting and leading to more nodes tested; however, I would expect it would still decrease node count a bit when coupled with the history heuristic.


Thanks,
Cheney

No chance you search some moves twice? IE a killer then the same move from history? I do killers before generating moves and explicitly exclude them from later re-searching.

[lucasart]

In Komodo we keep 2 killers but we have experimented with only using one and using the second only as an LMR veto. It's a very close call.

Same for me. I did experiment with exactly the same, and came to the same conclusion. Removing the second killer is a regression because the search reduces it. But if you keep it and only prevent reductions of the second killer, while not actually using it in the move ordering, its utility is barely measurable.

[Cheney]

Sorry, I may have been a bit misleading. I do separate my histories by color.

I have a KillerWhite[maxply][maxkillers], KillerBlack[maxply][maxkillers], HistoryWhite[64][64], and HistoryBlack[64][64]. maxkillers is two positions.

However, I was just using a KillerA and KillerB and did not separate them by color. I have reverted to my original method and am going to take another look.

Before I start the iterative deepening, I reset these tables.

During the search, I was just flipping between a color's two Killers each time there was a beta cut off. I store the move and the score. I noticed that many times the same move was in both positions. So I implemented and tested a replacement method of replacing the one with the lowest score and if the move was aleady stored, I just increase its stored score. This seems to preserve at least two separate moves.

As for the history, I just add in the depth when it is met. I am currently only storing histories that increase alpha.

When I am ordering these moves, the killers are set with a higher value than history moves so they are chosen before history.

The PV from previous iteration should be the same as the hash table move, right?

It does not appear so. After the PV has been played out on the left most branches of the tree, all (or most) of the following positions previously played will still be in the TT with a best move and that move is a lower, exact, or upper. If a given position is found in the TT, then I play its move if in the move list.

history[color][piece_type][from_square][to_square]

I did try a separate HistoryWhite[ply][64][64] (and without [ply]) for a Killer table to see if that would help but it really did not; I had the same results.

Is it not that important to maintain the ply at which a killer was found?

[Don]

Sorry, I may have been a bit misleading. I do separate my histories by color.

I have a KillerWhite[maxply][maxkillers], KillerBlack[maxply][maxkillers], HistoryWhite[64][64], and HistoryBlack[64][64]. maxkillers is two positions.

However, I was just using a KillerA and KillerB and did not separate them by color. I have reverted to my original method and am going to take another look.

Actually, killerA and killerB should be per ply of search. So if you have this array you will get FAR better results:

move_t killers[ply][2]

be careful to go by ply and not depth!

Before I start the iterative deepening, I reset these tables.

During the search, I was just flipping between a color's two Killers each time there was a beta cut off. I store the move and the score. I noticed that many times the same move was in both positions. So I implemented and tested a replacement method of replacing the one with the lowest score and if the move was aleady stored, I just increase its stored score. This seems to preserve at least two separate moves.

As for the history, I just add in the depth when it is met. I am currently only storing histories that increase alpha.

When I am ordering these moves, the killers are set with a higher value than history moves so they are chosen before history.

The PV from previous iteration should be the same as the hash table move, right?

It does not appear so. After the PV has been played out on the left most branches of the tree, all (or most) of the following positions previously played will still be in the TT with a best move and that move is a lower, exact, or upper. If a given position is found in the TT, then I play its move if in the move list.

history[color][piece_type][from_square][to_square]

I did try a separate HistoryWhite[ply][64][64] (and without [ply]) for a Killer table to see if that would help but it really did not; I had the same results.

Is it not that important to maintain the ply at which a killer was found?

[Cheney]

Hmm, are you saying that if I keep a move as a killer then I should think about avoiding keeping it as a history?

My move is s struct. An int for the move and an int for a sorting score.

During move generation, all captures get an MVVLVA sort score applied.

After all moves are generated, I loop through them once before playing any move out. The loop sets a sort score.
- Set the PV node to a max value.
- Set the TT best move to max/2
- The MVV/LVA score is between (max/2)-1 and max/4
- If a move is in the killer table, add its SortScore value to max/8 and not to exceed max/4.
- All other moves get the History value applied to the move's sort score (which is way less than max/8).

Next I run the loop to make all moves and I play the move with the highest sort score first.

Now, thinking about this, picking on Nc3, it could be stored as a killer and history, easliy, since there are many different parts of the tree where Nc3 could and does exist. Maybe it is getting overwritten and that should be avoided. Is that where you're getting at?

Thank you

[Don]

Hmm, are you saying that if I keep a move as a killer then I should think about avoiding keeping it as a history?

No. But don't store captures as killers, just ignore them. You already have excellent capture ordering so this just pollutes the array.

Same for history, don't store captures. But the history table of course is shaped a lot differently, it's just one table.

You also need to "age" the history table so that later entries have more weight. That's a whole new thread. You could try something simple like taking the score already in the table, multiple by (N -1), add 1 (if the move is best) or zero if it's not, and then divide by N. Aging is very important in history and can make a big different. But take this one step at a time and get the killers right first, then we can talk about the history..

My move is s struct. An int for the move and an int for a sorting score.

During move generation, all captures get an MVVLVA sort score applied.

After all moves are generated, I loop through them once before playing any move out. The loop sets a sort score.
- Set the PV node to a max value.
- Set the TT best move to max/2
- The MVV/LVA score is between (max/2)-1 and max/4
- If a move is in the killer table, add its SortScore value to max/8 and not to exceed max/4.
- All other moves get the History value applied to the move's sort score (which is way less than max/8).

Next I run the loop to make all moves and I play the move with the highest sort score first.

Now, thinking about this, picking on Nc3, it could be stored as a killer and history, easliy, since there are many different parts of the tree where Nc3 could and does exist. Maybe it is getting overwritten and that should be avoided. Is that where you're getting at?

Thank you

[bob]

Hmm, are you saying that if I keep a move as a killer then I should think about avoiding keeping it as a history?

My move is s struct. An int for the move and an int for a sorting score.

During move generation, all captures get an MVVLVA sort score applied.

After all moves are generated, I loop through them once before playing any move out. The loop sets a sort score.
- Set the PV node to a max value.
- Set the TT best move to max/2
- The MVV/LVA score is between (max/2)-1 and max/4
- If a move is in the killer table, add its SortScore value to max/8 and not to exceed max/4.
- All other moves get the History value applied to the move's sort score (which is way less than max/8).

Next I run the loop to make all moves and I play the move with the highest sort score first.

Now, thinking about this, picking on Nc3, it could be stored as a killer and history, easliy, since there are many different parts of the tree where Nc3 could and does exist. Maybe it is getting overwritten and that should be avoided. Is that where you're getting at?

Thank you

Not exactly, just that if you search move Mn as a killer, you should not search it a second time at this ply. Yes, the TT MIGHT provide a quick answer. Out near the leaves, the TT can get overwritten easily and you might end up searching the same sub-tree twice, which will hurt a small amount.

In Crafty, I have two killers per ply. When I start searching at ply=N, I first try the tt best move if available, before generating ANYTHING. I then generate captures and sort non-losing captures to the front of the list, clearing the tt-move if it is a capture. I then try the two killers before generating any non-captures, and since killers can't be captures (at least in my implementation) it is certain that when they don't cause a cutoff and I generate all non-captures, the two killers (if legal) will be in that list. I exclude them from searching again..

[Cheney]

OK, thanks, lots of good information here, which I'll put on my next to-do to try out . Interesting to try a type of move before even generating moves. Is there a writeup on that concept somewhere?

However, as for keeping histories, I think I might still be missing something and I wonder if it is at the basic understanding.

I am keeping two histories:

* one that maintains moves which are greater than beta - Killer[color][ply] and recently I tried Killer[color][ply][piece][tosq].

* the other maintains an incremented value if the alpha<score<beta - History[color][tosq][fromsq] += depth*depth

I reread CPW and feel that I am reading something new . Fundamentally, is my logic correct for storing these moves at these points? I think it is.

I have tried various alterations as suggested in some of these threads and I get the same performance. For example, from a new game's starting position:

Search, Depth 5, no history, no killer - ~24,400 nodes.
Search, Depth 5, no history, killer - ~14,600 nodes.
Search, Depth 5, history, no killer - ~11,000 nodes.
Search, Depth 5, history and killer - ~12,300 nodes.

I have tried on various different positions and get similar results. It is not that I am playing any given move twice at a given point in the tree because the move list only has the move once; but across the same ply, it is getting played early as a killer.

I will try a few other things, including playing the killer move only once across a ply. I am interpreting that as meaning across any amount of groups of moves in that ply.