History counters

[bob]

Last week someone posed the question about history counters and whether or not they should be cleared, etc.

First, what I have been doing for any versions of Crafty that used history.

I have always updated by depth*depth, rather than Schaeffer's 1<<depth, because 1<<depth is easy to overflow today. As the history counters are updated, I check for a value > MAX, or < -MAX and if found, I set a flag called "age". I update both sides of the thing by incrementing the counter for the move that failed high, and decrementing the counter for all the moves searched before that move that did not fail high. Once that is done, if any counter exceeded 2^20 or dropped below -2^20, I run through all the counters and shift every one right 4 bits (signed ints). Doesn't happen often enough to affect NPS.

I just finished three tests with one more "in the queue".

test 1. Zero history counters each time I start a new search (not a new iteration.

test 2. Rather than zeroing the counters, divide all by 16 (right shift 4
bits as above)

test 3. Rather than zeroing or dividing by 2^4, I divided by 2^8.

Bottom line... NO measurable difference

All ended up (after 30K games per test) within 2 Elo of each other, with an error bar of +/- 4.

Keep in mind that none of these versions let a single counter pass over +/- 2^20 without dividing everything by 16, so if you are just "letting them grow" then zeroing might have a positive effect. For me, I am leaving them alone and aging when they get too big. I once tuned that 2^20 number but I might test that again to see if it can be better optimized.

The one that is "in the queue" is zeroing after every iteration, which one suggested last week. I suspect that might begin to have a negative effect, but we will see.

Test conditions: no pondering, specific opening positions to start each game using no books, no parallel search.

I'll update after last test completed.

[PK]

There is also a variation where You decrease the counter for all the quiet moves that might be played in the position.

I'm curious if any engine other than Crafty succeeded in removing reduction logic for move sorting completely. I try to run that test periodically, but so far it's always a regression for move ordering. But I think that right now I am about to succeed to remove history check for late move reduction.

Also it is worth noting that Fruit Reloaded (Daniel Mehrmann & Ryan Benitez) uses history counters heavily, also in the contexts I'd never think of (like fiddling with futility margins). The result is unusual to say the least: it searches to rather low depths, but outsearching it does not guarantee enything (Rodent scores ca. 40% aginst it)

[Fabio Gobbato]

I think it depends in how you implement the history heuristic and what you do with the history scores.
In my engine I use LMP basing on the history score. I made a test and I found that it was good to clear the history counters on every iteration.
I don't think that it would work for everyone but for me it does.

[bob]

I think it depends in how you implement the history heuristic and what you do with the history scores.
In my engine I use LMP basing on the history score. I made a test and I found that it was good to clear the history counters on every iteration.
I don't think that it would work for everyone but for me it does.

That test just finished and it shows up about -4 Elo, but again, the error bar is +/- 4 so I would consider that a pretty much "no change." But I DID run a bunch of positions through the normal crafty and through the zero after each iteration (and divide by 16 after each iteration as well) and the original is uniformly searching smaller trees for the same depth. Which is not surprising. History information is supposed to guide the search. What is the point of losing that information after each iteration? Looks like for me, at least, between iteration clearing/reducing is not a good idea...

[bob]

There is also a variation where You decrease the counter for all the quiet moves that might be played in the position.

I'm curious if any engine other than Crafty succeeded in removing reduction logic for move sorting completely. I try to run that test periodically, but so far it's always a regression for move ordering. But I think that right now I am about to succeed to remove history check for late move reduction.

Also it is worth noting that Fruit Reloaded (Daniel Mehrmann & Ryan Benitez) uses history counters heavily, also in the contexts I'd never think of (like fiddling with futility margins). The result is unusual to say the least: it searches to rather low depths, but outsearching it does not guarantee enything (Rodent scores ca. 40% aginst it)

I am not sure what you mean by the first line. The original approach I did on this back circa 2005 when I first started to experiment with LMR was to increment the counter for the move that failed high or became the best move, and reduce the counters for all of the moves that were tried before that move.

I do turn off counter updating in the last 5 plies of search, and also don't use history counters for ordering in the last 5 plies since that can become expensive.

I also don't quite know what you mean by "remove reduction logic for move ordering." I reduce based on the order a move is searched in, but I don't use the history counter to disable reductions or modify them in any way. I do not reduce non-losing captures, or killers or the hash move. Anything else is a candidate however. Moreno as it moves down the move list order.

[Fabio Gobbato]

In my engine I add depth*depth to the history counter without subtracting anything.

I think that when the search analyze lots of nodes you have in the history only random noise so it good to clear the history, in my engine it works good.

Another thing is the history threshold (for LMP): with lots of nodes every quiet move is cut if you don't clear the history.

[PK]

OK, I was slightly sleepy writing my last post, and indeed it contains some gibberish.

In the first line I meant reducing history counter for all the quiet moves that has been generated (at the very moment when the list of quiet moves is created) ( counter -= depth*depth) and then increasing only the move that failed high or became a new pv (counter += 2 * depth * depth). Then it's easier to set some arbitrary threshold which means that a move performs well and perhaps should not be reduced. Otherwise a score hovering around 0 can signify one of the following a) a move that repeteadly failed low and b) a move of unknown history that has not been tried too often.

[hgm]

I am a bit worried about this implication: "performed well and thus should not be reduced". It only makes a difference whether you reduce or not (apart from the latter being much more expensive) when the result would not be the same. You only get something for the extra cost of not reducing when it alters the result. With a standard LMR approach it is especially dangerous if a move fails low on a reduced search, but would fail high unreduced. The opposite error would be caught, as you will re-search after a reduced fail high. But a reduced fail low would never make you discover that the result should in reality have been a fail high. So only in that case it would be important to force an unreduced search to start with.

So it seems to me you should not base the decision to exempt a move from reduction not based on whether it performed well, but on whether it performed better at high depth than at low depth. I.e. keep a history table where you increment the counters for moves that failed low on the hash hit from the previous iteration, but do fail high on the search (that was necessary because that hash hit did not have large-enough draft). And use those counters to force unreduced searches.

[bob]

In my engine I add depth*depth to the history counter without subtracting anything.

I think that when the search analyze lots of nodes you have in the history only random noise so it good to clear the history, in my engine it works good.

Another thing is the history threshold (for LMP): with lots of nodes every quiet move is cut if you don't clear the history.

I can see why you might want to clear things if you do not ever reduce the counters. If I get a fail high on move N, I increment it by depth*depth, and then reduce all the moves searched prior to move N by that same amount since they did not fail high and would have been better if they had been ordered later.

I don't use the history counters for LMP myself. I think the counters are way too random for that. But that is just an opinion of course. All I use 'em for is to order the first 1/2 of the moves at a ply, if not too close to the tips.