Author: Daniel Shawul
Date: 00:30:22 12/25/04
Go up one level in this thread
On December 25, 2004 at 03:09:40, Uri Blass wrote:
>On December 25, 2004 at 02:42:28, Daniel Shawul wrote:
>
>>On December 25, 2004 at 02:15:55, Daniel Shawul wrote:
>>
>>>On December 24, 2004 at 18:34:14, Uri Blass wrote:
>>>
>>>>On December 24, 2004 at 18:09:13, Uri Blass wrote:
>>>>
>>>>>On December 24, 2004 at 15:10:45, Joachim Rang wrote:
>>>>>
>>>>>>Hi Uri,
>>>>>>
>>>>>>On December 24, 2004 at 09:31:57, Uri Blass wrote:
>>>>>>
>>>>>>>On December 24, 2004 at 07:04:59, Joachim Rang wrote:
>>>>>>>
>>>>>>>>Hi,
>>>>>>>>
>>>>>>>>in the next hour Leo will add the new Fruit 2.0 on his website. The new version
>>>>>>>>comes with source as usual. Binaries for Linux come (perhaps) later.
>>>>>>>>
>>>>>>>>The biggest news: Fruit is no longer a blitzer! Fabien made a risky decision to
>>>>>>>>activate history pruning with rather aggressive values, so you will notice Fruit
>>>>>>>>prunes away a lot and reaches good depth rather soon. This makes him most
>>>>>>>>probably weaker in lightning or blitz, but will (hopefully) pay off in longer
>>>>>>>>time controls. If you aren't satisfied with the blitz-performance of Fruit try
>>>>>>>>deactivating history pruning.
>>>>>>>
>>>>>>>I think that history based pruning when used in the right conditions is not
>>>>>>>counter productive at blitz.
>>>>>>
>>>>>>That might be right, but the way Fabien implemented it, it_does_ hurt at least
>>>>>>with 2+1 on my AthlonXP@1540MHz. More on how Fabien implemented it see below.
>>>>>>
>>>>>>>
>>>>>>>You can try movei at blitz with history based pruning and without it.
>>>>>>>
>>>>>>>My impression was that the main advantage of it is in blitz based on the last
>>>>>>>time that I tested movei with and without history based pruning in test suites.
>>>>>>>
>>>>>>>You can disable history based pruning in movei by changing
>>>>>>>limit_history_depth from 101 to -1
>>>>>>>
>>>>>>>You can reduce history based pruning in movei by increasing selectivity from 7
>>>>>>>to bigger number but there is some pruning that will always remain so pruning
>>>>>>>does not converge to 0 by increasing selectivity.
>>>>>>>
>>>>>>>The problem is that I have condition:
>>>>>>>badvalue>(goodvalue<<selectivity)
>>>>>>>
>>>>>>>selectivity=7 means that you prune the move if the number of fail low is more
>>>>>>>than 128 times the number of fail high(there are more conditions and it is only
>>>>>>>one of the conditions).
>>>>>>>
>>>>>>>The problem is that this condition can happen also when goodvalue=0 and badvalue
>>>>>>>is small(there are more conditions so pruning when badvalue<=4 and goodvalue=0
>>>>>>>is not possible but pruning when badvalue=5 and goodvalue=0 may be possible and
>>>>>>>how much you increase selectivity is not important.
>>>>>>>
>>>>>>>Note also that big selectivity may cause the value of goodvalue<<selectivity to
>>>>>>>be wrong.
>>>>>>>
>>>>>>>I divide goodvalue and badvalue by 2 everytime when the remaining depth is at
>>>>>>>least 10 and badvalue>1000
>>>>>>>
>>>>>>>practically if I analyze the opening position for some minutes I find that
>>>>>>>always goodvalue<(1<<15) and I guess that practically in games I have always
>>>>>>>goodvalue<(1<<25) so it is no problem with the default parameters.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>>The threshold of history pruning is set to 60%.
>>>>>>>
>>>>>>>Can you explain what it means?
>>>>>>
>>>>>>I can only forward what Fabien answered me on this question:
>>>>>>
>>>>>>"To simplify, moves are given percentage scores in a separate history table.
>>>>>>They start at 100% and go up/down depending on how often they fail high
>>>>>>during the search.
>>>>>>
>>>>>>At a given node, moves that have a score below History Threshold are
>>>>>>reduced.
>>>>>>Move scores are always between 0 and 100. I think they are close to 100
>>>>>>most of the time due to the way I update scores (this might be a mistake but
>>>>>>is the price to pay to have a significantly-different implementation from
>>>>>>that of Tord and probably other engines)."
>>>>>>
>>>>>>My feeling is, that 60% is already a risky value, since it clearly misses some
>>>>>>key moves in testsuites (but find others do to higher depth).
>>>>>>
>>>>>>regards Joachim
>>>>>
>>>>>I do not understand the code
>>>>>
>>>>>line 66 of search_full.cpp
>>>>>static /* const */ int HistoryValue = 12288; // 75%
>>>>>
>>>>>line 175 of search_full.cpp
>>>>>
>>>>>HistoryValue = (option_get_int("History Threshold") * 16384 + 50) / 100;
>>>>>
>>>>>line 40 of options.cpp
>>>>>{ "History Threshold", true, "60", "spin", "min 0 max 100", NULL }
>>>>>
>>>>>What is History value?
>>>>>
>>>>>Is it (60*16384+50)/100=9830 or is it 12288?
>>>>>
>>>>>I guess it is 9830 so why line 66 of search_full.cpp?
>>>>>
>>>>>If I understand correctly the pruning is in case that
>>>>>hist_hit/hist_total<60% when hist_hit get higher in fail high when hist_total
>>>>>always get higher(there is exception when both get lower when they are too high
>>>>>but they get lower by the same margin so it is not important).
>>>>>
>>>>>It seems very risky because it means that move that most of the time fail
>>>>>high(fail high in 55% of the cases that it is tried and some move fail high) can
>>>>>get pruned.
>>>>>
>>>>>Maybe I do not understand the code but there are no comments in the code that
>>>>>explain it.
>>>>>
>>>>>Uri
>>>>
>>>>In a second thought maybe more conditions like the condition that the first 3
>>>>moves failed low (if I understand correctly) together with good order of moves
>>>>make sure that the probability for fail low is almost 100%.
>>>>
>>>>Movei use clearly more restricted conditions but it also counts more fail lows
>>>>than fruit because I see that fruit counts fail lows only when there is a fail
>>>>high and if I understand correctly it means that stupid moves like Ke2 in the
>>>>opening may not get pruned in a quiet position because of the fact that there is
>>>>never fail high when they are tried in a quiet position.
>>>>
>>>>Uri
>>>
>>>Do you do redutions more than once from ply 0 to current ply?
>>>Not doing this gets larger depths. When i added this condition (note i don't
>>>use history as a condition), the gain disappeared leaving me with risky
>>>reductions. Also null move should not be forgoten,since it works best without
>>>this reductions. They also add some more search instablility to the search.
>>>
>>>daniel
>>
>>Hashtables are also another issue
>
>I let more than one reduction but I do it rarely enough so I do not get a lot of
>depth.
i suppose you ask lot of questions before reducing a move.
>In my case hash tables are not used for pruning but only for better order of
>moves so they are no problem.
Not for me. But have you tried using them for pruining? The biggest gain of
hashtables for me is move ordering,and probably saving move generation. I don't
know exactly how much pruining using them benefits me.
>
>History based pruning is one of the reason for my choice not to use hash for
>pruning.
>
>I feel that using hash for pruning limit my freedom to try other ideas that may
>be productive without using hash for pruning.
yes hashtables do harm. but not trying them for pruining is not a good idea.
Same applies for reductions and nullmove.they work better exclusively
>I also believe that my history based pruning may be improved and I did not try
>lately to improve it.
>
IIRC you compare fail lows and fail highs , tord comapres fail highs with
nodes searched. i don't know what fabien does.
For me it sounds very risky to rely on only history for pruining. I think
it needs a complicated evaluation funcion which is able to evaluate
tactics(hanging pieces,pins etc),which is called befor and after the move is
made. And then using the history data sounds
better for me.
daniel
>Movei00_7_99 is the first public version that use history based pruning.
>
>I did some changes in history based pruning since that version but I did not
>test changes in it in the last few months and I plan testing changes in it
>again.
>
>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.