History bonus

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
Desperado
Posts: 782
Joined: Mon Dec 15, 2008 10:45 am

History bonus

Post by Desperado » Tue Feb 09, 2021 5:05 pm

Hello everybody.

I found a formula that seems to be quite common these days.

Code: Select all

HistoryTableEntry += 32 * bonus - HistoryTableEntry * abs(bonus) / 512;
What i like so far is, that negativ and positiv boni are handled with one formula.
I also like that only one table is used for good and bad updates instead of two tables.
Now...

1. How are history limits handled ? (e.g. MIN=-16000 MAX= 16000 for HistoryTableEntry) ?
None of the source codes uses a classic re-scaling scheme if limits are reached (why) ?

2. What is the idea behind the constants, how (why) are they choosed ?

3. Some implementations limit the bonus like MIN(depth*depth,400).
That makes sense to me because in the example depth = 20 seems to be very far away
from the current position. What are your thoughts about it?

Currently i use a classic approach based on history_good[] and history_bad[] tables.
The history score is the relative score of both values multiplied with HistoryMax.
I need to scale the tables when an entry reaches a limit. I really would like to switch to the above.

Well, it feels like a good idea but i really want to understand what i am going to implement.

Thanks in advance.

User avatar
xr_a_y
Posts: 1465
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: History bonus

Post by xr_a_y » Tue Feb 09, 2021 5:28 pm

So the formula says

H(n+1) = H(n) + a*X - H(n)* |X|/b = H(n) * ( 1 - |X|/b ) + a*X

where X can be a positive or negative bonus.

This can be viewed as an arithmetico–geometric sequence and thus you know what a and b to use in order to ensure you stay in the expected boundaries.

At least, that's how I use this...

User avatar
hgm
Posts: 25860
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: History bonus

Post by hgm » Tue Feb 09, 2021 6:41 pm

If you add the same, positive bonus every time, the value will saturate when historyTabEntry = 16K. The second term will then subtract 32*bonus (16K/512 = 32), and the first term adds it again. So you will never be able to exceed the range.

User avatar
Desperado
Posts: 782
Joined: Mon Dec 15, 2008 10:45 am

Re: History bonus

Post by Desperado » Tue Feb 09, 2021 8:18 pm

hgm wrote:
Tue Feb 09, 2021 6:41 pm
If you add the same, positive bonus every time, the value will saturate when historyTabEntry = 16K. The second term will then subtract 32*bonus (16K/512 = 32), and the first term adds it again. So you will never be able to exceed the range.

Code: Select all

// 32 * bonus == (HistMax/512) * abs(bonus)
// 32 * bonus == (16K/512) * abs(bonus)

// HTE = HTE + 32 * bonus - (16k/512) * abs(bonus)

Positive bonus:

1. Ok, if the bound has been reached nothing will be added.

2. Otherwise the delta = (32 - 16K/512) will be multiplied with the bonus and will be added. (correct ?!)

3. The delta muliplier ensures that the current HTE + delta * bonus <= HistMax

Code: Select all

HTE + delta * bonus <= HistMax
Negative bonus

Code: Select all

// HTE = HTE + 32 * -bonus - (HTE/512) * abs(bonus) // unlimited substruction ?!
Ok, if HTE contains the value of -16K the same logic can be applied.
The value is bounded to -16K and will not drop below.

In other words the bounds (negative+positive) are defined by the quotient 512/32. (i guess)
In our example the range would be -16k to 16k.

User avatar
hgm
Posts: 25860
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: History bonus

Post by hgm » Wed Feb 10, 2021 7:55 am

The product, actually: 32*512 = 16K. Your other statements are all correct.

User avatar
Desperado
Posts: 782
Joined: Mon Dec 15, 2008 10:45 am

Re: History bonus

Post by Desperado » Wed Feb 10, 2021 9:04 am

hgm wrote:
Wed Feb 10, 2021 7:55 am
The product, actually: 32*512 = 16K. Your other statements are all correct.
Thank you!

Meesha
Posts: 1
Joined: Sun Feb 23, 2020 4:11 pm
Full name: Gianni Casati

Re: History bonus

Post by Meesha » Tue Feb 23, 2021 2:04 am

Don't you find that using HistMax = 16K and HTE = HTE + 32 * bonus - HTE * abs(bonus)/512 causes too many history entries to max out at 16K ? Is this done on purpose?

I use History Max = 32,768 and HTE = HTE + 16 * bonus - HTE * abs(bonus) / 2048.

And what is the consensus on clearing the history tables after every move? I used to just age them after each move by dividing each entry by 2. But I'm thinking I'm just getting closer to random noise if I don't clear the tables after a completed search.

Post Reply