Killer and History: Increased Node Count

[bob]

Hi,

I found what's going on

My PVHistory table, used to hold the previous iteration's PV and to sort those moves first in the next iteration, was getting in the way. I was not clearing it between test searches which is why when I would enable/disable killer and history and run a new search on the same position, I was getting funky numbers. It was basically starting a new searching already knowing the PV.

Now that I am clearing it, the history and killer tables appear to be reducing nodes as expected where when both are enabled, I get the most reduced node count.

Thank you again for your help. All your other ideas and comments I will look into to see if I can squeeze a little more out of this.

Your killer table should just store a single move. From previous posts it appears you are using a big butterfly board like is used for history but killers are really simple, just an array by color and depth of moves:

move_type killerA[color][ply];
move_type killerB[color][ply];

If you instead are storing hit frequencies it's hardly any different than the history table. The PRIMARY benefit of a killer is that if a move is good NOW it will probably be good the very NEXT time at this level. History is a different animal altogether because it is more about the average utility of a move over time. The killer will be more relevant than the best history move most of the time.

If you are not making that distinction then you are probably not getting as much out of this as you should be.

I don't do the color thing at all. If I am white at the root, I will ALWAYS be white at odd plies, and black at even plies. Not much use in having white and black moves for each ply there.

[bob]

just an array by color and depth of moves:

move_type killerA[color][ply];
move_type killerB[color][ply];

Why "color"? The color is implicitly given through the ply, unless you don't clear the killer table with a new search.

Sven

In a pure Alpha beta search this is true (I think) however if the search incorporates any extensions or reductions then this is not the case.

Actually, it is. If you are white at the root (ply=1) how could you EVER be white at ply=2, 4, ...? You must alternate. Even null-move eats a ply in the tree. Reductions just affect how deep you go, nothing changes the basic idea of alternating color at each successive ply. I have always just had killers[ply][2] since the 70's when Slate/Atkin explained the idea in the Frey book.

[Don]

just an array by color and depth of moves:

move_type killerA[color][ply];
move_type killerB[color][ply];

Why "color"? The color is implicitly given through the ply, unless you don't clear the killer table with a new search.

Sven

In a pure Alpha beta search this is true (I think) however if the search incorporates any extensions or reductions then this is not the case.

Actually, it is. If you are white at the root (ply=1) how could you EVER be white at ply=2, 4, ...? You must alternate. Even null-move eats a ply in the tree. Reductions just affect how deep you go, nothing changes the basic idea of alternating color at each successive ply. I have always just had killers[ply][2] since the 70's when Slate/Atkin explained the idea in the Frey book.

Enough with the color thing - many posts ago I mentioned that this was an oversight and is basically redundant because ply already encodes color.

But for history, color IS relevant and crucial. Bob uses a refinement in history that I also use, it is weighted by depth * depth. That is a small but definite enhancement. But also, history has almost no impact these days without some sort of aging. Some programs for example periodically divide the value by 2. Also, unlike old-fashioned history it is good to consider not just the one best move, but the moves that are tried that don't prove to be best. There are various methods to accomplish this but in high level detail you basically maintain the success ratio of a move. A move is either best or it isn't and you can keep the ratio.