History Heuristic - when to reset counts

[AndrewShort]

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?

[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.

[Harald]

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

[Jan Brouwer]

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?

In Rotor, I multiply all entries by 0.5 each 10000 nodes.
History values are updated with (remaining depth) ^ 3 when a best move was found which is not a capture move.

[BubbaTough]

In Rotor, I multiply all entries by 0.5 each 10000 nodes.

This is a good idea. I divide by some large number (forget what, but larger than 2) when things go past a threshold. Your approach might be slightly better, not sure. Checking takes less time, but it probably gets triggered more often and dividing everything is a substantial operation.


For a long time a did nothing (besides resetting history before each search) and I don't think performance improved much when I added the "safer" code that keeps history in a reasonable range. Even in long games. And for me, history is better than no history, even without keeping them in range . I keep a separate history at each ply which might help because the first few ply would never get out of range, while the benefit of later plys is dubious anyway.

-Sam

[AndrewShort]

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...

[Harald Johnsen]

The compiler will allways output a right shift. But your counter should be declared as an unsigned integer to have the smallest code. If it is signed the compiler will add some 'safety' code (useless when you know that the number is not negative).

Code: Select all

	cdq
	sub	eax, edx
	sar	eax, 1

I reset the counters before a search, and I reduce the counters when they reach a rather high value (so this does not happen often).

Code: Select all

    // increment the history counter on failed high
    void INLINE update(const CM *cm, int depth) {
        if( Capt(cm->m) )
            return;
        int idx = HIST_INDEX(cm->m);
        good_hit[ idx ] += depth*depth;
        if( good_hit[ idx ] >= 0x00100000 ) {
            shift_count++;
            for(int i = 0; i < HIST_SIZE ; i++ ) {
                good_hit[ i ] = (good_hit[ i ] + 1) / 2;
            }
        }
    }

HJ.

[Kempelen]

I divide all history table by 4 when the max value of the table > 8191

until now it does not go bad.... but maybe I need more experimentation.

[Michael Sherwin]

In RomiChess I have made the history counters more dynamic by dividing any counter that exceeds 200 by 2. The history values are then expressed as a pecentage.

n = histTbln[fig][fs][ts] // n is the count
g = histTblg[fig][fs][ts] // g is the 'good' * 100

if(n > 99 && g / n < 12) reduce

[Karlo Bala]

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