Page 1 of 2
Possible history table improvement
Posted: Thu May 30, 2013 11:15 pm
by Laszlo Gaspar
Hi all,
Not so long ago there was - and recently still is - a discussion here about the usefulness of the good old history table which nowadays - at such big search depths - doesn't produce reliable data for move ordering any longer just "random noise". Even Prof. Hyatt mentioned that he entirely got rid of it.
I would like to share with you my simple idea, I don't remember if it was mentioned earlier.
Let's
collect and
use the history data only
on the first few plys like in the good old days
! This changes the formula a bit:
Code: Select all
if(ply < MAXHISTORYPLY & value >= beta)
{
historytable[piece][to] += (MAXHISTORYPLY - ply)*(MAXHISTORYPLY - ply);
}
This way we can(?
) improve move ordering closer to the root while we can still use other methods elsewhere. I use MAXHISTORYPLY=10 value in my engine together with aging.
Re: Possible history table improvement
Posted: Thu May 30, 2013 11:26 pm
by Daniel Shawul
At least this is better than a pseudo contest
I agree that is a simple proof that if it worked in the 70s it should word now too. Use it to the same depth that engines of the 70s used history successfully for, so 10 is a good guess.
Re: Possible history table improvement
Posted: Fri May 31, 2013 9:42 pm
by Harald
Code: Select all
if(ply < MAXHISTORYPLY & value >= beta)
{
historytable[piece][to] += (MAXHISTORYPLY - ply)*(MAXHISTORYPLY - ply);
}
Changing the history table only when beta is less than 1 (or 2) is strange.
In C and C++ you better use &&. Your compiler may also tell you that.
Code: Select all
if (ply < MAXHISTORYPLY && value >= beta)
{
historytable[piece][to] += (MAXHISTORYPLY - ply) * (MAXHISTORYPLY - ply);
}
Re: Possible history table improvement
Posted: Fri May 31, 2013 10:06 pm
by AlvaroBegue
Harald wrote:Code: Select all
if(ply < MAXHISTORYPLY & value >= beta)
{
historytable[piece][to] += (MAXHISTORYPLY - ply)*(MAXHISTORYPLY - ply);
}
Changing the history table only when beta is less than 1 (or 2) is strange.
In C and C++ you better use &&. Your compiler may also tell you that.
Code: Select all
if (ply < MAXHISTORYPLY && value >= beta)
{
historytable[piece][to] += (MAXHISTORYPLY - ply) * (MAXHISTORYPLY - ply);
}
Although you are correct that he should have used &&, I believe the code with a single & will work in every situation. The operator precedence for & and && is similar, so the expression is grouped the same way. The operator < on the left will evaluate to true or false, and so will the operator >= on the right. In order to apply operator & to those values, they will be converted to int, as 1 or 0. Then the bitwise operator & will do the right thing.
Re: Possible history table improvement
Posted: Sat Jun 01, 2013 2:43 am
by lucasart
AlvaroBegue wrote:Harald wrote:Code: Select all
if(ply < MAXHISTORYPLY & value >= beta)
{
historytable[piece][to] += (MAXHISTORYPLY - ply)*(MAXHISTORYPLY - ply);
}
Changing the history table only when beta is less than 1 (or 2) is strange.
In C and C++ you better use &&. Your compiler may also tell you that.
Code: Select all
if (ply < MAXHISTORYPLY && value >= beta)
{
historytable[piece][to] += (MAXHISTORYPLY - ply) * (MAXHISTORYPLY - ply);
}
Although you are correct that he should have used &&, I believe the code with a single & will work in every situation. The operator precedence for & and && is similar, so the expression is grouped the same way. The operator < on the left will evaluate to true or false, and so will the operator >= on the right. In order to apply operator & to those values, they will be converted to int, as 1 or 0. Then the bitwise operator & will do the right thing.
Yes, you're right indeed. I just checked, because I really had some doubts when reading it
http://www.difranco.net/compsci/C_Opera ... _Table.htm
Now I'm very careful with C operators. Mistying a '&&' into a '&', or making wrong assumptions about operator precednece and default associativity, has cost me quite a few hours of debugging already.
Recent versions of GCC will warn you if you are using a priority or associativity of operators in an 'unusual way', basically telling you: ' are you sure that's what you want to do?' (sometimes it is, but most often it's a mistake, it's really helped me quite a few times).
Re: Possible history table improvement
Posted: Sat Jun 01, 2013 9:39 am
by syzygy
lucasart wrote:Recent versions of GCC will warn you if you are using a priority or associativity of operators in an 'unusual way', basically telling you: ' are you sure that's what you want to do?' (sometimes it is, but most often it's a mistake, it's really helped me quite a few times).
It also doesn't hurt to compile your code with clang just to see what warnings you get. It recently helped me to find a && in my code that really should have been a &.
Re: Possible history table improvement
Posted: Sat Jun 01, 2013 12:43 pm
by lucasart
syzygy wrote:lucasart wrote:Recent versions of GCC will warn you if you are using a priority or associativity of operators in an 'unusual way', basically telling you: ' are you sure that's what you want to do?' (sometimes it is, but most often it's a mistake, it's really helped me quite a few times).
It also doesn't hurt to compile your code with clang just to see what warnings you get. It recently helped me to find a && in my code that really should have been a &.
I know. That's how I spotted a bug recently, and fixing it gained a few elo I was doing something like this
Code: Select all
bool x = f(...);
...
if (x == 2) ...
problem is that x can only be 0 or 1 due to bool type conversion of inf f().
Re: Possible history table improvement
Posted: Sat Jun 01, 2013 8:58 pm
by Laszlo Gaspar
Thank you, Harald, for the warning! I wrote in fact a Java code in which it is correct but it was intended just a pseudo code anyway.
Re: Possible history table improvement
Posted: Sat Jun 01, 2013 11:30 pm
by hgm
lucasart wrote:Now I'm very careful with C operators. Mistying a '&&' into a '&', or making wrong assumptions about operator precednece and default associativity, has cost me quite a few hours of debugging already.
I use & and | in stead of && and || quite often. This can save you branches, and branches that are not there can also not be mispredicted.
Re: Possible history table improvement
Posted: Sat Jun 01, 2013 11:50 pm
by Harald
And when I wrote that I thought that & had a higher priority than <.
That was also wrong. We learn: Just use a lot of () and be careful with & in conditions.