Author: Uri Blass
Date: 01:11:49 12/25/04
Go up one level in this thread
On December 25, 2004 at 03:44:02, Daniel Shawul wrote:
>On December 25, 2004 at 03:29:06, Uri Blass wrote:
>
>>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.
>>>In my case hash tables are not used for pruning but only for better order of
>>>moves so they are no problem.
>>>
>>>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.
>>>I also believe that my history based pruning may be improved and I did not try
>>>lately to improve it.
>>>
>>>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
>>
>>Another note is that I do research in case of unexpected fail high.
>>
> yes if the null window search fails , research with the full window and
>the full depth should be made.
practically I do today research with the same window and only if the research
with the same window fail high I increase the window.
Maybe it is better to do research immediatly with a bigger window and I need to
try and compare results.
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.