History Heuristic - when to reset counts

[Michael Sherwin]

for those of you using the history heuristic:

when do you reset the counts?

If you clear it too often, it loses its effectiveness.

If you clear it too rarely, it loses its effectiveness (and you risk overflow as you increase the values).

I presently reset the history table counts to 0 before each iteration of iterative deepening. [Clearing it between real moves on the board seems too rare to me.]

Anyone else do differently?

Why ever reset history counter?
Is it possible to use 2 counters? One for every move made and one for good move. Then define goodness: g = n[good]/n[all].
Then if for example if g < 30%(0.3) reduce move

Refreshing often by dividing by two causes the entries to seek the reality in the subtree that is being searched.

One idea that is promising is to have two tables, one short period and one long period that must both be in agreement before a reduction is made.

[bob]

for those of you using the history heuristic:

when do you reset the counts?

If you clear it too often, it loses its effectiveness.

If you clear it too rarely, it loses its effectiveness (and you risk overflow as you increase the values).

I presently reset the history table counts to 0 before each iteration of iterative deepening. [Clearing it between real moves on the board seems too rare to me.]

Anyone else do differently?

I no longer use them, but there are at least a couple of ideas.

Every so often, divide them all by 2. This doesn't throw them away, but inactive counters trend toward zero.

Or, if when you increment a counter, it passes some magic threshold, divide all counters by 2. This keeps all counters in the range 0 to N where N is your "magic" number...

Or, do as I did and throw 'em out completely.

When you say "divide them all by 2", I assume what you really mean is right shift 1 bit. Real division would be expensive...

I'll bet you can't tell the difference if you measure the speed. With super-scalar out-of-order execution, the divide won't matter at all...

But for any division by a power of 2 I would always shift, so long as the numbers are positive of course.

[Michael Sherwin]

for those of you using the history heuristic:

when do you reset the counts?

If you clear it too often, it loses its effectiveness.

If you clear it too rarely, it loses its effectiveness (and you risk overflow as you increase the values).

I presently reset the history table counts to 0 before each iteration of iterative deepening. [Clearing it between real moves on the board seems too rare to me.]

Anyone else do differently?

Disclaimer: My engine is weak and my history does not work very good.

I reset the history table before each search. The values are increased for good moves
with dist*dist but not more than 256. I also store the maximum of all values in the table.
Whenever a value grows over a limit the whole table is scaled down.
That can happen at any time.
When I read a value from the table it is always scaled to the interval [0..256],
thanks to the maximum. At any tyme the highest entry comes back as 256.

I hoped I could use this value in expressions like
if (history < 64) prune...
or
if (history > 200 ) expand...
or even as input in complex formulars like
centidepth += history * 100 / 256 / 10 - 5
or for move ordering
move_value = material_gain + pc_sq_value + (history / 10 - 10)
That gave many possibilities for experiments and disappointment.

Harald

Hi Harald,

I knew I saw this post but I could not find it for awhile.

I have spent years trying to find an extention method based on hitory tables, static eval, material_eval vs positional, hash moves and at least a hundred different other ideas. Thousands, if all the combinations of the various methods are concidered. Some were very promising and had good results against some engines. Overall they have resulted in nothing but slightly weaker programs at best! You are not alone!