Possible history table improvement

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, Dann Corbit, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Laszlo Gaspar
Posts: 64
Joined: Thu Mar 09, 2006 10:07 am
Location: Budapest, Hungary

Possible history table improvement

Post by Laszlo Gaspar » Thu May 30, 2013 9:15 pm

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&#40;ply < MAXHISTORYPLY & value >= beta&#41;
&#123;
       historytable&#91;piece&#93;&#91;to&#93; += &#40;MAXHISTORYPLY - ply&#41;*&#40;MAXHISTORYPLY - ply&#41;;
&#125;
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.
Regards,
László

Daniel Shawul
Posts: 4066
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Possible history table improvement

Post by Daniel Shawul » Thu May 30, 2013 9:26 pm

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.

Harald
Posts: 279
Joined: Thu Mar 09, 2006 12:07 am

Re: Possible history table improvement

Post by Harald » Fri May 31, 2013 7:42 pm

Code: Select all

if&#40;ply < MAXHISTORYPLY & value >= beta&#41;
&#123;
       historytable&#91;piece&#93;&#91;to&#93; += &#40;MAXHISTORYPLY - ply&#41;*&#40;MAXHISTORYPLY - ply&#41;;
&#125;
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 &#40;ply < MAXHISTORYPLY && value >= beta&#41;
&#123;
       historytable&#91;piece&#93;&#91;to&#93; += &#40;MAXHISTORYPLY - ply&#41; * &#40;MAXHISTORYPLY - ply&#41;;
&#125;

AlvaroBegue
Posts: 925
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Possible history table improvement

Post by AlvaroBegue » Fri May 31, 2013 8:06 pm

Harald wrote:

Code: Select all

if&#40;ply < MAXHISTORYPLY & value >= beta&#41;
&#123;
       historytable&#91;piece&#93;&#91;to&#93; += &#40;MAXHISTORYPLY - ply&#41;*&#40;MAXHISTORYPLY - ply&#41;;
&#125;
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 &#40;ply < MAXHISTORYPLY && value >= beta&#41;
&#123;
       historytable&#91;piece&#93;&#91;to&#93; += &#40;MAXHISTORYPLY - ply&#41; * &#40;MAXHISTORYPLY - ply&#41;;
&#125;
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.

User avatar
lucasart
Posts: 3168
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Possible history table improvement

Post by lucasart » Sat Jun 01, 2013 12:43 am

AlvaroBegue wrote:
Harald wrote:

Code: Select all

if&#40;ply < MAXHISTORYPLY & value >= beta&#41;
&#123;
       historytable&#91;piece&#93;&#91;to&#93; += &#40;MAXHISTORYPLY - ply&#41;*&#40;MAXHISTORYPLY - ply&#41;;
&#125;
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 &#40;ply < MAXHISTORYPLY && value >= beta&#41;
&#123;
       historytable&#91;piece&#93;&#91;to&#93; += &#40;MAXHISTORYPLY - ply&#41; * &#40;MAXHISTORYPLY - ply&#41;;
&#125;
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).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

syzygy
Posts: 4820
Joined: Tue Feb 28, 2012 10:56 pm

Re: Possible history table improvement

Post by syzygy » Sat Jun 01, 2013 7:39 am

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

User avatar
lucasart
Posts: 3168
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Possible history table improvement

Post by lucasart » Sat Jun 01, 2013 10:43 am

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&#40;...);
...
if &#40;x == 2&#41; ...
problem is that x can only be 0 or 1 due to bool type conversion of inf f().
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Laszlo Gaspar
Posts: 64
Joined: Thu Mar 09, 2006 10:07 am
Location: Budapest, Hungary

Re: Possible history table improvement

Post by Laszlo Gaspar » Sat Jun 01, 2013 6:58 pm

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.
Regards,
László

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

Re: Possible history table improvement

Post by hgm » Sat Jun 01, 2013 9:30 pm

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.

Harald
Posts: 279
Joined: Thu Mar 09, 2006 12:07 am

Re: Possible history table improvement

Post by Harald » Sat Jun 01, 2013 9:50 pm

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.

Post Reply