relative history heuristic

[smcracraft]

I used this old paper tonight:

http://www.springerlink.com/content/y15772m73q2l1080/

and the result was about 9% fewer searched nodes,
with a smaller squared solution time (14%)
and a slightly improved solution count in a tested
problem set.

I have no idea if it is implemented well enough here, but the
authors claimed a 10%-15% node reduction... perhaps there
are more ordering improvements people could talk about
besides RHH and/or about their own experience with RHH.

Stuart

[mcostalba]

I used this old paper tonight:

http://www.springerlink.com/content/y15772m73q2l1080/

Stuart

Why to post a link to a paper people cannot download ?

Thanks
Marco

[Alessandro Damiani]

www.personeel.unimaas.nl/m-winands/documents/relhis.pdf

[Eelco de Groot]

I used this old paper tonight:

http://www.springerlink.com/content/y15772m73q2l1080/

Stuart

Why to post a link to a paper people cannot download ?

Thanks
Marco

I think Stuart maybe is enrolled or has a job in a University where the library has access to these papers by subscription? Page 1 can be downloaded. But there is an alternative link to a paper, directly from Mark Winands at the University of Maastricht, in the south of the Netherlands. I'm not sure if this is a draft or essentially the same, or whether this paper was published in the ICCA journal or other publication.

http://www.personeel.unimaas.nl/m-winan ... relhis.pdf

Regards, Eelco

[mcostalba]

I used this old paper tonight:

http://www.springerlink.com/content/y15772m73q2l1080/

Stuart

Why to post a link to a paper people cannot download ?

Thanks
Marco

I think Stuart maybe is enrolled or has a job in a University where the library has access to these papers by subscription? Page 1 can be downloaded. But there is an alternative link to a paper, directly from Mark Winands at the University of Maastricht, in the south of the Netherlands. I'm not sure if this is a draft or essentially the same, or whether this paper was published in the ICCA journal or other publication.

http://www.personeel.unimaas.nl/m-winan ... relhis.pdf

Regards, Eelco

Hi Eelco,

thanks to you and Alessandro.

[smcracraft]

Marco - it wasn't necessary for me to have the full paper to
implement RHH and gain a 9% reduction in tree-nodes
and other improvements. The description in the abstract is
enough.

For details, I bump history heuristic by += depth*depth at
its normal places as usual.

butterfly heuristic is incremented by += depth*depth except when
there is a cut.

The score for sorting that used to have the history heuristic
component alone now has the hh/butterfly quotient described in the
abstract.

Both the butterfly heuristic [2][7][64] (color, piece, square) and
history heuristic table (same dimensions) are scaled when the
current bh[][][] or hh[][][] is greater then 32000 so that every
entry is halved.

Alessandro - thanks for finding and posting. You win the gold star.

Eelco - not a university, but there's someone I know who does have
access to the U.C. library and is generous with it but I had not thought
to do so. You win the silver star.

Still, I did not have the paper to gain from the abstract.
Now, due to Alessandro, I get to read the paper and see
the flaws in my implementation.

The abstract indicated, I believe, that the authors had not tried
it in Chess, only in LOA and Go. Since the paper is 3 years old,
I am sure it had been implemented earlier than this week in chess
and am curious what higher levels people can get than 9% hopefully.

Stuart

[Alessandro Damiani]

Rumour has it there is someone around with a cluster. He could provide results for very deep searches.

[Gerd Isenberg]

The abstract indicated, I believe, that the authors had not tried
it in Chess, only in LOA and Go. Since the paper is 3 years old,
I am sure it had been implemented earlier than this week in chess
and am curious what higher levels people can get than 9% hopefully.

Stuart

I think a lot used similar before the paper appeared or later without recognizing the paper. For sorting moves as well for LMR. Interestingly even Bob threw history counters out of Crafty

Re: About compiler optimizations Robert Hyatt December 23, 2002, Reply to Vincent Diepeveen:

>In not a single top program history tables work. Only exception is
>crafty. Matter of time before it's taken out. I just posted it 10
>times here so that might not be enough. i didn't check though whether
>it's already taken out of crafty

It isn't out and it won't be out. It works for me. It worked for Bruce the
last time we talked...

late move reductions Robert Hyatt March 01, 2006

LMR: history or not? Robert Hyatt Dec 13, 2007

I don't have any history counters in Crafty. I found that at the depths I see today, the history counters were simply saturated with nonsense...

[Uri Blass]

Marco - it wasn't necessary for me to have the full paper to
implement RHH and gain a 9% reduction in tree-nodes
and other improvements. The description in the abstract is
enough.

For details, I bump history heuristic by += depth*depth at
its normal places as usual.

butterfly heuristic is incremented by += depth*depth except when
there is a cut.

The score for sorting that used to have the history heuristic
component alone now has the hh/butterfly quotient described in the
abstract.

Both the butterfly heuristic [2][7][64] (color, piece, square) and
history heuristic table (same dimensions) are scaled when the
current bh[][][] or hh[][][] is greater then 32000 so that every
entry is halved.

Alessandro - thanks for finding and posting. You win the gold star.

Eelco - not a university, but there's someone I know who does have
access to the U.C. library and is generous with it but I had not thought
to do so. You win the silver star.

Still, I did not have the paper to gain from the abstract.
Now, due to Alessandro, I get to read the paper and see
the flaws in my implementation.

The abstract indicated, I believe, that the authors had not tried
it in Chess, only in LOA and Go. Since the paper is 3 years old,
I am sure it had been implemented earlier than this week in chess
and am curious what higher levels people can get than 9% hopefully.

Stuart

The idea is clearly more than 3 years old and the article is nothing new.

Many engines use history tables for ordering moves and I believe that many people use depth*depth because I remember it from old code that is more than 3 years old.

Uri

[Uri Blass]

The abstract indicated, I believe, that the authors had not tried
it in Chess, only in LOA and Go. Since the paper is 3 years old,
I am sure it had been implemented earlier than this week in chess
and am curious what higher levels people can get than 9% hopefully.

Stuart

I think a lot used similar before the paper appeared or later without recognizing the paper. For sorting moves as well for LMR. Interestingly even Bob threw history counters out of Crafty

Re: About compiler optimizations Robert Hyatt December 23, 2002, Reply to Vincent Diepeveen:

>In not a single top program history tables work. Only exception is
>crafty. Matter of time before it's taken out. I just posted it 10
>times here so that might not be enough. i didn't check though whether
>it's already taken out of crafty

It isn't out and it won't be out. It works for me. It worked for Bruce the
last time we talked...

late move reductions Robert Hyatt March 01, 2006

LMR: history or not? Robert Hyatt Dec 13, 2007

I don't have any history counters in Crafty. I found that at the depths I see today, the history counters were simply saturated with nonsense...

I do not know what do the majority and it is not clear to me if Bob is the majority.

It is only clear that Vincent claims nonsense when he claims
"In not a single top program history tables work"
because he does not know what works or does not work for other people.


Note that Strelka that is clearly stronger than everything of 2002 is using depth*depth in history tables for order of moves and it is not clear for me that history does not work for strelka.

If the counters are too big today because of overflow(when depth*depth may be above 2^32 then it is possible to use 64 bit numbers).

Uri