Author: Uri Blass
Date: 20:12:54 03/01/06
Go up one level in this thread
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
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.