Fruit and History Reductions

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Fruit and History Reductions

Post by bob » Sat Jul 21, 2007 7:01 pm

Uri Blass wrote:
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
I don't keep all data. There's simply too much. But the "pattern" was that reductions work, but using history information is not helpful. And simply disabling it completely but still doing everything else in the reduction algorithm normall produces results just as good and less random.

bob
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Fruit and History Reductions

Post by bob » Sun Jul 22, 2007 4:49 pm

ed wrote:
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
Note that fruit/crafty still did reductions, just didn't use the history counters as a limiting factor. All the other rules were still in force...

bob
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Fruit and History Reductions

Post by bob » Sun Jul 22, 2007 4:51 pm

yoshiharu wrote:
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
Chess programs always use some sort of domain-specific knowledge in the search. For example, check extensions, or passed pawn extensions. Back in the late 70's a student of mine took my old chess program and converted it to play checkers. That is where you really see how much chess-specific stuff has crept into the search code decision-making. :)

So yes, this is the kind of stuff used to limit reductions, it is all domain-specific in that area...

Post Reply