Author: Robert Hyatt
Date: 20:26:05 03/01/06
Go up one level in this thread
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...
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.