Author: Dieter Buerssner
Date: 10:44:14 06/21/05
Go up one level in this thread
On June 21, 2005 at 04:37:50, Vasik Rajlich wrote:
>On June 20, 2005 at 16:19:19, rasjid chan wrote:
>
>>On June 20, 2005 at 14:58:14, Dieter Buerssner wrote:
>>
>>>On June 19, 2005 at 12:38:09, Vasik Rajlich wrote:
>>>
>>>>On June 19, 2005 at 11:25:24, rasjid chan wrote:
>>>>
>>>>> I apologize I can never understand how to analyse the way search() intereacts
>>>>> with set board positions. But I understand now, also from dieter's reply,
>>>>> that fail-soft value need not be strictly correct UB / LB; ie some
>>>>> risk may be taken.
>>>>>
>>>>
>>>>I don't think Dieter is saying this. An UB should always be an UB - if you have
>>>>to make a mistake, you set it too high. This happens for example with lazy eval,
>>>>or using a margin for pruning in q-search.
>>>
>>>I fear, I don't fully understand Rasjid's statement neither Vasik's reply.
>>>I think, correctly implemented fail soft search gives always correct bounds.
>>>They are of course not the strictest bounds, one would like to have.
>>>
>>
>>Actually I too did not completely understand Vasic's reply; it seems
>>contradictory.
>>
>>I mentioned you because of your reply about skipping futile moves:-
>>
>> if (move-likely-futile...){
>> best = alpha;//added by me
>> continue;
>> }
>>
>>Your reply seemed to indicate(optimist_score..margin)some don't always set
>>best = alpha; My simple understanding of this is that when best is set to
>>anything less than alpha and if finally we fail-low and soft with this best,
>>then there is a "risk" as it is a guess of a fail-low and soft UB. So I presume
>>others do allow some margin of risk. Vasic probably too misunderstood.
>>
>
>Actually I see now that I interpreted the original statement correctly. :)
>
>You never want to set a fail soft score which is "too aggressive" and therefore
>has a chance to be incorrect. You are willing to have "not the strictest" bounds
>as Dieter says.
>
>Of course, you might in some really rare cases set an incorrect fail soft score,
>such as if you underestimate the margin. I guess the formal rule should be: you
>should never set a fail soft score which is riskier than the risk you already
>have with failing low/high in the first place. For example, if you use "margin"
>to prune in quiescence search, then you should remove "margin" from the softness
>of your bounds, etc ..
Yes. I think, my courrected code sample did it correctly. One might also note,
that "remove from softness" in the last sentence means "add to the score".
>>>Also, with fail soft you will search different trees. You can also visit the
>>>same node with different bounds at the same root depth. Perhaps with one bound,
>>>you get a null move fail high, while with the other (higher bound) will not be
>>>enough for the null move to fail high. It may turn out, that this null move fail
>>>high was actually "wrong" (search without null move would have shown, that the
>>>score of this node is worse than you have expected). But again, this situation
>>>can also arise in fail hard search (for example when you use a different HT
>>>size). I'd guess, that the chance of something like this happening is higher in
>>>fail soft - but it should be low enough to not matter (other than by some random
>>>noise).
>>>
>
>This is a great point, which I became aware of some time ago. The problem
>becomes serious when you start using really small aspiration windows. Another
>way to think of it is that you are effective putting null moves into your
>principal variations. (It takes a bit of thinking to understand this, but that's
>the effect.)
I obviously did not think enough about it yet. Can you elaborate on this? I see
no principal difference yet, between fail hard/soft or large/small aspiration
window. To me it looks simple (yet). Either you trust null move fail highs, or
you don't. We don't do the null move search at beta+margin, we do it at beta,
because we are convinced, that when we get a fail high there, it is a good
pruning decision. We are of course aware, that we get wrong pruning by this now
and then, and we live with it, because we are convinced, that advantages
outweigh disadvantages.
>>>About the REP3 - I had no time yet, to read this carefully (this became a really
>>>huge thread ...). You might want to google for "Dennis Breuker thesis". He shows
>>>a concrete example in detail, and explains why things go wrong there because of
>>>hash and repetition of position. You could try to probe your suggestions against
>>>that scenario.
>>
>>The specific case of rep3 which Vasic ignored is simple.
>>He hashed FL and soft when best == 0, but this 0 comes from rep3 FH and soft
>>from the ply above. So Vasic's 0 as the FL and soft score(is a correct UB) is
>>correct for the particular search.
>>
>>Hashing the search would give HT path-dependncy corruption. I suggested passing
>>down a _rep3_flag as this path-dependency may just propagate downwards. All
>>hashing may be corrupted as we never know when such dependency may be
>>inherited from above and passed down unless we keep a _rep3_flag. I think
>>it may happen also for FH/exact.
This will solve wrong zero repetition draw scores by HTs. The prize will be very
high (my guess). Also my guess: much more often than not, those draw scores will
be correct in the end, even when for the specific path and search depth they may
be not.
This is not the only problem we have with the interaction of HTs and repetion. I
think Breuker calls this "graph history interaction" (or game history
interaction). When you have no repetition (yet), one side might have tried hard
from the current position down, to avoid repetition. With another path reaching
this same position, it might have been easier to avoid repetition.
I just did a small experiment. For draw scores in the HT, I return "worthless"
(meaning the move can be used for move ordering, but not for cutoff). I changed
stalemate score to 1. With these changes in the following position, I believe it
is basically the same as your REP3 idea (I think all draw scores come from
stalemate or repetition).
In the following position white (Yace) just captured on g7 an threw away a win.
With my original code, big fail lows very fast and draw score in 30 seconds (I
do lots of extensions here - it is very deep, to see repetition). With my
experimental setup, still -7 score after 5 minutes, and I believe, no draw score
in days.
[D] 7k/6R1/6R1/1r5P/6K1/8/8/8 b - - 0 55
BTW. Current version with current hardware and not too fast time control could
avoid xg7.
Perhaps even a position to try the no progress ideas (and more things, like
stalemate detection in qsearch).
Regards,
Dieter
This page took 0.01 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.