Author: Harald Lüßen
Date: 12:43:35 03/02/06
Go up one level in this thread
On March 01, 2006 at 23:26:05, Robert Hyatt wrote:
>On March 01, 2006 at 23:12:54, Uri Blass wrote:
>
>>On March 01, 2006 at 22:52:40, Uri Blass wrote:
>>
>>>On March 01, 2006 at 22:22:09, Robert Hyatt wrote:
>>>
>>>>On March 01, 2006 at 21:41:45, Daniel Mehrmannn wrote:
>>>>
>>>>>On March 01, 2006 at 14:52:06, Robert Hyatt wrote:
>>>>>
>>>>>>Thought I would post a more detailed follow-up to what I have been playing with,
>>>>>>to prompt further discussion and maybe even additional ideas.
>>>>>>
>>>>>>1. I started off trying to use the raw history scores, but they really were not
>>>>>>useful for a simple reason, that they conginually grow throughout the search.
>>>>>>Prior to CCT I had noticed this and even experimented with "aging" the values by
>>>>>>dividing all by 2 at some interval. But regardless, the numbers get very large,
>>>>>>and chopping them back suddenly increases the reduction level, whereas longer
>>>>>>searches would decrease the level. I punted on this pretty quickly and left the
>>>>>>normal history mechanism in place solely for move ordering.
>>>>>>
>>>>>[...]
>>>>>
>>>>>Hello Bob,
>>>>>
>>>>>nice to see you're testing history reduction :)
>>>>>I can't agree in point one that's not good to work with history scores, because
>>>>>they are growing during the search and decrease the possibility of reduction.
>>>>>
>>>>>I found an easy way to use the history scores native for reduction without
>>>>>needing a new table or other stuff. I call it "PHR" (Peak History Reduction).
>>>>>
>>>>>The idea is to use allready kown tables and go the easest way as possible.
>>>>>Basicly we're searching the higest possible historyscore in our current moves.
>>>>>This is our "peak value" at this node. So we know this move produced much
>>>>>cutoff's in the past. So current moves should at least reached the half or more
>>>>>points of the score to be _not_ reduced othwhise we reducing the depth.
>>>>>
>>>>>What's the benefits of this idea ?
>>>>>- No extra table needed
>>>>>- If much moves close to the peak all are full searched
>>>>>- If no other move over 50% we reducing all
>>>>>- No static values creating a problem on long searches
>>>>>
>>>>>code example in Homer:
>>>>>
>>>>>if (sgdPtr->EnableHistPrune && currentExtend == 0) {
>>>>> if ((mPtr->flags & 4)) {
>>>>> if (HistoryBest == DROP_MOVE) {
>>>>> HistoryBest = score /2;
>>>>> goto PVS;
>>>>> } else if (reachedMoves > 3 && (score <= HistoryBest || score == 0)) {
>>>>> NextDepth--;
>>>>> history_ext++;
>>>>> HistoryPrune = TRUE;
>>>>> flags |= PruneMove;
>>>>> goto PVS;
>>>>> }
>>>>> }
>>>>>}
>>>>>
>>>>>Very simple, but works :) I'm using this now since june 2003 without any
>>>>>problems.
>>>>>
>>>>>Best
>>>>>Daniel
>>>>
>>>>
>>>>OK... I tried something similar. The problem I found was that as the history
>>>>values built up, pruning went away. At the speeds I saw this past weekend, the
>>>>2-3-4 minute searches slowed down significantly. I assume you are using some
>>>>sort of aging process to decay the history values so that they don't rise to
>>>>near 2^32-1 and sit there??? This weekend I was using actual history values,
>>>>and when they reached some max point, I was aging all by dividing by 2. But I
>>>>only did the aging between iterations to avoid suddenly opening the pruning
>>>>floodgates in mid-iteration, and the longer iterations did less and less
>>>>pruning...
>>>>
>>>>The current approach works the same whether a cutoff happened 10 times or 10
>>>>million...
>>>
>>>I divide all the history value by 2 every time that the remaining depth is more
>>>than 8 plies.
>>
>>To be more correct I do not do it exactly but this is the idea(I divide
>>something else that is not the history values that you mean).
>>
>>looking at my code I first divide when the remaining depth is bigger than 9
>>I also have 2 counters for every move(one counter of number of fail high and one
>>counter of number of cases when the move did not fail high)
>>
>>I use the ratio between these numbers in my decision if to prune and I divide
>>both of them by 2 only if the number of cases when it was tried and failed low
>>is bigger than 1000;
>>
>>Uri
>
>
>My worry is the usual worry seen with priority computations in operating systems
>that are based on accumulated CPU time. If you don't "age" often enough, the
>values climb to the top and you can't tell the difference between priorities.
>If you age too often, the values all tend toward zero, and once again you can't
>tell the difference between the priorities. It would seem that something very
>similar happens if one is not _extremely_ cautious...
>
>I am letting the values climb until one "touches" the upper range I want to see,
>then I divide all by 2 and start the process again, except this time they get
>back to the same "level" 2x faster since the biggest starts off at the half-way
>point rather than at zero...
I would like to get any comment on my method I posted a few days ago:
When I read my history values I always get values between 0 (not good)
and 256 (most often successfull). I do this with saved history values
between 0 and 65536 and an additional maximum value which is always
updated. Then I can return (history * 256 / (maximum + 1)). When maximum
gets too big, all values and the maximum are divided by a factor.
This is not very precise but you can easyly fix the flaws and
find good tuning values for too big and factor.
I do this because I want always be able to use the history
as input value for some formulas like reductions or margins.
Since my engine is not very good this might be a bad idea. ;-)
Harald
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.