Page 2 of 3

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 12:51 am
by bob
Cardoso wrote:Could you please tell me about those methods?
It has been some time I don't read the latest crafty's source.
Are those implemented in the latest version of crafty?

best regards,
alvaro
Source will be available soon. But simply we look at each individual move to decide whether to reduce it or not. At today's depths, the history counters are essentially nothing more than a good source of random numbers...

I did some experimentation with Crafty/Glaurung/Fruit a while back, and discovered that varying the history threshold for fruit has no significant impact on its overall game results, _IF_ one plays enough games to eliminate the inherent randomness in computer chess games.

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 12:55 am
by bob
Uri Blass wrote:
bob wrote:
ed wrote:
Peter Fendrich wrote:This is what it ment in Terra and still in Alaric:
History Move Number: The move number in your ordered list of moves t this node. The moves after that are regarded as "late" in LMR (Late Move Reduction)

History Treshold: You want to reduce "Late moves" (as above) but first you check that moves history performance. This is probably meassured differently in different programs (for instance number of fail high and fail low) and it is saved in the history table. If the move is "late" and its history value is below this treshold it is time to reduce!

/Peter
Understood now. I don't use the LMR condition, I just don't reduce PVS moves, captures, promotions, checking moves, king out of check moves, mate threats and moves that are within a 1/4 pawn margin of alpha.

Ed
I've stopped using history stuff completely as well. There are other ways to decide to not reduce besides that...
I am not sure what do you mean that you stopped using history stuff completely.
History stuff -> history counters of any sort. Nobody can eliminate _all_ history as you define it, because then alpha/beta would not work. But the normal definition of "history" is a counter that is somehow incremented or adjusted on fail highs or fail lows... and it applies to specific moves typically using <from><to> as a 12 bit index.


Even without history counters you can use history stuff.

1)Do you have a rule never to reduce killer moves?
I think that if you have a rule never to reduce killer moves then this rule is based on history stuff because the question if a move is killer move is based on history of the search.
Yes, but that is a very non-standard definition of "history stuff" since Schaeffer defined this pretty accurately years ago, and the history counter approach has been beat to death many times here. This only concerns those kinds of counters. Otherwise, again, alpha and beta are clearly "history".


2)Do you have a rule never to reduce the first N moves for some N?
If you have a rule like that then again you use history stuff because
I assume that order of the first moves after good captures and killers is based on history tables and you practically do not reduce moves that caused cutoff more often by not reducing first N moves.

Uri

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 12:56 am
by bob
hgm wrote:I interpreted Bob's 'history stuff' as anything that depends on the history tables (e.g. reductions as well as move ordering).
that was my intent. And no, I don't use history tables anywhere any longer. Not for ordering, not for LMR decisions. Not for anything... they have all been removed completely.

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 7:05 am
by Uri Blass
bob wrote:
Cardoso wrote:Could you please tell me about those methods?
It has been some time I don't read the latest crafty's source.
Are those implemented in the latest version of crafty?

best regards,
alvaro
Source will be available soon. But simply we look at each individual move to decide whether to reduce it or not. At today's depths, the history counters are essentially nothing more than a good source of random numbers...

I did some experimentation with Crafty/Glaurung/Fruit a while back, and discovered that varying the history threshold for fruit has no significant impact on its overall game results, _IF_ one plays enough games to eliminate the inherent randomness in computer chess games.
I disagree that history counters are nothing more than a good source of random numbers.

Maybe experiment suggest that they are not productive for you but if it is the case it suggests that maybe you should count in a different way and you may decide to memset the history counters every time that the remaining depth is high enough so history counters will be based only on results of small depth search.

You say:
"varying the history threshold for fruit has no significant impact on its overall game results"

I do not understand what is the experiment that you did.
Note that based on my knowledge history threshold in fruit means conditions for late move reductions when history threshold of 0 mean no late move reduction.

I believe that late move reduction help fruit so changing the history threshold clearly change the playing strength of fruit.

Uri

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 8:15 am
by ed
bob wrote:Source will be available soon. But simply we look at each individual move to decide whether to reduce it or not. At today's depths, the history counters are essentially nothing more than a good source of random numbers....
That can be easily dealt with, just don't update/reduce after the xx ply. You get far less reductions then, but hey, the first 1-2-3 reductions are the ones that really matter.
bob wrote:I did some experimentation with Crafty/Glaurung/Fruit a while back, and discovered that varying the history threshold for fruit has no significant impact on its overall game results, _IF_ one plays enough games to eliminate the inherent randomness in computer chess games.
Without history reductions mine plays considerable weaker.

Ed

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 3:24 pm
by yoshiharu
bob wrote: Source will be available soon. But simply we look at each individual move to decide whether to reduce it or not. At today's depths, the history counters are essentially nothing more than a good source of random numbers...
The last sentence is comforting, in a sense...
Anyways, are you relying on chess knowledge to reduce? I remember a post of yours saying you didn't want to use domain specific knowledge besides the obvious evaluation function: did you change your mind?

And regarding history counters: has there been any documented attempt of "deducing" features of the positions by history counters? In example about the "positional" importance of some square?

Thanks in adv.

Cheers, Mauro

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 4:33 pm
by bob
Uri Blass wrote:
bob wrote:
Cardoso wrote:Could you please tell me about those methods?
It has been some time I don't read the latest crafty's source.
Are those implemented in the latest version of crafty?

best regards,
alvaro
Source will be available soon. But simply we look at each individual move to decide whether to reduce it or not. At today's depths, the history counters are essentially nothing more than a good source of random numbers...

I did some experimentation with Crafty/Glaurung/Fruit a while back, and discovered that varying the history threshold for fruit has no significant impact on its overall game results, _IF_ one plays enough games to eliminate the inherent randomness in computer chess games.
I disagree that history counters are nothing more than a good source of random numbers.

Maybe experiment suggest that they are not productive for you but if it is the case it suggests that maybe you should count in a different way and you may decide to memset the history counters every time that the remaining depth is high enough so history counters will be based only on results of small depth search.

You say:
"varying the history threshold for fruit has no significant impact on its overall game results"

I do not understand what is the experiment that you did.
Note that based on my knowledge history threshold in fruit means conditions for late move reductions when history threshold of 0 mean no late move reduction.

I believe that late move reduction help fruit so changing the history threshold clearly change the playing strength of fruit.

Uri
For example, I took fruit and varied the history threshold from 0 to 100% of max. 0 effectively turns it off and that was worse. But once I turned it on, there was no "pattern" that said 10 is better than 0, 20 is better than 10, 30 is better than 20, ..., 60 is worse than 50, 70 is worse than 60, etc. The results showed that for Fruit (and for Crafty) varying this threshold (and fruit and crafty did not quite compute it the same way either) had no quantifiable influence on playing strength. I played 10K games per value, to get rid of almost all the randomess of the results.

I then removed it and still produce the same results as when I had 'em in. And when I say "I removed it" I mean I simply removed the history counter restriction on what gets reduced...

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 4:45 pm
by frankp
I do not use history in LMR decisions. It is either swamped by all my other restriction or has no obvious effect, positive or negative - although this is not based on 10k of testing data ........wow.

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 5:08 pm
by Uri Blass
bob wrote:
Uri Blass wrote:
bob wrote:
Cardoso wrote:Could you please tell me about those methods?
It has been some time I don't read the latest crafty's source.
Are those implemented in the latest version of crafty?

best regards,
alvaro
Source will be available soon. But simply we look at each individual move to decide whether to reduce it or not. At today's depths, the history counters are essentially nothing more than a good source of random numbers...

I did some experimentation with Crafty/Glaurung/Fruit a while back, and discovered that varying the history threshold for fruit has no significant impact on its overall game results, _IF_ one plays enough games to eliminate the inherent randomness in computer chess games.
I disagree that history counters are nothing more than a good source of random numbers.

Maybe experiment suggest that they are not productive for you but if it is the case it suggests that maybe you should count in a different way and you may decide to memset the history counters every time that the remaining depth is high enough so history counters will be based only on results of small depth search.

You say:
"varying the history threshold for fruit has no significant impact on its overall game results"

I do not understand what is the experiment that you did.
Note that based on my knowledge history threshold in fruit means conditions for late move reductions when history threshold of 0 mean no late move reduction.

I believe that late move reduction help fruit so changing the history threshold clearly change the playing strength of fruit.

Uri
For example, I took fruit and varied the history threshold from 0 to 100% of max. 0 effectively turns it off and that was worse. But once I turned it on, there was no "pattern" that said 10 is better than 0, 20 is better than 10, 30 is better than 20, ..., 60 is worse than 50, 70 is worse than 60, etc. The results showed that for Fruit (and for Crafty) varying this threshold (and fruit and crafty did not quite compute it the same way either) had no quantifiable influence on playing strength. I played 10K games per value, to get rid of almost all the randomess of the results.

I then removed it and still produce the same results as when I had 'em in. And when I say "I removed it" I mean I simply removed the history counter restriction on what gets reduced...
It may be interesting to see the results that you say that there is no pattern.

It is possible that the optimal value is 55 and the difference betwen 40 and 50 and 60 and 70 is simply too small but even in that case I will say that there is a pattern if all values of 40-70 are clearly better than 10.

Note also that results may be dependent on the time control.

Uri

Re: Fruit and History Reductions

Posted: Sat Jul 21, 2007 6:59 pm
by bob
frankp wrote:I do not use history in LMR decisions. It is either swamped by all my other restriction or has no obvious effect, positive or negative - although this is not based on 10k of testing data ........wow.
Mine wasn't based on 10K games either. :) Each _match_ was 7500 games, and we played at least 20 matches... :)