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.
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:
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.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
Yes, that is what I have reverted back to before discovering the PVHistory "bug". I store one move in KillerA[color][ply] and one in KillerB[color][ply].
I need to review some of your other threads here on this to make sure I understand, but I am curious if I should just be overwriting each KillerA and KillerB (just flip between writing each of them when exceeding beta) or maintain a counter to go with the move for aging out.
I noticed when I just flip, both A and B tables can have the same move. I did add a check to make sure that does not happen and I actually store two unique moves.
I have methods to handle both styles above but have not yet tested the numbers since fixing the PVHistory bug to see which really is better.
Yes, that is what I have reverted back to before discovering the PVHistory "bug". I store one move in KillerA[color][ply] and one in KillerB[color][ply].
I need to review some of your other threads here on this to make sure I understand, but I am curious if I should just be overwriting each KillerA and KillerB (just flip between writing each of them when exceeding beta) or maintain a counter to go with the move for aging out.
I noticed when I just flip, both A and B tables can have the same move. I did add a check to make sure that does not happen and I actually store two unique moves.
I have methods to handle both styles above but have not yet tested the numbers since fixing the PVHistory bug to see which really is better.
Thanks Don
Here is what Komodo and most other good programs do. When there is a CUTOFF and it's not a capture, you do this:
1. Is killer A already the same as this move? Do nothing if so.
2. move killer A to killer B - put this new move in killer A
Simple and effective. I don't know of any improvements to this.
So the killer part is pretty simple. Once that is in place you probably have a lot more potential improvements in how you do history. Getting history right (the modern way) is a big deal and I put it nearly on par with the big innovation in computer chess.
Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
Don wrote:
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.
What are typical "killer replacement" rates, i.e. given a non-capture cutoff, how often do you update the first killer slot?
Cheney wrote: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].
I just use killer[ply][2]
* the other maintains an incremented value if the alpha<score<beta - History[color][tosq][fromsq] += depth*depth
That's what I recommended to everyone 20 years ago. Schaeffer suggested 1<<depth, but that overflows too quickly. Every time I have used history (and I am back to working on it yet again now) I used depth*depth as a way to limit overflow.
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.
Not a position I like to test. No q-search to speak of. Development bonus dominates. Try some middlegame and endgame positions to get a better feel.
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.
How would you try a killer move more than once at a specific position (you use the term "ply" but I can't believe you mean "just once at depth=N".
. Fundamentally, is my logic correct for storing these moves at these points? I think it is.